Re: LL vs LR, strengths and weaknesses (Thomas F. Reid)
Wed, 13 May 1992 14:16:44 GMT

          From comp.compilers

Related articles
LL vs LR, no jihad initiation, but... (1992-05-11)
Re: LL vs LR, strengths and weaknesses (1992-05-11)
Re: LL vs LR, strengths and weaknesses (1992-05-13)
Re: LL vs LR, strengths and weaknesses (1992-05-13)
Re: LL vs LR, strengths and weaknesses (1992-05-14)
Re: LL vs LR, strengths and weaknesses (1992-05-14)
Re: LL vs LR, strengths and weaknesses (1992-05-15)
Re: LL vs LR, strengths and weaknesses (1992-05-19)
Re: LL vs LR, strengths and weaknesses (1992-05-16)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Thomas F. Reid)
Summary: Better Recursive Descent Parsing
Keywords: LL(1), LR(1), parse
Organization: VPI&SU Computer Science Department, Blacksburg, VA
References: 92-05-059 92-05-069
Date: Wed, 13 May 1992 14:16:44 GMT (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
> 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
Virginia Tech Northern Virginia Graduate Program (703)698-4712
2990 Telestar Court, Falls Church, VA 22042

Post a followup to this message

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