From ccab148f1310b3cadffb99005941e39fa932d295 Mon Sep 17 00:00:00 2001 From: Teddy Date: Mon, 24 Mar 2014 12:40:12 +0800 Subject: AST construction for expressions --- Makefile | 12 +++- ast.h | 37 +++++++++++-- cibic.y | 187 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++------- 3 files changed, 209 insertions(+), 27 deletions(-) diff --git a/Makefile b/Makefile index b6eeb33..4cf057a 100644 --- a/Makefile +++ b/Makefile @@ -3,12 +3,18 @@ all: cibic run: ./cibic -cibic: lex.yy.c cibic.tab.c - gcc -o cibic lex.yy.c cibic.tab.c +cibic: lex.yy.o cibic.tab.o ast.o + gcc -o cibic lex.yy.o cibic.tab.o ast.o +lex.yy.o: lex.yy.c + gcc -c lex.yy.c +cibic.tab.o: cibic.tab.c + gcc -c cibic.tab.c +ast.o: ast.c + gcc -c ast.c -g lex.yy.c: cibic.l flex cibic.l cibic.tab.c: cibic.y bison -d cibic.y clean: - rm -f cibic lex.yy.c cibic.tab.c + rm -f cibic lex.yy.c cibic.tab.c *.o diff --git a/ast.h b/ast.h index f6db7da..d438b92 100644 --- a/ast.h +++ b/ast.h @@ -1,7 +1,17 @@ -typedef struct { +#ifndef AST_H +#define AST_H + +#define EXP_POSTFIX 1024 +#define POSTFIX_ARR 1025 +#define POSTFIX_CALL 1026 +#define POSTFIX_DOT 1027 +#define POSTFIX_PTR 1028 +#define EXP_CAST 1029 + +typedef struct CNode { enum { /* Top Level */ - PROG = 1024, FUNC_DEF, PARAMS, + PROG, FUNC_DEF, PARAMS, DECL, /* declaration */ DECLR, /* declarator */ DECLRS, @@ -18,11 +28,17 @@ typedef struct { CONT_STMT , BREAK_STMT, RET_STMT, /* 'continue', 'break', 'return' */ /* Expressions (expressions use their token ID to denote their types */ - EXP + EXP, + TYPE_NAME, + ID, /* identifier */ + INT, /* INT_CONST */ + CHAR, + STR } type; union { int intval; - char *strvar; + int subtype; + char *strval; } rec; struct CNode *chd, *next; /* For error reporting */ @@ -30,3 +46,16 @@ typedef struct { int row, col; } loc; } CNode; + +CNode *cnode_create_exp(int exp_type, int pnum, ...); +CNode *cnode_create_type_spec(int spec_type, int pnum, ...); +CNode *cnode_append(CNode *node, CNode *tail); +CNode *cnode_create_identifier(char *val); +CNode *cnode_create_int_const(int val); +CNode *cnode_create_char_const(int val); +CNode *cnode_create_str_const(char *val); +CNode *cnode_debug_print(CNode *ast); + +extern CNode *ast_root; + +#endif diff --git a/cibic.y b/cibic.y index a27c247..daeb35a 100644 --- a/cibic.y +++ b/cibic.y @@ -2,22 +2,170 @@ #include #include "ast.h" %} +%union { + int intval; + char *strval; + struct CNode *cnode; +} + %token IDENTIFIER INT_CONST CHAR_CONST STR_CONST %token KW_VOID KW_CHAR KW_INT KW_STRUCT KW_UNION KW_IF KW_ELSE KW_WHILE %token KW_FOR KW_CONT KW_BREAK KW_RET KW_SIZEOF %token OPT_OR OPT_AND OPT_EQ OPT_NE OPT_LE OPT_GE OPT_SHL OPT_SHR OPT_INC OPT_DEC OPT_PTR %token ASS_MUL ASS_DIV ASS_MOD ASS_ADD ASS_SUB ASS_SHL ASS_SHR ASS_AND ASS_XOR ASS_OR %token UNKNOWN -%union { - int intval; - char *strval; -} +%type INT_CONST CHAR_CONST +%type IDENTIFIER STR_CONST +%type assignment_operator equality_operator relational_operator shift_operator additive_operator multiplicative_operator unary_operator +%type expression assignment_expression constant_expression +%type logical_or_expression logical_and_expression inclusive_or_expression exclusive_or_expression and_expression equality_expression relational_expression shift_expression additive_expression multiplicative_expression cast_expression type_name +%typeunary_expression postfix_expression identifier primary_expression arguments postfix type_specifier %% -program - : body { - printf("\n")} -body - : IDENTIFIER +debug_top + : expression { ast_root = $1; } +expression + : assignment_expression + | expression ',' assignment_expression { $$ = cnode_create_exp(',', 2, $1, $3); } + +assignment_expression + : logical_or_expression + | unary_expression assignment_operator assignment_expression { $$ = cnode_create_exp($2, 2, $1, $3); } + +assignment_operator + : '=' { $$ = '='; } + | ASS_MUL { $$ = ASS_MUL; } + | ASS_DIV { $$ = ASS_DIV; } + | ASS_MOD { $$ = ASS_MOD; } + | ASS_ADD { $$ = ASS_ADD; } + | ASS_SUB { $$ = ASS_SUB; } + | ASS_SHL { $$ = ASS_SHL; } + | ASS_SHR { $$ = ASS_SHR; } + | ASS_AND { $$ = ASS_AND; } + | ASS_XOR { $$ = ASS_XOR; } + | ASS_OR { $$ = ASS_OR; } + +constant_expression: logical_or_expression +logical_or_expression + : logical_and_expression + | logical_or_expression OPT_OR logical_and_expression { $$ = cnode_create_exp(OPT_OR, 2, $1, $3); } + +logical_and_expression + : inclusive_or_expression + | logical_and_expression OPT_AND inclusive_or_expression { $$ = cnode_create_exp(OPT_AND, 2, $1, $3); } + +inclusive_or_expression + : exclusive_or_expression + | inclusive_or_expression '|' exclusive_or_expression { $$ = cnode_create_exp('|', 2, $1, $3); } + +exclusive_or_expression + : and_expression + | exclusive_or_expression '^' and_expression { $$ = cnode_create_exp('^', 2, $1, $3); } + +and_expression + : equality_expression + | and_expression '&' equality_expression { $$ = cnode_create_exp('&', 2, $1, $3); } + +equality_expression + : relational_expression + | equality_expression equality_operator relational_expression { $$ = cnode_create_exp($2, 2, $1, $3); } + +equality_operator + : OPT_EQ { $$ = OPT_EQ; } + | OPT_NE { $$ = OPT_NE; } + +relational_expression + : shift_expression + | relational_expression relational_operator shift_expression { $$ = cnode_create_exp($2, 2, $1, $3); } + +relational_operator + : '<' { $$ = '<'; } + | '>' { $$ = '>'; } + | OPT_LE { $$ = OPT_LE; } + | OPT_GE { $$ = OPT_GE; } + +shift_expression + : additive_expression + | shift_expression shift_operator additive_expression { $$ = cnode_create_exp($2, 2, $1, $3); } + +shift_operator + : OPT_SHL { $$ = OPT_SHL; } + | OPT_SHR { $$ = OPT_SHR; } + +additive_expression + : multiplicative_expression + | additive_expression additive_operator multiplicative_expression { $$ = cnode_create_exp($2, 2, $1, $3); } + +additive_operator + : '+' { $$ = '+'; } + | '-' { $$ = '-'; } + +multiplicative_expression + : cast_expression + | multiplicative_expression multiplicative_operator cast_expression { $$ = cnode_create_exp($2, 2, $1, $3); } + +multiplicative_operator + : '*' { $$ = '*'; } + | '/' { $$ = '/'; } + | '%' { $$ = '%'; } + +cast_expression + : unary_expression + | '(' type_name ')' cast_expression { $$ = cnode_create_exp(EXP_CAST, 2, $2, $4); } + +type_name + : type_specifier + | type_name '*' { $$ = cnode_create_exp('*', 1, $1); } + +unary_expression + : postfix_expression + | OPT_INC unary_expression { $$ = cnode_create_exp(OPT_INC, 1, $2); } + | OPT_DEC unary_expression { $$ = cnode_create_exp(OPT_DEC, 1, $2); } + | unary_operator cast_expression { $$ = cnode_create_exp($1, 1, $2); } + | KW_SIZEOF unary_expression { $$ = cnode_create_exp(KW_SIZEOF, 1, $2); } + | KW_SIZEOF '(' type_name ')' { $$ = cnode_create_exp(KW_SIZEOF, 1, $3); } + +unary_operator + : '&' { $$ = '&'; } + | '*' { $$ = '*'; } + | '+' { $$ = '+'; } + | '-' { $$ = '-'; } + | '~' { $$ = '~'; } + | '!' { $$ = '!'; } + +postfix_expression + : primary_expression + | postfix_expression postfix { $$ = cnode_create_exp(EXP_POSTFIX, 2, $1, $2); } + +postfix + : '[' expression ']' { $$ = cnode_create_exp(POSTFIX_ARR, 1, $2); } + | '(' arguments ')' { $$ = cnode_create_exp(POSTFIX_CALL, 1, $2); } + | '(' ')' { $$ = cnode_create_exp(POSTFIX_CALL, 1, NULL); } + | '.' identifier { $$ = cnode_create_exp(POSTFIX_DOT, 1, $2); } + | OPT_PTR identifier { $$ = cnode_create_exp(POSTFIX_PTR, 1, $2); } + | OPT_INC { $$ = cnode_create_exp(OPT_INC, 0); } + | OPT_DEC { $$ = cnode_create_exp(OPT_DEC, 0); } + +arguments + : assignment_expression + | arguments ',' assignment_expression { $$ = cnode_append($1, $3); } + +primary_expression + : identifier + | INT_CONST { $$ = cnode_create_int_const($1); } + | CHAR_CONST { $$ = cnode_create_char_const($1); } + | STR_CONST { $$ = cnode_create_str_const($1); } + | '(' expression ')' { $$ = $2; } + +identifier + : IDENTIFIER { $$ = cnode_create_identifier($1); } + +type_specifier + : KW_VOID { $$ = cnode_create_type_spec(KW_VOID, 0); } + | KW_CHAR { $$ = cnode_create_type_spec(KW_CHAR, 0); } + | KW_INT { $$ = cnode_create_type_spec(KW_INT, 0); } + /* to be continue */ + + %% int yywrap() { return 1; @@ -27,18 +175,17 @@ int yyerror(char *s) { } extern FILE *yyin; +void test_ast() { + yyparse(); + if (ast_root) + cnode_debug_print(ast_root); + else + fprintf(stderr, "Syntax Error\n"); +} + int main() { int ret; - //yyin = fopen("in", "r"); - while (ret = yylex()) - { - printf("%d\n", ret); - if (ret == IDENTIFIER) - printf("id: %s\n", yylval.strval); - else if (ret == INT_CONST) - printf("int: %d\n", yylval.intval); - else if (ret == STR_CONST) - printf("str: %s\n", yylval.strval); - } + yyin = fopen("in", "r"); + test_ast(); return 0; } -- cgit v1.2.3-70-g09d2