?
Solved

shift reduce conflict. why??

Posted on 2008-11-02
10
Medium Priority
?
845 Views
Last Modified: 2013-11-18
I really don't know why it generates 24 shift/reduce conflict, I am assuming it's because of the TOK_MINUS as when I removed it, it's gone.. can someone please point me out how I can fix this? .. I already use prec %UNARY

I am also pretty sure it's because of the TOK_MINUS, It shouldn't have any problem as I have already use the predence option.. but why is it still showing that shift reduce error?
%{
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "ast.h"
#include "symbolTable.h"
#include "util.h"
 
/* other external function prototypes */
extern int yylex();
extern int initLex(int ,  char **);
 
   
/* external global variables */
 
extern int              yydebug;
extern int              lineno;
extern SymbolTableStackEntryPtr symbolStackTop;
extern int scopeDepth;
int fun_line; //function declaration line number
int cmpd_line; //Compound Statement line number
 
/* function prototypes */
void    yyerror(const char *);
 
/* global variables */
 
AstNodePtr  program;
FILE *outfile;
 
/* Additional Function Prototypes */
 
AstNodePtr new_FunctionNode(ElementPtr e,int line);
AstNodePtr new_FormalvarNode(ElementPtr e,int line);
 
ElementPtr lookAndInsert(char *name,Type* type,int line,int gscope);
 
%}
 
/* YYSTYPE */
%union
{
    AstNodePtr nodePtr;
    int        iVal;
    char      *cVal;
    Type      *type;
}
 
 
 
/* terminals */
 
%token TOK_ELSE TOK_IF TOK_RETURN TOK_VOID TOK_INT TOK_CHART TOK_WHILE TOK_FOR
%token TOK_PLUS TOK_MINUS TOK_NOT TOK_MULT TOK_DIV TOK_LT TOK_LE TOK_GT TOK_GE TOK_EQ TOK_NE TOK_ASSIGN TOK_OR TOK_AND TOK_SEMI TOK_COMMA
%token TOK_LPAREN TOK_RPAREN TOK_LSQ TOK_RSQ TOK_LBRACE TOK_RBRACE TOK_ERROR
%token <cVal> TOK_ID
%token <iVal> TOK_NUM
%token <iVal> TOK_CHAR
%token <iVal> TOK_STRING
 
%type <nodePtr> Declarations Functions
%type <type> Type_Specifier
%type <nodePtr> Compound_Stmt Statements Statement
%type <nodePtr> Expr_Statement If_Else_Statement Selection_Stmt Iteration_Stmt Return_Stmt
%type <nodePtr> Expression Assignment Factor Var Call
%type <nodePtr> Args Args_List
%type <nodePtr> Fun_Declaration Params Param_List Param
 
%left TOK_OR
%left TOK_AND
%left TOK_EQ TOK_NE
%left TOK_LT TOK_LE TOK_GT TOK_GE
%left TOK_PLUS TOK_MINUS
%left TOK_MULT TOK_DIV
%right UNARY
 
%nonassoc TOK_IF
%nonassoc TOK_ELSE
 
%%
 
 
Start   : Declarations {/*printSymbolTable();*/}
;
 
Declarations : Functions { program = $1;}
             | Var_Declaration Declarations {}
;
 
Functions    : Fun_Declaration {$$=$1;}
             | Fun_Declaration Functions {$$->sibling = $2;}
;
 
Var_Declaration : Type_Specifier TOK_ID TOK_SEMI
                  {
                        ElementPtr e=NULL;
                        if((e=lookAndInsert($2,$1,lineno,scopeDepth))==NULL)
                                yyerror("Duplicate Symbol!");
                  }
 
                | Type_Specifier TOK_ID TOK_LSQ TOK_NUM TOK_RSQ TOK_SEMI
                  {     ElementPtr e=NULL;
                        $1->kind=ARRAY;
                        $1->dimension = $4;
                        if((e=lookAndInsert($2,$1,lineno,scopeDepth))==NULL)
                                yyerror("Duplicate Symbol!");
                  }
