2/// @brief The bison grammar file that describes the LANCE language and
3/// the semantic actions used to translate it to assembly code.
19// The program currently being compiled.
20static t_program *program;
22void yyerror(const char *msg)
24 emitError(curFileLoc, "%s", msg);
32 * The starting non-terminal of the grammar will be `program'.
40 * Specifies the set of types available for the semantic values of terminal
41 * and non-terminal symbols.
52 t_whileStmt whileStmt;
56 * Terminal symbol declaration
58 * Here we declare all the token symbols that can be produced by the scanner.
59 * Bison will automatically produce a #define that assigns a number (or token
60 * identifier) to each one of these tokens.
61 * We also declare the type for the semantic values of some of these tokens.
64%token EOF_TOK // End of file.
65%token LPAR RPAR LSQUARE RSQUARE LBRACE RBRACE
66%token COMMA SEMI PLUS MINUS MUL_OP DIV_OP MOD_OP
67%token AND_OP XOR_OP OR_OP NOT_OP
68%token ASSIGN LT GT SHL_OP SHR_OP EQ NOTEQ LTEQ GTEQ
74// These are the tokens with a semantic value.
76%token <whileStmt> WHILE
78%token <string> IDENTIFIER
79%token <integer> NUMBER
82 * Non-terminal symbol semantic value type declarations
84 * Here we declare the type of the semantic values of non-terminal symbols.
85 * We only declare the type of non-terminal symbols of which we actually use
86 * their semantic value.
93 * Operator precedence and associativity
95 * Precedence is given by the declaration order. Associativity is given by the
96 * specific keyword used (%left, %right).
108%left MUL_OP DIV_OP MOD_OP
112 * Grammar and semantic actions
114 * The grammar of the language follows. The semantic actions are the pieces of
115 * C code enclosed in {} brackets: they are executed when the rule has been
116 * parsed and recognized up to the point where the semantic action appears.
121/* `program' is the starting non-terminal of the grammar.
122 * A program is composed by:
123 * 1. Declarations (zero or more),
124 * 2. A list of instructions (zero or more). */
126 : var_declarations statements EOF_TOK
128 // Generate the epilog of the program, that is, a call to the
131 // Return from yyparse().
136/* This non-terminal appears at the beginning of the program and represents
137 * all the declarations. */
139 : var_declarations var_declaration
143/* Each declaration consists of a type, a list of declarators, and a
144 * terminating semicolon. */
146 : TYPE declarator_list SEMI
150 : declarator_list COMMA declarator
154/* A declarator specifies either a scalar variable name or an array name
159 createSymbol(program, $1, TYPE_INT, 0);
161 | IDENTIFIER LSQUARE NUMBER RSQUARE
163 createSymbol(program, $1, TYPE_INT_ARRAY, $3);
167/* A block of code is a list of statements enclosed between braces. */
169 : LBRACE statements RBRACE
173 : statements statement
178 : assign_statement SEMI
181 | do_while_statement SEMI
182 | return_statement SEMI
183 | read_statement SEMI
184 | write_statement SEMI
188/* An assignment statement stores the value of an expression in the memory
189 * location of a given scalar variable or array element. */
193 genStoreRegisterToVariable(program, $1, $3);
195 | var_id LSQUARE exp RSQUARE ASSIGN exp
197 genStoreRegisterToArrayElement(program, $1, $3, $6);
201/* An if statements first computes the expression, then jumps to the `else' part
202 * if the expression is equal to zero. Otherwise the `then' part is executed.
203 * After the `then' part the `else' part needs to be jumped over. */
207 // Generate a jump to the else part if the expression is equal to zero.
208 $1.lElse = createLabel(program);
209 genBEQ(program, $3, REG_0, $1.lElse);
213 // After the `then' part, generate a jump to the end of the statement.
214 $1.lExit = createLabel(program);
215 genJ(program, $1.lExit);
216 // Assign the label which points to the first instruction of the else part.
217 assignLabel(program, $1.lElse);
221 // Assign the label to the end of the statement.
222 assignLabel(program, $1.lExit);
226/* The `else' part may be missing. */
232/* A while statement repeats the execution of its code block as long as the
233 * expression is different than zero. The expression is computed at the
234 * beginning of each loop iteration. */
238 // Assign a label at the beginning of the loop for the back-edge.
239 $1.lLoop = createLabel(program);
240 assignLabel(program, $1.lLoop);
244 // Generate a jump out of the loop if the condition is equal to zero.
245 $1.lExit = createLabel(program);
246 genBEQ(program, $4, REG_0, $1.lExit);
250 // Generate a jump back to the beginning of the loop after its body.
251 genJ(program, $1.lLoop);
252 // Assign the label to the end of the loop.
253 assignLabel(program, $1.lExit);
257/* A do-while statement repeats the execution of its code block as long as the
258 * expression is different than zero. The expression is computed at the
259 * end of each loop iteration. */
263 // Assign a label at the beginning of the loop for the back-edge.
264 $1 = createLabel(program);
265 assignLabel(program, $1);
267 code_block WHILE LPAR exp RPAR
269 // Generate a jump to the beginning of the loop to repeat the code block
270 // if the condition is not equal to zero.
271 genBNE(program, $6, REG_0, $1);
275/* A return statement simply exits from the program, and hence translates to a
276 * call to the `exit' syscall. */
280 genExit0Syscall(program);
284/* A read statement translates to a ReadInt syscall. The value it returns is
285 * then stored in the appropriate variable. */
287 : READ LPAR var_id RPAR
289 t_regID rTmp = getNewRegister(program);
290 genReadIntSyscall(program, rTmp);
291 genStoreRegisterToVariable(program, $3, rTmp);
295/* A write statement translates to a PrintInt syscall, followed by a PrintChar
296 * syscall which prints a newline. */
298 : WRITE LPAR exp RPAR
300 // Generate a call to the PrintInt syscall.
301 genPrintIntSyscall(program, $3);
302 // Also generate code to print a newline after the integer.
303 t_regID rTmp = getNewRegister(program);
304 genLI(program, rTmp, '\n');
305 genPrintCharSyscall(program, rTmp);
309/* The exp rule represents the syntax of expressions. The semantic value of
310 * the rule is the register ID that will contain the value of the expression
315 $$ = getNewRegister(program);
316 genLI(program, $$, $1);
320 $$ = genLoadVariable(program, $1);
322 | var_id LSQUARE exp RSQUARE
324 $$ = genLoadArrayElement(program, $1, $3);
332 $$ = getNewRegister(program);
333 genSUB(program, $$, REG_0, $2);
337 $$ = getNewRegister(program);
338 genADD(program, $$, $1, $3);
342 $$ = getNewRegister(program);
343 genSUB(program, $$, $1, $3);
347 $$ = getNewRegister(program);
348 genMUL(program, $$, $1, $3);
352 $$ = getNewRegister(program);
353 genDIV(program, $$, $1, $3);
357 $$ = getNewRegister(program);
358 genREM(program, $$, $1, $3);
362 $$ = getNewRegister(program);
363 genAND(program, $$, $1, $3);
367 $$ = getNewRegister(program);
368 genXOR(program, $$, $1, $3);
372 $$ = getNewRegister(program);
373 genOR(program, $$, $1, $3);
377 $$ = getNewRegister(program);
378 genSLL(program, $$, $1, $3);
382 $$ = getNewRegister(program);
383 genSRA(program, $$, $1, $3);
387 $$ = getNewRegister(program);
388 genSLT(program, $$, $1, $3);
392 $$ = getNewRegister(program);
393 genSGT(program, $$, $1, $3);
397 $$ = getNewRegister(program);
398 genSEQ(program, $$, $1, $3);
402 $$ = getNewRegister(program);
403 genSNE(program, $$, $1, $3);
407 $$ = getNewRegister(program);
408 genSLE(program, $$, $1, $3);
412 $$ = getNewRegister(program);
413 genSGE(program, $$, $1, $3);
417 $$ = getNewRegister(program);
418 genSEQ(program, $$, $2, REG_0);
422 t_regID rNormalizedOp1 = getNewRegister(program);
423 genSNE(program, rNormalizedOp1, $1, REG_0);
424 t_regID rNormalizedOp2 = getNewRegister(program);
425 genSNE(program, rNormalizedOp2, $3, REG_0);
426 $$ = getNewRegister(program);
427 genAND(program, $$, rNormalizedOp1, rNormalizedOp2);
431 t_regID rNormalizedOp1 = getNewRegister(program);
432 genSNE(program, rNormalizedOp1, $1, REG_0);
433 t_regID rNormalizedOp2 = getNewRegister(program);
434 genSNE(program, rNormalizedOp2, $3, REG_0);
435 $$ = getNewRegister(program);
436 genOR(program, $$, rNormalizedOp1, rNormalizedOp2);
443 t_symbol *var = getSymbol(program, $1);
445 yyerror("variable not declared");
455t_program *parseProgram(char *fn)
457 FILE *fp = fopen(fn, "r");
459 emitError(nullFileLocation, "could not open input file");
463 program = newProgram();
464 curFileLoc.file = fn;
471 fprintf(stderr, "%d error(s) generated.\n", numErrors);
473 deleteProgram(program);