[CS143-PA2] Parser
Target
write a cool parser using bison
0.Preparation
PA3 documentation
- A Tour of the Cool Support Code : section 6 “Abstract Syntax Trees”
- bison manual / Dragon book 4.9 Parser Generator
1. Type Declaration
temporary types
- class_list (for program) :
[[class;]]+
feature_list (for class) :[[feature;]]*
method (for feature) :ID( [ formal [[, formal]]* ] ) : TYPE { expr }
attribute (for feature) :ID : TYPE [ <- expr ]
formal_list (for method in feature) :[formal [[,formal]]* ]
expression_list (for dispatch in expression) :[expr [[,expr]]* ]
expression_blocks (for blocks in expression) :[[expr;]]+
let_expr (for let in expression) :ID : TYPE [ <- expr ] [[,ID : TYPE [ <- expr ] ]]* in expr
branch (for branch in case in expression) :ID : TYPE => expr;
case_list (for case in expression) :[[ID : TYPE => expr; ]]+
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | /* Declare types for the grammar's non-terminals. */ %type <program> program %type <classes> class_list %type <class_> class /* You will want to change the following line. */ %type <feature> feature %type <features> feature_list %type <feature> method %type <feature> attribute %type <formal> formal %type <formals> formal_list %type <expression> expression %type <expressions> expression_list %type <expressions> expression_blocks %type <expression> let_expr %type <case_> branch %type <cases> case_list |
2. Precedence
All binary operations are left-associative, with the exception of assignment, which is right-associative,
and the three comparison operations, which do not associate.
1 2 3 4 5 6 7 8 9 10 | /* Precedence declarations go here. */ %right ASSIGN %left NOT %nonassoc LE '<' '=' %left '+' '-' %left '*' '/' %left ISVOID %left '~' %left '@' %left '.' |
3. Write rules using Tree package
6 Abstract Syntax Trees
cool-tour.pdf
The AST data type provides, for each kind of Cool construct, a class for representing expressions of that kind. Objects of these classes are nodes in Cool abstract syntax trees.
Find constructor declarations in
cool-tree.aps
orinclude/cool-tree.h
See 6.5 The Constructors for the usage1 2 3 4 5 6 7 8 9 10
Program program(Classes); Class_ class_(Symbol, Symbol, Features, Symbol); Feature method(Symbol, Formals, Symbol, Expression); Feature attr(Symbol, Symbol, Expression); Formal formal(Symbol, Symbol); Case branch(Symbol, Symbol, Expression); Expression assign(Symbol, Expression); Expression static_dispatch(Expression, Symbol, Symbol, Expressions); Expression dispatch(Expression, Symbol, Expressions); ...
constructor of lists
1 2 3 4 5 6 7
// define the prototypes of the interface Classes nil_Classes(); Classes single_Classes(Class_); Classes append_Classes(Classes, Classes); Features nil_Features(); Features single_Features(Feature); ...
self : use idtable to convert into Symbol, use object function to convert into Expression
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 | /* Save the root of the abstract syntax tree in a global variable. */ program : class_list { @$ = @1; ast_root = program($1); } ; class_list : class /* single class */ { $$ = single_Classes($1); parse_results = $$; } | class_list class /* several classes */ { $$ = append_Classes($1,single_Classes($2)); parse_results = $$; } ; /* If no parent is specified, the class inherits from the Object class. */ class : CLASS TYPEID '{' feature_list '}' ';' { $$ = class_($2,idtable.add_string("Object"),$4, stringtable.add_string(curr_filename)); } | CLASS TYPEID INHERITS TYPEID '{' feature_list '}' ';' { $$ = class_($2,$4,$6,stringtable.add_string(curr_filename)); } | error ; /* Feature list may be empty, but no empty features in list. */ feature_list : /* empty */ { $$ = nil_Features(); } | feature ';' { $$ = single_Features($1); } | feature ';' feature_list { $$ = append_Features( single_Features($1), $3 ); } ; feature : method { $$ = $1; } | attribute { $$ = $1; } | error ; method : OBJECTID '(' formal_list ')' ':' TYPEID '{' expression '}' { $$ = method($1, $3, $6, $8); } ; attribute : OBJECTID ':' TYPEID { $$ = attr($1, $3, no_expr()); } | OBJECTID ':' TYPEID ASSIGN expression { $$ = attr ( $1, $3, $5 ); } ; formal_list : /* empty */ { $$ = nil_Formals(); } | formal { $$ = single_Formals($1); } | formal ',' formal_list { $$ = append_Formals( single_Formals($1), $3);} | error ; formal : OBJECTID ':' TYPEID { $$ = formal( $1, $3 ); } ; expression_list : /* empty */ { $$ = nil_Expressions(); } | expression { $$ = single_Expressions( $1 ); } | expression_list ',' expression { $$ = append_Expressions( $1, single_Expressions($3)); } ; expression_blocks : expression ';' { $$ = single_Expressions($1); } | expression ';' expression_blocks { $$ = append_Expressions( single_Expressions($1), $3 ); } | error ; expression /* assign */ : OBJECTID ASSIGN expression { $$ = assign( $1, $3 ); } /* dispatch */ | expression '@' TYPEID '.' OBJECTID '(' expression_list ')' { $$ = static_dispatch ( $1, $3, $5, $7 ); } | expression '.' OBJECTID '(' expression_list ')' { $$ = dispatch( $1, $3, $5 ); } | OBJECTID '(' expression_list ')' /* call object to convert symbol into expression */ { $$ = dispatch( object(idtable.add_string("self")), $1, $3 ); } /* if then else */ | IF expression THEN expression ELSE expression FI { $$ = cond( $2, $4, $6 ); } | IF error | IF expression THEN error | IF expression THEN expression ELSE error /* while loop */ | WHILE expression LOOP expression POOL { $$ = loop( $2, $4 ); } | WHILE error | WHILE expression LOOP error /* block */ | '{' expression_blocks '}' { $$ = block( $2 ); } /* let */ | LET let_expr { $$ = $2; } /* case */ | CASE expression OF case_list ESAC { $$ = typcase( $2, $4 ); } /* new */ | NEW TYPEID { $$ = new_( $2 ); } /* isvoid */ | ISVOID expression { $$ = isvoid( $2 ); } /* + - * / ~ < <= = ! () */ | expression '+' expression { $$ = plus( $1, $3 ); } | expression '-' expression { $$ = sub( $1, $3 ); } | expression '*' expression { $$ = mul( $1, $3 ); } | expression '/' expression { $$ = divide( $1, $3 ); } | '~' expression { $$ = neg( $2 ); } | expression '<' expression { $$ = lt( $1, $3 ); } | expression LE expression { $$ = leq( $1, $3 ); } | expression '=' expression { $$ = eq( $1, $3 ); } | NOT expression { $$ = comp( $2 ); } | '(' expression ')' { $$ = $2; } /* object, constant */ | OBJECTID { $$ = object( $1 ); } | INT_CONST { $$ = int_const( $1 ); } | STR_CONST { $$ = string_const( $1 ); } | BOOL_CONST { $$ = bool_const( $1 ); } /* error */ | error ; let_expr : OBJECTID ':' TYPEID IN expression { $$ = let( $1, $3, no_expr(), $5 ); } | OBJECTID ':' TYPEID ASSIGN expression IN expression { $$ = let( $1, $3, $5, $7 ); } | OBJECTID ':' TYPEID ',' let_expr { $$ = let( $1, $3, no_expr(), $5 ); } | OBJECTID ':' TYPEID ASSIGN expression ',' let_expr { $$ = let( $1, $3, $5, $7 ); } ; branch : OBJECTID ':' TYPEID DARROW expression ';' { $$ = branch( $1, $3, $5 ); } ; case_list : branch { $$ = single_Cases( $1 ); } | branch case_list { $$ = append_Cases( single_Cases( $1 ), $2 ); } ; /* end of grammar */ |
3.Errors
5 Error Handling
PA2.pdf
- If there is an error in a class definition but the class is terminated properly and the next class is syntactically correct, the parser should be able to restart at the next class definition.
- Similarly, the parser should recover from errors in features (going on to the next feature), a let binding (going on to the next variable), and an expression inside a {…} block.