Solved

yacc and C

Posted on 2008-10-13
20
702 Views
Last Modified: 2013-11-18
Ok, so first I want to do a type checking to my yacc code. The partial code I have is below:

What must I add to the code so that I can access $1.type? I already defined:

typedef struct Type{
int type;
} Type

%union{
int typ;
}

%type <typ> expr

However it still doesn't work


expr   : '-' expr %prec UNARY {$$ = -$2}

       | '!' expr %prec UNARY {$$ = !$2 }

       | expr '+' expr { 

	  if ($1.type != INTEGER || $3.type != INTEGER)

	  {

		fprintf(stderr, "Invalid type for addition, must be an integer\n");

	  }

	  else

	 	 $$.type = INTEGER;

	}

       | expr '-' expr {

	  if ($1.type != INTEGER || $3.type != INTEGER)

	  {

		fprintf(stderr, "Invalid type for substraction, must be an integer\n");

	  }

	  else

	 	 $$.type = INTEGER;

	}

       | expr '*' expr { 

	  if ($1.type != INTEGER || $3.type != INTEGER)

	  {

		fprintf(stderr, "Invalid type for multiplication, must be an integer\n");

	  }

	  else

	 	 $$.type = INTEGER;

	}

       | expr '/' expr { 

	  if ($1.type != INTEGER || $3.type != INTEGER)

	  {

		fprintf(stderr, "Invalid type for division, must be an integer\n");

	  }

	  else

	 	 $$.type = INTEGER;

	}

       | expr EQ expr 

       | expr NE expr

       | expr LE expr

       | expr '<' expr

       | expr GE expr

       | expr '>' expr

       | expr AND_OP expr

       | expr OR_OP expr

       | ID opt_idexpr

       | '(' expr ')'

	| '(' error {fprintf(stderr, "Missing expression after '(' \n");}

       | INTCON {

		  $1.type = INTEGER;

		  }

       | CHARCON {

		  $1.type = CHARMARK;

		  }

       | STRINGCON {

                $1.type = STRINGMARK;

		  } 

	

;

Open in new window

0
Comment
Question by:kuntilanak
  • 10
  • 10
20 Comments
 
LVL 53

Accepted Solution

by:
Infinity08 earned 500 total points
ID: 22709891
I think you meant something like :
typedef struct Type{

  int type;

} Type;
 

%union {

  Type typ;

}
 

%token <typ> expr
 
 
 

// and then for example in the scanner :
 

[0-9]+    { yylval.typ.type = INTEGER; return expr; }

Open in new window

0
 

Author Comment

by:kuntilanak
ID: 22711495
well, the weird thing is that when I do


it works.. can someone please explain to me in detail what the %union does? I tried to find lots of articles in the web but none happens to give me a clear explanation. As far as I know it is so that we can return other values besides just an integer, which is the default action of the yacc parser. Using the %union we can define other types that a nonterminal/terminal can return..
%union

{

   char* stringcon;

   char charcon;

   char *id;

   struct Type{

    int type;

   } typ 

}

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22711889
>> well, the weird thing is that when I do

Note that that's the same as what I suggested ;)


>> As far as I know it is so that we can return other values besides just an integer, which is the default action of the yacc parser. Using the %union we can define other types that a nonterminal/terminal can return..

That's exactly what it does :)

To re-define the type of yylval (the value set by the scanner), you can do :

        #define YYSTYPE char*

for example (to re-define it to a char* in this case). But that is quite limiting, since you always have to return a char* in that case.
To get around this limitation, you can also define a %union, which allows to have several different types for yylval depending on the token.


More info :

        http://www.faqs.org/docs/Linux-HOWTO/Lex-YACC-HOWTO.html#ss6.3
0
 

Author Comment

by:kuntilanak
ID: 22712869
ok I think I got it. When I specify

%  <type> expr

Does this mean that everything in the expr must return a expr??

When if I have :

expr : '-' expr {$$ = -$2}

It gives me an invalid return type. Why is this so??
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22715309
>> Does this mean that everything in the expr must return a expr??

It means that the yylvalue union for an expr token should be interpreted as a 'type'.


>> It gives me an invalid return type.

Always remember ah tyou are actually assigning ... unions ? structs ?
0
 

Author Comment

by:kuntilanak
ID: 22717069
ok here's part of my code, I hope you can help me to debug it somehow why the weird thing is happening:

