<p>From <a href="http://slkpg.com/llkparse.html" rel="nofollow">http://slkpg.com/llkparse.html</a></p>

<pre>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</pre>

<p>$A \rightarrow \alpha$</p>

<p>$A \rightarrow \beta$</p>

<p>$FIRST_k ( \alpha \,\, FOLLOW_k (A) ) \cap  FIRST_k ( \beta \,\, FOLLOW_k (A) ) = \emptyset$</p>

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

CC BY-SA 3.0
2011-05-07T11:56:21.903Z
2015-11-20T02:38:36.707Z
2015-11-20T02:38:36.707Z
Rehno Lindeque
<p>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).</p>

<p>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).</p>

<p>S -> a A a</p>

<p>S -> b A b a</p>

<p>A -> b</p>

<p>A -></p>

<p>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.</p>

<p>S -> a A a</p>

<p>S -> b A2 b a</p>

<p>A -> b</p>

<p>A -></p>

<p>A2 -> b</p>

<p>A2 -></p>

<p>Now the left context is not needed because A and A2 are different nonterminals. </p>

CC BY-SA 3.0
2015-10-16T09:23:22.890Z
*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
reinierpost
CC BY-SA 4.0
2021-02-11T20:55:24.423Z
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.
jlguenego
CC BY-SA 3.0
2011-08-23T01:44:17.473Z
2015-11-19T20:35:34.103Z
2015-11-19T20:35:34.103Z
slkpg
<p>Given a LL(2) grammar , how can i determine if it is strong ?</p>

CC BY-SA 3.0
2011-05-07T20:35:34.113Z
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.
Kaveh
CC BY-SA 3.0
2011-05-08T05:43:28.433Z
what is a "strong" grammar ?
Suresh Venkat
<fl.formal-languages><grammars>
Determine if a LL(2) grammar is strong
Alex
# Determine if a LL(2) grammar is strong

(Asked by: username_0 on 2011-05-07)

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

**Tags:** fl.formal-languages, grammars
> **Comments:**
> **username_1**: 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.  
> **username_2**: what is a "strong" grammar ?  

---

## 2 answers

### Answer by username_3 on 2011-05-07. Score: 4 | Accepted answer

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.


---

### Answer by username_4 on 2011-08-23. Score: 2

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.

> **Comments:**
> **username_5**: *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  
> **username_6**: 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.  

---

