Hot answers tagged

6

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 \mid b A b \mid a B b \mid b B a\\ A &\to c \\ B &\to c \end{align}$$ The language of this grammar is finite, so it is obviously $LL(k)$. (In this case, $...


5

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 context-free grammars. Informally, a CFG is a sequence of productions, where each production consists of a non-terminal, the derives symbol ($\to$) and a ...


3

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 by just looking at the first k symbols, you can't make the decision whether it is aaaa or aaaabbbb. No matter how large the value of k is, there will always be ...


3

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: a < a a | a a / a For precision: As written, it's not quite correct. In order to achieve what I imagine you meant by the FIRST sets, you'd actually need to he a bit more precise. Instead ...


3

$\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, $ is the special symbol that marks the end of input, and you may have to do things at that place and when you want to go past it, you are done (or in situation of ...


3

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 deterministic manner using only the next $k$ lookahead symbols. An important thing is you don't need any context for that decision, i.e. you don't need to remember the ...


2

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 Soisalon-Soininen (1990). I've looked briefly through it and it does have LL(2) examples too. EDIT: As rici says below, this is the 2nd volume of a two-book ...


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}(k)$ if $\text{FIRST}_k(\omega_1\delta)$ and $\text{FIRST}_k(\omega_2\delta)$ are disjoint whenever $xA\delta$ is a left sentential form of $G$ and $A \to \...


2

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 / following $k$ symbols. The basic principle is the same, but when $k > 1$ there is a complication, leading to the distinction between "strong" and regular grammars. ...


2

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


2

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 $k$ (see page 246). Presumably a similar proof will show that your language is not $\mathrm{LL}(k)$ for any $k$. You mention a confusion between grammars and ...


1

Something like the following: $\begin{align} S &\to A a \\ A &\to a \mid \epsilon \end{align}$


1

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 technique which combines LL and LR parsing is "left-corner" (LC) parsing, which should also be easy to search for. In practice, the existence of easy-to-use and ...


1

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)$. If the prediction is ambiguous, the construction of the tables should either have failed or used another way to resolve the conflict (for instance you ...


1

E → EE is obviously ambiguous, as as E → E*E. How should xxx be parsed? Is it [[x x] x] or [x [x x]]? X is only problematic if Y is nullable. If you remove the incorrect empty production for Y, you will also fix that issue. To clarify, Y → ε is incorrect because it would allow Y to derive let A in which is not a complete statement (...


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