The 2024 Developer Survey results are live! See the results

# Tag Info

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 ...
• 278k
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 ...
• 12.1k
Accepted

• 2,295
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." ...
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. ...
• 137

### 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 ...
• 12.1k
Accepted

• 12.1k

### 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 ...
• 163k
1 vote

### How to make LR(1) grammar for sequence that cannot have more "Up" than "Down" for any given prefix?

An earlier exercise in the same textbook asks you (in effect) to create a grammar for the balanced parenthesis language (disguised as a question about elevator motions) and then prove that your ...
• 12.1k
1 vote
Accepted

### Is there a language that has a LL(1) grammar but not LALR(1) grammar?

Every language which has an $LR(k)$ grammar for some $k$ has an $SLR(1)$ grammar (which is necessarily also $LALR(1)$ and $LR(1)$). The proof is constructive: from the $LR(k)$ grammar, you can ...
• 12.1k
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 ...
• 12.1k
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 (...
• 729
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 ...
• 247
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 ...
• 12.1k
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 ...
• 12.1k
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 ...
• 12.1k
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 ...
• 12.1k
1 vote
Accepted

• 12.1k
1 vote
Accepted

### Removing conflicts of LR(1) parsing tables

The ambiguity comes from I -> id because that rule means that both I ans E derive <...
• 12.1k
1 vote

### Can I mix LL and LR parsing?

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 ...
• 12.1k
1 vote

### Use DFA minimization on LR(1) states

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

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