Stack Overflow
Stack Overflow

Questions tagged [lr1]

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.

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
1
2