0
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ I am not sure if this is in the scope of cstheory since this does not seem to be a research-level question. Please read the FAQ. $\endgroup$
    – Kaveh
    May 7 '11 at 20:35
  • 10
    $\begingroup$ what is a "strong" grammar ? $\endgroup$ May 8 '11 at 5:43
4
$\begingroup$

From http://slkpg.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.
$\endgroup$
2
$\begingroup$

The term strong is misleading here. Strong LL(k) languages are a proper subset of LL(k) languages, 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.

$\endgroup$
2
  • 2
    $\begingroup$ Strong LL(k) grammars are a proper subset of LL(k) grammars, and every LL(k) grammar is also strong LL(k). <-- this is a contradiction $\endgroup$ Oct 16 '15 at 9:23
  • $\begingroup$ Strong LL(k) grammar are a subset of LL(k) grammar. But The LL(k) languages generated by these grammars are the same. The term strong only apply to grammars. Not languages. $\endgroup$
    – jlguenego
    Feb 11 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.