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

Phases of a Compiler

A compiler translates a source program into an equivalent target program through a sequence of phases, grouped into the analysis (front end) and synthesis (back end). Each phase consults the symbol table and an error handler.

Source program
     |
[1] Lexical Analyzer (Scanner)
     |   -> tokens
[2] Syntax Analyzer (Parser)
     |   -> syntax (parse) tree
[3] Semantic Analyzer
     |   -> annotated tree
[4] Intermediate Code Generator
     |   -> three-address code
[5] Code Optimizer
     |   -> optimized IR
[6] Target Code Generator
     |
Target program

(Symbol Table and Error Handler interact with all phases.)

Description of each phase

1. Lexical analysis – groups characters into tokens (identifiers, operators, constants) and removes whitespace/comments.
2. Syntax analysis – checks that tokens form valid sentences per the grammar and builds a parse/syntax tree.
3. Semantic analysis – performs type checking, scope resolution and inserts coercions.
4. Intermediate code generation – produces a machine-independent IR such as three-address code.
5. Code optimization – improves the IR (removes redundancy, folds constants) without changing meaning.
6. Code generation – produces target/assembly code, assigns registers.

Output of each phase for position = initial + rate * 60

Lexical analysis (tokens):

id1 = id2 + id3 * 60

where id1=position, id2=initial, id3=rate, and =, +, * are operators, 60 is a number.

Syntax analysis (syntax tree):

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

Semantic analysis – 60 (integer) is converted to real to match the real operands:

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

Intermediate code (three-address code):

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

Code optimization:

t1 = id3 * 60.0
id1 = id2 + t1

Code generation (assembly):

MOVF  id3, R2
MULF  #60.0, R2
MOVF  id2, R1
ADDF  R2, R1
MOVF  R1, id1

LR(1) / Canonical LR Parsing Table

Augmented grammar:

0. S' -> S
1. S  -> C C
2. C  -> c C
3. C  -> d

FIRST sets

$FIRST(S)=FIRST(C)=\{c,d\}$.

Canonical collection of LR(1) item sets

I0: S' -> .S, $ ; S -> .CC, $ ; C -> .cC, c/d ; C -> .d, c/d

I1 = goto(I0,S): S' -> S., $ (accept)

I2 = goto(I0,C): S -> C.C, $ ; C -> .cC, $ ; C -> .d, $

I3 = goto(I0,c): C -> c.C, c/d ; C -> .cC, c/d ; C -> .d, c/d

I4 = goto(I0,d): C -> d., c/d

I5 = goto(I2,C): S -> CC., $

I6 = goto(I2,c): C -> c.C, $ ; C -> .cC, $ ; C -> .d, $

I7 = goto(I2,d): C -> d., $

I8 = goto(I3,C): C -> cC., c/d

I9 = goto(I6,C): C -> cC., $

Gotos: goto(I3,c)=I3, goto(I3,d)=I4; goto(I6,c)=I6, goto(I6,d)=I7.

Parsing table

(sN=shift to N, rN=reduce by rule N, acc=accept)

Parsing the string cdd$

The string cdd is accepted (valid).

Directed Acyclic Graph (DAG)

A DAG is a directed graph with no directed cycles, used to represent the structure of basic blocks/expressions. Unlike a syntax tree, common sub-expressions are shared (a node is created only once and reused), so the DAG exposes redundancy and helps in optimization. Interior nodes are operators; leaves are identifiers/constants.

Expression: a + a * (b - c) + (b - c) * d

The common sub-expression (b - c) is computed once and shared.

DAG (described): a leaf b and c feed a - node giving t1. This t1 is used by both a * with a (t2 = a * t1) and a * with d (t4 = t1 * d). Then t3 = a + t2, and finally t5 = t3 + t4.

Three-Address Code

t1 = b - c
t2 = a * t1
t3 = a + t2
t4 = t1 * d
t5 = t3 + t4

Quadruples

(op, arg1, arg2, result)

Triples

(temporaries referenced by instruction index (n))

Compiler vs Interpreter

Grammar: A -> Aab | Ac | bd | f

Step 1: Eliminate left recursion

The rule has the form A -> A\alpha | \beta with $\alpha \in \{ab, c\}$ and $\beta \in \{bd, f\}$.

