Re: Beginner help with LALR(1) closure

dlester@cs.man.ac.uk (David Lester)14 Nov 1996 21:50:43 -0500

From comp.compilers

Related articles
Beginner help with LALR(1) closure kentr@rollinssoft.com (Kent Rollins) (1996-11-12)
Re: Beginner help with LALR(1) closure dlester@cs.man.ac.uk (1996-11-14)
Re: Beginner help with LALR(1) closure grout@sp55.csrd.uiuc.edu (1996-11-14)
Re: Beginner help with LALR(1) closure compres@world.std.com (1996-11-14)
Re: Beginner help with LALR(1) closure farzu@cs.tamu.edu (Francisco Arzu) (1996-11-14)
Re: Beginner help with LALR(1) closure adrian@dcs.rhbnc.ac.uk (1996-11-19)
Re: Beginner help with LALR(1) closure salomon@silver.cs.umanitoba.ca (1996-11-19)
Re: Beginner help with LALR(1) closure gianni@engr.sgi.com (Gianni Mariani) (1996-12-03)
[2 later articles]
| List of all articles for this month |

 From: dlester@cs.man.ac.uk (David Lester) Newsgroups: comp.compilers Date: 14 Nov 1996 21:50:43 -0500 Organization: Dept Computer Science, University of Manchester, U.K. References: 96-11-080 Keywords: LALR

Kent Rollins <kentr@rollinssoft.com> writes:
> 1. I've downloaded a few YACC-able grammars and I've noticed that
> they all have left-recusive grammars like (A) below.

> A //// statement-list statement
> A //// statement-list statement

The usual reason for using right recursion in LR parsing, is that
the stack usage whilst parsing is constant rather than proportional
to the length of the list of statements' being parsed.

> When I
> run this thru my generator, these cause infinite recursion.
> I can't find anything in Holub about how the LALR(1) generator
> should handle left-recursion. In order to get around the
> problem, I used a technique from a previous chapter which
> eliminates left-recursion (B) from LL grammars. I would like to
> know how the LALR(1) closure process avoids left recursion.
>
> B //// statement-list statement statement-list-pri
> B ////
> B //// statement-list-pri statement statement-list-pri
> B //// EPS

There should be no problem handling these things directly.
As a simplification consider the SLR parse table generation
for example A. [The only difference for LALR is that we need
to carry around lookahead tokens for the purpose of generating
the reduce actions.]

Productions: (X = statement-list, S = statement)

S' -> X
X -> S
X -> X S

0 = {S' -> .X, X -> .S, X -> .X S}
1 = goto(0,X) = {S' -> X. , X -> X. S}
2 = goto(0,S) = {X -> S. }
3 = goto(1,S) = {X -> X S.}

Now let's consider example B: (X = statement-list, S = statement,
X' = statement-list-pri)

S' -> X
X -> S X'
X' -> S X'
X' ->

0 = {S' -> .X, X -> .S X'}
1 = goto(0,X) = {S' -> X.}
2 = goto(0,S) = {X -> S.X' , X' -> .S X' , X' -> . }
3 = goto(2,S) = {X' -> S.X', X' -> .S X' , X' -> . }
4 = goto(2,X') = {X -> S X'.}
goto(3,S) = 3
goto(3,X') = 4

There are two possible candidates for the error you're observing:

(1) When union'ing in new items (of the form "A -> . \beta") you
are not checking whether you already have these items.

or, more likely,

(2) When constructing the collection of items, you are not checking
to see whether the set of items has already appeared (cf
goto(3,S) and goto(3,X') above).

write pretty-printing routines for whatever data-structures you've
chosen to represent items and sets of items, very early. Hopefully, if
I'm correct about (2) above, you'll see the repeated creation of sets
of items identical to 3 and 4 above.

The indirect recursion shown in your `C' types example, should also
drop out correctly (though I don't care to do this by hand).

---
David Lester, Computer Science, Manchester University, Manchester M13 9PL, UK.
--

Post a followup to this message