Coursify

Compiler Design (CD)

PYQ Analysis and Exam Preparation

50 mins

Comprehensive analysis of historical exam patterns for Module 3. Master the recurring theoretical comparisons, practice semantic action tracing, and review frequently tested objective questions.

Learning Goals

  • Identify the highest-yield topics that consistently appear in university examinations.
  • Master the step-by-step execution of Semantic Action tracing problems.
  • Construct annotated parse trees for arithmetic expressions as required by standard grading rubrics.
  • Review and memorize key definitions for objective (2-mark) questions.

📊 Exam Weightage & Pattern Analysis

Module 3 (Semantic Analysis & Run-Time Environments) is a heavily theoretical module, but it features highly predictable and scoring patterns. Based on recent examination cycles, you can consistently expect 15 to 20 marks from this module if you master a specific set of architectural comparisons and syntax-directed translation (SDT) diagrams.

Module 3: High-Yield Topic Frequency

Analysis of historically tested concepts in descriptive exam sections.

The SDD comparison (S-Attributed vs L-Attributed) is the single most tested question.

Exam Strategy: The 'Differentiate' Question

The comparison between S-Attributed and L-Attributed Syntax-Directed Definitions (SDDs) is a guaranteed 7-mark question. Do not just write paragraphs; examiners look for a 3-column table and at least one mathematical grammar example for each to award full marks.

Part A: High-Yield Objective Concepts

Mechanism: The actual parameter's value is copied into the formal parameter's local memory space (Activation Record).

Behavior: Any modifications made to the formal parameter inside the function do not affect the original variable in the caller's scope.

Usage: Standard in C (for non-pointers) and Java (for primitives).

Numerical Walkthrough: Semantic Action Tracing (7 Marks)

  1. 1
    Step 1

    Consider the following grammar and semantic actions:

    1. S→AS{print(1)}S \to AS \{ \text{print}(1) \}
    2. S→AB{print(2)}S \to AB \{ \text{print}(2) \}
    3. A→a{print(3)}A \to a \{ \text{print}(3) \}
    4. B→bC{print(4)}B \to bC \{ \text{print}(4) \}
    5. B→dB{print(5)}B \to dB \{ \text{print}(5) \}
    6. C→e{print(6)}C \to e \{ \text{print}(6) \}

    Goal: Trace and find the exact output string for the input aadbe.

  2. 2
    Step 2

    We must first perform a derivation to build the tree for aadbe. Top-down expansion looks like this:

  3. 3
    Step 3

    Because these are placed at the end of the productions, they act as synthesized actions. We evaluate them as the parser reduces the handles from bottom-left to top-right:

    1. Reduce a to AA: print(3)
    2. Reduce a to AA: print(3)
    3. Reduce e to CC: print(6)
    4. Reduce bC to BB: print(4)
    5. Reduce dB to BB: print(5)
    6. Reduce ABAB to SS: print(2)
    7. Reduce ASAS to SS: print(1)
  4. 4
    Step 4

    By listing the printed values in the exact order of reduction, the final output string is:

    3 3 6 4 5 2 1

    Exam Tip: Always explicitly state that semantic actions at the end of a rule are evaluated post-order (bottom-up).

Design Walkthrough: Infix to Prefix SDT (7 Marks)

  1. 1
    Step 1

    Construct a syntax-directed translation scheme that translates arithmetic expressions from infix to prefix notation. Draw the annotated parse tree for the expression 9 - 5 + 2.

  2. 2
    Step 2

    We need an SDD using synthesized attributes (a string attribute called val) that concatenates the operator before the operands.

    1. E→E1+T{E.val=’+’∥E1.val∥T.val}E \to E_1 + T \quad \{ E.val = \text{'+'} \parallel E_1.val \parallel T.val \}
    2. E→E1−T{E.val=’-’∥E1.val∥T.val}E \to E_1 - T \quad \{ E.val = \text{'-'} \parallel E_1.val \parallel T.val \}
    3. E→T{E.val=T.val}E \to T \quad \{ E.val = T.val \}
    4. T→num{T.val=num.lexval}T \to \text{num} \quad \{ T.val = \text{num.lexval} \}
  3. 3
    Step 3

    Standard arithmetic grammar evaluates left-to-right. For the string 9 - 5 + 2, the subtraction must be grouped first into a subtree: (9 - 5) + 2.

  4. 4
    Step 4

    Here is the final tree required for full marks. The root node yields the final prefix string + - 9 5 2.

Common Grading Trap: SDT Trees

When drawing annotated parse trees, students often forget to write the actual evaluated attribute inside the node (e.g., writing just E instead of E (val = '- 9 5')). Graders will deduct marks if the intermediate synthesized values are not visibly traced on the tree.

Part B: Theoretical Preparation Strategies (7-Marks)

Knowledge Check

Question 1 of 3
Q1Single choice

Which of the following attributes are evaluated in a strictly bottom-up manner?

Previous

Next