Using the standard transformation A -> \beta A', A' -> \alpha A' | \epsilon:

A  -> bd A' | f A'
A' -> ab A' | c A' | ε

Step 2: Left factoring

In the A productions, both alternatives bd A' and f A' begin with different symbols (b vs f), so there is no common prefix — no left factoring is needed for A.

For A', the alternatives ab A', c A', ε also have distinct first symbols (a, c), so no common prefix exists.

Final grammar (left-recursion-free, already left-factored)

A  -> bd A' | f A'
A' -> ab A' | c A' | ε

Symbol Table

A symbol table is a data structure maintained by the compiler that stores information about each identifier (variables, constants, functions, types) appearing in the source program. Typical attributes stored are the name, type, scope, storage location/offset, size, and parameter details.

Role in a compiler

• Lexical analysis – enters identifiers into the table as tokens are recognized.
• Syntax & semantic analysis – used for type checking, scope resolution and detecting undeclared/duplicate identifiers.
• Intermediate & code generation – provides addresses/offsets and type/size information for generating correct code.
• Optimization – supplies attribute information used during analysis.

It supports two main operations: insert (add a new entry) and lookup (retrieve an entry). It is commonly implemented using a hash table for fast access, or lists/trees. Thus the symbol table acts as a central repository accessed by almost all phases of the compiler.

Parse Tree vs Syntax Tree

Example: for a + b * c

Parse tree expands through E -> E + T, T -> T * F, F -> id, etc., showing all E, T, F nodes.

Syntax tree:

      +
     / \
    a   *
       / \
      b   c

Ambiguous Grammar

A grammar is ambiguous if there exists at least one string in its language that has more than one distinct parse tree (or equivalently, more than one leftmost/rightmost derivation).

Example

Grammar: E -> E + E | E * E | id

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

Parse tree 1 (multiplication first — correct precedence):

      +
     / \
   id   *
       / \
     id   id

Parse tree 2 (addition first):

        *
       / \
      +   id
     / \
   id   id

Since the same string yields two parse trees, the grammar is ambiguous. Ambiguity is undesirable because it makes parsing non-deterministic; it can be removed by introducing precedence/associativity (e.g. using E -> E + T | T, T -> T * F | F, F -> id).

Role of the Lexical Analyzer (Scanner)

The lexical analyzer 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. identifiers, keywords, constants, operators, punctuation).

Main roles / functions

• Tokenization – scans input and produces <token-name, attribute-value> pairs for the parser.
• Removing whitespace and comments – discards blanks, tabs, newlines and comments.
• Symbol table interaction – enters identifiers/constants into the symbol table.
• Error reporting – detects illegal characters/tokens and reports their line number.
• Macro/preprocessing & line counting in some implementations.

It works on demand: the parser calls getNextToken(), and the scanner returns the next token. It typically uses regular expressions specified by the language and is implemented as a finite automaton (DFA), often generated by tools like LEX/Flex.

LL(1) vs LR Parsers

Regular Expressions

A regular expression (RE) is a notation for describing regular languages — the set of strings recognized by finite automata. They are used in lexical analysis to specify the patterns of tokens.

Operations

Given REs r and s:

• Union: r | s
• Concatenation: r s
• Kleene closure (zero or more): r*
• Positive closure (one or more): r+

Regular expression for identifiers

An identifier begins with a letter or underscore, followed by zero or more letters, digits, or underscores:

letter -> A | B | ... | Z | a | b | ... | z
digit  -> 0 | 1 | ... | 9

identifier -> ( letter | _ ) ( letter | digit | _ )*

Compactly: [A-Za-z_][A-Za-z0-9_]*

Handle and Handle Pruning in Shift-Reduce Parsing

Handle

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

Handle Pruning

Handle pruning is the process of repeatedly finding a handle and reducing it (replacing it by the corresponding non-terminal) until the start symbol is reached. It produces a rightmost derivation in reverse and is the basis of bottom-up (shift-reduce) parsing.

Example

Grammar: E -> E + E | E * E | id, input id + id * id:

In a shift-reduce parser, symbols are shifted onto the stack until a handle appears on top, which is then reduced (pruned).