;
 
 
Fun_Declaration : Type_Specifier TOK_ID TOK_LPAREN {enterScope();} Params TOK_RPAREN {fun_line=lineno;} Compound_Stmt  
{
        leaveScope(); /* This leaves the scope of the params */
        ElementPtr e=NULL;
        if((e=lookAndInsert($2,new_type(FUNCTION),fun_line,scopeDepth))==NULL)
                yyerror("Duplicate Symbol!");
        if(e!=NULL){
                e->stype->function = $1;
               
                //create AST for this function declaration
                $$ = new_FunctionNode(e,lineno);
                $$->children[0]=$5;
                $$->children[1]=$8;
                $$->nType=$1;
               
                e->snode = $$;
                $$->sibling = NULL;
               
        }
}
		| TOK_VOID TOK_ID TOK_LPAREN {enterScope();} Params TOK_RPAREN {fun_line=lineno;} Compound_Stmt  
{
        leaveScope(); /* This leaves the scope of the params */
        ElementPtr e=NULL;
        if((e=lookAndInsert($2,new_type(FUNCTION),fun_line,scopeDepth))==NULL)
                yyerror("Duplicate Symbol!");
        if(e!=NULL){
                e->stype->function = VOID;
               
                //create AST for this function declaration
                $$ = new_FunctionNode(e,lineno);
                $$->children[0]=$5;
                $$->children[1]=$8;
                $$->nType= VOID;
               
                e->snode = $$;
                $$->sibling = NULL;
               
        }
}
;
 
Params : Param_List {$$=$1;}
       | TOK_VOID {$$ = NULL;}
;
 
Param_List : Param TOK_COMMA Param_List
             {      
                     $$->sibling=$3;
             }
            | Param { $$=$1;}
;
 
Param : Type_Specifier TOK_ID  { ElementPtr e=NULL;
                                 if((e=lookAndInsert($2,$1,lineno,scopeDepth))==NULL)
                                        yyerror("Duplicate Parameter!");
                                 if(e){
                                        $$ = new_FormalvarNode(e,lineno);
                                        $$->nType=$1;
                                        e->snode = $$;
                                 }
                                }
      | Type_Specifier TOK_ID TOK_LSQ TOK_RSQ   { ElementPtr e=NULL;
                                                  $1->kind = ARRAY;
                                                  if((e=lookAndInsert($2,$1,lineno,scopeDepth))==NULL)
                                                        yyerror("Duplicate Array Parameter!");
                                                  if(e){
                                                        $$ = new_FormalvarNode(e,lineno);
                                                        $$->nType=$1;
                                                        e->snode = $$;
                                                  }
                                                }      
;
Type_Specifier : TOK_INT {$$=new_type(INT);}
		 | TOK_CHART {$$=new_type(CHAR);}
;
 
Compound_Stmt : TOK_LBRACE {cmpd_line=lineno; enterScope();} Statements TOK_RBRACE
                {      
                        $$=new_StmtNode(COMPOUND_STMT,cmpd_line);
                        $$->children[0]=$3; //statements are the first child of compound stmt
                        $$->nInfo.nSymbolTabPtr = symbolStackTop->symbolTablePtr;
                        leaveScope(); /*This pops the scope of this block */
                }
              | TOK_LBRACE {cmpd_line=lineno; enterScope();} Local_Declarations Statements TOK_RBRACE
                {
                        $$=new_StmtNode(COMPOUND_STMT,cmpd_line);
                        $$->children[0]=$4;
                        $$->nInfo.nSymbolTabPtr = symbolStackTop->symbolTablePtr;
                        leaveScope(); //This pops the scope of this block
                }
;
 
Local_Declarations : Var_Declaration Local_Declarations {}
                   | Var_Declaration {}
;
 
Statements : Statement Statements
             {  
                $$->sibling = $2;
             }
           | {$$=NULL;}
;
 
Statement : Expr_Statement  {$$=$1;}
          | Call TOK_SEMI {$$=$1;}
          | Selection_Stmt {$$=$1;}
          | Iteration_Stmt {$$=$1;}
          | Return_Stmt {$$=$1;}
;
 
Expr_Statement : Assignment TOK_SEMI
                {
                        $$=new_StmtNode(EXPRESSION_STMT,lineno);
                        $$->children[0]=$1;
                }
               | TOK_SEMI {$$=new_StmtNode(EXPRESSION_STMT,lineno); $$->children[0]=NULL;}
;
 
 
Selection_Stmt : If_Else_Statement %prec TOK_IF {$$=$1;}
               | If_Else_Statement TOK_ELSE Statement {$1->children[2]=$3; $$=$1;}
;
 
If_Else_Statement : TOK_IF TOK_LPAREN Expression TOK_RPAREN Statement
                    {
                        $$=new_StmtNode(IF_THEN_ELSE_STMT,lineno);
                        $$->children[0] = $3;
                        $$->children[1] = $5;
                    }
;
 
Iteration_Stmt : TOK_WHILE TOK_LPAREN Expression TOK_RPAREN Statement
                 {
                        $$=new_StmtNode(WHILE_STMT,lineno);
                        $$->children[0]=$3;
                        $$->children[1]=$5;
                 }
		 | TOK_FOR TOK_LPAREN Expression TOK_RPAREN Statement
		   {
			  $$=new_StmtNode(FOR_STMT, lineno);
			  $$->children[0]=$3;
                       $$->children[1]=$5;
		   }
