Hot answers tagged

8 votes
Accepted

Are LR(k) languages and DCFLs equivalent?

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 ...
Yuval Filmus's user avatar
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 \...
rici's user avatar
  • 11.9k
5 votes
Accepted

can every LR(k) grammer be transformed to LR(1)

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 ...
rici's user avatar
  • 11.9k
4 votes

What is handle in bottom up LR parsing?

"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 ...
rici's user avatar
  • 11.9k
4 votes
Accepted

Item lookaheads versus dot lookaheads for $LR(k)$ with $k \gt 1$?

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: ...
AProgrammer's user avatar
  • 3,024
4 votes
Accepted

How much bigger can an LR(1) automaton for a language be than the corresponding LR(0) automaton?

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 ...
AProgrammer's user avatar
  • 3,024
4 votes

When will SLR(1) parser fail but CLR(1) will not

No, the authors meant that there is no right-sentential form of the grammar that starts with R =. That is, the = in that ...
rici's user avatar
  • 11.9k
4 votes

Is LR(1) closed under union?

A simple example is $$L_1 = \{a^i b^i c^j \mid i,j\ge 0\}$$ $$L_2 = \{a^i b^j c^j \mid i,j\ge 0\}$$ Clearly, both languages are $LR(1)$. (Indeed, they are $LL(1)$.) But their union is inherently ...
rici's user avatar
  • 11.9k
3 votes

DCFL with prefix property have LR(0) grammar?

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 ...
Thinh D. Nguyen's user avatar
3 votes
Accepted

Need for an augmented grammar

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, ...
Ran G.'s user avatar
  • 20.6k
2 votes
Accepted

Is $\{a^nb^n\}\cup\{a^nb^{2n}\}$ LR(k)?

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." ...
Peter Leupold's user avatar
2 votes
Accepted

Is THEADS the same as FIRST?

I recently had the same question in mind when reading Pager's work. I found the paper The Edge-Pushing LR(k) Algorithm by Chen and Pager, which seems to say that the two terms are indeed the same. ...
Perry's user avatar
  • 137
2 votes
Accepted

How to remove empty strings a.k.a (lambda, epsilon) from a LR(0) grammar

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 &...
Anton Trunov's user avatar
  • 3,469
2 votes
Accepted

An intuitive explanation for LR grammars?

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 ...
vonbrand's user avatar
  • 13.9k
2 votes

Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),LALR(1) ) same?

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 ...
rici's user avatar
  • 11.9k
2 votes
Accepted

Merging states in LALR parser

No, you can't do that. The definition of LALR parsers is that it has combined(union of lookaheads) states having the same cores but different lookaheads. So what would happen if you were to combine ...
Rinkesh P's user avatar
  • 1,018
2 votes
Accepted

How does LALR(1) parser behave compared to LR(1) paser?

The explanation is given in the following paragraphs. Given a correct input, the LALR parser produces exactly the same sequence of reduce and shift actions as would an LR parser for the same grammar. ...
rici's user avatar
  • 11.9k
2 votes
Accepted

What are cases where we cannot perform LR parsing without augmented grammar?

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 ...
rici's user avatar
  • 11.9k
2 votes
Accepted

How is the lookahead for an LR(1) automaton computed?

$\text{FIRST}(\beta)$ is the set of possible first tokens in a derivation from β. (It's usual to also add ε to the first set if β could derive the empty sequence.) So $\text{FIRST}(\mathbf{+}\mathit{T}...
rici's user avatar
  • 11.9k
2 votes
Accepted

Is following grammar LR(0)?

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 ...
rici's user avatar
  • 11.9k
2 votes

Equivalence of LR(k) and LL(k′) parsers

Yes, $\{a^i b^j c \mid i \ge j \ge 0\}$ can be parsed by a $LR(0)$ parser but not by any $LL(k')$ parser for any $k'$. See How does $LL(n)$ languages compare with $LR(0)$, for $n>0$?. See also ...
D.W.'s user avatar
  • 156k
1 vote

How to disambiguate CFG with unary/binary minus and binary prefix operator

I'm going to limit myself, at least for now, to the question actually asked here: how to deal with the ambiguity between an operator which could be prefix or infix (such as unary negation) and a ...
rici's user avatar
  • 11.9k
1 vote

Edit distance into a DCFL

It would appear the language edit distance problem for the class of deterministic context-free languages requires cubic time. In Language Edit Distance Approximation via Amnesic Dynamic Programming (...
Jonas Kölker's user avatar
1 vote
Accepted

Analysis of a LALR shift-reduce conflict

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 ...
rici's user avatar
  • 11.9k
1 vote

What is the time complexity of SLR and LALR parsers?

They all run linear time with regards to input length ($O(n)$). The different algorithms have different memory trade offs for making it easier to write grammar for. That is not all grammars that work ...
clinux's user avatar
  • 237
1 vote
Accepted

Reduce-reduce conflict in SLR vs LALR

Note: I'm assuming that when you wrote $SLR$ and $LALR$ that you actually meant $SLR(1)$ and $LALR(1)$. It is certainly the case that if a grammar shows a conflict in an $LALR(1)$ automaton, that ...
rici's user avatar
  • 11.9k
1 vote
Accepted

Why can't a LR(0) parser have GOTO and Reduce Items in the same canonical set?

This isn't what you asked, but let me start by saying that I suspect the answer they're looking for in the question you link is (D), "A LR(0) parser can parse any regular grammar". That ...
rici's user avatar
  • 11.9k
1 vote
Accepted

How to create a LR(k) grammar for an arbitrary k

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 ...
rici's user avatar
  • 11.9k
1 vote
Accepted

Wikipedia says this grammar is LR(0), but Grammophone says it is not; is it?

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 ...
rici's user avatar
  • 11.9k
1 vote

LR parsers and ambiguous and non deterministic grammars

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 ...
rici's user avatar
  • 11.9k

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