Validating LL Grammar (2)

Question

Problem 19.5 of languages ​​and machines Sudkamp asks the reader to verify that the grammar

G : S' -> S## S -> aSa | bSb | λ 

strongly LL(2) . The set of FIRST and FOLLOW for the variable S calculated using algorithm 19.5.1 (p. 583, 3rd ed.):

 FIRST(2)(S) = {λ,aa,bb,ab,ba} FOLLOW(2)(S) = {##,a#,b#,aa,bb,ab,ba} 

It is clear that definitions of look-head of length-2 for rules S will not break the set of look-head length-2 for S , because of the rule S -> λ , which leads to the appearance of length-2 set consisting of FOLLOW(2)(S) :

 LA(2)(S) = {##,a#,b#,aa,bb,ab,ba} LA(2)(S -> aSa) = {a#,aa,ab} LA(2)(S -> bSb) = {b#,bb,ba} LA(2)(S -> λ) = {##,a#,b#,aa,bb,ab,ba} 

Now it’s possible that I made a mistake when calculating the FIRST , FOLLOW or LA(2) sets for G However, I am sure that the algorithm performed correctly. In particular, I can return to their definitions:

 FIRST(2)(S) = trunc(2)({x : S =>* x AND x IN Σ*}) = trunc(2)({uu^R : u IN {a,b}^*}) = {λ,aa,bb,ab,ba} FOLLOW(2)(S) = trunc(2)({x : S' =>* uSv AND x IN FIRST(2)(v)}) = trunc(2)({x : x IN FIRST(2)({a,b}^*{##})}) = trunc(2)({##,a#,b#,aa,bb,ab,ba}) = {##,a#,b#,aa,bb,ab,ba} 

Now the question arises: why is LL(2) strong grammar LL(2) . If the look-head set of length-2 for S rules does not break the set of look-head of length-2 for S , then the grammar should not be strong LL(2) . But I cannot come to the conclusion expected in the book. What? I do not understand?

Answer 1

Here is the solution. The above grammar G not a strong LL(2) . To see this, remember the definition of strong grammar LL(k) . The grammar G is LL(k) for some k > 0 if whenever there are two leftmost differentiations

 S =>* u1Av1 => u1xv1 =>* uzw1 S =>* u2Av2 => u2yv2 =>* u2zw2 

where ui,wi IN Σ* for i IN {1,2} and |z| = k |z| = k , then x = y . Consider the following left outputs in G grammar above:

 S =>* aaSaa## (u1 = aa, v1 = aa##) S =>* baSab## (u2 = ba, v2 = ab##) =>1 aaaa## (x = λ) =>1 baaSaab## (y = aSa) =>* aaaA## (z = aa, w1 = aa##) =>* baaaab## (z = aa, w2 = ab##) 

Conclusions satisfy the conditions for determining a strong grammar LL(2) . However, λ \= aSa and, therefore, G not strongly LL(2) .

It is clear that we can construct many left conclusions that demonstrate that G not a strong LL(2) . But there are several more reasons why G not a strong LL(2) . For example, it is obvious that G cannot be restored using deterministic pushdown automata, because there is no way to determine when to start removing items from the stack.