CODEWITHSUNDEEP
yacc
Gello
Gello

Reputation: 35

How to fix yacc: "2 shift/reduce conflicts" error?

I started to programming a few days ago in yacc / flex and i don't know why I can't do recursive call only in line 31 (s: SKIP { System.out.println("txt: "+$1); } s). The recursive call enables me to keep on digit free text without using parenthesis.. What I'm doing wrong?

%{
  import java.io.*;
%}

%token OPEN_PAREN;
%token CLOSE_PAREN;
%token <sval> SKIP;

%start s

%%

parens  : OPEN_PAREN s CLOSE_PAREN
        | OPEN_PAREN CLOSE_PAREN

exp     : parens

exps    : exp SKIP { System.out.println("S: "+$2); }
        | exp

s       : SKIP { System.out.println("txt: "+$1); } s
        | exps
        | s exps

%%

void yyerror(String s)
{
 System.out.println("err:"+s);
 System.out.println("   :"+yylval.sval);
}

static Yylex lexer;
int yylex()
{
 try {
  return lexer.yylex();
 }
 catch (IOException e) {
  System.err.println("IO error :"+e);
  return -1;
 }
}

public static void main(String args[])
{
 System.out.println("[Quit with CTRL-D]");
 Parser par = new Parser();
 lexer = new Yylex(new InputStreamReader(System.in), par);
 par.yyparse();
}

Upvotes: 0

Views: 698

Answers (1)

rici
rici

Reputation: 241721

There is only one shift/reduce conflict in that excerpt, which is the result of the ambiguous recursiveness in s. Since it has nothing to do with the mid-rule action, it can be simplified to the following:

s: BEFORE s
 | AFTER
 | s AFTER

which is a grammar for BEFORE* AFTER+. (The fact that AFTER in your grammar is actually a non-terminal doesn't change anything either.)

This is ambiguous because the order of applying the first and last productions is not constrained by the grammar. Even in the simple input

BEFORE AFTER AFTER

there are two different parses:

      s                             s
   /     \                       /    \
  /       \                     /      \
BEFORE     s                   s      AFTER
  |      /   \               /   \      |
  |    AFTER   s         BEFORE   s     |
  |      |     |            |     |     |
BEFORE AFTER AFTER       BEFORE AFTER AFTER

Possibly it doesn't matter to you which of these parses is applied (although actually it does, because it affects the order of execution of the actions). But it matters to bison/yacc, which cannot know whether the order is unimportant or not.

To solve the conflict, we need to specify an order. There are two possibilities:

  1. Postfix before prefix. This is the usual order applied in programming languages, where postfix operators (like array subscripting) bind more tightly than prefix operators (like unary minus), so that -a[1] is the same as -(a[1]) rather than (-a)[1]. In that case the grammar would look like this:

    s: t
 | BEFORE s
t: AFTER
 | t AFTER

  2. Prefix before postfix. This has the advantage that actions in the prefix part are executed before actions in the postfix part. (But note that the right-recursiveness of t means that if its productions had actions, the actions would be executed right-to-left.)

    s: t
 | s AFTER
t: AFTER
 | BEFORE t

    A completely left-recursive implementation of this alternative:

    s: t AFTER
 | s AFTER
t: %empty
 | t BEFORE

Upvotes: 1

Related Questions