Syntax-directed translation in Compiler Design - Mini Project: Build & Apply

Syntax-directed Translation Basics

📖 Scenario: You are learning how compilers convert simple arithmetic expressions into their equivalent values using syntax-directed translation.Imagine a calculator that reads expressions like 3 + 5 and computes the result by following rules linked to the expression's structure.

🎯 Goal: Build a step-by-step translation process that takes a simple arithmetic expression represented as nested dictionaries and computes its value by applying syntax-directed translation rules.

📋 What You'll Learn

Create a nested dictionary representing an arithmetic expression with operators and operands

Add a configuration variable to hold the current operator

Write a function that applies syntax-directed translation rules to compute the expression's value

Complete the translation by returning the final computed value

💡 Why This Matters

🌍 Real World

Syntax-directed translation is used in compilers to convert source code expressions into machine-understandable instructions or intermediate code.

💼 Career

Understanding syntax-directed translation is essential for compiler developers, language designers, and software engineers working on interpreters or code analysis tools.

1

Create the expression data structure

Create a variable called expression that holds this nested dictionary representing the arithmetic expression (3 + (2 * 4)) exactly as: {'op': '+', 'left': 3, 'right': {'op': '*', 'left': 2, 'right': 4}}

Compiler Design

# Create the nested dictionary called expression
# Your code here

Hint

Use a dictionary with keys 'op', 'left', and 'right'. The 'right' value is itself a dictionary for the multiplication part.

2

Add a variable for the current operator

Create a variable called current_op and set it to the operator in the top-level expression dictionary using expression['op']

Compiler Design

expression = {'op': '+', 'left': 3, 'right': {'op': '*', 'left': 2, 'right': 4}}
# Create current_op to hold the top-level operator
# Your code here

Hint

Access the 'op' key from the expression dictionary and assign it to current_op.

3

Write the syntax-directed translation function

Define a function called translate that takes a parameter expr. Inside, use if statements to check if expr is an integer and return it directly. Otherwise, recursively call translate on expr['left'] and expr['right'], then apply the operator expr['op'] to compute and return the result.

Compiler Design

expression = {'op': '+', 'left': 3, 'right': {'op': '*', 'left': 2, 'right': 4}}
current_op = expression['op']
# Define translate(expr) function to compute expression value
# Your code here

Hint

Use recursion to evaluate left and right parts, then apply the operator.

4

Complete the translation by computing the final value

Create a variable called result and set it to the value returned by calling translate(expression).

Compiler Design

expression = {'op': '+', 'left': 3, 'right': {'op': '*', 'left': 2, 'right': 4}}
current_op = expression['op']

def translate(expr):
    if isinstance(expr, int):
        return expr
    left_val = translate(expr['left'])
    right_val = translate(expr['right'])
    if expr['op'] == '+':
        return left_val + right_val
    elif expr['op'] == '*':
        return left_val * right_val

# Compute the final result by calling translate on expression
# Your code here

Hint

Call the translate function with the expression and store the output in result.

Practice

1. What is the main purpose of syntax-directed translation in compiler design?

easy

A. To manage memory allocation during runtime

B. To optimize machine code for faster execution

C. To check syntax errors in source code

D. To associate grammar rules with actions for translation

Solution

1. Step 1: Understand the role of syntax-directed translation

   It connects grammar rules with specific actions or computations to translate source code.

2. Step 2: Differentiate from other compiler tasks

   Unlike optimization or error checking, it focuses on translation based on syntax structure.

3. Final Answer:

   To associate grammar rules with actions for translation -> Option D

4. Quick Check:

   Syntax-directed translation = associate grammar with actions [OK]

Hint: Focus on linking grammar rules to translation actions [OK]

Common Mistakes:

• Confusing translation with optimization
• Thinking it only checks syntax errors
• Assuming it manages runtime memory

2. Which of the following is the correct way to write a semantic rule in syntax-directed translation for an expression E -> E1 + T that computes the value of E?

easy

A. val(E) = val(E1) * val(T)

B. E = E1 + T

C. E.val = E1.val + T.val

D. E.val = E1.val - T.val

Solution

1. Step 1: Identify the semantic rule for addition

   The rule should compute the value of E by adding values of E1 and T.

2. Step 2: Match the correct syntax for semantic rules

   Using E.val = E1.val + T.val correctly assigns the computed value.

3. Final Answer:

   E.val = E1.val + T.val -> Option C

4. Quick Check:

   Semantic rule for addition uses '+' operator [OK]

Hint: Semantic rules use attribute assignments like X.val = ... [OK]

Common Mistakes:

• Using assignment without '.val' attributes
• Using wrong operators like '*' or '-'
• Writing rules as expressions without assignment

3. Given the grammar rule and semantic actions:
E -> E1 + T { E.val = E1.val + T.val }
T -> digit { T.val = digit.lexval }
What is the value of E.val for input 3 + 5?

medium

A. 8

B. 35

C. Error

D. 0

Solution

1. Step 1: Evaluate terminal values

   For digits 3 and 5, digit.lexval gives 3 and 5 respectively.

2. Step 2: Apply semantic rule for addition

   Using E.val = E1.val + T.val, compute 3 + 5 = 8.

3. Final Answer:

   8 -> Option A

4. Quick Check:

   3 + 5 = 8 [OK]

Hint: Add digit values as per semantic rules [OK]

Common Mistakes:

• Concatenating digits as strings (35)
• Assuming syntax error without reason
• Returning zero without calculation

4. Identify the error in the following semantic rule for the grammar E -> E1 + T:
{ E.val = E1.val - T.val }

medium

A. Missing attribute assignment for E1

B. Wrong operator used; should be addition instead of subtraction

C. Semantic rule should be outside braces

D. No error; rule is correct

Solution

1. Step 1: Check grammar operation

   The grammar rule uses '+' operator, so semantic rule must reflect addition.

2. Step 2: Identify mismatch in semantic action

   The semantic rule uses '-', which contradicts the grammar's '+' operator.

3. Final Answer:

   Wrong operator used; should be addition instead of subtraction -> Option B

4. Quick Check:

   Operator in semantic rule must match grammar [OK]

Hint: Semantic operator must match grammar operator [OK]

Common Mistakes:

• Ignoring operator mismatch
• Thinking braces placement causes error
• Assuming missing attribute assignment

5. Consider a syntax-directed translation scheme that computes the value of arithmetic expressions with addition and multiplication:

E -> E1 + T { E.val = E1.val + T.val }
E -> T { E.val = T.val }
T -> T1 * F { T.val = T1.val * F.val }
T -> F { T.val = F.val }
F -> digit { F.val = digit.lexval }

What is the computed value of 2 + 3 * 4 using this scheme?

hard

A. 14

B. 20

C. 24

D. Error due to ambiguity

Solution

1. Step 1: Apply operator precedence in grammar

   Multiplication (T -> T1 * F) has higher precedence than addition (E -> E1 + T).

2. Step 2: Compute multiplication first

   Calculate 3 * 4 = 12, then add 2: 2 + 12 = 14.

3. Final Answer:

   14 -> Option A

4. Quick Check:

   Multiplication before addition = 14 [OK]

Hint: Multiply before adding as per grammar rules [OK]

Common Mistakes:

• Adding before multiplying (2+3=5, then 5*4=20)
• Multiplying all digits (2*3*4=24)
• Assuming ambiguity error