Any shift/reduce experts out there?

[Jim Freeze]

Hi:

I am developing a grammar used in Racc.
Today, I added a single statement and it
has generated a shift reduce conflict.

Are there any yacc experts that can provide
some insight on how to remove this problem,
whether it be through re-writing the rule or
adding precedence or nonassoc definitions.

start : METH_DEFS process '{' '}' NEWLINE
| METH_DEFS process '{' NEWLINE
PARAMS
CONSTANTS
CONSTANTS_TABLE
'}'
;

METH_DEFS : OPT_NEWLINE
| METH_DEF
| METH_DEFS METH_DEF
;


The grammar has no conflicts with METH_DEFS removed:

start : process '{' '}' NEWLINE
| process '{' NEWLINE
PARAMS
CONSTANTS
CONSTANTS_TABLE
'}'
;

 

[Ryan Pavlik]

On Tue, 21 Oct 2003 03:47:03 +0900

METH_DEFS : OPT_NEWLINE
| METH_DEF
| METH_DEFS METH_DEF
;

<snip>

I could be wrong---it's been awhile since I really did this---but I
think it's the last line that's the problem here. It might work if
you do "METH_DEF METH_DEFS", but I could be wrong there, too.

 

[Jim Freeze]

On Tue, 21 Oct 2003 03:47:03 +0900


<snip>

I could be wrong---it's been awhile since I really did this---but I
think it's the last line that's the problem here. It might work if
you do "METH_DEF METH_DEFS", but I could be wrong there, too.

Nope, that doesn't help. The production:

XS : /*empty*/ | X | XS X ;

is fairly common.

 

[Jim Freeze]

In case anyone else travels this way, I will answer my own question:

I split the offending rule:

start : METH_DEFS process '{' '}' NEWLINE
| METH_DEFS process '{' NEWLINE
PARAMS
CONSTANTS
CONSTANTS_TABLE
'}'
;

METH_DEFS : OPT_NEWLINE
| METH_DEF
| METH_DEFS METH_DEF

;

to

start : PROCESS
| METH_DEFS PROCESS
;


PROCESS : process '{' '}' NEWLINE
| process '{' NEWLINE
PARAMS
CONSTANTS
CONSTANTS_TABLE
'}'
;

METH_DEFS : /*empty*/
| METH_DEF
| METH_DEFS METH_DEF
;

Now all is well.

 

[daz]

I split the offending rule:


start : PROCESS
| METH_DEFS PROCESS
;


PROCESS : process '{' '}' NEWLINE
| process '{' NEWLINE
PARAMS
CONSTANTS
CONSTANTS_TABLE
'}'
;

METH_DEFS : /*empty*/
| METH_DEF
| METH_DEFS METH_DEF
;

Now all is well.

[IANAE]

You also dumped OPT_NEWLINE which might have been the cause.


I guess you wanted OPT_NEWLINE to be part of the rule
rather than it being one complete description of METH_DEFS
(as you had it before).


OPT_NEWLINE : /* empty */
| NEWLINE
;

METH_DEF : OPT_NEWLINE DEF blah END_DEF /* whatever */
;

METH_DEFS : METH_DEF
| METH_DEFS METH_DEF
;


daz

 

[daz]

[...] btw, isn't X XS preferred?

No, Jim's right here.

This (from Ruby - code removed) is left-recursive
and therefore less demanding on the stack.

args : arg_value
| args ',' arg_value
;

 

[Jim Freeze]

well, you're production doesn't match this does it? try putting empty

It does. What I found out is that the XS rule is ok, but it did not
like the /*empty*/ being defined only in XS.
For example, it did not like:

start : A B ;
A : /*empty*/ | a | A a ;
B : whatever ;

Bu, the following is ok:

start : B | A B;
A : /*empty*/ | a | A a ;
B : whatever ;

or new line into XS instead. btw, isn't X XS preferred?

I don't know. In all the examples I have read, it is XS : X | XS X;

 

[Nikolai Weibull]

It does. What I found out is that the XS rule is ok, but it did not
like the /*empty*/ being defined only in XS. yeah, ok.
I don't know. In all the examples I have read, it is XS : X | XS X;

ok, long time since i looked at stuff like this. X XS just feals more
natural to me. but the other way may be faster or something.
nikolai

 

[Jim Weirich]

I don't know. In all the examples I have read, it is XS : X | XS X;

I'm reaching deep into the my personal memory banks from the days I
actually took a compiler theory course (mumble, mumble) years ago. So
be aware the information may be a bit old.

The parse tree generated from the two expressions will have different
associativity.

(1) XS : X | XS X; => ((X X) X)
(2) XS : X | X XS; => (X (X X))

So if associativity matters, choose appropriately.

Also, I seem to recall that some parser generators have problems with
infinite recursion when the expansion is first (as in (1)), but I'm not
sure I see the problem here. Perhaps that problem only happens with
grammers like (3).

(3) XS : <empty> | XS X;

As I said, its been a long time since I looked at this stuff.

 

[YANAGAWA Kazuhisa]

In Message-Id: <1066740248.9552.19.camel@traken>

Also, I seem to recall that some parser generators have problems with
infinite recursion when the expansion is first (as in (1)), but I'm not
sure I see the problem here.

Yes, in theory LL(1) parser doesn't treat left-recursive rules, so you
can't give such rule for LL(1) parser generators such as cocorb.

On the contrary, since LALR(1) parser tend to be small for
left-recursive rules, samples for LALR(1) parser generators such as
yacc or racc are often written in left-recursive manner.

As I said, its been a long time since I looked at this stuff.

Me also, thus the description above may be wrong or contain false info.