11 Nov 2003 13:37:48 -0500

Related articles |
---|

Grammar LR(1) but not LALR(1) jm@bourguet.org (Jean-Marc Bourguet) (2003-10-31) |

Re: Grammar LR(1) but not LALR(1) oliver@zeigermann.de (Oliver Zeigermann) (2003-11-02) |

Re: Grammar LR(1) but not LALR(1) cfc@shell01.TheWorld.com (Chris F Clark) (2003-11-02) |

Re: Grammar LR(1) but not LALR(1) stefan@infoiasi.ro (ANDREI Stefan) (2003-11-08) |

Re: Grammar LR(1) but not LALR(1) jm@bourguet.org (Jean-Marc Bourguet) (2003-11-08) |

Re: Grammar LR(1) but not LALR(1) RLake@oxfam.org.uk (2003-11-11) |

From: | RLake@oxfam.org.uk |

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'

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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.