Questions tagged [lr1]

LR parsers are a type of bottom-up parsers that can efficiently parse deterministic context-free languages in guaranteed linear time. The name LR is often followed by a numeric qualifier, as in LR(1), indicating the number of lookahead tokens needed by the parser. An LR(1) parser can handle many but not all common grammars.

lr1
Filter by
Sorted by
Tagged with
-1 votes
1 answer
163 views

Is this grammar LALR(1)?

I have the following grammar: S -> aSb S -> c It can be used for LR(1) parsers are there is no conflict. However, when I combine states with same LR(0) items and different lookaheads, I get a ...
Lobster3221's user avatar
1 vote
0 answers
76 views

Does Golang have LR(1) grammar?

Does Golang have LR(1) grammar? In other words, can any Golang code be parsed by LR(1) parser? If yes, can we get this grammar rules? The question is about the latest Go versions 1.20+ I have tried to ...
House MD's user avatar
2 votes
1 answer
501 views

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 | ...
ishaangupte's user avatar
1 vote
1 answer
127 views

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: ...
Sjoerd's user avatar
  • 74.9k
1 vote
1 answer
391 views

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's user avatar
  • 43
0 votes
1 answer
351 views

Why does this Grammar work in LALR(1) but not LR(1)

By all accounts, LR(1) should be more powerful in every way compared to LALR(1) since LR(1) builds a canonical collection of LR(1) items, and LALR(1) is just a better SLR(1) parser. Then why does this ...
Raiyyan Siddiqui's user avatar
1 vote
1 answer
259 views

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 ...
Felix.leg's user avatar
  • 739
2 votes
1 answer
316 views

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 */ ...
Swordow's user avatar
  • 35
1 vote
1 answer
279 views

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 ...
nz881's user avatar
  • 73
0 votes
0 answers
200 views

LR(1) parsing, problem with look ahead symbols

I understand the concept of LR(1) parsing and lookahead symbols. I have the solution to the exercise and it does not agree with my solution. I'm trying to fill the LR(1) parsing table for the grammar ...
Nikos 's user avatar
  • 23
0 votes
1 answer
236 views

LR(1) table construction confusion

I'm confused on how to parse this grammar using LR(1): S -> A A -> A(A) | empty I'm aware there is left recursion but I was told it isn't necessary to remove it for LR(1). My item sets look ...
Ryan Foster's user avatar
0 votes
1 answer
126 views

How to Parse a given LALR(1) Grammar

I'm having trouble parsing the following grammar using the LALR method. s -> y y -> dX | ydX X -> e | Zd z -> F | epsilon I'm ok at the beginning, here is item state 0: (the , seperates ...
Ryan Foster's user avatar
1 vote
1 answer
935 views

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: $ ...
Ryan Foster's user avatar
0 votes
1 answer
48 views

Which productions are considered in LR(1) lookahead?

I'm currently looking at two closure calculation examples using the tool at http://jsmachines.sourceforge.net/machines/lr1.html Example 1 S -> A c A -> b B B -> A b Here, in the initial ...
Brendan Rollinson's user avatar
1 vote
1 answer
385 views

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 ...
Alec Thilenius's user avatar
6 votes
1 answer
2k views

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 -...
Astinog's user avatar
  • 1,171
0 votes
0 answers
72 views

Bison : shift-reduce conflicts even though %left %right directive [duplicate]

I know that most of the shift/reduce conflicts can be solved by using %left or %right directives. But even with that, I am getting conflicts. Following is a block of my grammar: expression: ...
Chaitanya Patel's user avatar
-1 votes
1 answer
274 views

LR(1) items and LALR(1) Parsing table how to do this?

From the grammar given below create LR(1) items and merge the sets of items having give the set of LALR(1) items. I am not sure how to construct from this grammar B -> id | id ( B ) | B . id | B [ B ]...
dan123's user avatar
  • 1
0 votes
0 answers
103 views

LR(1) Automata: difference between items

I have a doubt regarding the LR(1) automata construction: Is the state with the kernel [A->b., x] (state_1) equivalent to the state with the kernel [A->b.,x/y] (state_2)? Like, if I'm on the state [...
Frank's user avatar
  • 241
1 vote
0 answers
260 views

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 ...
user655321's user avatar
1 vote
1 answer
113 views

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 ...
Crysis85's user avatar
  • 345
2 votes
1 answer
526 views

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 ...
Devin Wall's user avatar
0 votes
0 answers
724 views

How to create Lr(1) parser for very simple programming language

I need to create the parser for code with variables, simple conditions, cycles and functions, something like: f=1; i=1; while(i<10){ f=f*i; i=i+1; } print(f); I read a lot of theory, but I ...
Manunich's user avatar
0 votes
1 answer
667 views

How do I rewrite a context free grammar so that it is LR(1)?

For the given context free grammar: S -> G $ G -> PG | P P -> id : R R -> id R | epsilon How do I rewrite the grammar so that it is LR(1)? The current grammar has shift/reduce conflicts ...
rpgdude's user avatar
0 votes
0 answers
120 views

LR(1) - How to compute Lookaheads

I have trouble understanding how to compute the lookaheads. Lets say that I have this extend grammar: S'-> S S -> L=R | R L -> *R | i R -> L I wrote the State 0 so: S'-> .S, {$} S -&...
Pascal NoPascensor's user avatar
0 votes
1 answer
332 views

printing parse Tree as a dynamic list in c language

I have written a code in C to implement LR(1) parse table, however now I am facing a problem in printing the parse tree. How do we do that in C? The tree can have variable children and since the ...
noobLearner's user avatar
2 votes
2 answers
2k views

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. ...
navige's user avatar
  • 2,467
1 vote
2 answers
3k views

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)...
user541686's user avatar
  • 208k
0 votes
1 answer
98 views

what's the matter with this grammar

s : cmd | cmd SOMETHING cmd :WORD WORD and SOMETHING are non null terminals it's an LR1 grammar so bison should parse it without problems. however i faced an unexpected problem in runtime: ...
Amine Hajyoussef's user avatar
0 votes
1 answer
217 views

Dealing with infinite loops when constructing states for LR(1) parsing

I'm currently constructing LR(1) states from the following grammar. S->AS S->c A->aA A->b where A,S are nonterminals and a,b,c are terminals. This is the construction of I0 I0: S' ->...
Bruce's user avatar
  • 1
7 votes
2 answers
7k views

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'...
Chris's user avatar
  • 9,389