Syntax-directed definitions in Compiler Design - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a syntax-directed definition (SDD)?

A syntax-directed definition is a set of rules that attach attributes to grammar symbols and define how to compute these attributes based on the syntax structure of a language.

beginner

What are attributes in syntax-directed definitions?

Attributes are values associated with grammar symbols that hold information like types, values, or other properties needed during compilation.

intermediate

What is the difference between synthesized and inherited attributes?

Synthesized attributes are computed from the attributes of child nodes and passed up the parse tree, while inherited attributes are passed down or across the parse tree from parent or sibling nodes.

intermediate

How do semantic rules work in syntax-directed definitions?

Semantic rules specify how to compute attribute values using the attributes of related grammar symbols, usually written alongside grammar productions.

beginner

Why are syntax-directed definitions important in compilers?

They help compilers perform semantic analysis by systematically associating meaning with syntax, enabling tasks like type checking and code generation.

What do synthesized attributes do in a syntax-directed definition?

A Define grammar rules

B Pass information down the parse tree

C Pass information up the parse tree

D Ignore semantic information

Synthesized attributes collect information from child nodes and pass it up the parse tree.

Which of the following is true about inherited attributes?

A They pass information from parent or siblings to a node

B They are computed from child nodes

C They are not used in syntax-directed definitions

D They only apply to terminal symbols

Inherited attributes pass information from parent or sibling nodes down or across the parse tree.

What is the main purpose of semantic rules in SDDs?

A To define syntax structure

B To generate machine code

C To ignore syntax errors

D To compute attribute values

Semantic rules specify how to compute attribute values based on grammar symbols.

In syntax-directed definitions, attributes are attached to:

A Only terminal symbols

B Both terminal and non-terminal symbols

C Only the start symbol

D Only non-terminal symbols

Attributes can be attached to both terminal and non-terminal grammar symbols.

Why are syntax-directed definitions used in compilers?

A To associate meaning with syntax

B To ignore semantic errors

C To speed up parsing

D To replace grammar rules

They help compilers attach meaning to syntax for semantic analysis.

Explain the roles of synthesized and inherited attributes in syntax-directed definitions.

Think about the direction of information flow in the parse tree.

Describe how semantic rules work in syntax-directed definitions and why they are important for compilers.

Focus on the connection between syntax and meaning.

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