Re: Grammar LR(1) but not LALR(1)
11 Nov 2003 13:37:48 -0500

          From comp.compilers

Related articles
Grammar LR(1) but not LALR(1) (Jean-Marc Bourguet) (2003-10-31)
Re: Grammar LR(1) but not LALR(1) (Oliver Zeigermann) (2003-11-02)
Re: Grammar LR(1) but not LALR(1) (Chris F Clark) (2003-11-02)
Re: Grammar LR(1) but not LALR(1) (ANDREI Stefan) (2003-11-08)
Re: Grammar LR(1) but not LALR(1) (Jean-Marc Bourguet) (2003-11-08)
Re: Grammar LR(1) but not LALR(1) (2003-11-11)
| List of all articles for this month |

Newsgroups: comp.compilers
Date: 11 Nov 2003 13:37:48 -0500
Organization: Compilers Central
References: 03-10-139 03-11-013
Keywords: parse, LALR
Posted-Date: 11 Nov 2003 13:37:48 EST

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

Post a followup to this message

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