Skip to main content
6 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 ...
rici's user avatar
  • 12.1k
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 \...
rici's user avatar
  • 12.1k
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: ...
rici's user avatar
  • 12.1k
3 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 ...
André Souza Lemos's user avatar
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 ...
kiv's user avatar
  • 339
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 $...
Yuval Filmus's user avatar
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}...
rici's user avatar
  • 12.1k
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 / ...
rici's user avatar
  • 12.1k
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 ...
rici's user avatar
  • 12.1k

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