Re: Why LL(1) Parsers do not support left recursion?

Hans-Peter Diettrich <DrDiettrich1@aol.com> writes:
....
> 1. LL parsers cannot handle left recursion, whereas LR parsers cannot
> handle right recursion.
>
> 2. Most languages are ambiguous at the syntax level, so that implicit
> disambiguation (longest match...) or explicit semantical constraints
> must be introduced. (see: dangling else...).
>
> 3. Only LL(1) recursive descent parsers are readable, that's why no
> LL(k) parser generators exist, in contrast to LR(k) parser generators.
>
> 4. When at least one terminal must be consumed, before a recursive
> invocation of a rule, no infinite recursion can occur. (every loop will
> terminate after all terminals in the input stream have been consumed)
>
> Any objections, so far?


Yes.


Point 1 is incorrect; LR parsers can handle right recursion in
addition to left recursion.


Point 2 is incorrectly stated, at the least. You seem to have meant
not that the languages are ambiguous, but rather than particular
grammars that are commonly used for those languages are ambiguous.
Taking the example of the dangling else problem, there are unambiguous
grammars for this as well as ambiguous ones. The published reference
grammar for Java, for example, is unambiguous, rather than relying
upon an extragrammatical disambiguation rule. (Note that such a
disambiguation rule is not semantic, contrary to what you say, just a
portion of the syntax specification that may, in some cases, be
presented extragrammatically.) Therefore, it seems that your point 2
boils down to a claim that "most" of the time the specifiers of
programming language syntaxes find it more convenient to use an
ambiguous grammar coupled with extragrammatical disambiguation rules,
rather thon to use an unambiguous grammar. This is an empirical
question about the frequency with which different notational
approaches are used, which I would be hesitant to try to answer just
based on what I personally have seen. It certainly is not an
implausible claim, however.


Point 3 can be read two ways; both are incorrect. You may be claiming
that recursive descent parsers are only are readable when based on
LL(1) grammars, or you may be making the stronger claim that no parser
other than an LL(1)-recursive-descent parser is readable, including no
non-recursive-descent parser. By refuting the weaker claim, I can
show that both are false. There are readable recursive descent
parsers that are not based on LL(1) grammars, both ones that are based
on LL(k) grammars for k>1, and ones that are not based on any LL(k)
grammar, but rather require general unbounded backtracking. Taking
the simpler case of k>1, consider, for example, the following grammar,
which is LL(2) but not LL(1):


S -> a b S | a c


The recursive descent parser for this can be written quite readably.
As some evidence of that, I append to the end of this posting a Java
program that embodies such a parser. (It isn't the world's greatest
Java style, but I think it still makes the point.)


> ...
> Ad (3): This is the only reason for the preference of LR parsers. Why
> spend time with tweaking a grammar to LR(1)/LL(1), when a parser
> generator for LR(k) is available?


No, the preference for LR parsers over LL has little to do with point
3, not only because point 3 is incorrect, but also because you are
here addressing the k>1 case, whereas most practical parsers use k=1
in any case. The issue is that LR(1) parsers are more powerful than
LL(1); the grammars suitable for LR(1) parsing are a proper superset
of those suitable for LL(1) parsing.


  -Max Hailperin
    Professor of Computer Science
    Chair, Mathematics and Computer Science Department
    Gustavus Adolphus College
    http://www.gustavus.edu/+max/


====== a Java LL(2) recursive descent parser follows ==========


import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;


public class LL2 {
        // a simple LL(2) recursive descent parser
        // using individual bytes of input as tokens (no lexical analysis)


        private static boolean S(BufferedReader input) throws IOException {
                input.mark(2); // prepare to put back up to 2 characters


                // try production 1
                if(input.read() == 'a' && input.read() == 'b')
                        return S(input);
                else
                        input.reset();


                // try production 2
                if(input.read() == 'a' && input.read() == 'c')
                        return true;
                else
                        input.reset();


                // no more productions; failure
                return false;
        }


        public static void main(String[] args){
                try{
                        BufferedReader in = new BufferedReader(new FileReader(args[0]));
                        if(S(in) && in.read() == -1)
                                System.out.println("Input succesfully parsed.");
                        else
                                System.out.println("Input was not in the language.");
                } catch(Exception e) {
                        System.err.println(e);
                }
        }
}

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