Solved

shift reduce conflict. why??

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

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
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
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

Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

Join & Write a Comment

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
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 …
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

746 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now