grammar question

[Fernando Pereira]

On 2/26/02 1:54 PM, in article
mailman.1014749745.3940.python-list at python.org, "Justin Sheehy"
<justin at iago.org> wrote:

> Fernando Pereira <pereira at cis.upenn.edu> writes:
> 
>> In general, languages with infix operators and complex nested
>> structures like lists are not LL(k), because a parser can only
>> decide the role of a subexpression after it sees the operator or
>> terminator that follows it.
> 
> One can usually (but not always) create an LL(k) grammar for such
> languages.  It just requires some interesting manipulation of the
> grammar productions such as left factoring and removal of left
> recursion.
> 
What do you mean to "usually"? It can be done for the LC(k) class by
expanding the set of nonterminals and productions considerably, but not all
deterministic languages are LC. (Daniel J. Rosenkrantz, Philip M. Lewis II:
Deterministic Left Corner Parsing (Extended Abstract). FOCS 1970: 139-152)
The LC->LL transformation is rather pretty and can be optimized in
interesting ways; unfortunately I know of no widely avaliable tools that
perform it. The problem with LC is that you need to commit to a reduction
after seeing the first RHS nonterminal and the lookahead at that point,
which may not be good enough for your favorite language.

> This is a pain to do, but once you have done it you can use a nice
> recursive-descent LL(1) parser.

Exactly. Doing the LC transformation by hand is no fun. Also, accurate error
reporting would seem to be harder than with a shift-reduce parser.

-- F