Solved

shift reduce conflict. why??

Posted on 2008-11-02
10
829 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 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
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

Suggested Solutions

Title # Comments Views Activity
wordcount challenge 11 163
How To Loop - Python 19 102
Fill Null values 5 50
Setting variables in a stored procedure 5 74
How to remove superseded packages in windows w60 or w61 installation media (.wim) or online system to prevent unnecessary space. w60 means Windows Vista or Windows Server 2008. w61 means Windows 7 or Windows Server 2008 R2. There are various …
Having just graduated from college and entered the workforce, I don’t find myself always using the tools and programs I grew accustomed to over the past four years. However, there is one program I continually find myself reverting back to…R.   So …
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

733 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