Search code examples
javacompiler-constructiongrammarleft-recursion

Grammar restrictions on token look ahead

I know that there are two types of restriction on grammars that are used with recursive descent parsers.

  1. the grammar cannot have any left recursive productions
  2. the grammar must not require more than on token look ahead.

I understand the first one but am a little lost on the second restriction. Why is this restriction necessary and can production even exist without it?

Solution

  • The second restriction can be relaxed somewhat by requiring that a parser can decide which production to use based on the first k tokens (as opposed to based on a single token). This allows for efficient (i.e. linear time) parsing algorithms for this class of grammars (see Recursive descent parser).

    The main reason for choosing k=1 in practice seems to be that parsers for LL(1) grammars are easier to construct. Apparently many computer languages are designed to be generated by an LL(1) grammar. See LL parser.

    The grammar comprised of productions S -> A | B, A -> a A b | eps, and B -> a B b b | eps is an example of a non-ambiguous non-LL(1) grammar because the parser cannot decide which production to use based on a single token. (Taken from here.)