;
 
 
Return_Stmt : TOK_RETURN Expression TOK_SEMI
              {
                        $$=new_StmtNode(RETURN_STMT,lineno);
                        $$->children[0]=$2;
              }
            | TOK_RETURN TOK_SEMI
              {
                        $$=new_StmtNode(RETURN_STMT,lineno);
                        $$->children[0]=NULL;
              }
;
 
Assignment : Var TOK_ASSIGN Expression  
             {
                        $$=new_ExprNode(ASSI_EXP,lineno);
                        $$->children[0]=$1;
                        $$->children[1]=$3;
             }
;
 
Var : TOK_ID
      {
                $$=new_ExprNode(VAR_EXP,lineno);
                ElementPtr e;
                if((e=symLookup($1))==NULL){
                        yyerror("Undefined Variable.");
                }
                if(e)
                  $$->nInfo.nSymbolPtr=e;
      }
    | TOK_ID TOK_LSQ Expression TOK_RSQ
      {
          $$=new_ExprNode(ARRAY_EXP,lineno);
          ElementPtr e;
          if((e=symLookup($1))==NULL){
              yyerror("Undefined Array Variable.");
          }
          if(e)
             $$->nInfo.nSymbolPtr=e;
          $$->children[0]=$3;
      }
;
 
Expression : 	    | Expression TOK_OR Expression
			{$$=new_ExprNode(OR_EXP,lineno); $$->children[0]=$1; $$->children[1]=$3;}
       	    | Expression TOK_AND Expression
			{$$=new_ExprNode(AND_EXP,lineno); $$->children[0]=$1; $$->children[1]=$3;} 
		    | Expression TOK_GT Expression
                    {$$=new_ExprNode(GT_EXP,lineno); $$->children[0]=$1; $$->children[1]= $3;}
                  | Expression TOK_LT Expression
                    {$$=new_ExprNode(LT_EXP,lineno); $$->children[0]=$1; $$->children[1]= $3;}
                  | Expression TOK_GE Expression
                    {$$=new_ExprNode(GE_EXP,lineno); $$->children[0]=$1; $$->children[1]= $3;}
                  | Expression TOK_LE Expression
                    {$$=new_ExprNode(LE_EXP,lineno); $$->children[0]=$1; $$->children[1]= $3;}
                  | Expression TOK_EQ Expression
                    {$$=new_ExprNode(EQ_EXP,lineno); $$->children[0]=$1; $$->children[1]= $3;}
                  | Expression TOK_NE Expression
                    {$$=new_ExprNode(NE_EXP,lineno); $$->children[0]=$1; $$->children[1]= $3;}
		    | Expression TOK_PLUS Expression
                      {$$=new_ExprNode(ADD_EXP,lineno); $$->children[0]=$1; $$->children[1]=$3;}
	           | Expression TOK_MINUS Expression
                      {$$=new_ExprNode(SUB_EXP,lineno); $$->children[0]=$1; $$->children[1]=$3;}
                  | Expression TOK_MULT Expression  
       		 {$$=new_ExprNode(MULT_EXP,lineno); $$->children[0]=$1; $$->children[1]=$3;}
     		    | Expression TOK_DIV Expression
        	        {$$=new_ExprNode(DIV_EXP,lineno); $$->children[0]=$1; $$->children[1]=$3;}
                  | Factor
                    {$$ = $1;}
;
 
Factor : TOK_LPAREN Expression TOK_RPAREN {$$=$2;}
	| Var {$$=$1;}
       | Call {$$=$1;}
       | TOK_NUM 
		{$$=new_ExprNode(CONST_EXP,lineno); $$->nInfo.nValue=$1;}
	| TOK_CHAR 
		{$$=new_ExprNode(CONST_EXP,lineno); $$->nInfo.nValue=$1;}
	| TOK_STRING 
		{$$=new_ExprNode(CONST_EXP,lineno); $$->nInfo.nValue=$1;}
	| TOK_MINUS Expression %prec UNARY
		{$$ = $2;}  
	| TOK_NOT Expression %prec UNARY 
		{$$ = $2;}	
	    
	
;
 
Call : TOK_ID TOK_LPAREN Args TOK_RPAREN
        {$$=new_ExprNode(CALL_EXP,lineno); $$->function_name=strdup($1);$$->children[0]=$3;}
;
 
Args : Args_List
        { $$= $1;}
     | {$$=NULL;}
