Solved

shift reduce conflict. why??

Posted on 2008-11-02
10
790 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
  • 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 500 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
Netscaler Common Configuration How To guides

If you use NetScaler you will want to see these guides. The NetScaler How To Guides show administrators how to get NetScaler up and configured by providing instructions for common scenarios and some not so common ones.

 

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

VMware Disaster Recovery and Data Protection

In this expert guide, you’ll learn about the components of a Modern Data Center. You will use cases for the value-added capabilities of Veeam®, including combining backup and replication for VMware disaster recovery and using replication for data center migration.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Python Encoding Problem \u2013 4 114
wordcount challenge 11 121
Not needed 13 112
Problem to open Excel file 15 133
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
If you haven’t already, I encourage you to read the first article (http://www.experts-exchange.com/articles/18680/An-Introduction-to-R-Programming-and-R-Studio.html) in my series to gain a basic foundation of R and R Studio.  You will also find the …
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

770 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