Path: csiph.com!xmission!news.snarked.org!news.linkpendium.com!news.linkpendium.com!panix!usenet.stanford.edu!not-for-mail
From: worley@alum.mit.edu (Dale R. Worley)
Newsgroups: gnu.bash.bug
Subject: Removing the shift/reduce conflict in the parser
Date: Sun, 26 Apr 2020 20:14:33 -0400
Lines: 68
Approved: bug-bash@gnu.org
Message-ID: <mailman.1349.1587946484.3066.bug-bash@gnu.org>
References: <871ro9zswm.fsf@hobgoblin.ariadne.com>
NNTP-Posting-Host: lists.gnu.org
To: bug-bash@gnu.org
Envelope-to: bug-bash@gnu.org
Received-SPF: softfail client-ip=2001:558:fe21:29:69:252:207:39; envelope-from=worley@alum.mit.edu; helo=resqmta-ch2-07v.sys.comcast.net
Precedence: list
Xref: csiph.com gnu.bash.bug:16245

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]