grammarll-grammarleft-recursion

Why can't a LL grammar be left-recursive?

In the dragon book, LL grammar is defined as follows:

A grammar is LL if and only if for any production A -> a|b, the following two conditions apply.

  1. FIRST(a) and FIRST(b) are disjoint. This implies that they cannot both derive EMPTY

  2. If b can derive EMPTY, then a cannot derive any string that begins with FOLLOW(A), that is FIRST(a) and FOLLOW(A) must be disjoint.

And I know that LL grammar can't be left recursive, but what is the formal reason? I guess left-recursive grammar will contradict rule 2, right? e.g., I've written following grammar:

S->SA|empty
A->a

Because FIRST(SA) = {a, empty} and FOLLOW(S) ={$, a}, then FIRST(SA) and FOLLOW(S) are not disjoint, so this grammar is not LL. But I don't know if it is the left-recursion make FIRST(SA) and FOLLOW(S) not disjoint, or there is some other reason? Put it in another way, is it true that every left-recursive grammar will have a production that will violate condition 2 of LL grammar?

Solution

  • OK, I figure it out, if a grammar contains left-recursive production, like:

    S->SA

    Then somehow it must contain another production to "finish" the recursion,say:

    S->B

    And since FIRST(B) is a subset of FIRST(SA), so they are joint, this violates condition 1, there must be conflict when filling parse table entries corresponding to terminals both in FIRST(B) and FIRST(SA). To summarize, left-recursion grammar could cause FIRST set of two or more productions to have common terminals, thus violating condition 1.