0
$\begingroup$

One of the conditions for A → α | β to be LL(1) grammar states that

If β → ε in one or more steps then α doesn't derive any string beginning with a terminal in FOLLOW(A). Likewise If α → ε in one or more steps then β doesn't derive any string beginning with a terminal in FOLLOW(A).

I couldn't understand what is the intuitive meaning of this condition and why this condition should hold? I could easily understand if an example is provided for the answer.

$\endgroup$
  • $\begingroup$ What is your question? General, lengthy explanations can be found in textbooks and other sources. Community votes, please: unclear? $\endgroup$ – Raphael Aug 1 '16 at 18:30
1
$\begingroup$

Considering the above condition, should α derive a string beginning with a terminal in FOLLOW(A), then it becomes impossible to determine which derivation will be used to produce this symbol with lookahead limited to one symbol.

For instance, should $\mathrm{s}$ be the symbol that is both on FIRST(α) and FOLLOW(A), and $x$ the leftmost substring already parsed, then the following sequences are both possible:

$xA$ω $ \Rightarrow x$βω $ \Rightarrow^* x$ω $ \Rightarrow^* x\mathrm{s}$…

$xA$ω $ \Rightarrow x$αω $ \Rightarrow^* x\mathrm{s}$…ω

Even if the grammar is not ambiguous, you can't decide which path to take by reading just $\mathrm{s}$.

$\endgroup$

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.