Code:
%{
#include "tree.h"
extern tree root;
tree BuildTree(int, tree, tree, tree);
tree BuildIntTree(int, int);
tree BuildFloatTree(int, float);
%}
%token <i> Ident 1 IntConst 2
%token <f> RealConst 3
%token Var 11 Int 12 Real 13 Boolean 14 Record 15
%token End 16 Bind 17 To 18 Assert 19 Begin 20
%token Loop 21 Exit 22 When 23 If 24 Then 25
%token Elsif 26 Else 27 Put 28 Or 29 And 30
%token Not 31 NotEq 32 Div 33 Mod 34
%token SemiColon 40 Colon 41 Assign 42 Gt 43 Lt 44
%token Eq 45 Lte 46 Gte 47 Plus 48 Minus 49
%token Star 50 Slash 51 Dot 52 Comma 53 LParen 54 RParen 55
%start program
%union { tree t; int i; float f; }
%type <t> program pStateDeclSeq id_list type field_list state_decls
%type <t> declaration statement ref end_if expr and_expr not_expr
%type <t> rel_expr sum prod factor basic
%%
program
: pStateDeclSeq
{ root = $1; }
;
pStateDeclSeq
: /* nullable */
{ $$ = NULL; }
| statement SemiColon pStateDeclSeq
{ $1->next = $3; $$ = $1; }
| Var id_list Colon type SemiColon pStateDeclSeq
{ $$ = BuildTree(Var, $2, $4, $6); }
;
id_list
: Ident
{ $$ = BuildIntTree(Ident, $1); }
| Ident Comma id_list
{ $$ = BuildTree(Comma, BuildIntTree(Ident, $1), $3, NULL); }
;
type
: Int
{ $$ = BuildIntTree(Int, $<i>1); }
| Real
{ $$ = BuildFloatTree(Real, $<f>1); }
| Boolean
{ $$ = BuildIntTree(Boolean, $<i>1); }
| Record field_list End Record
{ $$ = BuildTree(Record, $2, BuildTree(End, NULL, NULL, NULL), BuildTree(Record, NULL, NULL, NULL)); }
;
field_list
: id_list Colon type
{ $$ = BuildTree(Colon, $1, $3, NULL); }
| id_list Colon type SemiColon field_list
{ $$ = BuildTree(Colon, $1, $3, $5); }
;
state_decls
: /* nullable */
{ $$ = NULL; }
| statement SemiColon pStateDeclSeq
{ $1->next = $3; $$ = $1; }
| declaration SemiColon pStateDeclSeq
{ $1->next = $3; $$ = $1; }
;
declaration
: Var id_list Colon type
{ $$ = BuildTree(Var, $2, $4, NULL); }
| Bind Ident To ref
{ $$ = BuildTree(Bind, BuildIntTree(Ident, $2), BuildTree(To, $4, NULL, NULL), NULL); }
| Bind Var Ident To ref
{ $$ = BuildTree(Bind, BuildTree(Var, BuildIntTree(Ident, $3), NULL, NULL), BuildTree(To, $5, NULL,
NULL), NULL); }
;
statement
: ref Assign expr
{ $$ = BuildTree(Assign, $1, $3, NULL); }
| Assert expr
{ $$ = BuildTree(Assert, $2, NULL, NULL); }
| Begin state_decls End
{ $$ = BuildTree(Begin, $2, BuildTree(End, NULL, NULL, NULL), NULL); }
| Loop state_decls End Loop
{ $$ = BuildTree(Loop, $2, BuildTree(End, NULL, NULL, NULL), BuildTree(Loop, NULL, NULL, NULL)); }
| Exit
{ $$ = NULL; }
| Exit When expr
{ $$ = BuildTree(Exit, BuildTree(When, $3, NULL, NULL), NULL, NULL); }
| If expr Then state_decls end_if
{ $$ = BuildTree(If, $2, BuildTree(Then, $4, $5, NULL), NULL); }
;
ref
: Ident
{ $$ = BuildIntTree(Ident, $1); }
| Ident Dot Ident
{ $$ = BuildTree(Dot, BuildIntTree(Ident, $1), BuildIntTree(Ident, $3), NULL); }
;
end_if
: End If
{ $$ = NULL; }
| Else state_decls End If
{ $$ = BuildTree(Else, $2, NULL, NULL); }
| Elsif expr Then state_decls end_if
{ $$ = BuildTree(Elsif, $2, $4, $5); }
;
expr
: expr Or and_expr
{ $$ = BuildTree(Or, $1, $3, NULL); }
| and_expr
{ $$ = $1; }
;
and_expr
: and_expr And not_expr
{ $$ = BuildTree(And, $1, $3, NULL); }
| not_expr
{ $$ = $1; }
;
not_expr
: Not not_expr
{ $$ = BuildTree(Not, $2, NULL, NULL); }
| rel_expr
{ $$ = $1; }
;
rel_expr
: sum
{ $$ = $1; }
| rel_expr Eq sum
{ $$ = BuildTree(Eq, $1, $3, NULL); }
| rel_expr NotEq sum
{ $$ = BuildTree(NotEq, $1, $3, NULL); }
| rel_expr Lt sum
{ $$ = BuildTree(Lt, $1, $3, NULL); }
| rel_expr Lte sum
{ $$ = BuildTree(Lte, $1, $3, NULL); }
| rel_expr Gt sum
{ $$ = BuildTree(Gt, $1, $3, NULL); }
| rel_expr Gte sum
{ $$ = BuildTree(Gte, $1, $3, NULL); }
;
sum
: prod
{ $$ = $1; }
| sum Plus prod
{ $$ = BuildTree(Plus, $1, $3, NULL); }
| sum Minus prod
{ $$ = BuildTree(Minus, $1, $3, NULL); }
;
prod
: factor
{ $$ = $1; }
| prod Star factor
{ $$ = BuildTree(Star, $1, $3, NULL); }
| prod Slash factor
{ $$ = BuildTree(Slash, $1, $3, NULL); }
| prod Div factor
{ $$ = BuildTree(Div, $1, $3, NULL); }
| prod Mod factor
{ $$ = BuildTree(Mod, $1, $3, NULL); }
;
factor
: Plus basic
{ $$ = BuildTree(Plus, $2, NULL, NULL); }
| Minus basic
{ $$ = BuildTree(Minus, $2, NULL, NULL); }
| basic
{ $$ = $1; }
;
basic
: ref
{ $$ = $1; }
| LParen expr RParen
{ $$ = $2; }
| IntConst
{ $$ = BuildIntTree(IntConst, $1); }
| RealConst
{ $$ = BuildFloatTree(RealConst, $1); }
;
%%
The tree.c file: