2080

CSC376 · TU past paper

Compiler Design and Construction 2080 question paper

The complete TU 2080 exam paper for Compiler Design and Construction (CSC376), all 12 questions with solved model answers written to the mark scheme.

Past Papers2081.120812080207820762075

Tap a question to open its answer.

  1. 110 marksNumericalTop-down parsingAnswer

    Differentiate between one-pass and multi-pass compiler. Construct the LL(1) parsing table for the following grammar.S→ABCDS \rightarrow ABCDS→ABCDA→a∣εA \rightarrow a | \varepsilonA→a∣εB→bB \rightarrow bB→bC→0∣εC \rightarrow 0 | \varepsilonC→0∣εD→d∣εD \rightarrow d | \varepsilonD→d∣ε[10]

    Feature One-Pass Compiler Multi-Pass Compiler --------- Number of scans Scans source exactly once Scans source/intermediate form multiple times Speed Faster compilation Slower (multiple traversals) Memory usage Requires less memory Requi...

  2. 210 marksNumericalSpecification and Recognition of tokensAnswer

    How does a Lexical Analyzer recognize a token? Give an example to make it clear. Convert the regular expression $a(a+b)(b+c)⭒a# to DFA.[10]

    --- A Lexical Analyzer (scanner) reads the source program character by character from left to right, groups sequences of characters into meaningful units called lexemes, and classifies each lexeme into a token by matching it against pred...

  3. 310 marksNumericalLR parsingAnswer

    Construct the LR(1) parsing table for the following grammar.S→AaAbS \rightarrow AaAbS→AaAbA→BbBaA \rightarrow BbBaA→BbBaA→εA \rightarrow \varepsilonA→εB→εB \rightarrow \varepsilonB→ε[10]

    Number the productions: - (0) $S' \to S$ - (1) $S \to AaAb$ - (2) $A \to BbBa$ - (3) $A \to \varepsilon$ - (4) $B \to \varepsilon$ Terminals: $$a, b, $ $$. Non-terminals: $S', S, A, B$. - $\text{FIRST}(B) = {\varepsilon}$ - $\text{FIR...

  4. 45 marksSyntax directed definitionsAnswer

    Describe about syntax directed translation with an example. [5]

    Syntax Directed Translation (SDT) refers to a method of compiler implementation where the source language translation is completely driven by the parser. In SDT, a parse tree or syntax tree is constructed and the values of attributes at ...

  5. 55 marksNumericalLR parsingAnswer

    Given the following grammar with SLR parsing table, test whether the string "int * (int + int)" will be accepted or rejected.

    $$ \begin{aligned} E &\to T + E \quad \ldots (1) \ E &\to T \quad \ldots (2) \ T &\to int * T \quad \ldots (3) \ T &\to int \quad \ldots (4) \ T &\to (E) \quad \ldots (5) \end{aligned} $$

    $$\begin{array}{|c|c|c|c|c|c|c||c|c|}\hline & \text{ACTION} & & & & & & \text{GOTO} & \ \hline \text{STATE} & \text{int} & * & + & ( & ) & $ & E & T \ \hline 1 & S5 & & & S4 & & & 2 & 3 \ \hline 2 & & & & & & \text{ACC} & & \ \hline 3 & & S6 & & & R2 & R2 & & \ \hline 4 & S5 & & & S4 & & & 7 & 3 \ \hline 5 & & S8 & R4 & & R4 & R4 & & \ \hline 6 & S5 & & & S4 & & & 9 & 3 \ \hline 7 & & & & & S10 & & & \ \hline 8 & S5 & & & S4 & & & & 11 \ \hline 9 & & & & & R1 & R1 & & \ \hline 10 & & & R5 & & R5 & R5 & & \ \hline 11 & & & R3 & & R3 & R3 & & \ \hline \end{array} $$

    Grammar: - (1) $E \rightarrow T + E$ - (2) $E \rightarrow T$ - (3) $T \rightarrow int T$ - (4) $T \rightarrow int$ - (5) $T \rightarrow (E)$ Input string: int ( int + int ) $ Parsing table (as given): STATE int + ( ) $ E T -------------...

  6. 65 marksBasic blocks and flow graphsAnswer

    How do you recognize basic block? Discuss about the factors that affect code generator. [5]

    --- A basic block is a sequence of consecutive statements in which flow of control enters at the beginning and leaves at the end without any halt or possibility of branching except at the end. First, we identify leaders (the first statem...

  7. 75 marksNumericalTop-down parsingAnswer

    Find the FIRST and FOLLOW of all the non terminals in following grammar. S→aAbcD∣εS \rightarrow aAbcD | \varepsilonS→aAbcD∣εA→SD∣εA \rightarrow SD | \varepsilonA→SD∣εC→SaC \rightarrow SaC→SaD→aBD∣εD \rightarrow aBD | \varepsilonD→aBD∣ε[5]

    Grammar productions: $$S \rightarrow aAbcD \mid \varepsilon$$ $$A \rightarrow SD \mid \varepsilon$$ $$C \rightarrow Sa$$ $$D \rightarrow aBD \mid \varepsilon$$ Non-terminals present in productions: $S, A, C, D$ (and $B$ appears on the RH...

  8. 85 marksCode OptimizationAnswer

    Why code optimization is needed? Describe any two techniques for loop optimization. [5]

    Code optimization is the process of transforming a program to make it more efficient without changing its output or meaning. It is needed because: - Reduces space and increases speed: Optimization reduces the memory consumed by the progr...

  9. 95 marksThree-address codeAnswer

    What is three-address code? How high level code is converted to three address code? Illustrate with an example. [5]

    Three-address code is an intermediate code representation where each instruction uses at most three addresses: two for operands and one for the result. Each instruction in three-address code is described as a 4-tuple: (operator, operand1...

  10. 105 marksRun-time storage managementAnswer

    What is activation tree? Define type checking system with examples. [5]

    Activation Tree and Type Checking System

    Part 1: Activation Tree

    An activation tree is a tree data structure used to represent the sequence and nesting of procedure/function calls during the execution of a program at runtime.

    Key Properties:

    • Each node in the tree represents an activation (call) of a procedure.
    • The root represents the activation of the main program.
    • If procedure A calls procedure B, then the node for B is a child of the node for A.
    • The execution of a called procedure must complete before the calling procedure resumes (LIFO order), which is why a stack is used to manage activations at runtime.

    Example:

    Consider the following program:

    main() {
    A();
    B();
}
A() {
    C();
}
B() { }
C() { }

    The activation tree is:

            main
       /    \
      A      B
      |
      C
    • main calls A and B sequentially.
    • A calls C.
    • The left-to-right order of children represents the order of calls.

    Note: The activation tree directly corresponds to the stack storage allocation model, where activation records are pushed and popped in LIFO order as activations begin and end.

    Part 2: Type Checking System

    Definition:

    A type checking system is a component of the semantic analyzer in a compiler that verifies whether the operands and operators in expressions are type-compatible according to the rules of the source language. It ensures that operations are applied to correct types of data, preventing type errors.

    As per the notes: "Type-checking is an important part of semantic analyzer."

    Types of Type Checking:

    TypeDescription
    Static Type CheckingPerformed at compile time
    Dynamic Type CheckingPerformed at runtime

    Type Checking Rules:

    1. Type of an expression is determined by the types of its sub-expressions.
    2. If an operator is applied to incompatible types, a type error is reported.
    3. Type coercion (implicit conversion) may be applied where allowed.

    Examples:

    Example 1: Arithmetic Expression

    int a = 5;
float b = 3.2;
float c = a + b;   // Valid: int is coerced to float
    • Type checker detects a is int and b is float.
    • Applies widening coercion: int → float.
    • Result type is float. No error.

    Example 2: Type Mismatch Error

    int x = 10;
char *p = x;   // Type Error: cannot assign int to pointer
    • Type checker detects incompatible types (int vs char *).
    • Reports a type error at compile time.

    Example 3: Function Call Type Checking

    int add(int a, int b) { return a + b; }
add(3, "hello");   // Type Error: second argument is string, expected int
    • Type checker verifies that actual parameter types match formal parameter types.
    • Reports a type mismatch error.

    Type Checking System Summary:

    Source Code
    |
    v
Lexical Analyzer --> Tokens
    |
    v
Syntax Analyzer --> Parse Tree
    |
    v
Semantic Analyzer (Type Checker)
    --> Checks type compatibility
    --> Reports type errors
    --> Annotates parse tree with type info
    |
    v
Intermediate Code Generator

    The type checking system ensures type safety and produces type-annotated intermediate representations for further compilation phases.

  11. 115 marksInformation provided by Symbol TableAnswer

    What are the advantages of intermediate code? What types of information are provided by symbol table? [5]

    --- Intermediate code is a machine-independent representation generated between the front-end and back-end of a compiler. Its main advantages are: 1. Machine Independence Intermediate code is not tied to any specific target machine. The ...

  12. 125 marksAnnotated Parse TreeAnswer

    What is annotated parse tree? Define S-attributed grammar with an example. [5]

    --- An annotated parse tree is a parse tree in which each node is labeled with its grammar symbol along with the values of its associated attributes. In Syntax-Directed Translation (SDT), semantic rules are used to compute attribute valu...

Keep going

Important questions + predictions
Full syllabusFlashcards and practice

Other papers

2081.1 paper2081 paper2078 paper2076 paper2075 paper