Re: Beginner help with LALR(1) closure (David Lester)
14 Nov 1996 21:50:43 -0500

          From comp.compilers

Related articles
Beginner help with LALR(1) closure (Kent Rollins) (1996-11-12)
Re: Beginner help with LALR(1) closure (1996-11-14)
Re: Beginner help with LALR(1) closure (1996-11-14)
Re: Beginner help with LALR(1) closure (1996-11-14)
Re: Beginner help with LALR(1) closure (Francisco Arzu) (1996-11-14)
Re: Beginner help with LALR(1) closure (1996-11-19)
Re: Beginner help with LALR(1) closure (1996-11-19)
Re: Beginner help with LALR(1) closure (Gianni Mariani) (1996-12-03)
[2 later articles]
| List of all articles for this month |

From: (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 <> 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).

My usual advice to undergraduate students in this situation is to
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

Return to the comp.compilers page.
Search the comp.compilers archives again.