;
 
Args_List :  Args_List TOK_COMMA  Expression
           {
                $$->sibling = $3;
           }
          | Expression {$$=$1;}
;
 
%%
void yyerror (char const *s) {
       fprintf (stderr, "Line %d: %s\n", lineno, s);
}
 
int main(int argc, char **argv){
 
        initLex(argc,argv);
        initSymbolTable();
 
#ifdef YYLLEXER
   while (gettok() !=0) ; //gettok returns 0 on EOF
    return;
#else
    yyparse();
 
    printf("Type Checking the program ...");
    if(typecheck())
        printf("Type Checking Succeeded.\n");
    else
        printf("Type Checking Failed!\n");
 
    //print_Ast();
    outfile = fopen("a.out.s", "w");
 
    codegen();
 
#endif
   
}
 
/* Additional functions */
 
AstNodePtr new_FunctionNode(ElementPtr e,int line)
{
        AstNodePtr f_node =  (AstNodePtr)(malloc(sizeof(AstNode)));
        f_node->nKind = METHOD;
 
        f_node->nInfo.nSymbolPtr = e;
        f_node->nLinenumber = line;
 
        return f_node;
}
 
AstNodePtr new_FormalvarNode(ElementPtr e,int line)
{
        AstNodePtr f_node =  (AstNodePtr)(malloc(sizeof(AstNode)));
        f_node->nKind = FORMALVAR;
        f_node->sibling = NULL;
 
        f_node->nInfo.nSymbolPtr = e;
        f_node->nType = new_type(FUNCTION);
        f_node->nLinenumber = line;
 
        return f_node;
}
 
ElementPtr lookAndInsert(char* name,Type* type,int line,int gscope)
{
        ElementPtr e;
        if((e=symLookup(name))==NULL)
        {
                e=symInsert(name,type,line);
        }
        else
        {
                if(gscope!=e->scope)
                        e=symInsert(name,type,line);
                else
                        return NULL;
        }
        return e;
}

Open in new window

0
Comment
Question by:kuntilanak
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 6
  • 4
10 Comments
 
LVL 53

Expert Comment

by:Infinity08
ID: 22865463
What are the reported shift/reduce conflicts ? Can you post the complete y.output file ?
0
 

Author Comment

by:kuntilanak
ID: 22867285
here it is
y.output.txt
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 2000 total points
ID: 22867484
Try this :
//<SNIP>
 
Factor : TOK_LPAREN Expression TOK_RPAREN
           {$$=$2;}
       | Var
           {$$=$1;}
       | Call
           {$$=$1;}
       | TOK_NUM
           {$$=new_ExprNode(CONST_EXP,lineno); $$->nInfo.nValue=$1;}
       | TOK_CHAR
           {$$=new_ExprNode(CONST_EXP,lineno); $$->nInfo.nValue=$1;}
       | TOK_STRING
           {$$=new_ExprNode(CONST_EXP,lineno); $$->nInfo.nValue=$1;}
       | TOK_MINUS Factor %prec UNARY            // <--- Factor instead of Expression
           {$$ = $2;}
       | TOK_NOT Factor %prec UNARY            // <--- Factor instead of Expression
           {$$ = $2;}
 
//<SNIP>

Open in new window

0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:kuntilanak
ID: 22867515
wouldn't that change the grammar? then I can't have:

!(5>2)
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22867535
You could have that in yours too, since Factor is a valid Expression :


Expression :
 
//<SNIP>
 
           | Factor
               {$$ = $1;}
           ;

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22867543
And you still can, because :

Factor : TOK_LPAREN Expression TOK_RPAREN
           {$$=$2;}
 
//<SNIP>

Open in new window

0
 

Author Comment

by:kuntilanak
ID: 22867666
hmm..and why is there one rule that is never reduced
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22867771
What is the new y.output you get after the modification I suggested ?
0
 

Author Comment

by:kuntilanak
ID: 22869096
here's the new one which is still the same:
y.output.txt
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22880577
>> which is still the same:

That's not true. That specific shift/reduce conflict involving the Expression rule has been resolved by the modification. The other TOK_MINUS shift/reduce conflicts have to be resolved in a similar fashion.
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
When we want to run, execute or repeat a statement multiple times, a loop is necessary. This article covers the two types of loops in Python: the while loop and the for loop.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
In a recent question (https://www.experts-exchange.com/questions/29004105/Run-AutoHotkey-script-directly-from-Notepad.html) here at Experts Exchange, a member asked how to run an AutoHotkey script (.AHK) directly from Notepad++ (aka NPP). This video…
Suggested Courses

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question