# Tag Info

8

According to Wikipedia: For every fixed $k \geq 1$: A language has an LR($k$) grammar iff it is DCFL. A language has an LR(0) grammar iff it is DCFL and has the prefix property (no word is a prefix of another word). The first property is proved in Knuth's original paper, in Section V on page 628.

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 Remember that the point of parsing (in almost all practical applications) is not simply to recognize whether or not a sentence is in a language, but rather to find the parse tree corresponding to the sentence in order to do further processing (such as compilation). Or, to put it another way, few people would purchase a "compiler" which took some input and ... 3 Your grammar is$\mathrm{LR}(0)$by adding a$\mathrm{\$}$ symbol to the alphabet and a starting deduction rule $S'\rightarrow S\$$when constructing the \mathrm{LR}(0) automaton (and it is a standard construction). Omitting syntactical purposes, every DCFL \mathrm{L} can be parsed by an \mathrm{LR}(0) grammar for \mathrm{L}\$$. What makes$\mathrm{...

3

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

3

"When I use a word," Humpty Dumpty said, in rather a scornful tone, "it means just what I choose it to mean—neither more nor less." Charles Dodgson -- who wrote those words under the name of Lewis Carroll -- was a brilliant mathematician with a taste for whimsy, all of which provide an interesting undercurrent to works such as Through ...

3

The grammar $$\begin{array}{l} S \rightarrow T_0 \\ T_n \rightarrow a \; T_{n+1} \\ T_n \rightarrow b \; T_{n+1} \\ T_n \rightarrow b \; T_{n+1} \; t_n \\ T_N \rightarrow t_N \end{array}$$ has the LR(0) state $$T_N \rightarrow t_N \dot \\$$ expanded to $2^N$ variants in the LR(1) automata as all the partitions of $\{t_0 \dots t_{N-1}\}$ are possible look-...

3

Yes, if you follow the canonical conversion of augmented grammars, a first step is adding a new start symbol $S'$ and the production $S' \to S$, since the algorithm may later "change" $S$. However, it may not be necessary at all times. If you ask whether or not it is necessary specifically in this case, why don't you try without it and check if you get a ...

3

I think you are mistaken, they are needed but the dot look-ahead there is so obvious that you have not paid attention to the fact it is used. First, let's remark that there are three kinds of items: those in which the dot is just before a non-terminal. They never participate in an ambiguous situation: when a non-terminal has been produced, it is shifted. ...

2

A language is $LR(k)$ if looking at the right side of a production, and looking $k$ symbols ahead, one can determine the left hand side of the production. This is quite incomplete, but intuitively easy (hah!) to grasp. In particular, it explains why $LR$ grammars are a much richer set than the $LL$ ones. In practice, it is probably much more relevant to be ...

2

Find all nullable variables. In this case only E' is nullable. Let me illustrate the second step with an example: Replace a production A -> BCD with a family of productions like this (assuming B, C & D are nullable): A -> BCD | BC | BD | CD | B | C | D Delete all the productions with the empty string as the right-hand side. With all that in mind ...

2

Propbably you should read the citation as: "The problem is that the c (which separates the two parts of the language) is at the extreme right and not at the extreme left, where we start parsing." Therefore it is of no help (unlike the case where you start reading at the right), and therefore there is no LR-grammar for this language. Neither with the c nor ...

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 Once we have a parsing table, we can parse (or reject) any sentence without any reference to the grammar. So at that point, the fact that the grammar was or was not augmented is essentially moot. (It would be meaningful if there were a user semantic action attached to the augmented start symbol's sole production, but that seems impossible, since the ... 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 \ whereS$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 ...

1

The grammar is really ambiguous. $\textbf{ if } expr \textbf{ then if }expr \textbf{ then } stmt \textbf{ else } stmt$ has two possible parses with that grammar. (The $\textbf{ else }$ can attach to either $\textbf{ if }$.) As you say, determinism and ambiguity are orthogonal. Certainly, there are unambiguous grammars which are not LR. But no ...

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

This grammar (which isn't ambiguous) isn't LR(k) due to the right-recursion, thus it isn't LR(1).

1

You question is very strangely stated. The answer is however very trivial. Your language $L$ is a regular language, hence recognizable by a DFA. It does not even need a pushdown stack. Hence it has to be LR(k). Indeed, the lookahead is necessary only to make the recognition deterministic, but in this case, it is deterministic to start with if you use the DFA ...

1

As shown here, minimizing the states in an LR(1) parser is NP-hard. The basic idea is that given an arbitrary graph, you can construct a grammar such that for every node in the original graph, the LR(1) parser contains a corresponding state in its state graph, and two states can be merged if and only if there is no edge between them in the original graph. ...

1

The following paper uses DFA minimisation for a minimal LR(1) parser: https://www.researchgate.net/publication/258746690_An_LR_parser_with_less_states

1

The point of generating a parser (usually) is to parse: "Analyse (a string or text) into logical syntactic components" (some online dictionary). That's different from simply recognizing that a text is a member of a language. A given language has a variety of grammars which will recognize its sentences, but typically there is a specific grammar which defines ...

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