LR(k) grammars are grammars that can be parsed bottom-up from the left-to-right, producing a rightmost derivation, using k tokens of lookahead. LR(k) parsers are among the most powerful deterministic parsers available, but are often too large to use in practice.
Questions tagged [lr-grammar]
178 questions
269
votes
4 answers
What is the difference between LL and LR parsing?
Can anyone give me a simple example of LL parsing versus LR parsing?
Creativity2345
- 2,721
- 3
- 15
- 3
110
votes
9 answers
What is the difference between LR, SLR, and LALR parsers?
What is the actual difference between LR, SLR, and LALR parsers? I know that SLR and LALR are types of LR parsers, but what is the actual difference as far as their parsing tables are concerned?
And how to show whether a grammar is LR, SLR, or LALR?…
Prasoon Saurav
- 91,295
- 49
- 239
- 345
91
votes
4 answers
What is the difference between LR(0) and SLR parsing?
I am working on my compilers concepts however I am a little confused...
Googling got me nowhere to a definite answer.
Is SLR and LR(0) parsers one and same? If not, whats the difference?
Nitish Upreti
- 6,312
- 9
- 50
- 92
80
votes
5 answers
How to identify whether a grammar is LL(1), LR(0) or SLR(1)?
How do you identify whether a grammar is LL(1), LR(0), or SLR(1)?
Can anyone please explain it using this example, or any other example?
X → Yz | a
Y → bZ | ε
Z → ε
Prashant Bhardwaj
- 1,203
- 2
- 18
- 26
61
votes
4 answers
Examples of LL(1), LR(1), LR(0), LALR(1) grammars?
Is there a good resource online with a collection of grammars for some of the major parsing algorithms (LL(1), LR(1), LR(0), LALR(1))? I've found many individual grammars that fall into these families, but I know of no good resource where someone…
templatetypedef
- 362,284
- 104
- 897
- 1,065
42
votes
3 answers
What is the difference between LALR and LR parsing?
I understand both LR and LALR are bottom-up parsing algorithms, but what's the difference between the two?
What's the difference between LR(0), LALR(1), and LR(1) parsing? How can I tell if a grammar is LR(0), LALR(1), or LR(1)?
AAB
- 1,594
- 2
- 25
- 40
38
votes
7 answers
What advantages do LL parsers have over LR parsers?
What advantages do LL parsers have over LR parsers to warrant their relative popularity in today's parser generator tools?
According to Wikipedia, LR parsing appears to have advantages over LL:
LR parsing can handle a larger range of languages than…
Adam Paynter
- 46,244
- 33
- 149
- 164
29
votes
2 answers
How do Java, C++, C#, etc. get around this particular syntactic ambiguity with < and >?
I used to think C++ was the "weird" one with all the ambiguities with < and >, but after trying to implement a parser I think I found an example which breaks just about every language that uses < and > for generic types:
f(g(j));
This could…
user541686
- 205,094
- 128
- 528
- 886
22
votes
4 answers
LR(1) Item DFA - Computing Lookaheads
I have trouble understanding how to compute the lookaheads for the LR(1)-items.
Lets say that I have this grammar:
S -> AB
A -> aAb | a
B -> d
A LR(1)-item is an LR(0) item with a lookahead. So we will get the following LR(0)-item for state 0:
S ->…
mrjasmin
- 1,230
- 6
- 21
- 37
21
votes
1 answer
Why are there LR(0) parsers but not LL(0) parsers?
I've been reading on both in Wikipedia, and noticed that although LR(0) parsers exist, there's no such thing as LL(0) parser.
From what I read, I understand that the k in LL(k)/LR(k) means how many characters the parser can see beyond the current…
Shmoopy
- 5,334
- 4
- 36
- 72
20
votes
1 answer
Example of an LR grammar that cannot be represented by LL?
All LL grammars are LR grammars, but not the other way around, but I still struggle to deal with the distinction. I'm curious about small examples, if any exist, of LR grammars which do not have an equivalent LL representation.
Puppy
- 144,682
- 38
- 256
- 465
16
votes
7 answers
Limitations of LL vs LR parsers?
I know the basic differences of LL vs LR parsers. I also know that GLR, SLR, and LALR are all extensions of LR parsers. So my question in more details is...
Given a LL(*) parser and any variation on a LR parser, is there any language that can be…
Andrew White
- 52,720
- 19
- 113
- 137
14
votes
1 answer
Why is this LR(1) grammar not LALR(1)?
This is not my homework, I'm trying to understand LALR(1) grammars. So I found this
S -> aEa | bEb | aFb | bFa
E -> e
F -> e
I wrote the LR items, but I can't figure out
why this is an LR(1) grammar and not LALR(1)?
Can anyone help me? Thank you
Jan Vorcak
- 19,261
- 14
- 54
- 90
13
votes
1 answer
Why can't a compiler have a "shift/shift" conflict?
I currently am studying about compilers and as I understand in LR(0) there are cases where we have "shift/reduce" or "reduce/reduce" conflicts, but it's impossible to have "shift/shift" conflicts! Why we can't have a "shift/shift" conflict?
user1888149
- 143
- 1
- 4
10
votes
1 answer
