Questions tagged [lr-k]

LR(k) is a common type of parser for context-free grammars

Filter by
Sorted by
Tagged with
1 vote
0 answers
16 views

Number of DCFG parse tree nodes with respect to input length

I read the question and answer at Number of nodes of a parse tree when the Grammar is in CNF?, and I'm curious about a related matter: obviously with a unrestrained LR grammar (as opposed to CNF) the ...
Petr Skocik's user avatar
0 votes
0 answers
24 views

Any reference implementation of PCC algorithm out there?

Currently I'm exploring LALR(1) lookahead generation algorithms to implement. I've implemented Aho and Ullman one from their textbook, but recently stumbled upon "A new analysis of LALR ...
Sunfline's user avatar
1 vote
1 answer
41 views

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

Are there languages that can be parsed by an LR(k) parser but not by an LL(k′) parser for any k′?
Gator's user avatar
  • 11
0 votes
1 answer
59 views

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

I am working on a problem that asks me to write an LR(1) grammar that satisfies the following rules: Consider a robot arm that accepts two commands: $\triangledown$ puts an apple in the bag and $\...
Dean DeRosa's user avatar
1 vote
1 answer
254 views

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

I know that languages that have LL(1) grammar also will have LR(1) grammar as LL(1) grammar can be written only for a subset of DCFL whereas LR(1) grammar can be written for all DCFL, but I wanted to ...
Arun Madhav's user avatar
1 vote
1 answer
68 views

Is LR(1) closed under union?

Suppose I have two LR(1) languages $L_1$, $L_2$. Is $L_1 \cup L_2$ also LR(1)? References to proofs would be very helpful.
Jonathon's user avatar
2 votes
0 answers
50 views

Is LR(1) closed under concatenation?

Suppose I have two LR(1) languages $L_1$, $L_2$. Is $L_1 L_2$ (their concatenation) guaranteed to also be LR(1)? References to proofs would be very helpful.
Jonathon's user avatar
1 vote
2 answers
328 views

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

I'm designing an expression language that's trying to (a) be maximally compatible with a different ambiguous language; and (b) be LR(1). I'm facing the current fragment of the language: $$ \begin{...
Jonas Kölker's user avatar
-1 votes
1 answer
218 views

Argument for an $\epsilon$ free LL(1) grammar being in LR(0)?

I am trying to understand the reason as given in this answer If an ε-free grammar is not LR(0), then there is some state with both a shift and a reduce action. Since the grammar is ε-free, that state ...
user2277550's user avatar
1 vote
1 answer
29 views

Edit distance into a DCFL

I would like to generate helpful parser errors, telling the user how to fix their program. Specifically I have a deterministic context-free language $L$, given in the form of an $LR(1)$ grammar. I ...
Jonas Kölker's user avatar
1 vote
1 answer
2k views

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

I'm reading Douglas Thain's book called "Introduction to Compilers and Language Design" and I've come across the following grammar: , with the following LR(1) automaton: , and I am not ...
alexandrosangeli's user avatar
-1 votes
1 answer
325 views

What is the time complexity of SLR and LALR parsers?

What is the difference between time complexity of SLR(k) and SLR(1)? and also what about LALR(k) and LALR(1)? How can I calculate time complexity of parsers? I think time complexity of LR(k) is O(n) ...
Mahla Kazemzadeh's user avatar
0 votes
1 answer
132 views

find LR(1) items of the first state

