Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > gnu.bash.bug > #16245

Removing the shift/reduce conflict in the parser

Show all headers | View raw

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]

Back to gnu.bash.bug | Previous | Next | Find similar

Thread

Removing the shift/reduce conflict in the parser worley@alum.mit.edu (Dale R. Worley) - 2020-04-26 20:14 -0400

csiph-web