small medium large xlarge

22 Sep 2014, 15:12
Nikolaos Havaranis (1 post)

In Chapter 2, Pattern 4 “LL(k) Recursive Descent Parser”, the following is given as an example of a LL(1) grammar that has become LL(2) with the addition of an extra rule:

list     : '[' elements ']' ;
elements : element (',' element)* ;
element  : NAME '=' NAME
         | NAME
         | list

The extra rule is

element  : NAME '=' NAME

However, the grammar is still LL(1), which can be shown by expressing the rules for element in a more compact way.

element  : NAME ('=' NAME)?
         | list

That is not to say that it isn’t LL(2) also. An LL(1) grammar with empty rules (in CFG form) has an equivalent LL(2) grammar without empty rules. Empty rules in the CFG form are expressed in BNF by making part of a production optional. Which means you can avoid the need for making part of a production optional by increasing the lookahead. This holds for any LL(k) grammar with empty rules.[1] Hence the grammar is still LL(1), although it can be expressed as LL(2) as well.

The problem with finding a good example of a LL(2) grammar lies in the fact that any LL(2) grammar without empty rules has an equivalent LL(1) grammar with empty rules. This also holds for any LL(k), k > 1 grammar without empty rules.[1]

[1] D. J. Rosenkrantz, R. E. Stearns (1970). “Properties of Deterministic Top-Down Grammars”, Information and Control (17), pp 226-256, Theorems 3 & 5

21 Apr 2015, 16:56
Terence Parr (53 posts)

The grammar is not LL(1) the language is, which means you can rewrite an LL(2) grammar for it to be LL(1).

You must be logged in to comment