My guess why:

expr   : '-' expr %prec UNARY {$$=$2;}

gives me an error is because expr is declared to return a type which is an int. Am I right?

I also defined :

#define INTEGER 1
#define CHARMARK 2
#define STRINGMARK 3
#define IDMARK 4
#define BOOLEAN 5

on top of the page.

Can you please guide me what I should do so I can do $$=-$2; properly, without giving a type error


%union

{

   char* stringcon;

   char charcon;

   char *id;

   struct Type{

    int type;

   } typ 

}
 
 

%type <typ> expr
 
 
 

expr   : '-' expr %prec UNARY {$$=$2;}

       | '!' expr %prec UNARY {$$=!$2;}

       | expr '+' expr { 

	  if ($1.type != INTEGER || $3.type != INTEGER)

	  {

		fprintf(stderr, "Invalid type for addition, must be an integer\n");

	  }

	  else

	 	 $$.type = INTEGER;

	}

       | expr '-' expr {

	  if ($1.type != INTEGER || $3.type != INTEGER)

	  {

		fprintf(stderr, "Invalid type for substraction, must be an integer\n");

	  }

	  else

	 	 $$.type = INTEGER;

	}

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22719922
>> gives me an error is because expr is declared to return a type which is an int. Am I right?

expr is declared to return a Type struct which contains an int.

You have to do it similarly as for expr '+' expr
0
 

Author Comment

by:kuntilanak
ID: 22721632
well I tried putting it for expr + expr, and here's what I got
parse.y:183: error: wrong type argument to unary minus

parse.y:184: error: wrong type argument to unary exclamation mark

parse.y:185: error: invalid operands to binary + (have âstruct Typeâ and âstruct Typeâ)

parse.y:193: error: invalid operands to binary - (have âstruct Typeâ and âstruct Typeâ)

parse.y:201: error: invalid operands to binary * (have âstruct Typeâ and âstruct Typeâ)

parse.y:209: error: invalid operands to binary / (have âstruct Typeâ and âstruct Typeâ)

parse.y:217: error: invalid operands to binary == (have âstruct Typeâ and âstruct Typeâ)

parse.y:225: error: invalid operands to binary != (have âstruct Typeâ and âstruct Typeâ)

parse.y:233: error: invalid operands to binary <= (have âstruct Typeâ and âstruct Typeâ)

parse.y:241: error: invalid operands to binary < (have âstruct Typeâ and âstruct Typeâ)

parse.y:249: error: invalid operands to binary >= (have âstruct Typeâ and âstruct Typeâ)

parse.y:257: error: invalid operands to binary > (have âstruct Typeâ and âstruct Typeâ)

parse.y:265: error: used struct type value where scalar is required

parse.y:273: error: used struct type value where scalar is required

Open in new window

0
 

Author Comment

by:kuntilanak
ID: 22722005
oh and for the info here's what I head for the type.

I am guessing that in the scanner I will need to assign the real value of an integer to int v, how do I do that?

I tried doing:

 yylval.typ.v = atoi(yytext);

but it doesn't work

typedef struct Data {

     int type;

     union {

        float f;

        char *str;

        int v;

     } d;

} Data;
 

%}
 

%union

{ 

   Data *typ;

   char* stringcon;

   char charcon;

   char *id;

}
 

%type <typ> expr

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22725544
>> parse.y:183: error: wrong type argument to unary minus

Well yes, that's because you're dealing with structs rather than integers as I said ;) You need to access the members of the struct just like you did for expr + expr.


>> I am guessing that in the scanner I will need to assign the real value of an integer to int v, how do I do that?

You defined yylval to be a Data* (pointer to a Data struct) in the case of an expr, so that's what yylval should be set to. You'll have to allocate memory for a struct somewhere (statically or dynamically), fill in the appropriate fields, and then pass its address to yylval.
0
What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

 

Author Comment

by:kuntilanak
ID: 22725653
oh and the code above generates an :

 y.tab.h:24: error: expected specifier-qualifier-list before âDataâ

I tried your suggestion on top of this page, still it doesn't work: I want to defined the typedef struct Data
inside the

%{


}%

so then I could make a separate file for it and then just include it
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22725801
>>  y.tab.h:24: error: expected specifier-qualifier-list before âDataâ

