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 \...
- 11.9k
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 ...
- 11.9k
5
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 ...
- 3,469
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, <...
- 3,024
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:
...
- 11.9k
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 ...
- 3,256
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 ...
- 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 $...
- 275k
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}...
- 11.9k
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 / ...
- 11.9k
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 ...
- 11.9k
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)...
- 3,024
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 ...
- 11.9k
Only top scored, non community-wiki answers of a minimum length are eligible