|
|
 | | From: | Martyn Weiss | | Subject: | Yacc shift/reduce conflicts | | Date: | 19 Dec 2004 23:53:14 -0500 |
|
|
 | Hi.
I'm updating a language grammar I wrote a while ago using MKS Yacc,
which consists of one or more statements separated by semicolons, i.e.
S1;S2;...SN
..
One of the things I want to do is to allow for superfluous embedded
and trailing semicolons, as in S1;;S2;
I had a bit if trouble expressing this in rules without getting
shift/reduce conflicts. I found that if I simplify the grammar down
to the following:
program:
statements
;
statements:
statement
| statements semicolon
| statements semicolon statement
;
statement:
someterminal
;
yacc reports no conflicts, but it looks a bit clumsy to me. However,
if I replace "someterminal" by "expression", which has a number of
alternative definitions (simpleexpression, term, factor, etc) I
immediately get a whole raft of shift/reduce conflicts, which leads me
to think the simplified version above isn't the best way to express
the "superfluous semicolons" point mentioned above.
Can anyone suggest a better formulation of "statements" or explain how
I go about getting rid of the s/r conflicts in the fuller version.
Cheers & TIA, Martyn (you can probably guess that this isn't my usual
subject, but it isn't homework, either)
|
|
| | From: | Dawid Pawlata | | Subject: | Re: Yacc shift/reduce conflicts | | Date: | 22 Dec 2004 01:05:42 -0500 |
|
|
| Martyn Weiss wrote:
> I'm updating a language grammar I wrote a while ago using MKS Yacc,
> which consists of one or more statements separated by semicolons, i.e.
> S1;S2;...SN
>
> One of the things I want to do is to allow for superfluous embedded
> and trailing semicolons, as in S1;;S2;
>
> I had a bit if trouble expressing this in rules without getting
> shift/reduce conflicts. I found that if I simplify the grammar down
> to the following:
>
> program:
> statements
> ;
> statements:
> statement
> | statements semicolon
> | statements semicolon statement
> ;
> statement:
> someterminal
> ;
Hi!
what would you say about:
program:
statements
;
statements:
statement
| statements statement
;
statement:
| semicolon
someterminal_or_nonterminal semicolon
;
best regards
Dawid Pawlata
|
|
| | From: | Hugues_Cassé | | Subject: | Re: Yacc shift/reduce conflicts | | Date: | 22 Dec 2004 01:05:24 -0500 |
|
|
| I think this grammar is at less LALR(1) if you have only one terminal
in someterminal. But it should become LALR(k) if you have at most k
terminals in someterminal.
I think that rules (1) and (3) may create ambiguity according their
derivation. The following form would be better, I guess:
statements:
statement
| statements semicolon statement
;
statement:
/* empty */
| someterminal
;
Martyn Weiss wrote:
> Hi.
>
> I'm updating a language grammar I wrote a while ago using MKS Yacc,
> which consists of one or more statements separated by semicolons, i.e.
> S1;S2;...SN
> .
>
> One of the things I want to do is to allow for superfluous embedded
> and trailing semicolons, as in S1;;S2;
>
> I had a bit if trouble expressing this in rules without getting
> shift/reduce conflicts. I found that if I simplify the grammar down
> to the following:
>
> program:
> statements
> ;
> statements:
> statement
> | statements semicolon
> | statements semicolon statement
> ;
> statement:
> someterminal
> ;
>
> yacc reports no conflicts, but it looks a bit clumsy to me. However,
> if I replace "someterminal" by "expression", which has a number of
> alternative definitions (simpleexpression, term, factor, etc) I
> immediately get a whole raft of shift/reduce conflicts, which leads me
> to think the simplified version above isn't the best way to express
> the "superfluous semicolons" point mentioned above.
>
> Can anyone suggest a better formulation of "statements" or explain how
> I go about getting rid of the s/r conflicts in the fuller version.
|
|
| | From: | Scott Nicol | | Subject: | Re: Yacc shift/reduce conflicts | | Date: | 22 Dec 2004 01:05:07 -0500 |
|
|
| Martyn Weiss wrote:
> program:
> statements
> ;
> statements:
> statement
> | statements semicolon
> | statements semicolon statement
> ;
> statement:
> someterminal
> ;
>
> yacc reports no conflicts, but it looks a bit clumsy to me. However,
> if I replace "someterminal" by "expression", which has a number of
> alternative definitions (simpleexpression, term, factor, etc) I
> immediately get a whole raft of shift/reduce conflicts, which leads me
> to think the simplified version above isn't the best way to express
> the "superfluous semicolons" point mentioned above.
>
> Can anyone suggest a better formulation of "statements" or explain how
> I go about getting rid of the s/r conflicts in the fuller version.
Yes, it's clumsy. It would be better to allow a statement to be empty,
like this:
program:
statements
;
statements:
statement
| statements semicolon statement
;
statement:
/* nix */
| expression
;
expression:
simpleExpression
| term
| factor
| ...
;
If this change causes conflicts, there are two possibilities:
1. your grammer already accepted empty statements, through a rule
subordinate to statement, In other words, you didn't have to make any
changes. For example:
term:
/* nix */
| TERMINAL
;
2. Some other rule that uses statement also accepts an empty result in
place of statement. A modification of that rule would probably fix
things. For example, given that statement has been modified to accept
an empty result, the last alternative in the following example can be
eliminated:
if:
IF expression statement
| IF expression statement else statement
| IF expression else statement
;
y.output (generated when using the -v option) will tell you what is
going on.
--
Scott Nicol
snicol@apk.net
|
|
|
