Show that LL1 construction fails for an unambiguous grammar

Show that LL(1) construction fails for an unambiguous grammar that is not LR(1).

Solution

Give an unambiguous grammar that is not LL(1).

LL Grammars

LL(k) grammars are a subset of CFGs . Permit the deterministic left – to – right top –down recognition with a look ahead k symbols.

If the correct production can be deduced from the partially constructed tree and the next k symbols in the unscanned string, for every possible top-down parsing step , then the grammar is said to be LL(k)

Properties of LL(k)

Each LL(k) grammar is unambiguous

To ensure that a grammar is LL(k), we must do the following:

Remove any ambiguity,

Eliminate any left recursion,

Eliminate any common left prefixes,

Once we have taken those steps, then we can prove that it is LL(1) by generating the FIRST and FOLLOW sets for the grammar, and using them to create the LL(1) parse table. If the parse table contains no conflicts, then we have proven that the grammar is LL(1).

An example for an unambiguous grammar that is not LR(1).

There are an infinite number of unambiguous non-LR(1) grammars.

Here is one of the simpler ones:

S A x y | B x z

A a

B a

The grammar is unambiguous; it contains exactly two strings and each string has a unique

derivation:

S A x y a x y

S B x z a x z,

// The grammar is not LR(1). Consider an input that begins with “ax”.

After shifting the a, the parser must reduce to either A or B.

Character of x, we cannot decide which of A or B is correct, leading to a reduce/reduce conflict.

Parsing this grammar correctly would require SLR(2), LR(2), or LALR(2).

With two characters, we would know to reduce a to A on look ahead x y, but to reduce a to B on look ahead x z.

The strings in the language of the grammar S a

The language of a grammar is the set of strings derivable from the grammar’s start symbol.

A derivation results from applying some finite sequence of productions from the grammar;

A string is a finite sequence of terminals selected from a given alphabet .

The grammar given above can never have a finite derivation that yields a finite string.

There is no string of terminals such that S + . Therefore, there are zero strings in the language of this grammar.

// Neither LL(1) nor SLR(1) nor LR(1) is able to parse any ambiguous grammar

E A | B

A a | c

B b | c

The grammar is ambiguous; there are two possible derivations of the string “c”. So none of LL(1), SLR(1), or LR(1) can possibly work.

This example shows that LR(1) is unambiguous.