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


2

No, the authors meant that there is no right-sentential form of the grammar that starts with R =. That is, the = in that observation is a literal terminal symbol. A right-sentential form is a sequence of terminal and/or non-terminal symbols which might appear in a rightmost derivation. So what they are saying is that no rightmost derivation of that grammar ...


2

Every reduce action corresponds to a production; the action "undoes" the production by replacing its right-hand side with the non-terminal which produced it. That can only happen in one way; the parsing automaton does not invent or suppress non-terminals. So it doesn't matter which algorithm was used to create the automaton; the actions will be the same. ...


2

You haven't actually augmented the grammar. The augmented grammar has the production $$start\to SL\;\$$$ With that change, state 1 is not a reduction state and there is no conflict. If you did not intend to augment the grammar, then it is not $LR(0)$, because the language does not have the prefix property. But that's not very useful, so normally we augment ...


1

Here's one pattern for an LR(k) grammar which is not LR(k-1). I didn't fill in the definition of $A$; there's nothing particularly special about it. It might have an empty right-hand side, or it might match any LR(k) subgrammar. $a^k$ represents $k$ instances of $a$. $$ \begin{align}S&\to B a^{k-1} b\\ S&\to C a^{k-1} c\\ B&\to A\\ C&\to A\\ ...


1

This conflict arises because when the parser is at the beginning of a line and the lookahead is VAR, it can't tell whether or not to reduce an empty maybe_specifier. In this simple grammar, that decision could be resolved with one more lookahead token, making the grammar LR(2), but that might not be true in the original unsimplified version. So the conflict ...


1

Before applying the LR algorithm to a grammar, the grammar must be "augmented" by adding the rule $S' \to S \$$ where $S$ is the original start symbol and $S'$ and $\$$ are symbols not in the grammar. $S'$ becomes the start symbol for the augmented grammar, and the string to be parsed is augmented by appending a $\$$ at the end. A reduce action for this ...


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