Re: Quick way to recognize grammar type

>Is there any way of determining quickly if a given grammar is one of
>LL(0)/LR(0)/LALR/LR(1). I know that we can construct the set of items
>and hence the parsing table. But I am looking for some tricks/tips by
>which we can quickly determine if the grammar is one of the above four
>types.


Some definitions first:


"null" no-terminal symbol: a no-terminal tha ONLY derives or produces the
null string (lambda)
"p-reduced" no-terminal symbol: a no-terminal symbol tha is not "null"
"p-reduced" grammar: a reduced grammar with all it's no-terminal symbols
"p-reduced"




You can compute First(1) sets to know if the no-terminals are "null" or
"p-reduced":


if First(A) == {lambda} then A is NULL
if First(A) != {lambda} then A is P-REDUCED


Then check if the grammar is LL(1).
We know that when a CFG is LL(1) then it's LR(1). The problem is that this
is not true for other members of the LR family: LR(0), SLR(1) and LALR(1).
But there are two sufficient conditions that can help us:


if a CFG is LL(1) AND


a) do not have lambda-rules, then the CFG is LR(0)
b) is "p-reduced", then is LALR(1)


If you know that the CFG G is reduced and LL(1) then:


if G don't have lambda-rules then
G is LR(0)
else
if G is "p-reduced" then
G is LALR(1)
else (there are lambda-rules and null terminals in G)
You must try to construct the LALR automaton and check for conflicts...
endif
endif


These are ideas from


On the relationship Betwen the LL(1) and LR(1) Grammars.
John C. Beatty
JACM Vol. 29, Nš 4, 1982.




Hope this help




Salvador Cavadini
http://www.ucse.edu.ar/fma/staff/svcavadini
Software for Teach Parsing Techniques: www.ucse.edu.ar/fma/sepa

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