Re: Beginner help with LALR(1) closure

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).


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.
--

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