Re: Grammar LR(1) but not LALR(1)

Jean-Mark asked:
> I'm convinced that such a transformation (contructing an LALR(1)
> grammar by duplicating productions) is possible for every LR(1)
> grammars, such duplication preventing the merge of the states LR(1)
> automaton.
> . . .
> Could someone point me to a counter example for my claim or a proof of
> its correctness?


And then people who know a lot more about the subject than me responded.


But I think this is fairly simple.


Take an LR(1) grammar G = <N, T, P, S> and
create G' = < N', T, P', <S x $> >
where N' is a subset of N x T


(that is, the non-terminals in G' are the cartesian product of the
original non-terminals and the original terminals.)


N' and P' are constructed basically with the LR construction.
Start with N' = {<S x $>} and repeat until no new non-terminals are added:


Let <A, a> be an element of N' for which there are no productions in P'.


Now, for each production in P of the form:
A -> w1 w2 ... wn
add all possible productions
<A, a> -> w1' w2' ... wn'
where
    wi' = wi if wi is in T
    wi' = <wi, b> where b is in FIRST(w(i+1)...wn ++ a)
        if wi is in N
The second definition is multiple valued, so you might have to add a lot of
rules :)
Furthermore, if any new rule mentions a non-terminal <W, w> which is not
yet in N', add it to N'


It is clear that this must terminate, because all the sets are finite.
Also, the function FIRST used above never yields epsilon.


Now, I assert that G' recognises exactly the same language as G, and
furthermore that if G is LR(1) then G' is SLR(1), because it is impossible
to have a reduce/reduce conflict between <W, a> and <W, b>.


Of course, all this has done is move the lookahead sets into the definition
of the non-terminals, so the resulting SLR table is going to be just as big
as the original LR table (bigger, actually, since no merging of lookaheads
has been done), but I think it does answer the original question.

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