GTU 3170701 Compiler Design (CD) Summer 2025 Solved Paper & Solutions

A compiler translates the whole source program into machine code in one go, before the program runs. An interpreter translates and runs the program one statement at a time.

Both are translators that take a high-level language program as input and both report errors in it.

Left factoring is a change made to a grammar when two or more productions of a non-terminal start with the same symbols (a common prefix). The common prefix is taken out and the different endings are moved to a new non-terminal.

Rule:

Significance:

• A top-down parser sees only the next input symbol. With a common prefix it cannot decide which production to use.
• After left factoring the choice is delayed until enough input has been seen, so no backtracking is needed.
• It is a required step to make a grammar suitable for predictive (LL(1)) parsing.

Example:

Both productions of S start with iEtS. Taking it out gives:

Now the parser reads iEtS first and then chooses eS or ε by looking at the next symbol.

A compiler works in six phases. They are grouped into two parts: the front end and the back end.

The symbol table and the error handler work with all six phases.

Front end

The front end depends on the source language and not on the target machine.

1. Lexical analysis: reads characters and groups them into tokens.
2. Syntax analysis: checks the grammar and builds a parse tree.
3. Semantic analysis: checks meaning, such as types, and adds type conversions.
4. Intermediate code generation: produces a machine-independent code, such as three address code.

Back end

The back end depends on the target machine and not on the source language.

5. Code optimisation: improves the intermediate code so that it runs faster or uses less memory.
6. Code generation: produces the target assembly or machine code and assigns registers.

Example

Statement: position = initial + rate * 60, where all three variables are of type float.

Intermediate code:

After code optimisation:

After code generation:

Significance

• Front end: it finds the errors in the program and gives a code that does not depend on any machine. To support a new machine, the same front end is used again.
• Back end: it gives fast and small target code for one machine. To support a new language, the same back end is used again.
• For $m$ languages and $n$ machines, only $m$ front ends and $n$ back ends are needed, in place of $m \times n$ full compilers.

1. Lexeme: a sequence of characters in the source program that matches the pattern of a token. Example: in count = 10, the lexeme count belongs to the token id.

2. Handle pruning: a handle is a substring that matches the right side of a production and whose reduction is one step of a rightmost derivation in reverse. Handle pruning means finding the handle and reducing it, again and again, until the start symbol is reached.

3. Viable prefixes: the prefixes of a right sentential form that can appear on the stack of a shift-reduce parser. They never go past the right end of the handle.

Here $\mid$ means "or" and $^\ast$ means "zero or more times".

1. Starts and ends with different symbols. The string starts with a and ends with b, or starts with b and ends with a. Anything can come in between.

2. Even number of a. The a's are taken in pairs, and any number of b's can come before, between and after them.

3. Odd number of b. First take one b, then take the remaining b's in pairs.

4. At least two times a. Two a's must be present, and anything can come before, between and after them.

Quick check: for the second expression, the strings bb, aba and baab are accepted, and the string ab is not accepted.

A grammar is LL(1) if its parsing table has at most one production in every cell. The table is built from the FIRST and FOLLOW sets.

Applying the rules:

• S → aABb goes under a.
• A → c goes under c. A → ε goes under d and b, which are FOLLOW(A).
• B → d goes under d. B → ε goes under b, which is FOLLOW(B).

Empty cells are error entries.

A parse tree shows how the input is derived from the grammar. A syntax tree is a short form of the parse tree that shows only operators and operands.

Example for a + b:

An attribute is a value attached to a grammar symbol, such as its type or its value.

An inherited attribute of a non-terminal is an attribute whose value is calculated from the attributes of its parent or its siblings in the parse tree. The information moves down or sideways in the tree.

It is the opposite of a synthesized attribute, whose value comes from the children.

Example: a declaration such as int a, b.

Here L.in is an inherited attribute. L gets the type from its sibling T, and passes it down to L1.

So the type integer reaches both a and b, and both are entered in the symbol table as integers.

A grammar is SLR(1) if its SLR parsing table has no cell with two actions.

Both cells have two reduce actions. This is a reduce-reduce conflict. The parser cannot decide whether to reduce by A → ε or by B → ε.

A sentinel is a special character placed at the end of each half of the input buffer. It is a character that cannot be part of the source program, usually eof.

The lexical analyser reads the input through a buffer of two halves. Without a sentinel, every move of the forward pointer needs two tests: "is this the end of the buffer?" and "which character is this?". With a sentinel, one test is enough in most cases.

Example:

When the forward pointer reads eof at the end of a half, the other half is loaded. If eof comes anywhere else, the input is over.

When a parser finds an error, it should report it and continue, so that more errors can be found in the same run. The four strategies are:

1. Panic mode recovery: the parser skips input symbols one by one until it finds a synchronising token, such as a semicolon or a closing bracket. It is simple and never goes into an infinite loop, but it may skip a lot of input.

2. Phrase level recovery: the parser makes a small local correction to the remaining input. For example, it replaces a comma by a semicolon, or inserts a missing semicolon.

3. Error productions: productions for common mistakes are added to the grammar. When such a production is used, the parser prints a proper error message for that mistake.

4. Global correction: the parser finds the smallest number of changes (insert, delete, replace) that turn the wrong program into a correct one. It gives the best result, but it costs too much time and space, so it is studied mostly in theory.

Three address code is an intermediate code in which each statement has at most one operator on the right side and at most three addresses. It can be stored in three forms.

Example statement: x = (a + b) * (c - d)

Its three address code:

1. Quadruples

A quadruple is a record with four fields: op, arg1, arg2 and result. Temporary names such as t1 are stored in the result field.

2. Triples

A triple has three fields: op, arg1 and arg2. There is no result field. A result is referred to by the number of the triple that calculates it, so no temporary names are needed.

3. Indirect triples

Indirect triples use the same triple table and one more list of pointers to the triples. The pointer list gives the order in which the statements run.

Comparison

Moving statements is common in code optimisation. So quadruples and indirect triples suit an optimising compiler better than plain triples.

A dangling reference is a reference (a pointer) to a memory location that has already been freed. The pointer still holds the old address, but that memory no longer belongs to the program.

It happens when storage is deallocated while a pointer to it is still in use.

Another case is a function that returns the address of its local variable. The variable is removed when the function returns.

Using a dangling reference gives wrong results or crashes the program.

An LR parser decides its action from the state on top of the stack and the next input symbol. A conflict occurs when one cell of the parsing table gets two actions. There are two types.

1. Shift-reduce conflict

The parser cannot decide whether to shift the next symbol or to reduce by a production. It occurs when one state has a complete item and also an item with the dot before a terminal.

Example: the grammar for if-then-else. One state contains

On input e, the first item says reduce and the second says shift. This is the dangling else problem.

2. Reduce-reduce conflict

The parser cannot decide which of two productions to use for a reduction. It occurs when one state has two complete items with a common lookahead symbol.

Example: a state that contains

with the same symbol in FOLLOW(A) and FOLLOW(B).

Removing conflicts: rewrite the grammar, use a stronger parser such as LALR or canonical LR, or give precedence and associativity rules to the parser. There is no shift-shift conflict.

A recursive descent parser is a top-down parser with one procedure for each non-terminal. A procedure tries the productions of its non-terminal, matches terminals with the input, and calls other procedures for non-terminals.