Syntax-directed definitions

ACompressed recap

🧾

An SDD attaches attributes to grammar symbols and semantic rules to productions. Synthesized attributes flow up from children; inherited attributes flow down from the parent or across from siblings; terminals only have synthesized attributes from the lexer. An annotated parse tree shows all values; the dependency graph orders their computation (any topological order; none if there is a cycle). Always build the tree from the grammar first, then apply the rules, however strange the operators.

BMerged rule card

3.1 Syntax-directed definitions: attributes, semantic rules, synthesized vs inherited, annotated parse trees, dependency graphs and evaluation order

• SDD = grammar + attributes + semantic rules per production.
• Synthesized: computed at the node’s own production from children; flows up.
• Inherited: computed at the parent’s production from parent/siblings; flows down or sideways.
• Terminals: synthesized only (lexval).
• Annotated parse tree shows all attribute values.
• Dependency graph: edge b → a if a uses b; evaluate in topological order; cycle ⇒ no order.

CInterleaved GATE-style questions

Q1NAT2 marksEvaluation

With E → E₁ # T {E.val = E₁.val × T.val}, E → T, T → T₁ & F {T.val = T₁.val + F.val}, T → F, F → n, evaluate 1 & 2 # 3 & 4.

Numerical answer: ________

Q2NAT1 markDesk calculator

With the desk-calculator SDD, what is L.val for ( 2 + 3 ) * 4?

Numerical answer: ________

Q3MCQ1 markTerms

A parse tree with every attribute value shown is called:

• (A) a dependency graph
• (B) an annotated parse tree
• (C) an item set
• (D) a DAG

Q4MCQ1 markInherited

In A → B C, the rule C.i = B.s defines:

• (A) a synthesized attribute of A
• (B) an inherited attribute of C
• (C) a synthesized attribute of C
• (D) an attribute of the lexer

Q5NAT2 marksBinary

An SDD has N → N₁ d {N.val = 2 × N₁.val + d.lexval}, N → d {N.val = d.lexval}. What is N.val for the digit string 1 0 1 1?

Numerical answer: ________

Q6MSQ1 markFacts

Which are true?

• (A) Terminals can have inherited attributes.
• (B) A topological order of the dependency graph is a valid evaluation order.
• (C) Synthesized attributes at a node depend on its children.
• (D) An inherited attribute can depend on a sibling’s attribute.

Q7MCQ2 marksOrder

For float a, b, the dependency graph includes T.type → L.inh (top). Which must be computed first?

• (A) L.inh (top)
• (B) T.type
• (C) addType(a)
• (D) any of them

Q8NAT1 markCalls

For int x, y, z, w with the declaration SDD, how many times is addType called?

Numerical answer: ________