[CS143-PA2] Parser

Posted on | In |

[CS143-PA2] Parser

Target

write a cool parser using bison


0.Preparation



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 or include/cool-tree.h
    See 6.5 The Constructors for the usage

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