bug-bash
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Removing the shift/reduce conflict in the parser


From: Dale R. Worley
Subject: Removing the shift/reduce conflict in the parser
Date: Sun, 26 Apr 2020 20:14:33 -0400

I've been annoyed by the fact that parse.y has a shift/reduce conflict.
It stems from the grammar for a function declaration:

function_def:   WORD '(' ')' newline_list function_body
        |       FUNCTION WORD '(' ')' newline_list function_body
        |       FUNCTION WORD newline_list function_body
        ;

You can see the problem by running "bison --report=state -y -d
./parse.y" and looking at y.output.  The difficulty being that when the
parser is standing here:

    FUNCTION WORD   '('
                  ^

it can't tell whether it is before the () of the second alternative, or
it is before a function_body which is a "subshell" (a list of commands
in (...)), a version of the third alternative.  In the latter case, the
parser has to generate an empty newline_list before it can consume the
'('.

It turns out that the solution is simple:  Separate the third
alternative into two, one of which has no newline_list (the case of the
original 3rd alternative where newline_list is empty), and one in which
the newline_list is not empty:

function_def:   WORD '(' ')' newline_list function_body
        |       FUNCTION WORD '(' ')' newline_list function_body
        |       FUNCTION WORD function_body
        |       FUNCTION WORD '\n' newline_list function_body
        ;

In the state that caused the conflict before, the parser no longer has
to decide whether to generate a newline_list, it can shift the '(' and
look at the following token before deciding what the situation is
(whether it is now inside a function_body or still working its way
through the function header).

I've appended the patch to fix this.  In the patch, I also remove a
couple of empty lines that don't conform to the overall conventions of
the file.


Dale
----------------------------------------------------------------------
diff --git a/parse.y b/parse.y
index 3ff87bc..75b6957 100644
--- a/parse.y
+++ b/parse.y
@@ -926,12 +926,12 @@ case_command:     CASE WORD newline_list IN newline_list 
ESAC
 
 function_def:  WORD '(' ')' newline_list function_body
                        { $$ = make_function_def ($1, $5, function_dstart, 
function_bstart); }
-
        |       FUNCTION WORD '(' ')' newline_list function_body
                        { $$ = make_function_def ($2, $6, function_dstart, 
function_bstart); }
-
-       |       FUNCTION WORD newline_list function_body
-                       { $$ = make_function_def ($2, $4, function_dstart, 
function_bstart); }
+       |       FUNCTION WORD function_body
+                       { $$ = make_function_def ($2, $3, function_dstart, 
function_bstart); }
+       |       FUNCTION WORD '\n' newline_list function_body
+                       { $$ = make_function_def ($2, $5, function_dstart, 
function_bstart); }
        ;
 
 function_body: shell_command
[END]



reply via email to

[Prev in Thread] Current Thread [Next in Thread]