That means that you're trying to use the Data type before it has been defined.


>> I want to defined the typedef struct Data
>> inside the
>>
>> %{
>>
>>
>> }%
>>
>> so then I could make a separate file for it and then just include it

That's where it's supposed to be, yes, and placing it in a separate header file is certainly not a bad idea.
0
 

Author Comment

by:kuntilanak
ID: 22725842
well,. that's what I did and I don't know why it still gives me an error
typedef struct Type{

  int type;

  union {

    char* id;

    char *str;

    int val;

  } value;

} Type;
 

%} ==> notice this part here
 

%union

{ 

  Type typ;

}
 

%type <typ> expr

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22726324
>> it still gives me an error

What error ?


Didn't you mean %token instead of %type btw ?

Also, it's unnecessary to use %union if you're only specifying one type. You might as well use :

        #define YYSTYPE Type
0
 

Author Comment

by:kuntilanak
ID: 22726401
no I really mean %type, as I want the expr rule to return a typ, oh well.. anyway can we just move on and look at this code:

Based on your understanding looking at the code, what do you think these means:

  int level;                  /* static level */
  int offset;                 /* offset in block */
 int live;                   /* one if symbol is live */
  int live_on_exit;           /* one if symbol is live */
struct _icode *next_use;/* next use of symbol */
  int framesize;              /* size of a-record for function */
  struct _callgraph *callgraphnode;   /* Node in callgraph */


I have no idea on what callgraphnode is
struct _symbol {

  char id[MAXIDLENGTH];       /* identifier name */

  int type;                   /* INTEGER, REAL, BOOLEAN, NOTYPE */

  int class;                  /* VAR, FUNC, PAR, CONST, TEMP, UNDEF */

  int used;                   /* zero if not in scope */

  int level;                  /* static level */

  int offset;                 /* offset in block */

  int nrparms;                /* Number of parameters */

  int value;                  /* Value for integer constant */

  char *string;               /* Value for string constant */

  int live;                   /* one if symbol is live */

  int live_on_exit;           /* one if symbol is live */

  struct _icode *next_use;/* next use of symbol */

  int framesize;              /* size of a-record for function */

  struct _callgraph *callgraphnode;   /* Node in callgraph */

  struct _location *loc;      /* List of locations for symbol */

  struct _symbol *nextsym;    /* next symbol */

};
 

typedef struct _symbol *SYMBOL;
 

#define SNULL (SYMBOL) NULL
 

struct _expression {

  SYMBOL place;

  int type;           /* boolean or arithmetic */

};

Open in new window

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22728994
First of all, as I've said earlier : you need to first analyze what it is YOU need, rather than trying to understand what it was others needed. A parse tree implementation will generally be very specific to the application it's written for.


In any case :

>>   int level;                  /* static level */

The level is just the nesting level (for nested blocks)

>>   int offset;                 /* offset in block */

The offset seems to be related to the location of a symbol within a function definition (and thus also within the stack frame).

>>  int live;                   /* one if symbol is live */
>>   int live_on_exit;           /* one if symbol is live */

Pretty straightforward, no ? These just say whether the symbol is live or not.

>> struct _icode *next_use;/* next use of symbol */

Seems to be used for linking usages of the same symbol together for data flow analysis.

>>   int framesize;              /* size of a-record for function */

The size of the stack frame for the function.

>>   struct _callgraph *callgraphnode;   /* Node in callgraph */

A call graph is simply a graph of all functions and which functions call which functions. Used for call flow analysis.
0
 

Author Comment

by:kuntilanak
ID: 22731324
what is the call flow and data flow analysis used for? is it for the code generation step?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22738997
It is used for knowing the lifetime of data, and especially for optimization purposes. Generally, that happens before the code generation - the parse tree is modified and re-structured for optimal performance before it's translated into code.

I gather you are writing a compiler then ?
0
 

Author Comment

by:kuntilanak
ID: 22740956
yes, I am writing a compiler for a very simple grammar though..well not that simple I guess.. and really all I need to work on right now is type checking and building up syntax tree
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 22756647
>> well not that simple I guess..

Heh. As long as you realize that ;)
0

Featured Post

Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

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…
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.
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.

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

Need Help in Real-Time?

Connect with top rated Experts

8 Experts available now in Live!

Get 1:1 Help Now