Any shift/reduce experts out there?

ruby-talk
1

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
’}’
;

···

–
Jim Freeze

2
> METH_DEFS : OPT_NEWLINE > > METH_DEF > > METH_DEFS METH_DEF > ;

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.

···

On Tue, 21 Oct 2003 03:47:03 +0900 Jim Freeze jim@freeze.org wrote:

–
Ryan Pavlik rpav@mephle.com

“Short version: yes. Long version: Hell yes.” - 8BT

3

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.

···

–
Jim Freeze

Paul Revere was a tattle-tale

4

Nope, that doesn’t help. The production:

XS : /empty/ | X | XS X ;

is fairly common.

···

On Tuesday, 21 October 2003 at 3:52:29 +0900, Ryan Pavlik wrote:

On Tue, 21 Oct 2003 03:47:03 +0900 > Jim Freeze jim@freeze.org wrote:

> METH_DEFS : OPT_NEWLINE > > METH_DEF > > METH_DEFS METH_DEF > ;

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

VMS is like a nightmare about RSX-11M.

5

Nope, that doesn’t help. The production:
XS : /empty/ | X | XS X ;
well, you’re production doesn’t match this does it? try putting empty
or new line into XS instead. btw, isn’t X XS preferred?
nikolai

···

–
::: name: Nikolai Weibull :: aliases: pcp / lone-star / aka :::
::: born: Chicago, IL USA :: loc atm: Gothenburg, Sweden :::
::: page: www.pcppopper.org :: fun atm: gf,lps,ruby,lisp,war3 :::
main(){printf(&linux["\021%six\012\0"],(linux)[“have”]+“fun”-97);}

6

Nope, that doesn’t help. The production:
XS : /empty/ | X | XS X ;
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 ;
B : whatever ;

Bu, the following is ok:

start : B | A B;
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;

···

On Tuesday, 21 October 2003 at 6:33:23 +0900, Nikolai Weibull wrote:
A : /empty/ | a | A a ;
A : /empty/ | a | A a ;

–
Jim Freeze

In a five year period we can get one superb programming language. Only
we can’t control when the five year period will begin.

7

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

···

–
::: name: Nikolai Weibull :: aliases: pcp / lone-star / aka :::
::: born: Chicago, IL USA :: loc atm: Gothenburg, Sweden :::
::: page: www.pcppopper.org :: fun atm: gf,lps,ruby,lisp,war3 :::
main(){printf(&linux["\021%six\012\0"],(linux)[“have”]+“fun”-97);}

8

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 : | XS X;

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

···

On Mon, 2003-10-20 at 22:50, Jim Freeze wrote:

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;

–
– Jim Weirich jweirich@one.net http://onestepback.org

“Beware of bugs in the above code; I have only proved it correct,
not tried it.” – Donald Knuth (in a memo to Peter van Emde Boas)

9

In Message-Id: 1066740248.9552.19.camel@traken
Jim Weirich jweirich@one.net writes:

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.

···

–
kjana@dm4lab.to October 22, 2003
So many men, so many minds.