Q4Compiler Design

In compiler architecture, a Context-Free Grammar (CFG) is mathematically capable of defining the rigid structure of a language, but it is physically incapable of defining the meaning or semantics of that structure. To evaluate mathematical logic (like calculating the result of an addition, or generating target code), compiler engineers utilize Syntax-Directed Definitions (SDD) and Syntax-Directed Translation (SDT). This paradigm aggressively attaches logical, executable semantic rules and data attributes directly to the abstract nodes of the parse tree during the compilation process.

Syntax-Directed Definitions (SDD)

An SDD is a high-level, mathematically declarative specification. It strictly defines the grammar rules alongside a set of associated semantic rules, but crucially, it completely ignores the physical order in which these rules must be evaluated by the CPU. In an SDD, every grammar symbol (like an expression E or a variable id) is assigned mathematical "Attributes" (e.g., a data type, a memory location, or an integer value). Attributes are strictly divided into two distinct engineering classes:

• 1. Synthesized Attributes: The value of a synthesized attribute at a node is mathematically calculated exclusively by combining the attribute values of its absolute child nodes. Data flows violently from the bottom of the tree (leaves) upwards to the root. This is universally compatible with Bottom-Up (LR) parsing.
• 2. Inherited Attributes: The value of an inherited attribute at a node is mathematically forced upon it from above or the side; it is calculated using the attributes of its parent node or its sibling nodes. Data flows downwards or laterally. This is highly complex to implement in standard Bottom-Up parsers without structural modifications.

Syntax-Directed Translation (SDT)

While an SDD is purely declarative, an SDT is aggressively operational. An SDT explicitly embeds physical semantic action code (usually enclosed in curly braces { }) directly inside the right-hand side of the grammar productions. It violently enforces the exact execution sequence. When the parser mathematically recognizes the surrounding grammatical symbols, it physically executes the embedded code.

Practical Example: Translating Arithmetic Expressions

Let us mathematically model a simple SDD designed to evaluate the physical value of standard arithmetic expressions (e.g., calculating 3 * 5 + 4). We will utilize exclusively Synthesized Attributes (specifically, the .val attribute, which stores the integer value). Data will flow from the bottom up.

Consider the following grammar and attached Semantic Rules:

• Production 1: $LightarrowE\text{ n}$ Semantic Rule: print(E.val) (Explanation: When the entire expression is reduced, print the final mathematical value).
• Production 2: $Eightarrow{E}_1+T$ Semantic Rule: E.val = E_1.val + T.val (Explanation: The value of this addition node is strictly the mathematical sum of its left child and right child).
• Production 3: $EightarrowT$ Semantic Rule: E.val = T.val (Explanation: Direct mathematical value transfer).
• Production 4: $Tightarrow{T}_1\ast F$ Semantic Rule: T.val = T_1.val * F.val (Explanation: The value of this multiplication node is the mathematical product of its children).
• Production 5: $TightarrowF$ Semantic Rule: T.val = F.val
• Production 6: $Fightarrow(E)$ Semantic Rule: F.val = E.val (Explanation: Parentheses physically alter precedence but do not alter the inner value).
• Production 7: $Fightarrow\text{digit}$ Semantic Rule: F.val = digit.lexval (Explanation: The absolute leaf node. The lexical analyzer physically scanned a digit (like '3'). Its value is passed up the tree).

As the Bottom-Up parser aggressively builds the tree from the tokens 3, *, 5, it will eventually reduce them to $Tightarrow{T}_1\ast F$. At the exact millisecond of reduction, the semantic rule T.val = 3 * 5 is executed, storing 15 in T.val, which is then passed upwards to complete the mathematical translation flawlessly.