BSc CSIT (TU) Science Compiler Design and Construction (BSc CSIT, CSC365) Question Paper 2081 Nepal

Target Code Generation

The code generator is the final phase of a compiler. It takes the optimized intermediate representation (IR) of the source program (e.g. three-address code) together with information in the symbol table and produces equivalent target code (assembly or machine code). The generated code must be correct and of high quality (fast and compact), and the generator itself should run efficiently.

Input: $\text{IR (three-address code, DAGs, etc.)}$ + symbol table. Output: relocatable machine code / assembly.

Register Allocation and Assignment

Because register operations are far faster than memory operations, keeping frequently used values in registers improves performance. This is handled in two sub-problems:

• Register allocation — decide which variables/values will reside in registers at each point in the program.
• Register assignment — decide the specific physical register each selected value will occupy.

Finding an optimal assignment is NP-complete, so heuristics are used. A common technique is graph coloring: build an interference graph whose nodes are values whose live ranges overlap; two nodes are connected if they are simultaneously live and therefore cannot share a register. Coloring the graph with $k$ colors (where $k$ = number of available registers) gives a valid assignment; if it cannot be colored, some values are spilled to memory. Usage counts ($\sum (\text{uses} + \text{defs}) \times c^{\text{loop depth}}$) help decide which values are most beneficial to keep in registers.

Issues in the Design of a Code Generator

