Re: LL vs LR, strengths and weaknesses

eifrig@blaze.cs.jhu.edu (Jonathan Eifrig) writes:
>>The disadvantage really only lies in the fact that you have more constraints
>>when writing LL(k) grammars--no left-recursion and no common prefixes of
>>tokens >= k tokens in length.
>
> But this is no small restriction! Consider the common expression
>grammar:
> E -> E + T | E - T | T
> T -> T * N | T / N | N
> N -> (E) | 1 | 2 | ...
>
> This grammar is not LL(k) for any k (since I can pump with the
>parentheses.) But this is the natural grammar for this language. Sure, I
>can change it to LL(1) by changing the associativity of the operators, but
>that produces a parse tree that doesn't reflect the intended semantics of
>the language, and will cause me headaches later on.
>
> I don't see any good solution to this, other than LR parsing. How


I agree that "pure" LL is a pain to work with. Your example is unfair
though because you made no attempt to translate it into an equivalent LL
grammar (by left-factoring). I could give you an equally unfair LR set of
productions that had right recursion.


However, using extended BNF for recursive descent parsing removes the
horrors of left recursion and common prefixes. It also makes attachment
of semantic actions very easy. I would rewrite your grammar as:


E -> T { ("+" | "-") T }
T -> N { ("*" | "/") N }
N -> "(" E ")" | 1 | 2 | . . .


The first translator writer strategy I tried was translating the EBNF back
to LL BNF and then traditional LL parsing. This too was a pain. I then
discovered the syntax trees approach on Barrett, Bates, Gustofson, and
Couch "Compiler Construction: Theory and Practice" which builds a
canonical syntax tree for EBNF productions, enables first and follow set
evaluation, and very nicely allows you to produce one procedure for each
EBNF production. The semantic actions are neatly embedded between the
grammar symbols.


A TWS language is not easy by adding specification of attributes
(inherited, synthized, and local = temporary values). This allows the TWS
to automatically generate the local storage declarations as well as the
formal and actual procedure header declarations. Add to this the matching
of a name with each grammar terminal symbol and the produced parser is
even readable.


The above has been implemented in Modula-2 if anyone is interested.


The bottom line is that producing recursive descent translator writer
systems is very straight forward and clean if one uses EBNF. It works for
me much better than LR parsing.


Tom Reid, Director of Computer Science reid@vtopus.cs.vt.edu
Virginia Tech Northern Virginia Graduate Program (703)698-4712
2990 Telestar Court, Falls Church, VA 22042
--

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