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

Building a Simple Syntax-Directed Definition

📖 Scenario: You are learning how compilers use syntax-directed definitions to assign meaning to parts of a program. Imagine you want to create a simple system that calculates the value of arithmetic expressions using rules attached to grammar parts.

🎯 Goal: Build a step-by-step syntax-directed definition that assigns values to arithmetic expressions using attributes and rules.

📋 What You'll Learn

Create a grammar rule with attributes

Define synthesized attributes for expression values

Write semantic rules to compute values

Combine rules to evaluate a full expression

💡 Why This Matters

🌍 Real World

Syntax-directed definitions are used in compilers to attach meaning to program syntax and compute values or generate code.

💼 Career

Understanding syntax-directed definitions is essential for compiler developers, language designers, and anyone working on programming language tools.

1

Define the grammar rule for an expression

Create a grammar rule called Expr that can be a number or an addition of two expressions. Write it as Expr -> number and Expr -> Expr + Expr.

Compiler Design

# Define the grammar rules for Expr
# Your code here

Hint

Write two lines defining the grammar rules exactly as shown.

2

Add synthesized attribute for expression value

Add a synthesized attribute called val to the Expr rule to hold the computed value of the expression.

Compiler Design

Expr -> number
Expr -> Expr + Expr
# Add synthesized attribute val to Expr
# Your code here

Hint

Declare the attribute val for the non-terminal Expr.

3

Write semantic rules to compute values

Write semantic rules for the grammar: for Expr -> number, set Expr.val = number.lexval; for Expr -> Expr1 + Expr2, set Expr.val = Expr1.val + Expr2.val. Use these exact variable names.

Compiler Design

Expr.val
Expr -> number
Expr -> Expr + Expr
# Add semantic rules for Expr.val
# Your code here

Hint

Write semantic rules in braces exactly as shown, using Expr1 and Expr2 for the two subexpressions.

4

Combine grammar and semantic rules into a syntax-directed definition

Combine the grammar rules and semantic rules into a complete syntax-directed definition for Expr with attributes and semantic actions as shown in previous steps.

Compiler Design

Expr.val
Expr -> number { Expr.val = number.lexval }
Expr -> Expr1 + Expr2 { Expr.val = Expr1.val + Expr2.val }
# Finalize the syntax-directed definition
# Your code here

Hint

Ensure the full syntax-directed definition is present with grammar and semantic rules combined.

Practice

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

easy

A. To associate computations with grammar rules using attributes

B. To optimize machine code after compilation

C. To manage memory allocation during program execution

D. To handle user input and output operations

Solution

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

   They link grammar rules to computations by associating attributes with grammar symbols.

2. Step 2: Identify the correct purpose

   This linking helps in semantic analysis and translation during compilation.

3. Final Answer:

   To associate computations with grammar rules using attributes -> Option A

4. Quick Check:

   Syntax-directed definitions = associate computations with grammar rules [OK]

Hint: Remember: syntax-directed means linking syntax to actions [OK]

Common Mistakes:

• Confusing syntax-directed definitions with code optimization
• Thinking they handle runtime memory management
• Assuming they manage input/output operations

2. Which of the following is the correct syntax to define an attribute in a syntax-directed definition?

easy

A. A.attr = B.attr + 1

B. attr A = B + 1

C. A := B + 1

D. define A.attr as B + 1

Solution

1. Step 1: Recall attribute assignment syntax

   Attributes are assigned using dot notation like A.attr = ....

2. Step 2: Match correct syntax

   A.attr = B.attr + 1 uses the correct form: A.attr = B.attr + 1.

3. Final Answer:

   A.attr = B.attr + 1 -> Option A

4. Quick Check:

   Attribute assignment uses dot and equals sign [OK]

Hint: Look for dot notation and equals sign for attributes [OK]

Common Mistakes:

• Using := instead of = for attribute assignment
• Writing attribute declarations like variables
• Using keywords like 'define' incorrectly

3. Given the syntax-directed definition:

S -> A B
A.val = 2
B.val = 3
S.val = A.val + B.val

What is the value of S.val after evaluation?

medium

A. Error

B. 6

C. 23

D. 5

Solution

1. Step 1: Identify attribute values for A and B

   A.val is 2 and B.val is 3 as given.

2. Step 2: Calculate S.val using the rule

   S.val = A.val + B.val = 2 + 3 = 5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   S.val = 2 + 3 = 5 [OK]

Hint: Add attribute values as per rules to find result [OK]

Common Mistakes:

• Concatenating numbers as strings (23 instead of 5)
• Mixing up attribute names
• Assuming syntax error without checking values

4. Consider this syntax-directed definition snippet:

E -> E1 + T
E.val = E1.val + T.val
E1.val = 5
T.val = 7

What is the error in this definition?

medium

A. The rule causes infinite recursion

B. No error; the definition is correct

C. Attributes are assigned in the wrong order

D. Attribute E1.val is used before being defined

Solution

1. Step 1: Check attribute usage and definitions

   E1.val and T.val are both defined before use in E.val.

2. Step 2: Verify rule correctness

   The rule correctly sums E1.val and T.val to get E.val without recursion or order issues.

3. Final Answer:

   No error; the definition is correct -> Option B

4. Quick Check:

   Attributes defined before use, no recursion [OK]

Hint: Check if all attributes are defined before use [OK]

Common Mistakes:

• Assuming recursion error without context
• Thinking attribute order matters if dependencies are clear
• Confusing attribute names

5. You want to compute the value of an arithmetic expression using syntax-directed definitions. The grammar is:

Expr -> Expr1 '+' Term
Expr.val = Expr1.val + Term.val
Expr -> Term
Expr.val = Term.val
Term -> 'num'
Term.val = num.value

Given the input expression 3 + 4 + 5, how should the attributes be evaluated to get the correct total?

hard

A. Use inherited attributes to pass partial sums from left to right

B. Use semantic actions to print values without computing sum

C. Use synthesized attributes only, evaluating bottom-up

D. Use attributes to store tokens but not compute values

Solution

1. Step 1: Understand attribute types in the grammar

   The grammar uses synthesized attributes (Expr.val, Term.val) computed bottom-up.

2. Step 2: Evaluate expression bottom-up

   Each Term.val is the number's value; Expr.val sums left Expr1.val and Term.val recursively.

3. Step 3: Confirm correct evaluation method

   Using synthesized attributes bottom-up correctly computes 3 + 4 + 5 = 12.

4. Final Answer:

   Use synthesized attributes only, evaluating bottom-up -> Option C

5. Quick Check:

   Synthesized attributes compute values bottom-up [OK]

Hint: Use synthesized attributes to compute expression values bottom-up [OK]

Common Mistakes:

• Confusing inherited and synthesized attributes
• Trying to pass partial sums left to right incorrectly
• Ignoring attribute evaluation order