Stack Overflow
Stack Overflow

Questions tagged [shift-reduce-conflict]

Shift Reduce is an LR parser paradigm. A shift/reduce conflict occurs when there is ambiguity in the grammar being parsed.

When parsing using an LALR parser a stack is maintained of the tokens that have been seen, then given what is on input and what is on the stack, either the next token is shifted onto the stack or a production is made and the necessary tokens are popped off the stack and reduced to the appropriate production. A shift reduce conflict occurs when given the tokens on the stack and given the input, both a shift and a reduce action should occur according to the grammar.

This ambiguity is often mitigated through the use of precedence instructions to the parser.

167 questions
23
votes
3 answers

Reforming the grammar to remove shift reduce conflict in if-then-else

How do I remove shift-reduce conflict for bison for the given grammar? selection-stmt -> if ( expression ) statement | if ( expression ) statement else statement A solution giving the modified grammar would be highly…
Aakash Anuj
  • 3,773
  • 7
  • 35
  • 47
15
votes
1 answer

Shift/reduce conflicts in bison

I'm new to Bison and I'm having trouble with shift/reduce conflicts... I'm trying to load from file to array data[]: struct _data { char name[50]; char surname[50]; int year; } data[1000]; Here is part of my bison code: %token ID NUM NL…
Zrinka
  • 163
  • 1
  • 1
  • 7
13
votes
3 answers

How to solve a shift/reduce conflict?

I'm using CUP to create a parser that I need for my thesis. I have a shift/reduce conflict in my grammar. I have this production rule: command ::= IDENTIFIER | IDENTIFIER LPAREN parlist RPAREN; and I have this warning: Warning : *** Shift/Reduce…
dierre
  • 7,140
  • 12
  • 75
  • 120
7
votes
5 answers

How to fix YACC shift/reduce conflicts from post-increment operator?

I'm writing a grammar in YACC (actually Bison), and I'm having a shift/reduce problem. It results from including the postfix increment and decrement operators. Here is a trimmed down version of the grammar: %token NUMBER ID INC DEC %left '+'…
Zifre
  • 26,504
  • 11
  • 85
  • 105
6
votes
4 answers

Issue resolving a shift-reduce conflict in my grammar

I'm trying to write a small parser with Irony. Unfortunately I get a "shift-reduce conflict". Grammars are not my strong point, and I only need to get this one small thingy done. Here's the reduced grammar that produces the error: ExpressionTerm :=…
Vilx-
  • 104,512
  • 87
  • 279
  • 422
6
votes
1 answer

Shift reduce and reduce reduce conflicts

I'm having a hard time wrapping my head around this and need some help understanding shift reduce and reduce reduce conflicts. I have a grammar which I can't seem to understand why it's problematic. I could attach the grammar, but I want to learn…
John Leidegren
  • 59,920
  • 20
  • 131
  • 152
6
votes
1 answer

Solving parsing conflicts in a tiny Lemon grammar

I'm trying to learn basics of the Lemon parser generator, but I stuck quickly. Here's a tiny grammar: %right PLUS_PLUS. %left DOT. program ::= expr. member_expr ::= expr DOT IDENTIFIER. lhs_expr ::= member_expr. expr ::= lhs_expr. expr ::=…
Dmitry Frank
  • 10,417
  • 10
  • 64
  • 114
6
votes
1 answer

Grammar spec resolving Shift/Reduce conflicts

I'm using Jison (Bison) to create a simple markup language. I'm clearly new to this, but slight variations are working very well. I just don't understand the source of the S/R conflict. It doesn't seem matter that 'Text' is returned by two lexer…
Jason Kleban
  • 20,024
  • 18
  • 75
  • 125
5
votes
4 answers

Why does this simple grammar have a shift/reduce conflict?

%token PLUS MINUS INT %left PLUS MINUS THIS WORKS: exp : exp PLUS exp; exp : exp MINUS exp; exp : INT; THIS HAS 2 SHIFT/REDUCE CONFLICTS: exp : exp binaryop exp; exp : INT; binaryop: PLUS | MINUS ; WHY?
MustafaM
  • 493
  • 1
  • 4
  • 14
4
votes
1 answer

How to solve SHIFT/REDUCE conflict - in parser generator

I need help to solve this one and explanation how to deal with this SHIFT/REDUCE CONFLICTS in future. I have some conflicts between few states in my cup file. Grammer look like this: I have conflicts between "(" [ActPars] ")" states. 1. Statement =…
Milan Bojovic
  • 199
  • 4
  • 10
4
votes
1 answer

How to solve LR(1) grammar ambiguity between ternary expressions (a ? b : c) and "maybe" expressions (a?)?

I have created a grammar, a stripped-down version of which is reproduced below: (0) exp1: ternary; (1) exp1: exp2; (2) ternary: exp2 "?" exp1 ":" exp1; (3) exp2: exp2 "+" exp3; (4) exp2: exp3; (5) exp3: maybe; (6) exp3: "1"; (7) maybe: exp3 "?"; I…
user541686
  • 205,094
  • 128
  • 528
  • 886
4
votes
4 answers

Bison shift-reduce conflict - Unable to resolve

The grammar is as follows: 1. program -> declaration-list 2. declaration-list -> declaration-list declaration | declaration 3. declaration -> var-declaration | fun-declaration 4. var-declaration -> type-specifier ID ; | type-specifier ID [ NUM ]…
Aakash Anuj
  • 3,773
  • 7
  • 35
  • 47
4
votes
2 answers

How to resolve a shift/reduce conflict forcing a shift or a reduce?

When there is a shift/reduce conflict in Yacc/Bison, is it possible to force the conflict to be solved exactly as you want? In other words: is it possible explicitly force it to prioritize the shift or the reduce? For what I have read, if you are…
dbarbosa
  • 2,969
  • 5
  • 25
  • 29
4
votes
2 answers

Using precedence in Bison for unary minus doesn't solve shift/reduce conflict

I'm devising a very simple grammar, where I use the unary minus operand. However, I get a shift/reduce conflict. In the Bison manual, and everywhere else I look, it says that I should define a new token and give it higher precedence than the binary…
gablin
  • 4,678
  • 6
  • 33
  • 47
3
votes
2 answers

Bison shift/reduce conflict in A ::= AA rule

I've written following bison grammar file: %left '+' '-' %left '*' '/' %token NUMBER %% expr : NUMBER | expr '+' expr | expr '-' expr | expr '*' expr | expr '/' expr | expr expr %prec '*' /* implicit multiplication */ ; Now bison reports…
UncleAli
  • 495
  • 1
  • 5
  • 13
1
2 3
…
11 12