Determine if a LL(2) grammar is strong

Question

Given a LL(2) grammar , how can i determine if it is strong ?

Answer 1

From http://slkpg.byethost7.com/llkparse.html

Definition:  A grammar G = ( N, T, P, S ) is said to be strong
LL(k) for some fixed natural number k if for all
nonterminals A, and for any two distinct A-productions in the grammar

$A \rightarrow \alpha$

$A \rightarrow \beta$

$FIRST_k ( \alpha \,\, FOLLOW_k (A) ) \cap FIRST_k ( \beta \,\, FOLLOW_k (A) ) = \emptyset$

That is, each parsing decision is based only on the next k tokens of the
input for the current nonterminal that is being expanded.

Answer 2

The term strong is misleading here. Strong LL(k) grammars are a proper subset of LL(k) grammars, and every LL(k) grammar is also strong LL(k). So the answer is that if you have an LL(2) grammar, it is strong LL(2).

Briefly, the use of FOLLOW sets causes some left context information to be lost. A more interesting question is give an example of an LL(k) grammar that is not strong. Consider the classic example of a grammar that is LL(2), but not strong LL(2).

S -> a A a

S -> b A b a

A -> b

A ->

The problem is that "ba" predicts both of the S productions. The left context before the A is needed to resolve the conflict. This grammar is made strong LL(2) by adding a new, duplicate nonterminal A2 in the following way.

S -> a A a

S -> b A2 b a

A -> b

A ->

A2 -> b

A2 ->

Now the left context is not needed because A and A2 are different nonterminals.