LR parsers are a type of bottom-up parsers that efficiently handle deterministic context-free languages in guaranteed linear time. The name LR is often followed by a numeric qualifier, as in LR(1). An LR(1) parser can handle many but not all common grammars.
Questions tagged [lr1]
29 questions
7
votes
2 answers
LR1 Parser and Epsilon
I'm trying to understand how LR1 Parsers work but I came up with a strange problem: What if the grammar contains Epsilons? For instance: if I have the grammar:
S -> A
A -> a A | B
B -> a
It's clear how to start:
S -> .A
A -> .a A
A -> .B
... and…
Chris
- 9,209
- 16
- 58
- 74
6
votes
1 answer
LR(1) parsing table with epsilon productions
I'm having trouble building the collection of sets of items for LR(1) parsers with a grammar containing epsilon productions. For example, given the following grammar (where eps stands for epsilon)
S -> a S U
U -> b
| eps
State0 would be
S' ->…
Astinog
- 1,151
- 3
- 12
- 35
2
votes
1 answer
LR(1) item sets for left recursive grammar
I read several papers about creating LR(1) item sets, but none of them pertained to left recursive grammars, such as those used for parsing expressions. If I had the following grammar,
E -> E + T | T
T -> T * F | F
F -> (E) | NUMBER
How would I go…
ishaangupte
- 248
- 2
- 11
2
votes
1 answer
Is QML Grammar LALR(1)?
Here is a QML grammar (extracted from https://github.com/kropp/intellij-qml/blob/master/grammars/qml.bnf):
/* identifier, value, integer and float are terminals */
qml ::= object /* Simplified */
object ::= type body
body ::= '{'…
Swordow
- 35
- 6
2
votes
1 answer
How do I translate LR(1) Parse into a Abstract syntax tree?
I have coded a table driven LR(1) parser and it is working very well however I am having a bit of a disconnect on the stage of turing a parse into a syntax tree/abstract syntax tree. This is a project that I m very passionate about but I have really…
Devin Wall
- 180
- 1
- 16
2
votes
2 answers
LR(1) grammar: how to tell? examples for/against?
I'm currently having a look at GNU Bison to parse program code (or actually to extend a program that uses Bison for doing that). I understand that Bison can only (or: best) handle LR(1) grammars, i.e. a special form of context-free grammars; and I…
navige
- 2,447
- 3
- 27
- 53
1
vote
1 answer
Adding rule to Treesitter LR1 grammar changes precedence
I am trying to get operator precedence correct in a Treesitter grammar. Treesitter is a LR1 parser generator.
I have a straightforward artithmetic grammar, which partially looks like this:
multiply_expression: $ => prec.left(2, seq(
…
Sjoerd
- 74,049
- 16
- 131
- 175
1
vote
1 answer
Show that an LR(1) grammar that is not LALR(1) must have only reduce/reduce conflicts
Can someone please explain to me why an LR(1) grammar that is not LALR(1) must have only reduce/reduce conflicts
django
- 43
- 6
1
vote
1 answer
LR(1) Parser: Why adding an epsilon production makes r/r or s/r conflicts
I wanted to make a reader which reads configuration files similar to INI files for mswin.
It is for exercise to teach myself using a lexer/parser generator which I made.
The grammar is:
%lexer
HEADER ::= "\\[[0-9a-zA-Z]+\\]"
TRUE ::=…
Felix.leg
- 622
- 1
- 4
- 13
1
vote
1 answer
Computing the FIRST & FOLLOW sets of a grammar
I have the following grammar:
S -> aXab
S -> Y
X -> bYa
X -> epsilon
Y -> Sc
I have computed the first and follow sets for this grammar and I would like to know if it is correct. Here is my solution:
First Sets:
S -> {a}
X -> {b,epsilon}
Y ->…
nz881
- 73
- 2
- 9
1
vote
1 answer
Can a grammar ever be parsed by LL(1) but not with LR(1)?
For homework, I was given the following grammar:
S: D
D: AbBb | BaAb
A: ε
B: ε
I computed it using LL(1) just fine. The first sets were:
S: a, b
D: a,b
A: ε
B: ε
The follow sets were:
S: $
D: $
A: b
B: a,b
When I made my parsing table, the…
Ryan Foster
- 103
- 9
1
vote
1 answer
LR(1) Shift/Reduce Disambiguation
Given input with repeating BLOCKs, where each block has repeating BEGIN EVENT and END EVENT entries (END EVENT always follows a BEGIN EVENT):
[TIMESTAMP] BLOCK
[TIMESTAMP] BEGIN EVENT
[TIMESTAMP] END EVENT
[TIMESTAMP] BEGIN EVENT
[TIMESTAMP] END…
Alec Thilenius
- 524
- 5
- 12
1
vote
0 answers
Given a grammar, generate the LR(1) items
I am working on LR(1) items and I am having a bit of doubt and hoping someone can clarify for me. Given the following grammar, I must generate the LR(1) items. I generated the first item but am unsure if its correct, so before I continue, I want to…
user655321
- 143
- 4
- 18
1
vote
1 answer
This parser generator says that this grammar isn't LR(1) but I have my doubts
I've written a parser generator in Java, after a few bumps (an early version didn't particularly like left recursion for example), I managed to make it work with some simple grammars (so i can verify by hand the productions are correct)
I tried…
Crysis85
- 345
- 3
- 17
1
vote
2 answers
Where can I find a _simple_, easy to understand implementation of an LR(1) parser generator?
Where can I find a simple (as much as possible, but no simpler!) implementation of an LR(1) parser generator?
I'm not looking for performance, just the ability to generate the LR(1) states (item sets).
C++, C#, Java, and Python would all work for…
user541686
- 205,094
- 128
- 528
- 886