Example grammars - not necessarily LL(1)

Example: Grammar with left recursion and an equivalent LL(1) grammar

A subset of Java: statements

A grammar proposed for describing composed statements in curly brackets (for instance as the body of a method):

• Suite --> {  Seq  }
• Seq -->   E  |  Seq  E
• E -->  A  |  IF  |  Appel
• A -->  id  =  Exp  ;
• IF -->  if  (  Exp  )  Suite  ELSE
• ELSE -->  epsilon  |  else  Suite
• Appel -->  id  (  P  )  ;
• P -->  epsilon |  ...

Now consider the following steps:

1. calculate the sets FIRST and FOLLOW
2. Verify whether the grammar is LL(1): one sees that there are the following problems:
   1. The two alternatives of the nonterminal Seq have the same First sets (because of the left recursion)
   2. The alternatives A and Appel of the nonterminal E have the same First sets (the two alternatives start with an identifier)
3. Can one find an equivalent grammar that avoids these problems ? - The answer is YES:
   1. A method for eliminating left recursion is explained in the course notes. One obtains:   Seq --> E Encore      and       Encore --> epsilon | E Encore.
   2. A method for solving the problem of alternatives that start with the same symbols is to combine the common prefixes (see course notes). One obtains:   E --> IF  | id  SuiteId     and     SuiteId --> = Exp ;  |  (  P  )  ;

Ambiguity of the Pascal grammar

We refer here to a simplified Pascal grammar. If we add the possibility of having an IF statement without an ELSE, one could add an alternative for the nonterminal Statement in the form: statement -->  if expression then statement . Combined with the rule that exists already in the grammar (including the ELSE), one obtains the rule: statement --> if expression then statement  ELSE    and    ELSE --> epsilon  |  else statement .

Then

1. Calculation of FIRST and FOLLOW: since ELSE may generate the empty word, one has to determine the set Follow(ELSE); it contains Follow(statement). One sees that Statement may preceed ELSE, therefore First(ELSE) is included in Follow(ELSE). Therefore Follow(ELSE) includes "else" since the latter is in First(ELSE). This means that First(ELSE) and Follow(ELSE) are not disjoint; and the grammar is not LL(1).
2. In effect, the grammar is not only not LL(1), but it is ambiguous. For the sentence if x=1 then if y=2 then z:=3 else z:=4 there are two syntax trees that have Statement as root: one tree associates the else clause with the first if, the other associates it with the second if.
3. It is not easy to find an equivalent grammar that is LL(1).

Translated from french: March 2, 2008