Re: How to get this to an lalr(1) grammar?

Mark_Tarrabain@mindlink.bc.ca (Mark Tarrabain) writes:


> Hi. I've been trying to figure out how to make a certain grammar
>lalr(1).


> s -> c | s t c
> c -> V n p
> a -> A | C o
> o -> /* empty */ | A
> t -> T | D | a u
> u -> /* empty */ | T
> n -> /* empty */ | L b | q
> q -> N | q a N
> b -> /* empty */ | B q
> p -> /* empty */ | P N


[ grammar condensed by me, "|" denotes alternatives ]


> Capital letters denote terminals, lower case letters nonterminals. The
>language and grammar are very evidently LR(2). If my understanding is
>correct, it should be possible to simplify it to LR(1), perhaps even
>LALR(1).


I did the conversion by hand and came very easily on:


s -> c | s t c | sa u c
sa -> ca | s t ca | sa u ca
c -> V n | V n P N
ca -> V na | V n P N a
a -> A | C o
o -> /* empty */ | A
t -> T | D
u -> /* empty */ | T
n -> /* empty */ | L b | q
na -> a | L ba | qa
q -> N | qa N
qa -> N a | qa N a
b -> /* empty */ | B q
ba -> a | B qa


with only little impact on the structure of the grammar:
- non-terminal p has vanished
- non-terminal t has lost one option
- some rules have two versions


Then, mickunas@mickunas.cs.uiuc.edu (Dennis Mickunas) writes:


> [ The grammar is LR(3) ]
> I believe that your intention was to preserve the structure imposed by
> the grammar. (Otherwise, it's dead easy to construct a grammar that
> works. Note that the language is regular. Simple back-substitution
> and recursion-to-Kleene-closure provides a regular expression.)
> [ Mechanical conversion of this grammar is hard ]


Did I do "back-substitution and recursion-to-Kleene-closure", did I do
some other mechanical conversion, or was I just lucky and does my
method fail on other grammars?


Ciao,
Rene'
--
Rene Dekker Delft University of Technology
R.Dekker@twi.tudelft.nl Department of Technical Mathematics and Informatics
Tel: +3115 783850 Julianalaan 132
Fax: +3115 787141 2628 BL Delft, The Netherlands
--

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