LinuxQuestions.org - Yacc/bison:conflicts: 1 shift/reduce problem

- Programming (https://www.linuxquestions.org/questions/programming-9/)

- - Yacc/bison:conflicts: 1 shift/reduce problem (https://www.linuxquestions.org/questions/programming-9/yacc-bison-conflicts-1-shift-reduce-problem-4175436694/)

Yacc/bison:conflicts: 1 shift/reduce problem

Its has something to do with the arg_list I know that but I dont know how to fix it. I just keep getting conflicts: 1 shift/reduce. Any help would be great.

Code:

%{

#include "l8t3.h"

%}



%union

{

double dval;

char *sval;

struct ast_node *astNode;

};



%token <sval> FUNC

%token <sval> CONDITON

%token <dval> NUMBER

%token <sval> SYMBOL

%token <sval> TYPE

%token LPAREN RPAREN EOL QUIT LET COND



%type <astNode> s_expr

%type <astNode> let_section

%type <astNode> let_list

%type <astNode> list_item

%type <astNode> condition

%type <astNode> s_expr_list

%type <astNode> arg_list

%type <astNode> symbol

%%



program:/* empty */ { 

printf("> ");

}

| program s_expr EOL {

eval($2);

freeNode($2);

printf("\n> "); 

}

;

s_expr:

NUMBER{ 

$$ = number($1); 

}

|symbol{

$$ = $1;

}

|LPAREN SYMBOL s_expr_list RPAREN{

$$ = myFunc($2,$3);

}

|LPAREN COND condition s_expr s_expr RPAREN {

$$ = conditionExpr($3,$4,$5);

}

|LPAREN let_section s_expr RPAREN {

$$ = letSection($2,$3);

}

|LPAREN FUNC s_expr s_expr RPAREN {

$$ = function($2, $3, $4);

}

|QUIT { 

//printf("QUIT\n"); 

exit(0);

}



| error { 

printf("error#1\n"); 

//printf("> ");

}



;

symbol:

SYMBOL{

$$ = symbol($1);

}



arg_list:

symbol arg_list {

$$ = argList($1,$2);

}

|symbol{

$$ = argList($1,0);

}

;

let_section:

LPAREN LET let_list RPAREN {

$$ = $3;

}

;



let_list:

list_item let_list {

$$ = letList($1, $2);

}

|list_item {

$$ = letList($1,0);

}



;

list_item:

LPAREN TYPE SYMBOL s_expr RPAREN {

$$ = letElement($2,$3,$4,0);

}

|LPAREN SYMBOL s_expr RPAREN{

$$ = letElement(0,$2,$3,0);

}

|LPAREN SYMBOL LPAREN arg_list RPAREN s_expr RPAREN{

$$ = letElement(0,$2,$6,$4);

}

;

s_expr_list:



s_expr s_expr_list {

$$ = exprList($1,$2);

}

|s_expr{

$$ = exprList($1,0);

}

;

condition:

LPAREN CONDITON s_expr s_expr RPAREN {

$$ = condition($2,$3,$4);

}

;

%%

Hi.

To figure out what rule causes the conflict, add the `-rall' option to bison:

Code:

$ bison -rall  gram.y 

gram.y: conflicts: 1 shift/reduce

After that there should be file gram.output. Here is the relevant portion of it:

Code:

State 44 conflicts: 1 shift/reduce



....

state 5



  11 symbol: SYMBOL .



    $default  reduce using rule 11 (symbol)

....

state 44



    3 s_expr: . NUMBER

    4      | . symbol

    5      | . LPAREN SYMBOL s_expr_list RPAREN

    5      | LPAREN SYMBOL . s_expr_list RPAREN

    6      | . LPAREN COND condition s_expr s_expr RPAREN

    7      | . LPAREN let_section s_expr RPAREN

    8      | . LPAREN FUNC s_expr s_expr RPAREN

    9      | . QUIT

  10      | . error

  11 symbol: . SYMBOL

  11      | SYMBOL .  [SYMBOL, RPAREN]

  20 s_expr_list: . s_expr s_expr_list

  21            | . s_expr



    error  shift, and go to state 3

    NUMBER  shift, and go to state 4

    SYMBOL  shift, and go to state 5

    LPAREN  shift, and go to state 6

    QUIT    shift, and go to state 7



    SYMBOL  [reduce using rule 11 (symbol)]

    RPAREN  reduce using rule 11 (symbol)



    s_expr      go to state 17

    symbol      go to state 9

    s_expr_list  go to state 18

....

The syntax of this file is outlined here.

If I interpret it correctly, the conflict here is when there is SYMBOL on top of the stack and another SYMBOL in input stream. Parser can not decide whether to shift SYMBOL to the stack and then interpret it as `symbol' or to reduce SYMBOL on the stack to `symbol' (and keep input stream untouched).

I can't suggest any fix yet, but at least using this method you may analyze further conflicts. Anyway, your grammar looks overcomplicated to me. It looks like you try to impose too much structure on a quite structureless s-expressions, which is hard to do unambiguously (when parsing). Another approach would be to construct an abstract syntax tree of the s-expression using simple parser and then evaluate/analyze it using a dedicated recursive function.

Finally, I'd recommend to replace right recursion by left recursion, for example

Code:

arg_list: arg_list symbol { $$ = argList($1,$2); }

|symbol{ $$ = argList($1,0); }

;

This way parser can process arbitrarily long sequences using bounded stack space.

Thanks you for the info. You are right the symbol SYMBOL thing is the problem. I and my entire class have been working on this for a few days and no one can figure it out. I think our professor set up the grammer wrong. I think I could do it but I would have to completely redo the whole project and I dint have enough time because its do tomorrow afternoon.

The -rall though thing was very useful to know thanks for telling me about that.