Hot answers tagged

11

$LL(k)$ and $LR(k)$ grammars are nice not just because they can be parsed efficiently, but also because we can check if a grammar is $LL(k)$ or $LR(k)$, and because we can generate tables for them (parse tables are used to parse input strings). Note that for these two classes, having the parse table immediately allows you to check whether the grammars are in ...


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


4

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

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

I do not believe one can obtain directly a minimum $k$ such that $G$ is a strong $LL(k)$ grammar. However, as it is possible to (dis)prove that a grammar is strong $LL(k)$, one can iterate the proof over $k$. A grammar $G$ is strong $LL(k)$ iff for every pair of distinct production rules $A \to \alpha$ and $A \to \beta$ (with $\alpha \neq \beta$), we have: ...


2

We have to check only that a grammar is LL or not because every LL grammar is LR that is LL is proper subset of LR. So if a grammar is LL then it must be LR but every LR is not LL. A grammar G is in LL iff whenever A->C|D , the following condition should hold: First(C) and First(D) are disjoint sets. If empty is in First(D) the First(C) and Follow(A) are ...


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


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

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


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


1

A 'top down parser' is usually understood to be a hand-written $LL(1)$ parser, or $LL(k)$ for some low $k$, which would explain the use of this terminology. These two concepts are therefore essentially the same. I'm unsure what you mean exactly by 'common prefixes' - I guess you are talking about common lookaheads. If you ensure that you can always uniquely ...


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