I need to calculate the LR(1) items of the following grammar: S -> E E -> E + T E -> T T -> ID T -> ( E ) I can not even calculate the first group {[...
Mtuo's user avatar
  • 3
0 votes
1 answer
609 views

Reduce-reduce conflict in SLR vs LALR

I was wondering if I could say any of the following is true. Given a grammar $G$, If the LALR parser has reduce-reduce conflict for $G$, then the SLR parser also has reduce-reduce conflict for $G$. ...
Ramasamy Kandasamy's user avatar
3 votes
1 answer
461 views

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

I am talking in reference to this question from this compiler test. I think it is actually true that a GOTO and REDUCE can't be present in the same set, but am having a hard time coming up with an ...
 nietzsche's user avatar
0 votes
1 answer
266 views

Merging states in LALR parser

I was learning LALR parsers from the dragon book (Compilers: Principles, Techniques, and Tools by Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman) and I came across the example on page ...
Kiruphasankaran Nataraj's user avatar
2 votes
1 answer
461 views

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

In Section 4.7.4 of the book "Compilers: Principles, Techniques, and Tools" (2nd Edition), it reads: "The revised parser (LALR(1)) behaves essentially like the original (LR(1)), .... ...
hengxin's user avatar
  • 9,501
0 votes
1 answer
280 views

What to do following a reduce in LR(1) parsing?

I am using this standard question from Dragonbook as an example, (the first problem) . I have trouble with what happens in State 4 on LR(1) parsing. Once it is reduced by the rule C->d, now what ...
user2277550's user avatar
1 vote
0 answers
41 views

Is there a direct way to obtain the RE for the handle-finding DFA of a grammar?

LR parser for a (CFG) grammar uses a handle-find automaton (which is a DFA) to find the handles. Such automata can be constructed by computing the canonical collection of sets of LR(0)/LR(1) items. Is ...
hengxin's user avatar
  • 9,501
1 vote
1 answer
83 views

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

Many standard Compiler Design texts mention constructing augmented grammar as first step of LR parsing. The reason frequently is It is required in cases where start symbol comes on right hand of any ...
user83335's user avatar
0 votes
1 answer
26 views

Why shift means push terminal symbol and state into the stack? Why not push only state?

Shift means that you need to put the status and terminal symbol on the stack. But what is the terminal symbol used for? After all, if the reduce command is executed, both the state and the terminal ...
none9632's user avatar
0 votes
1 answer
41 views

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

Is there a simple procedure for constructing a grammar that is LR(k) but not LR(k-1) for any k?
Brandon Neth's user avatar
0 votes
1 answer
1k views

Is following grammar LR(0)?

I know how to verify whether grammar is LR(0) or not. But this particular case is little tricky and hence the question. Grammar: $SL \rightarrow SL ; S \space | \space \epsilon$ $S \...
Vimal Patel's user avatar
0 votes
1 answer
450 views

Analysis of a LALR shift-reduce conflict

I have created an extremely simple byacc grammar (ok, it's not really that simple but I simplified purposefully to be a minimal complete verifiable example): ...
juhist's user avatar
  • 283
0 votes
2 answers
638 views

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

I understand the difference in the parsing tables of the above 4 parsers. I understand that CLR>LALR>SLR>LR(0) in terms of power. Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),...
Surbhi Jain's user avatar
1 vote
1 answer
99 views

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

E -> E * B . E -> E + B . E -> B . B -> 0 . B -> 1 . I am confused because Wikipedia cites this grammar as an example of an LR(0) grammar ...
gaazkam's user avatar
  • 179
0 votes
1 answer
230 views

Is there a LL(K) Grammar which is not LALR(K) Grammar?

It is easy to know that there are LALR(K) grammars which are not LL(K) because any grammar with left recursion which is LALR(K), is not LL(K) because all LL(K) grammar must be left recursion free. And ...
user's user avatar
  • 215
2 votes
1 answer
2k views

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

Dragon book says following about where SLR(1) parser can fail but CLR(1) wont: Recall that in the SLR method, state $i$ calls for reduction by $A→α$ if the set of items $I_i$ contains item $[A→α.]$...
RajS's user avatar
  • 1,647
1 vote
1 answer
963 views

LR parsers and ambiguous and non deterministic grammars

Dragon book says: An ambiguous grammar can never be LR. And then immediately further it says: For example, consider the dangling-else grammar: $\begin{align} stmt \rightarrow & \textbf{...
RajS's user avatar
  • 1,647
4 votes
1 answer
2k views

What is handle in bottom up LR parsing?

I was taking course on compilers by Alex Aiken. You can find the slide discussing handles on this page. On the page of the slide, the instructor defines handle as follows: Assume a rightmost ...
RajS's user avatar
  • 1,647
1 vote
0 answers
1k views

Are LL(1) grammars a subset of LR(0) grammars?

As far as I've understood it seems that LL1 are a subset of LR0, but studying the following grammar I end up in a contraddiction. Grammar : S -> (S) | [S] | {S} | ε This is an LL1 while it seems ...
Zeno Raiser's user avatar
1 vote
1 answer
203 views

Removing conflicts of LR(1) parsing tables

...
wox's user avatar
  • 15
6 votes
1 answer
1k views

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

when i was studying compilers i came across this in Wikipedia every DCFL has a corresponding unambiguous grammar and hence can be parsed by an LR(1) parser which is the most powerful parser then what ...
venkat's user avatar
  • 189
1 vote
0 answers
262 views

Is the Java 8 Grammar still a LALR(1) grammar?

As I found out here: http://www.eclipse.org/jdt/core/howto/generate%20parser/generateParser.html , the Java Version of 2005 (might be Java 6, I'm not sure) is a LALR(1) grammar. However, I couldn't ...
Niklas Wünsche's user avatar
2 votes
0 answers
315 views

Intuitive Explanation on Converting BNF Grammar to LR(1)

Consider the following BNF Grammar G: ...
Grant Miller's user avatar
7 votes
2 answers
2k views

DCFL with prefix property have LR(0) grammar?

There are two important theorems about LR(k) grammars and DCFL. Mentioned here. A language has an LR(1) grammar iff it is DCFL. A language has an LR(0) grammar iff it is DCFL and has prefix property. ...
user3699192's user avatar
6 votes
1 answer
1k views

Are LR(k) languages and DCFLs equivalent?

In the familiar book of Theory of Computation by M. Sipser, the author proved that for endmarked context-free languages, the set of languages having a LR(k) grammar for a predefined $k \in \mathbb{N}$ ...
Vincent J. Ruan's user avatar
1 vote
1 answer
99 views

Can I mix LL and LR parsing?

I want to go RD parsing with Shunting Yard for expression (for the sake of easier operator precedences and less left-recusion), is that considered no-good because nobody did that before?
Steve Fan's user avatar
  • 121
3 votes
1 answer
161 views

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

I was reading Knuth's paper "On The Translation of Languages from Left to Right", my particular interest being on RL($k$) languages (not a typo). By the end of the paper, he puts the grammar: $$ S \...
paulotorrens's user avatar
2 votes
1 answer
3k views

Need for an augmented grammar

The question is under the concept of LR parser. Suppose the original grammar is S->AA A->aA|b Is it necessary to add an additional rule S'->S to make it as augmented grammar? In short, I want to ...
Sharanya's user avatar
2 votes
0 answers
434 views

How to find conflicts in LALR parser?

I have a LR analyser and I can't find out how to know whether the grammar is or is not LALR(1). I think that I have to merge states with the same rules. So I have to merge states: $2 - 12, 3 - 13, 4 -...
Milano's user avatar
  • 339
2 votes
0 answers
43 views

Determine if two LR(1) action/goto tables always produce the same derivation

I am experimenting with implementing minimal LR(1) algorithms/techniques, but I find it very difficult to verify the correctness of what I've implemented. Is there a fast algorithm to determine if ...
orlp's user avatar
  • 12.9k
7 votes
1 answer
113 views

Is THEADS the same as FIRST?

I'm reading the paper "A Practical General Method for Constructing LR(k) Parsers" by David Pager, and it contains the following paragraph: We will first of all briefly review the LR(1) ...
orlp's user avatar
  • 12.9k
1 vote
1 answer
1k views

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

Say I have the following grammar: E -> TE' E' -> +TE'| -TE' | λ T -> (E) | id I need to build the finite state machine with the LR(0) items, But I ...
Andres Zapata's user avatar
4 votes
1 answer
199 views

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

I was reading "Parsing Techniques: A Practical Guide, Second Edition" by Grune and Jacobs, which details a bunch of different parsing algorithms. In the section on $LR(2)$ parsing, they mention that ...
templatetypedef's user avatar
4 votes
1 answer
258 views

An intuitive explanation for LR grammars?

With LL grammars, there seems to be a very intuitive explanation, in terms of first and follow tables.( The first letter/s encountered in a particular state, can only mean a particular rule). With LR ...
user2277550's user avatar
2 votes
2 answers
334 views

Use DFA minimization on LR(1) states

I have recently started reading more about context-free parsing techniques, in particular LR parsing. As I have read, LR state transition graph (or table(s)) used for finding handles in sentential ...
Stipo's user avatar
  • 121
1 vote
0 answers
26 views

How equality of item (production state) is defined in LR parser?

Whenever I read about equality I took it for granted, but few days ago I wondered if my understanding is not too shallow. Consider such example (taken from: http://david.tribble.com/text/honalee.html):...
greenoldman's user avatar
0 votes
1 answer
240 views

Chomsky NF or Greibach NF benefits for LR parser?

Are there any benefits of having grammar in CNF/GNF for LR parser? I have those in mind: total speed of creating a parser (that is time for creating CNF/GNF out of the grammar, and then creating ...
greenoldman's user avatar
4 votes
1 answer
181 views

Are there automatic transformation of grammar algorithms?

From time to time you can write a grammar that creates shift/reduce conflict (for example) but after reading the grammar you notice that if you rewrite the productions the conflict will go away, ...
greenoldman's user avatar