LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 11-11-2012, 04:23 PM   #1
bigfetz
LQ Newbie
 
Registered: Nov 2012
Posts: 3

Rep: Reputation: Disabled
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);
}
;
%%
 
Old 11-12-2012, 03:41 PM   #2
firstfire
Member
 
Registered: Mar 2006
Location: Ekaterinburg, Russia
Distribution: Debian, Ubuntu
Posts: 709

Rep: Reputation: 428Reputation: 428Reputation: 428Reputation: 428Reputation: 428
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.

Last edited by firstfire; 11-12-2012 at 03:43 PM.
 
Old 11-12-2012, 11:17 PM   #3
bigfetz
LQ Newbie
 
Registered: Nov 2012
Posts: 3

Original Poster
Rep: Reputation: Disabled
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.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
[SOLVED] how to instruct bison to show detail for a shift/reduce conflict famsinyi Programming 2 11-01-2009 09:37 AM
Resolving shift/reduce conflicts pragnya Programming 3 08-07-2006 08:54 AM
Newbie Yacc/Bison shift reduce question IncendiaryProgrammer Programming 5 07-02-2006 11:15 AM
Bison and Yacc Compatibility Problem oulevon Programming 1 10-23-2005 10:56 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 06:08 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration