D - ACSE

This chapter transitions from the general theory of compiler construction to a practical, hands-on example: the ACSE (Advanced Compiler System for Education). We will explore its architecture, the source language it compiles, and the detailed grammar that defines that language. This will lay the groundwork for understanding the final phase: code generation.

Warning

A full understanding of the material in this chapter requires a working knowledge of assembly language and the RISC-V architecture. Readers are encouraged to review supplemental materials on these topics if necessary.

Real-World Compilers

Before diving into our educational compiler, it’s helpful to understand the structure and purpose of industrial-strength, real-world compilers.

Definition

At its core, the purpose of a compiler is to translate a program written in a source language () into a semantically equivalent program in a target language (). This translation is not a single, monolithic step but is organized as a pipeline, where each stage applies a transformation to the program, passing its output to the next stage.

Modern compilers like GCC and LLVM use a three-stage pipeline structure. This modular design provides significant flexibility and reusability.

Front-end: Converts the source language (e.g., C, Fortran) into a common, generic intermediate form or Intermediate Representation (IR).
Middle-end: Applies transformations and powerful optimizations on the IR. This stage is independent of both the source language and the target machine.
Back-end: Converts the optimized IR into the target machine’s assembly language (e.g., x86, ARM).

This structure allows for a mix-and-match approach. For example, a single middle-end can support multiple languages by having a different front-end for each, and it can target multiple architectures by using different back-ends.

The Front-End Structure

The front-end itself is a multi-step pipeline responsible for understanding the source code. Its main tasks are to recognize language constructs and verify their syntactic and semantic correctness.

The process flows as follows:

Lexical Analyzer (Scanner): Reads the source code and produces a token stream.
Syntax Analyzer (Parser): Takes the token stream and builds an Abstract Syntax Tree (AST), verifying the code against the language’s grammar.
Semantic Analyzer: Traverses the AST to check for semantic correctness (e.g., type checking, ensuring variables are declared). It “decorates” the AST with this additional information.
Code Generator: Traverses the decorated AST to produce the final Intermediate Representation (IR).

Throughout this process, a Symbol Table is used to store information about identifiers like variables and functions.

A Real-World Example: LLVM

The LLVM project is a perfect real-world example of this modular pipeline:

Many Front-ends: It has different front-ends for various languages. The most well-known is Clang, which handles C, C++, and Objective-C. Each front-end translates its source language into a unified IR called LLVM-IR.

Powerful Middle-end: The LLVM-IR is passed to a sophisticated optimizer that performs tasks like removing redundant computations, rearranging loops for speed, and attempting to vectorize code.

Multiple Back-ends: Finally, the optimized IR is sent to a back-end specific to the target CPU. These back-ends use algorithms to map IR instructions to real machine instructions and use “Printers” to emit the final assembly code or binary.

Introduction to ACSE

ACSE is a simple compiler designed for educational purposes. It follows the same fundamental principles as a real-world compiler but is simplified to focus on core concepts.

Functionality: ACSE accepts a C-like source language called LANCE and emits RISC-V (RV32IM) assembly language.
Toolchain: It comes with its own helper tools to form a complete toolchain:
- asrv32im: An assembler to convert RISC-V assembly into machine code.
- simrv32im: A RISC-V simulator to run the machine code.
Alternative Tool: The popular RARS (RISC-V Assembler and Runtime Simulator) can also be used to assemble and run the output of ACSE.

ACSE follows a simplified but complete compilation pipeline:

Front-end:
1. The LANCE source code is tokenized by a Flex-generated scanner.
2. The stream of tokens is parsed by a Bison-generated parser.
3. The semantic actions within the parser translate the code directly into a temporary intermediate representation.
Back-end: 4. The IR is normalized to account for the physical limitations of the target RISC-V architecture. 5. Each instruction in the IR is printed out, producing the final assembly file.

The LANCE Language

LANCE (LANguage for Compiler Education) is the source language for ACSE. It is a very small subset of C with several key limitations:

Types: Only one scalar type (int) and one aggregate type (array of int).
Operators: A standard set of arithmetic, logic, and comparison operators.
Control Flow: A reduced set of control flow statements: while, do-while, and if.
Functions: No support for function definitions or calls.
I/O: Limited support for input/output operations:
- read(var): Reads an integer from standard input and stores it in var.
- write(expr): Writes the value of expr to standard output.

A LANCE source file is composed of two sections in order:

Variable declarations.
The program body, which is a list of statements.

// ==== Variable Declarations ====
int x, y, z, i;
int arr[10];
 
// ==== Program Body (Statements) ====
read(x);
read(y);
z = 42;
 
i = 0;
while (i < 10) {
  arr[i] = (y - x) * z;
  i = i + 1;
}
 
z = arr[9];
write(z);

The Grammar of LANCE

The structure of the LANCE language is formally defined by its grammar.

A LANCE program is split into two sections, represented by two root non-terminals: var_declarations followed by statements.

program → var_declarations statements
 
var_declarations → var_declarations var_declaration
                 | ε
 
statements → statements statement
           | statement

Variable declarations are similar to C, but without inline initialization. An IDENTIFIER is the non-terminal for a variable or array name.

var_declaration → TYPE declarator_list SEMI
 
declarator_list → declarator_list COMMA declarator
                | declarator
 
declarator → IDENTIFIER
           | IDENTIFIER LSQUARE NUMBER RSQUARE

For example, the line int a, b, c[20]; is parsed using these rules, where a, b, and c[20] are each a declarator.

Statements

A statement is a unit that expresses an action. LANCE statements can be classified into two types:

Simple: An indivisible element of computation, like an assignment (=), read, or write.
Compound: A statement that contains other statements, such as if, while, and do-while.

The grammar for simple statements is as follows. Notice that a semicolon SEMI by itself is a valid (empty) statement.

statement → assign_statement SEMI
          | if_statement
          | while_statement
          | do_while_statement SEMI
          | read_statement SEMI
          | write_statement SEMI
          | return_statement SEMI
          | SEMI
          | ... (compound statements)
 
assign_statement → var_id ASSIGN exp
                 | var_id LSQUARE exp RSQUARE ASSIGN exp
return_statement → RETURN
read_statement → READ LPAR var_id RPAR
write_statement → WRITE LPAR exp RPAR
var_id → IDENTIFIER

Here, exp represents a generic expression and var_id is a variable name (symbol).

LANCE supports a wide range of unary and binary operators. The expression grammar is written in a simple but highly ambiguous way, relying on Bison’s precedence declarations to resolve conflicts.

exp → NUMBER 
    | var_id                        
    | var_id LSQUARE exp RSQUARE    
    | LPAR exp RPAR                   
    | MINUS exp                        
    | exp PLUS exp                   
    | exp MINUS exp                 
    | exp MUL_OP exp                
    | exp DIV_OP exp                
    | exp MOD_OP exp                
    | exp AND_OP exp                
    | exp XOR_OP exp                
    | exp OR_OP exp                
    | exp SHL_OP exp                
    | exp SHR_OP exp                
    | exp LT exp                    
    | exp GT exp                    
    | exp EQ exp                    
    | exp NOTEQ exp                 
    | exp LTEQ exp                  
    | exp GTEQ exp                  
    | NOT_OP exp                    
    | exp ANDAND exp                
    | exp OROR exp

where

Token	Description
`PLUS`	Addition operator (`+`)
`MINUS`	Subtraction operator (`-`)
`MUL_OP`	Multiplication operator (`*`)
`DIV_OP`	Division operator (`/`)
`MOD_OP`	Modulus operator (`%`)
`AND_OP`	Bitwise AND operator (`&`)
`OR_OP`	Bitwise OR operator (`\|`)
`XOR_OP`	Bitwise XOR operator (`^`)
`SHL_OP` and `SHR_OP`	Shift Left (`<<`) and Shift Right (`>>`) operators
`LT`, `GT`, `LTEQ`, `GTEQ`	Comparison operators (`<`, `>`, `<=`, `>=`)
`EQ`, `NOTEQ`	Equality (`==`) and Inequality (`!=`) operators
`NOT_OP`	Logical NOT operator (`!`)
`ANDAND` and `OROR`	Logical AND (`&&`) and Logical OR (`\|\|`) operators
`LPAR`, `RPAR`	Left and Right Parentheses (`(`, `)`)
`LSQUARE`, `RSQUARE`	Left and Right Square Brackets (`[`, `]`)

Compound statements are built using a code_block non-terminal, which represents a list of statements enclosed by braces ({ ... }).

code_block → LBRACE statements RBRACE
 
if_statement → IF LPAR exp RPAR code_block else_part
else_part → ELSE code_block | ε
 
while_statement → WHILE LPAR exp RPAR code_block
do_while_statement → DO code_block WHILE LPAR exp RPAR

Operator Precedence and Associativity

The ambiguities in the expression grammar are resolved using the following precedence rules, listed from lowest to highest priority. All binary operators are left-associative except for NOT_OP, which is unary and right-associative.

%left OROR
%left ANDAND
%left OR_OP
%left XOR_OP
%left AND_OP
%left EQ NOTEQ
%left LT GT LTEQ GTEQ
%left SHL_OP SHR_OP
%left PLUS MINUS
%left MUL_OP DIV_OP MOD_OP
 
%right NOT_OP

This ordering is the same as in C, including its “weirdnesses.”

For example, the bitwise operators & and | have lower priority than comparison operators like ==.

An Important Quirk: The Unary Minus Bug

The LANCE grammar has a deliberate bug in how it handles the unary minus. Because MINUS is declared as left-associative with the same priority as PLUS, it is always treated as a binary subtraction operator.

This leads to incorrect interpretations:

Expression Normal Interpretation LANCE Interpretation

This misinterpretation of the unary minus is an important characteristic of the LANCE language.

Note: This bug can be fixed using the %prec directive, as discussed in "Encoding Precedence in BNF Grammars".

Code Generation in ACSE

Having established the grammar of the LANCE language, we now turn to the most critical part of the compiler: the translation from source code to the target assembly language. This section delves into the internal architecture of ACSE, its intermediate representation, and the mechanisms used by its semantic actions to generate RISC-V code.

A Syntax-Directed Translator

The core of the ACSE compiler is built from three main components:

scanner.l: The Flex source filedefining the lexical analyzer.
parser.y: The Bison source file containing the LANCE grammar and the semantic actions for translation.
codegen.h: A C header file providing helper functions for generating instructions.

ACSE is a syntax-directed translator, which means it produces the compiled output directly while parsing. The order of the generated assembly instructions is dictated by the syntax of the input program and the bottom-up traversal of the parse tree. The parser.y file is therefore the most important file in the project, as its semantic actions are responsible for the entire translation process.

It is essential to re-emphasize the distinction between compile time and run time:

Definition

Compile Time: The semantic actions (C code within parser.y) are executed during compilation. Their job is not to perform the calculations of the LANCE program but to decide which RISC-V assembly instructions to generate and in what order.

Run Time: The generated RISC-V assembly code is executed only when the compiled program is launched later. This is when the actual computations (additions, memory loads, etc.) take place.

The process can be visualized as a bottom-up, left-to-right traversal of the syntax tree. When the C code associated with a node is executed, it generates a piece of RISC-V assembly code and, optionally, a semantic value that it passes up to its parent node.

The ACSE Intermediate Representation (IR)

To manage the program being built, a compiler uses an Intermediate Representation (IR). This is the central data structure where the program is stored during compilation. In ACSE, the IR is composed of two main parts:

The Instruction List: A list where the generated RISC-V assembly code is stored.
The Symbol Table: A table to store information about declared variables (name, type, etc.).

The semantic actions in the parser work by modifying these two data structures to build the final compiled program.

The `program` Instance

During parsing, the entire IR and other contextual information are stored in a global C structure called program, which is declared at the top of parser.y.

typedef struct {
    t_listNode *labels;
    t_listNode *instructions;
    t_listNode *symbols;
    t_regID firstUnusedReg;
    unsigned int firstUnusedLblID;
    t_label *pendingLabel;
} t_program;
 
t_program program;

This single structure holds pointers to the instruction list and symbol table, and it also tracks the state of the compiler, such as the next available register and label IDs. Almost every helper function in ACSE takes a pointer to this program instance as an argument.

The IR Instruction Set

The instruction set used in ACSE’s IR is a superset of RISC-V assembly. While real-world compilers often use an IR that is completely different from the target assembly, ACSE uses a closely related one for simplicity.

This superset provides a layer of abstraction that simplifies the front-end’s task by removing certain hardware limitations:

Infinite Registers: The front-end can assume it has an infinite supply of temporary registers. The mapping to the finite set of physical RISC-V registers is handled later by the back-end.
No Restrictions on Immediates: The front-end can generate instructions with immediate values of any size, without worrying about the 12-bit limit in the actual RISC-V architecture.
“Syscall” Instructions: High-level instructions like ReadInt and PrintInt are included in the IR to simplify I/O operations.

To implement the concept of infinite registers, ACSE uses register identifiers (t_regID). In compiler terminology, these are known as temporaries or virtual registers. They serve to decouple the program’s logic from the physical Application Binary Interface (ABI) of the target machine. ACSE denotes these registers as temp(n) to distinguish them from physical machine registers (like x1, t0, etc.). The value of a t_regID is simply the number n.

A new temporary register can be allocated by calling:

t_regID getNewRegister(t_program *program);

Additionally, the machine’s hardwired zero register is always available via the constant REG_0.

Code Generation Functions

ACSE provides a set of C functions that add one instruction to the end of the program’s instruction list. These are called code generation functions, and by convention, their names are prefixed with gen.

// Example: Generate an R-type instruction (e.g., ADD, SUB)
t_instruction *genXXX(t_program *program, t_regID rd, t_regID rs1, t_regID rs2);
 
// Example: Generate an I-type instruction (e.g., ADDI)
t_instruction *genXXX(t_program *program, t_regID rd, t_regID rs1, int immediate);
 
// Example: Generate a conditional branch (e.g., BEQ)
t_instruction *genBcc(t_program *program, t_regID rs1, t_regID rs2, t_label *label);

Higher-level helper functions are also provided to generate common sequences of instructions, such as those for accessing variables and array elements.

t_regID genLoadVariable(t_program *program, t_symbol *var);
 
void genStoreRegisterToVariable(t_program *program, t_symbol *var, t_regID reg);
void genStoreConstantToVariable(t_program *program, t_symbol *var, int val);

t_regID genLoadArrayElement(t_program *program, t_symbol *array, t_regID rIdx);
 
void genStoreRegisterToArrayElement(t_program *program, t_symbol *array, t_regID rIdx, t_regID rVal);
void genStoreConstantToArrayElement(t_program *program, t_symbol *array, t_regID rIdx, int val);

Semantic Values in ACSE

Semantic values are crucial for passing information up the parse tree. The following table summarizes the types used for the key symbols in ACSE’s grammar:

Symbol	Type	Purpose
`NUMBER`	`int`	The numeric value of the number token.
`IDENTIFIER`	`char*`	The string value (name) of the identifier token.
`var_id`	`t_symbol*`	A pointer to the symbol table object for the variable.
`exp`	`t_regID`	The ID of the virtual register containing the computed value of the expression.

Implementing Code Generation in Bison

With the IR and helper functions defined, we can now examine how the semantic actions in parser.y perform the translation.

Declaration: When a declarator rule is recognized, its semantic action calls the createSymbol() function. This function checks if the symbol already exists (and exits with an error if it does) and then adds the new symbol to the symbol table.

declarator: IDENTIFIER
            { createSymbol(program, $1, TYPE_INT, 0); }
          | IDENTIFIER LSQUARE NUMBER RSQUARE
            { createSymbol(program, $1, TYPE_INT_ARRAY, $3); }
          ;

Lookup: When a variable is used in the code, the var_id rule is matched. Its action looks up the identifier in the symbol table using getSymbol(). If the symbol is not found, it reports an error. If found, it sets the semantic value $$ to be a pointer to the symbol table entry.

var_id: IDENTIFIER
        {
            t_symbol *var = getSymbol(program, $1);
            if (var == NULL) {
                yyerror("variable not declared");
                YYERROR;
            }
            $$ = var;
            free($1); // Free the string allocated by the lexer
        }
      ;

The true power of syntax-directed translation is evident in how expressions are handled.

The goal of the exp non-terminal's semantic actions is to:

Generate the RISC-V code required to compute the expression.

Store the final result in a new temporary register.

Pass the ID of that register up the tree as its semantic value ($$).

exp: NUMBER
     {
         $$ = getNewRegister(program);
         genLI(program, $$, $1); // Load Immediate
     }
   | var_id
     {
         $$ = genLoadVariable(program, $1); // Load variable's value
     }
   | exp PLUS exp
     {
         $$ = getNewRegister(program);
         genADD(program, $$, $1, $3); // Add values from child registers
     }
   ;

For an assignment, the assign_statement rule uses the results from its children. The exp on the right ($3) provides the register ID containing the value to be stored, and the var_id on the left ($1) provides the symbol table entry for the destination variable.

assign_statement: var_id ASSIGN exp
                  { genStoreRegisterToVariable(program, $1, $3); }
                | var_id LSQUARE exp RSQUARE ASSIGN exp
                  { genStoreRegisterToArrayElement(program, $1, $3, $6); }
                ;

Consider the execution of the sentence: res = a + b * c / 15;

Let’s trace the compilation of res = a + b * c / 15; to see how these pieces work together in a bottom-up fashion.

Leaves: The parser first reaches the leaves of the expression tree: a, b, c, and 15.

For a, b, and c, the exp -> var_id rule is reduced. The semantic action calls genLoadVariable, which generates code to load the variable’s value from memory into a new temporary register (e.g., temp2 for a, temp4 for b, etc.). The semantic value passed up is the register ID (e.g., 2, 4).

For 15, the exp -> NUMBER rule is reduced. The action calls genLI to generate code to load the constant 15 into a new register (e.g., temp8). The semantic value 8 is passed up.

b * c: The parser now sees exp MUL_OP exp. The semantic values of the children are available as $1 (the register for b, e.g., temp4) and $3 (the register for c, e.g., temp6).

The semantic action gets a new register (temp7).

It calls genMUL(program, temp7, temp4, temp6).

It passes the new register ID, 7, up the tree as its result ($$). The previously generated code for loading b and c now precedes this mul instruction.

(b * c) / 15: Next is exp DIV_OP exp. $1 holds the result from the multiplication (register temp7) and $3 holds the register for 15 (temp8).

The action gets a new register (temp9).

It calls genDIV(program, temp9, temp7, temp8).

It passes 9 up as its result.

a + ((b * c) / 15): The parser sees exp PLUS exp. $1 holds the register for a (temp2) and $3 holds the result from the division (temp9).

The action gets a new register (temp10).

It calls genADD(program, temp10, temp2, temp9).

It passes 10 up as the final result of the entire right-hand side expression.

res = ...: Finally, the assign_statement rule is reduced. Its left child ($1) is the symbol for res, and its right child ($3) is the semantic value 10 (for temp10).

The action calls genStoreRegisterToVariable(program, res_symbol, 10), which generates the final la and sw instructions to store the value from temp10 into the memory location for res.

The final, linear sequence of instructions in the IR is the ordered concatenation of the code generated at each step.

Operand Normalization

Logical operators like && (ANDAND) and || (OROR) require their operands to be Boolean (0 for false, 1 for true). However, in LANCE (as in C), any non-zero value is considered true. Before performing the logical operation, the operands must be normalized.

An operand equal to 0 should remain 0.
An operand not equal to 0 should become 1.

This normalization is elegantly achieved by generating a SNE (Set if Not Equal) instruction for each operand, comparing it against the zero register.

SNE rNormOp, rOrigOp, REG_0

This instruction will place 1 in rNormOp if rOrigOp is not zero, and 0 otherwise.

Once both operands are normalized into new temporary registers, the corresponding bitwise instruction (AND for &&, OR for ||) can be used to compute the final result.

exp: exp ANDAND exp
   {
       // Normalize first operand ($1) into rNormOp1
       t_regID rNormOp1 = getNewRegister(program);
       genSNE(program, rNormOp1, $1, REG_0);
 
       // Normalize second operand ($3) into rNormOp2
       t_regID rNormOp2 = getNewRegister(program);
       genSNE(program, rNormOp2, $3, REG_0);
 
       // Perform bitwise AND on normalized values
       $$ = getNewRegister(program);
       genAND(program, $$, rNormOp1, rNormOp2);
   }
 ;

Generating Code for Control Flow

Translating control flow statements like if, while, and do-while is one of the most interesting challenges for a syntax-directed translator. These constructs require generating non-linear control flow using branches and labels, which complicates the otherwise linear, bottom-up generation of code.

In assembly language, branches transfer control to a named label. There are two fundamental types of branches:

Backward Branch: The branch instruction jumps to a label that has already appeared earlier in the code. This is simple for a compiler, as the label’s location is already known.
Forward Branch: The branch instruction jumps to a label that has not yet been defined and will appear later in the code.

This poses a problem for a syntax-directed translator like ACSE. As the parser consumes the input, it generates code in a single pass. When it encounters the condition of an if or while statement, it must generate a branch instruction, but the target label (e.g., the start of the else block or the code after the loop) has not been reached yet.

To solve this, ACSE provides two primary functions for managing labels:

t_label *createLabel(t_program *program);

This function allocates and returns a new label object but does not insert it into the instruction list. It effectively reserves a name for a future location in the code.

void assignLabel(t_program *program, t_label *label);

This function takes a label object (created earlier) and inserts it into the current position in the instruction list. This is analogous to the genXXX() functions that “print” instructions; assignLabel() “prints” a label.

By creating a label first and assigning it later, we can generate forward-branching code.

The `while` Statement

// standard while loop structure
while(exp){
	code_block
}

A while loop first evaluates a condition. If it is true, the body is executed, and control returns to the condition. If false, control jumps to the code following the loop.

while_statement: WHILE LPAR exp RPAR code_block;

This requires two labels: one for the start of the loop (for jumping back) and one for the exit (for jumping out). The translation requires three distinct code-generation steps placed at different points within the rule. ACSE handles this with mid-rule actions.

The trick is to store the pointers to the two required label objects in the semantic value of the WHILE token itself.

A struct is defined to hold the labels.

// In parser.h
typedef struct {
	t_label *lLoop; // Label for the start of the loop
	t_label *lExit; // Label for the code after the loop
} t_whileStmt;

The %union in parser.y is updated, and the WHILE token is associated with this struct type.

%union {
	...
	t_whileStmt whileStmt;
}
 
%token <whileStmt> WHILE

The while_statement Rule with Semantic Actions:

while_statement
    : WHILE
      {   // Action 1: Before the condition
          $1.lLoop = createLabel(program);
          assignLabel(program, $1.lLoop);
      }
      LPAR exp RPAR
      {   // Action 2: After the condition
          $1.lExit = createLabel(program);
          // genBEQ: branch if $4 (exp) is zero (false) to the exit label
          genBEQ(program, $4, REG_0, $1.lExit);
      }
      code_block
      {   // Action 3: After the body
          genJ(program, $1.lLoop); // Unconditional jump back to the start
          assignLabel(program, $1.lExit); // Place the exit label here
      }
    ;

Action 1: Before the condition expression (exp) is parsed, the l_loop label is created and immediately placed in the instruction stream. This marks the top of the loop.
The code for the condition (exp) is generated. Its result is in the register identified by $4.
Action 2: After the condition code, a forward branch (BEQ) is generated. If the condition is false (i.e., its result is 0), the program will jump to the l_exit label, which has been created but not yet placed.
The code for the loop body (code_block) is generated.
Action 3: After the body, an unconditional jump (J) is generated to branch back to l_loop. Immediately following this jump, the l_exit label is finally placed, marking the end of the loop structure.

This sequence produces the classic assembly structure for a while loop.

The `do-while` Statement

// standard do-while loop structure
do {
  code_block
} while(exp);

The do-while loop is simpler because the condition is checked after the body is executed.

do_while_statement
    : DO
      {   // Action 1: Before the body
          $1 = createLabel(program); // $1 is just a t_label*
          assignLabel(program, $1);
      }
      code_block WHILE LPAR exp RPAR
      {   // Action 2: After the condition
          // genBNE: branch if $6 (exp) is not zero (true) back to the start
          genBNE(program, $6, REG_0, $1);
      }
    ;

This is much simpler than while:

The loop’s entry label can be created and placed immediately before the body.
At the end, only a single backward branch is needed. If the condition is true, control jumps back to the already-known label. No forward branching is necessary for the loop mechanic itself.

The `if-else` Statement

// standard if-else structure
if (exp) {
  code_block
} else {
  code_block
}

An if statement evaluates a condition and conditionally executes one of two blocks of code.

if_statement: IF LPAR exp RPAR code_block else_part;
else_part   : ELSE code_block 
			| %empty;

This requires two forward jumps:

A conditional jump to the else part if the condition is false.
An unconditional jump over the else part if the condition is true.

Similar to while, we store two labels (lElse, lExit) in the semantic value of the IF token.

if_statement
    : IF LPAR exp RPAR
      {   // Action 1: After the condition
          $1.lElse = createLabel(program);
          // Branch to else-part if condition ($3) is false
          genBEQ(program, $3, REG_0, $1.lElse);
      }
      code_block
      {   // Action 2: After the 'then' block
          $1.lExit = createLabel(program);
          // Unconditionally jump over the else-part
          genJ(program, $1.lExit);
          // Place the label for the else-part
          assignLabel(program, $1.lElse);
      }
      else_part
      {   // Action 3: After the 'else' part
          // Place the exit label for the whole statement
          assignLabel(program, $1.lExit);
      }
    ;

The condition expression (exp) code is generated.
Action 1: A BEQ instruction is generated. If the condition is false, it performs a forward jump to lElse.
The code for the then part (code_block) is generated.
Action 2: An unconditional J instruction is generated to jump over the else block to the lExit label. Then, the lElse label is placed, marking the beginning of the else part.
The code for the else_part is generated (which may be nothing if the rule is empty).
Action 3: Finally, the lExit label is placed, marking the point where both control paths converge.

Generating Code for Simple Statements

The remaining simple statements in LANCE translate directly to specific syscall sequences.

The `return` Statement

In LANCE, there are no functions, so a return statement simply exits the entire program. This translates directly to the Exit0 syscall.

return_statement: RETURN
                  { genExit0Syscall(program); }
                ;

The `read` Statement

A read statement gets an integer from standard input and stores it in a variable. The process is:

Allocate a new temporary register to hold the input value.
Generate a ReadInt syscall, which places the integer in that register.
Generate code to store the value from the temporary register into the target variable’s memory location.

read_statement: READ LPAR var_id RPAR
                {
                    t_regID rTmp = getNewRegister(program);
                    genReadIntSyscall(program, rTmp);
                    genStoreRegisterToVariable(program, $3, rTmp);
                }
              ;

The `write` Statement

A write statement prints the value of an expression to standard output. This translates to a PrintInt syscall. However, there is a crucial detail: the standard PrintInt syscall in the RARS simulator does not automatically add a newline character. To match the behavior of printf("%d\n"), the compiler must also generate code to print a newline.

write_statement: WRITE LPAR exp RPAR
                 {
                     // Print the integer value from the expression
                     genPrintIntSyscall(program, $3);
 
                     // Explicitly print a newline character
                     t_regID rTmp = getNewRegister(program);
                     genLI(program, rTmp, '\n');
                     genPrintCharSyscall(program, rTmp);
                 }
               ;

Polimi CS - Notes

Explorer

D - ACSE

Table of Contents

Real-World Compilers

The Front-End Structure

Introduction to ACSE

The LANCE Language

The Grammar of LANCE

Statements

Operator Precedence and Associativity

Code Generation in ACSE

A Syntax-Directed Translator

The ACSE Intermediate Representation (IR)

The `program` Instance

The IR Instruction Set

Code Generation Functions

Semantic Values in ACSE

Implementing Code Generation in Bison

Operand Normalization

Generating Code for Control Flow

The `while` Statement

The `do-while` Statement

The `if-else` Statement

Generating Code for Simple Statements

The `return` Statement

The `read` Statement

The `write` Statement

Graph View

Table of Contents

Polimi CS - Notes

Explorer

D - ACSE

Table of Contents

Real-World Compilers

The Front-End Structure

Introduction to ACSE

The LANCE Language

The Grammar of LANCE

Statements

Operator Precedence and Associativity

Code Generation in ACSE

A Syntax-Directed Translator

The ACSE Intermediate Representation (IR)

The program Instance

The IR Instruction Set

Code Generation Functions

Semantic Values in ACSE

Implementing Code Generation in Bison

Operand Normalization

Generating Code for Control Flow

The while Statement

The do-while Statement

The if-else Statement

Generating Code for Simple Statements

The return Statement

The read Statement

The write Statement

Graph View

Table of Contents

The `program` Instance

The `while` Statement

The `do-while` Statement

The `if-else` Statement

The `return` Statement

The `read` Statement

The `write` Statement