Questions tagged [lr-k]
LR(k) is a common type of parser for context-free grammars
0
votes
1answer
19 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 ...
0
votes
1answer
8 views
An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if The LR(1) parser for G has S-R conflicts [on hold]
This is an interesting property, I have given the explanation below.
0
votes
0answers
29 views
Understanding handle, viable prefix and valid item in the context of LR(0) and LR(1) items
Dragon book gives definition of handle, viable prefix and valid item at various different places. I am trying to understand these definitions in each other's context. Various definitions given are as ...
1
vote
1answer
58 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→α.]$...
0
votes
1answer
110 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{...
1
vote
1answer
177 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 ...
1
vote
0answers
300 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 ...
1
vote
1answer
40 views
2
votes
1answer
203 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 ...
1
vote
0answers
144 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 ...
2
votes
0answers
136 views
6
votes
1answer
968 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.
...
3
votes
1answer
475 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}$ ...
0
votes
1answer
40 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?
3
votes
1answer
119 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 \...
1
vote
1answer
2k 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 ...
1
vote
0answers
143 views
Upper bound of automaton states for SLR parsing
How do I tell, given a specific grammar, which is the upper bound for the number of states of a LR(0) or LR(1) automaton for its SLR parsing?
My guess is that generating the canonical item collection ...
2
votes
0answers
230 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 -...
2
votes
0answers
24 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 ...
6
votes
0answers
62 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) parsing and ...
0
votes
1answer
388 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 ...
2
votes
1answer
55 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 ...
4
votes
1answer
132 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 ...
2
votes
1answer
162 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 ...
1
vote
0answers
23 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):...
0
votes
1answer
136 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 ...
4
votes
1answer
128 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, ...
10
votes
2answers
441 views
How much bigger can an LR(1) automaton for a language be than the corresponding LR(0) automaton?
In an LR(0) parser, each state consists of a collection of LR(0) items, which are productions annotated with a position. In an LR(1) parser, each state consists of a collection of LR(1) items, which ...
1
vote
1answer
294 views
Is this grammar LR(1)?
A bit confused about whether this grammar is ambiguous or not
C' -> C
C -> d C u C
C -> d C
C -> ε
I tried building the DFA for this but I get this ...
0
votes
1answer
141 views
How to create an LR($k$) grammar for a given language?
How can I construct an LR($k$) grammar (which $k$ is not really of interest for now) for a given language, say:
$$L=\left\{w \in \{a, b\}^\star \ | \ \exists u \in \{a, b\}, v \in \{a, b\}^\star: w = ...
12
votes
2answers
4k views
Is there any way to distinguish between LL(k) and LR(k) grammar?
I am recently studying about Compilers designing. I came to know about two types of grammar one is LL grammar and other is LR grammar.
We also know the facts that every LL grammar is LR that is LL ...
