Hot answers tagged

6 votes
Accepted

Is there a LL(K) Grammar which is not LALR(K) Grammar?

Every $LL(k)$ grammar is $LR(k)$, but there are $LL(k)$ grammars which are not $LALR(k)$. There's a simple example in Parsing Theory by Sippu&Soisalon-Soininen $$\begin{align}S &\to a A a \...
user avatar
  • 11.3k
5 votes

Lookahead in LL(k) parsing

No, you still consume one symbol at a time. However, you are allowed to consult the next $k$ symbols in order to decide what to do before consuming the symbol. Here's a simple example: the grammar of ...
user avatar
  • 11.3k
4 votes
Accepted

What exactly is the LL(k) grammar condition?

It's actually a definition of a strong LL(k) grammar. First of all, see Raphael's comment. In short, the condition means that while parsing $A$ you can choose the next production rule in a ...
user avatar
  • 3,419
3 votes

Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$

I would approach this question in this way, (k) in $\mathrm{LL}(k)$ means the number of lookaheads. The grammar of $\mathrm{L}$ here possess non-determinism. For example, if you can only see aaaa then ...
user avatar
  • 341
3 votes

Is this a proper LL(1) Grammar?

It's a perfectly valid grammar, and it's certainly LL(1). But since it only generates three sentences, it's probably not what you are looking for. The three sentences: ...
user avatar
  • 11.3k
3 votes

How to treat $\epsilon$ and '$' in top-down predictive parsing (predict table)?

$\epsilon$ is a terminal symbol No. $\epsilon$ is the empty string, i.e. no symbols at all. However, I've somehow interpreted that I could/should add '$' as a terminal symbol as well. Yes, <...
user avatar
  • 3,004
2 votes
Accepted

LL(k) Prediction Techniques (and Insight on method applied)

It turns out someone wrote half a book about LL(k) parsing, which wasn't mentioned on Wikipedia until I added it a coupe of minutes ago. Parsing Theory: LR(k) and LL(k) Parsing by Seppo Sippu; Eljas ...
user avatar
  • 1,230
2 votes

Proof that the grammar is LL(2)

Sippu and Soisalon-Soininen (1982) carefully distinguish between two definitions of LL(k) grammars, one of which -- the one I think you are using -- they call strong LL(k): A grammar $G$ is $\text{LL}...
user avatar
  • 11.3k
2 votes
Accepted

How to generate an LL(2) parse table?

There is a pretty reasonable discussion in this essay from the SLK parser generator. Basically, you just need to extend $FIRST$ and $FOLLOW$ to be $FIRST_k$ and $FOLLOW_k$, meaning the first / ...
user avatar
  • 11.3k
2 votes

Conditions for LL(1) grammar

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 ...
user avatar
2 votes
Accepted

Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$

Rosenkrantz and Stearns prove in their paper Properties of deterministic top-down grammars that the language $$ \{ a^n b^n : n \ge 0 \} \cup \{ a^n c^n : n \ge 0 \} $$ is not $\mathrm{LL}(k)$ for any $...
user avatar
1 vote

Not respecting the 3rd rule of a LL(1) grammar

Something like the following: $\begin{align} S &\to A a \\ A &\to a \mid \epsilon \end{align}$
user avatar
  • 13.6k
1 vote

Can I mix LL and LR parsing?

Using recursive descent in combination with an operator precedence variant for expressions is a very common approach. You might also want to search for Pratt parsing. An older, now uncommon ...
user avatar
  • 11.3k
1 vote

How to treat ϵ-productions in table-driven predictive parsing?

It will predict $A\rightarrow B$ if the look-ahead is in $FIRST(B)$, it will predict $A\rightarrow c$ if the look-ahead is $c$, it will predict $A\rightarrow\epsilon$ is the look-ahead is in $FOLLOW(A)...
user avatar
  • 3,004
1 vote
Accepted

How should I show that a grammar is not LL(1) and convert grammar to LL(1)

E → EE is obviously ambiguous, as as E → E*E. How should xxx be parsed? Is it [[x ...
user avatar
  • 11.3k

Only top scored, non community-wiki answers of a minimum length are eligible