我正在尝试制作一个 Cminus 编译器，并专门尝试为它创建一个 AST。
在我的 step3.fl 文件中
%option noyywrap
%{
/* Definitions and statements */
#include "step3.tab.h"
//extern YYSTYPE yylval;
YYSTYPE yylval;
%}
ID {letter}{letter}*
NUM {digit}{digit}*
letter [a-zA-Z]
digit [0-9]
%option noinput nounput
%option yylineno
%option noyywrap
%%
"if" { return T_IF; }
"else" { return T_ELSE; }
"int" { return T_INT; }
"return" { return T_RETURN; }
"void" { return T_VOID; }
"while" { return T_WHILE; }
"+" { return yytext[0]; }
"-" { return yytext[0]; }
"*" { return yytext[0]; }
"/" { return yytext[0]; }
">" { return T_GREAT; }
">=" { return T_GREATEQ; }
"<" { return T_SMALL; }
"<=" { return T_SMALLEQ; }
"==" { return T_COMPARE; }
"!=" { return T_NOTEQ; }
"=" { return yytext[0]; }
";" { return yytext[0]; }
"," { return yytext[0]; }
"(" { return yytext[0]; }
")" { return yytext[0]; }
"[" { return yytext[0]; }
"]" { return yytext[0]; }
"{" { return yytext[0]; }
"}" { return yytext[0]; }
{ID} { yylval.string=strdup(yytext); return T_ID; }
{NUM} { yylval.value=atoi((const char *)yytext); return T_NUM; }
%%
在我的 step3.y 文件中：
%{
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include "ast.h"
#include "symtable.h"
static int level=0;
static int offset=0;
static int goffset=0;
static int maxoffset=0;
extern int yylex();
extern int yyparse();
extern char *yytext;
extern FILE *yyin;
void yyerror(const char* s);
extern int yylineno;
%}
%start program
%union {
int value;
char *string;
struct ASTnode * node;
enum OPERATORS op;
}
%right "then" T_ELSE
%token T_IF T_ELSE T_INT T_RETURN T_VOID T_WHILE
T_GREAT T_GREATEQ T_SMALL T_SMALLEQ T_NOTEQ T_COMPARE
%token <value> T_NUM
%token <string> T_ID
%type <node> declaration-list declaration var-declaration fun-declaration params
%type <node> param-list param compound-stmt local-declarations statement-list statement expression-stmt
%type <node> selection-stmt iteration-stmt return-stmt expression
%type <node> var simple-expression additive-expression term factor
%type <node> call args arg-list
%type <op> relop addop mulop type-specifier
%%
program:
declaration-list {prog=$1;}
;
declaration-list:
declaration-list declaration { $1->left = $2; $$ = $1; }
| declaration { $$ = $1; }
;
declaration:
var-declaration { $$ = $1; }
| fun-declaration { $$ = $1; }
;
var-declaration:
type-specifier T_ID';'
{
/* search symbol table for ID
insert if not found, then add the pointer from
insertion into the ASTnode to have reference
to the symbol table entry */
if(Search($2,level,0))
{
fprintf(stderr,"\n\tThe name %s exists at level %d ",$2,level);
fprintf(stderr,"already in the symbol table\n");
fprintf(stderr,"\tDuplicate can.t be inserted(found in search)");
yyerror(" ");
exit(1);
}
$$=ASTCreateNode(VARDEC);
$$->name=$2;
/* we use the op to determine its type while printing*/
$$->op=$1;
$$->symbol=Insert($2,$1,0,level,1,offset,NULL);
$$->isType=$1;
offset += 1;
if(offset > maxoffset)
maxoffset = offset;
}
| type-specifier T_ID'['T_NUM']' ';'
{ /* search for symbol, if we find it error*/
if(Search($2,level,0))
{
fprintf(stderr,"\n\tThe name %s exists at level %d ",$2,level);
fprintf(stderr,"already in the symbol table\n");
fprintf(stderr,"\tDuplicate can.t be inserted(found in search)");
yyerror(" ");
exit(1);
}
$$=ASTCreateNode(VARDEC);
$$->name=$2;
/* we use the op to determine its type while printing*/
$$->op=$1;
/* value links to the NUM nod to store the dimension*/
$$->value=$4;
$$->symbol=Insert($2,$1,2,level,$4,offset,NULL);
$$->isType=$1;
offset += $4;
if (offset>maxoffset)
maxoffset = offset;
}
;
type-specifier: T_INT { $$ = INTDEC; }
| T_VOID { $$ = VOIDDEC; }
;
fun-declaration:
type-specifier T_ID '('
{ /*name already used, cant make new dec*/
if(Search($2,level,0))
{
yyerror($2);
yyerror("Name already used ");
exit(1);
}
Insert($2,$1,1,level,1,0,NULL);
goffset=offset;
offset=2;
if(offset>maxoffset)
maxoffset = offset;
}
params
{ /*need the formal params to compare later */
(Search($2,0,0))->fparms = $5;
}
')' compound-stmt
{
$$=ASTCreateNode(FUNCTIONDEC);
$$->name=$2;
/* we use the op to determine its type while printing*/
$$->op=$1;
/* s1 links to the params which can be void
or a paramList */
$$->s1=$5;
/* right links to the compund statement,
called a BLOCK in the enumerated type */
$$->right=$8;
/*get the symbtab entry we made earlier*/
$$->symbol=Search($2,0,0);
/*Remove symbols put in, in the function call*/
offset -=Delete(1);
level = 0;
$$->value=maxoffset;
//we change this in the symbol table because it is not used
//anywhere else for functions. We have access to this
//in calls, so we can use it to determine where the
//stack pointer is going to have to be
$$->symbol->mysize = maxoffset;
/*change the offset back to the global offset*/
offset=goffset;
maxoffset=0;
}
;
params: param-list
{ /* params found */
$$ = $1;
}
| T_VOID
{ /* no params */
$$ = NULL;
}
;
param-list:
param-list',' param
{ /* attach the param to the list */
$1->left=$3;
$$ = $1;
}
| param { $$ = $1; }
;
param:
type-specifier T_ID
{ /*dont want overlap between params and vars*/
if(Search($2,level,0))
{
yyerror($2);
yyerror("\tDuplicate can.t be inserted(found in search)");
exit(1);
}
$$ = ASTCreateNode(PARAM);
$$->name=$2;
/* we use the op to determine its type while printing*/
$$->op=$1;
/* if value is 0 it is not an array, used for printing */
$$->value=0;
/*inherit the type*/
$$->isType=$1;
$$->symbol=Insert($2,$1,0,level+1,1,offset,NULL);
offset+=1;
if(offset>maxoffset)
maxoffset = offset;
}
| type-specifier T_ID'['']'
{
if(Search($2,level,0))
{
yyerror($2);
yyerror("\tDuplicate can.t be inserted(found in search)");
exit(1);
}
$$ = ASTCreateNode(PARAM);
$$->name=$2;
/* we use the op to determine its type while printing*/
$$->op=$1;
/* there was an array param */
$$->value=1;
/*inherit the type*/
$$->isType=$1;
/*2 is used for IsAFunc to show its an array ref*/
$$->symbol=Insert($2,$1,2,level+1,1,offset,NULL);
offset+=1;
if(offset>maxoffset)
maxoffset = offset;
}
;
compound-stmt:
'{' { level++; } local-declarations statement-list '}'
{
$$=ASTCreateNode(BLOCK);
if($3 == NULL) /*dont add decls if null*/
$$->right=$4;
else {
/* add the stmtList to the end of the localDecls
and then make the link to the right of BLOCK
be the whole decls and stmtList*/
ASTattachleft($3,$4);
$$->right=$3;
}
/*delete the old symbols from this block so they can
be used in a different block later on*/
offset -=Delete(level);
level--;
}
;
local-declarations:
local-declarations var-declaration
{ /*check for null, if not attach it*/
if($1 != NULL){
$1->left=$2;
$$=$1;
}
else
$$=$2;
}
| { $$ = NULL; }
;
statement-list:
statement-list statement
{ /*check for null, if not attch it*/
if($1 != NULL) {
$1->left=$2;
$$=$1;
}
else
$$=$2;
}
| { $$ = NULL; }
;
statement:
expression-stmt
{ /*everything here is just the simplification to general stmt
to be put into a stmtList above */
$$ = $1;
}
| compound-stmt
{
$$ = $1;
}
| selection-stmt
{
$$ = $1;
}
| iteration-stmt
{
$$ = $1;
}
| return-stmt
{
$$ = $1;
}
;
expression-stmt:
expression ';'
{
$$=ASTCreateNode(EXPRSTMT);
$$->right=$1;
$$->isType=$1->isType;
}
| ';' { $$ = NULL; }
;
selection-stmt:
T_IF '('expression')' statement %prec "then"
{
$$ = ASTCreateNode(IFSTMT);
/* right is the expression to be evaluated*/
$$->right=$3;
/* s1 is link to statment (it can be a block)*/
$$->s1=$5;
}
| T_IF '('expression')' statement T_ELSE statement
{
$$ = ASTCreateNode(IFSTMT);
/* right is the expression to be evaluated*/
$$->right=$3;
/* s1 is link to statment (it can be a block)*/
$$->s1=$5;
/* s2 holds the link to the else statment (can be a block)*/
$$->s2=$7;
}
;
iteration-stmt:
T_WHILE '('expression')' statement
{
$$ = ASTCreateNode(ITERSTMT);
/* right holds expression to be evaluated*/
$$->right=$3;
/* s1 holds the stmt to execute, can be block*/
$$->s1=$5;
}
;
return-stmt:
T_RETURN ';' {$$ = ASTCreateNode(RETURNSTMT);}
| T_RETURN expression';'
{
$$ = ASTCreateNode(RETURNSTMT);
/*expression to return*/
$$->s2=$2;
}
;
expression:
var '=' expression
{
/*we dont have to check both for void because if only one
is void there will be a type mismatch, otherwise they are
the same. So if one is void the other is also*/
if (($1->isType != $3->isType) || ($1->isType == VOIDDEC))
{
yyerror("Type mismatch or void in Assignment");
exit(1);
}
$$=ASTCreateNode(ASSIGN);
/* hold the link to the var node*/
$$->right=$1;
/* hold the link to the expression statement*/
$$->s1=$3;
/*inherit the type, already check for equivalence
so can just use $1*/
$$->isType=$1->isType;
$$->name=CreateTemp();
$$->symbol=Insert($$->name,$$->isType,0,level,1,offset,NULL);
offset+=1;
if(offset>maxoffset)
maxoffset = offset;
}
| simple-expression {$$ = $1;}
;
var:
T_ID
{
struct SymbTab * p;
if ((p=Search($1,level,1)) != NULL)
{
$$ = ASTCreateNode(IDENT);
$$->name=$1;
$$->symbol=p;
/*give the node op Type, based on SymbTab*/
$$->isType=p->Type;
if (p->IsAFunc == 2)
{
yyerror($1);
yyerror("Variable is an array, syntax error");
}
}
else
{
yyerror($1);
yyerror("undeclared variable used");
exit(1);
}
}
| T_ID '['expression']'
{
struct SymbTab * p;
if ((p=Search($1,level,1)) != NULL)
{
$$ = ASTCreateNode(IDENT);
$$->name=$1;
/* hold expression inside of array reference */
$$->right=$3;
$$->symbol=p;
/*capital Type is enum op*/
$$->isType=p->Type;
if (p->IsAFunc != 2)
{
yyerror($1);
yyerror("Variable is not an array, syntax error");
}
}
else
{
yyerror($1);
yyerror("undeclared variable used");
exit(1);
}
}
;
simple-expression:
additive-expression relop additive-expression
{ /* must ensure it is left recursive, to work properly */
/*we dont have to check both for void because if only one
is void there will be a type mismatch, otherwise they are
the same. So if one is void the other is also*/
if (($1->isType != $3->isType) || ($1->isType == VOIDDEC))
{
yyerror("Type mismatch or void in simpleExpression");
exit(1);
}
$$ = ASTCreateNode(EXPR);
$$->op=$2;
$$->left=$1;
$$->right=$3;
/*inherit the type, already check for equivalence
so can just use $1*/
$$->isType=$1->isType;
$$->name=CreateTemp();
$$->symbol=Insert($$->name,$$->isType,0,level,1,offset,NULL);
offset+=1;
if(offset>maxoffset)
maxoffset = offset;
}
| additive-expression {$$ = $1;}
;
relop:
T_SMALLEQ { $$=LESSTHANEQUAL; }
| T_SMALL { $$=LESSTHAN; }
| T_GREAT { $$=GREATERTHAN; }
| T_GREATEQ { $$=GREATERTHANEQUAL; }
| T_COMPARE { $$=EQUAL; }
| T_NOTEQ { $$=NOTEQUAL; }
;
additive-expression:
additive-expression addop term
{ /* must ensure it is left recursive, to work properly */
/*we dont have to check both for void because if only one
is void there will be a type mismatch, otherwise they are
the same. So if one is void the other is also*/
if (($1->isType != $3->isType) || ($1->isType == VOIDDEC))
{
yyerror("Type mismatch or void in additive exp");
exit(1);
}
$$ = ASTCreateNode(EXPR);
$$->op=$2;
$$->left=$1;
$$->right=$3;
/*inherit the type, already check for equivalence
so can just use $1*/
$$->isType=$1->isType;
$$->name=CreateTemp();
$$->symbol=Insert($$->name,$$->isType,0,level,1,offset,NULL);
offset+=1;
if(offset>maxoffset)
maxoffset = offset;
}
| term {$$ = $1;}
;
addop:
'+' { $$ = PLUS; }
| '-' { $$ = MINUS; }
;
term:
term mulop factor
{ /* must ensure it is left recursive, to work properly */
/*we dont have to check both for void because if only one
is void there will be a type mismatch, otherwise they are
the same. So if one is void the other is also*/
if (($1->isType != $3->isType) || ($1->isType == VOIDDEC))
{
yyerror("Type mismatch or void in term/factor exp");
exit(1);
}
$$ = ASTCreateNode(EXPR);
$$->op=$2;
$$->left=$1;
$$->right=$3;
/*inherit the type, already check for equivalence
so can just use $1*/
$$->isType=$1->isType;
$$->name=CreateTemp();
$$->symbol=Insert($$->name,$$->isType,0,level,1,offset,NULL);
offset+=1;
if(offset>maxoffset)
maxoffset = offset;
}
| factor {$$ = $1;}
;
mulop:
'*' { $$ = TIMES; }
| '/' { $$ = DIVIDE; }
;
factor:
'('expression')' {$$ = $2;}
| var { $$ = $1; }
| call { $$ = $1; }
| T_NUM
{
$$=ASTCreateNode(NUMBER);
$$->value=$1;
/*numbers are always ints here*/
$$->isType=INTDEC;
}
;
call:
T_ID '('args')'
{
struct SymbTab * p;
if ((p=Search($1,0,1)) != NULL)
{ /*make sure symbol is a function*/
if(p->IsAFunc != 1)
{
yyerror($1);
yyerror("Is a variable, but was called as function");
exit(1);
}
/*have to make sure we are calling with right params*/
$$=ASTCreateNode(CALLSTMT);
/* hold the link to args in right*/
$$->right=$3;
$$->name=$1;
$$->symbol=p;
$$->isType=p->Type;
}
else
{
yyerror($1);
yyerror("Function not defined in symbol table");
exit(1);
}
}
;
args:
arg-list { $$ = $1; }
| { $$ = NULL; }
;
arg-list:
arg-list',' expression
{ /*attach the expressions to the tree in order
the use of the argList is handled above */
$$=ASTCreateNode(ARGLIST);
$$->left=$3;
$$->right=$1;
}
| expression
{
$$=ASTCreateNode(ARGLIST);
$$->right=$1;
}
;
%%
int main(int argc, char *argv[]) {
if (argc == 2)
yyin = fopen(argv[1], "r");
else {
printf("No files - Exit\n");
exit(1);
}
Display();
yyparse();
ASTprint(0, prog);
return 0;
}
void yyerror(const char* s) {
//fprintf(stderr, "%s-:%d %s\n", filename, yylineno, s);
fprintf (stderr,"%s On Line: %d\n", s, yylineno);
}
在我的 ast.h 文件中
#ifndef ASTH
#define ASTH
#include <stdio.h>
#include <malloc.h>
/* define the enumerated types for the AST. THis is used to tell us what
sort of production rule we came across */
/* this is a partial list of NODE types for the ASTNode */
enum ASTtype {
PROGRAM,
VARDEC,
ARGLIST,
IDENT,
BLOCK,
NUMBER,
ASSIGN,
EXPRSTMT,
FUNCTIONDEC,
CALLSTMT,
EXPR,
IFSTMT,
ITERSTMT,
RETURNSTMT,
PARAM,
STRINGNODE
};
enum OPERATORS {
PLUS,
MINUS,
TIMES,
DIVIDE,
LESSTHANEQUAL,
LESSTHAN,
GREATERTHAN,
GREATERTHANEQUAL,
EQUAL,
NOTEQUAL,
INTDEC,
VOIDDEC,
STRINGDEC,
null
};
/* define a type AST node which will hold pointers to AST structs that will
allow us to represent the parsed code
*/
struct ASTnode
{
enum ASTtype type;
enum OPERATORS op;
enum OPERATORS isType;
char * name;
char * str;
int value;
struct SymbTab * symbol;
struct ASTnode *left,*right; /* left is usually the connector for statements */
struct ASTnode *s1,*s2 ; /* used for holding IF and WHILE components -- not very descriptive */
};
struct ASTnode *prog;
//prototypes
struct ASTnode *ASTCreateNode(enum ASTtype mytype);
void ASTattachleft(struct ASTnode *p, struct ASTnode *q);
void ASTprint(int level, struct ASTnode *p);
#endif /* of ASTH */
当我尝试使用这些命令进行编译时：
bison -d step3.y
flex step3.fl
gcc step3.tab.c lex.yy.c -lfl -o a.out
它给了我以下错误：
In file included from step3.fl:15:0:
step3.y:39:17: error: field ‘op’ has incomplete type
enum OPERATORS op;
我在整个互联网上都查看了，找不到可能的解决方法。谁能帮我解决这个问题？
提前致谢。