1. Input to the code generator — form of IR (postfix, three-address code, syntax trees, DAGs) and the assumption that the front end has done type checking.
2. Target program / target language — absolute machine code, relocatable machine code, or assembly language; affects how addresses and linking are handled.
3. Instruction selection — choosing machine instructions that implement each IR operation; must consider instruction speed, cost, and addressing modes (e.g. using INC a instead of ADD a, #1).
4. Register allocation and assignment — choosing which values stay in registers (discussed above).
5. Evaluation order — the order in which computations are performed affects the number of registers needed and the efficiency of the code.
6. Memory management — mapping names in the symbol table to run-time addresses and handling activation records.
7. Approach / target machine details — the instruction set, number of registers, and cost model strongly influence the design.

A good code generator balances correctness, code quality, and its own efficiency, given that optimal code generation is theoretically intractable.

Semantic Analysis

Semantic analysis is the compiler phase that checks the source program for semantic (meaning-level) consistency that cannot be captured by context-free grammar alone. It uses the syntax tree and the symbol table to verify that the program is meaningful — e.g. variables are declared before use, the number/types of arguments match, operators are applied to compatible operands, and break is used only inside a loop. It also gathers type information for the code-generation phase. It is commonly implemented using a syntax-directed definition with semantic rules attached to grammar productions.

Type Checking

Type checking is the major task of semantic analysis. The type checker verifies that each operation in the program receives operands of permissible types according to the language's type rules; otherwise it reports a type error. It can be static (done at compile time) or dynamic (done at run time). Example rule:

Type Expressions

A type expression denotes the type of a language construct, built from basic types and type constructors:

• Basic types: int, char, boolean, real, plus type_error and void.
• Type constructors applied to type expressions:
  • Array: array(I, T) — array with index set $I$ and element type $T$.
  • Product: $T_1 \times T_2$.
  • Record: a product with field names.
  • Pointer: pointer(T).
  • Function: $D \rightarrow R$ (domain type to range type).

For example, int x[10] has type array(0..9, int), and int f(char a, char b) has type $char \times char \rightarrow int$.

Type Systems

A type system is the collection of rules that assigns type expressions to the parts of a program. It determines well-typed programs and is the basis of the type checker.

• Statically typed: types are checked at compile time (C, Java, Pascal) → catches errors early, faster code.
• Dynamically typed: types are checked at run time (Python, Lisp) → more flexible but slower and errors appear later.
• A type system is sound if it never accepts a program that would commit a type error at run time. A strongly typed language guarantees no type errors escape detection.

Type Conversion (Coercion vs Casting)

When an operator is applied to operands of different types, a conversion is needed:

• Implicit conversion (coercion) — performed automatically by the compiler, e.g. in x = i + 3.14 the integer i is converted to real (widening) before the addition.
• Explicit conversion (casting) — written by the programmer, e.g. (int) y in C.
• Widening (e.g. int → real) is usually safe; narrowing (e.g. real → int) may lose information and often needs an explicit cast.

The type checker inserts conversion operations and records the result type so that subsequent phases generate correct code.

Phases of a Compiler

A compiler is organized into a sequence of phases, each transforming the program from one representation to another. The first four constitute the analysis (front end) and the last two the synthesis (back end). The symbol table and error handler interact with all phases.

Source program
      |
[1] Lexical Analyzer  ---> tokens
      |
[2] Syntax Analyzer   ---> parse/syntax tree     <----> Symbol Table
      |                                            <----> Error Handler
[3] Semantic Analyzer ---> annotated syntax tree
      |
[4] Intermediate Code Generator ---> three-address code
      |
[5] Code Optimizer    ---> optimized IR
      |
[6] Target Code Generator ---> target machine code

1. Lexical Analysis (Scanner) — reads source characters and groups them into tokens, stripping whitespace and comments; enters identifiers into the symbol table.
2. Syntax Analysis (Parser) — groups tokens into grammatical phrases, producing a parse tree / syntax tree, and reports syntax errors.
3. Semantic Analysis — checks meaning (type checking, declaration before use) and annotates the tree; inserts type-conversion operations.
4. Intermediate Code Generation — produces a machine-independent IR, typically three-address code.
5. Code Optimization — improves the IR to make it faster/smaller without changing its meaning.
6. Target Code Generation — produces the final relocatable machine/assembly code, performing register allocation.

Output of Each Phase for position = initial + rate * 60

Lexical Analyzer (tokens):

id1 = id2 + id3 * 60

where id1=position, id2=initial, id3=rate (entered in the symbol table) and 60 is a number constant.

Syntax Analyzer (syntax tree):

        =
       / \
     id1   +
          /  \
        id2    *
              /  \
            id3   60

Semantic Analyzer — 60 (integer) is coerced to real to match rate:

        =
       / \
     id1   +
          /  \
        id2    *
              /  \
            id3   inttofloat
                     |
                     60

Intermediate Code Generator (three-address code):

t1 = inttofloat(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3

Code Optimizer:

t1 = id3 * 60.0
id1 = id2 + t1

Target Code Generator (assembly, register R1/R2):

LDF  R2, id3
MULF R2, R2, #60.0
LDF  R1, id2
ADDF R1, R1, R2
STF  id1, R1

Compiler vs Interpreter

In short: a compiler translates the entire program once and then runs the fast object code, whereas an interpreter translates and runs one statement at a time.

Given Grammar

Step 1: Eliminate Left Recursion

The rule has the form $A \rightarrow A\alpha_1 \mid A\alpha_2 \mid \beta_1 \mid \beta_2$ with

• $\alpha_1 = ab$, $\alpha_2 = c$ (left-recursive parts)
• $\beta_1 = bd$, $\beta_2 = f$ (non-left-recursive parts)

Using $A \rightarrow \beta A'$, $A' \rightarrow \alpha A' \mid \varepsilon$:

Step 2: Left Factoring

Look for common prefixes among alternatives.

• In $A \rightarrow bd\,A' \mid f\,A'$ — the first symbols are b and f, no common prefix, so no factoring needed.
• In $A' \rightarrow ab\,A' \mid c\,A' \mid \varepsilon$ — first symbols a, c, $\varepsilon$, no common prefix, so no factoring needed.

Final Grammar (left-recursion-free, left-factored)

This grammar is now suitable for top-down (LL/predictive) parsing.

Symbol Table

A symbol table is a data structure maintained by the compiler that stores information about each identifier (names of variables, functions, objects, classes, etc.) appearing in the source program. For each name it keeps attributes such as:

• name (lexeme)
• type and data type
• scope and visibility
• memory location / offset / address
• for functions: number and types of parameters, return type.

It is usually implemented as a hash table (or linked list / tree) for fast insertion and lookup.

Role in a Compiler

The symbol table is created in early phases and used by almost every phase:

1. Lexical analyzer — inserts identifiers into the table as it recognizes them.
2. Syntax analyzer — adds structural/scope information.
3. Semantic analyzer — checks declarations, scope rules, and uses stored types for type checking.
4. Intermediate / target code generation — retrieves addresses, sizes, and types to allocate storage and generate correct code.
5. Error handling — detects undeclared variables, multiple declarations, and type mismatches.

Thus the symbol table is the central repository that links the phases together and enables efficient storage and retrieval of identifier information throughout compilation.

Parse Tree vs Syntax Tree

Example for a + b * c:

Parse tree (using E -> E + T | T, T -> T * F | F, F -> id) expands every non-terminal E, T, F. The syntax tree is simply:

      +
     / \
    a   *
       / \
      b   c

The syntax tree is more convenient for semantic analysis and code generation.

Ambiguous Grammar

A grammar is ambiguous if there exists at least one string in its language that has more than one distinct parse tree (equivalently, more than one leftmost or rightmost derivation). Ambiguity is undesirable because the meaning/precedence of a construct becomes unclear and parsers cannot decide which tree to build.

Example

Consider the grammar:

For the string id + id * id, two different parse trees are possible:

Tree 1 (interpreting as id + (id * id)):

      +
     / \
   id    *
        / \
      id   id

Tree 2 (interpreting as (id + id) * id):

        *
       / \
      +   id
     / \
   id   id

Since the same string id + id * id has two distinct parse trees, the grammar is ambiguous. It can be made unambiguous by introducing precedence and associativity, e.g.

Role of the Lexical Analyzer

The lexical analyzer (scanner) is the first phase of a compiler. It reads the source program as a stream of characters and groups them into meaningful units called tokens (e.g. keywords, identifiers, constants, operators, punctuation). Its main roles are:

1. Tokenization — scan the input and produce a sequence of <token-name, attribute-value> pairs that are passed to the parser (usually one token per request, on demand).
2. Remove non-essential characters — strip out whitespace, tabs, newlines, and comments.
3. Symbol table interaction — enter identifiers and constants into the symbol table and store/return pointers to their entries.
4. Error reporting — detect and report lexical errors (e.g. illegal characters, malformed tokens) along with the line number.
5. Bookkeeping — keep track of the line number (for error messages) and may expand macros / handle preprocessor directives.

It is typically specified using regular expressions and implemented with finite automata (DFA). By separating scanning from parsing, the compiler design becomes simpler, more efficient, and more portable.

Source chars --> [ Lexical Analyzer ] --token--> [ Parser ]
                        ^  |
                        |  v
                    Symbol Table

LL(1) vs LR Parsers

Summary: LL(1) is top-down, simpler, and weaker; LR is bottom-up, more powerful, and handles a wider class of grammars but needs larger parsing tables.

Regular Expressions

A regular expression (RE) is a notation used to specify patterns of strings, i.e. it describes a regular language (a set of strings over an alphabet). Regular expressions are used in the lexical-analysis phase to define the structure of tokens such as identifiers, numbers, and keywords.

Basic rules (over alphabet $\Sigma$), with the operators in order of decreasing precedence: closure *, concatenation, alternation |:

• $\varepsilon$ is an RE denoting $\{\varepsilon\}$ (empty string).
• For each symbol $a \in \Sigma$, $a$ is an RE denoting $\{a\}$.
• If $r$ and $s$ are REs: $r \mid s$ (union), $rs$ (concatenation), $r^*$ (zero or more), and $(r)$ are REs.

Extensions: $r^+$ = one or more, $r?$ = optional.

Regular Expression for Identifiers

An identifier begins with a letter or underscore, followed by any number of letters, digits, or underscores. Define:

Then the regular expression for an identifier is:

For example, this matches count, _temp, x1, total_sum but not 9abc or a-b.

Handle and Handle Pruning in Shift-Reduce Parsing

Shift-reduce parsing is a bottom-up parsing technique that builds the parse tree from the leaves to the root by repeatedly shifting input symbols onto a stack and reducing a substring on top of the stack to a non-terminal.

Handle

A handle of a right-sentential form is a substring that matches the right-hand side of a production, and whose reduction to the left-hand-side non-terminal represents one step of a rightmost derivation in reverse. Formally, if $S \Rightarrow_{rm}^* \alpha A w \Rightarrow_{rm} \alpha \beta w$, then the production $A \rightarrow \beta$ at the position following $\alpha$ is a handle of $\alpha \beta w$. Choosing the correct handle is the central decision of a shift-reduce parser.

Handle Pruning

Handle pruning is the process of obtaining the rightmost derivation in reverse by repeatedly finding a handle and reducing (replacing) it with the non-terminal on the left of the matching production, until the start symbol is reached. The sequence of reductions traces the parse bottom-up.

Example

Grammar: $E \rightarrow E + E \mid E * E \mid id$. Parse id + id * id:

Each highlighted substring is a handle; replacing it is one step of handle pruning, ultimately reducing the input to the start symbol $E$.