Syntax-Directed Definitions: S-Attributed vs L-Attributed Systems
“Inherited vs synthesized attributes, dependency graphs, bottom-up semantic stacks, and DFS traversal rules.”
1.The Semantic Attribute Evaluation Model
§ 4.1.A Syntax-Directed Definition (SDD) attaches semantic attributes (such as data types, values, or code fragments) to grammar symbols, and associates semantic rules with productions.
Parse Tree Decoration: Evaluating the semantic rules on a parse tree annotates each node with its computed attribute values, creating a decorated (or annotated) parse tree.
Dependency Graphs: If attribute b at node N is computed using attribute c at node M, a directed edge M.c o N.b is drawn in the dependency graph. Valid evaluation is possible if and only if the dependency graph contains no directed cycles (an acyclic graph admitting a topological sort).
S-Attributed Definitions:
- All attributes are synthesized.
- Can be evaluated in a strictly bottom-up postorder traversal.
- Can be evaluated on the fly during bottom-up shift-reduce parsing by maintaining a semantic value stack alongside the parser state stack.
L-Attributed Definitions:
- Allows synthesized attributes plus restricted inherited attributes.
- Dependencies flow strictly from top-to-bottom and left-to-right (the 'L' stands for left-to-right).
- Can be evaluated in a single depth-first traversal (preorder for inherited attributes, postorder for synthesized attributes).
2. Worked Analysis: Classifying SDDs and Attribute Evaluation
Distinguish between parent inherited attributes (valid in L-attributed) and parent synthesized attributes (invalid in L-attributed).
Problem Statement (Modeled on GATE Pattern):
Consider the following Syntax-Directed Definition with semantic rules:
(1) S -> A B { S.val = A.val + B.val; }
(2) A -> x { A.val = 2 * x.lexval; }
(3) B -> y C { B.val = C.val; C.in = B.in + 5; }
(4) C -> z { C.val = C.in * z.lexval; }
Classify whether this SDD is: (A) S-attributed, (B) L-attributed but not S-attributed, or (C) Neither.
Step 1: Check if S-attributed:
- Look at rule (3): C.in = B.in + 5. Here, C.in is an attribute of symbol C computed from B.in (its parent).
- Since C.in is an INHERITED attribute (computed for a child node), this SDD contains inherited attributes.
- Therefore, it is NOT S-attributed.
Step 2: Check if L-attributed:
- In rule (3): B -> y C, we have C.in = B.in + 5.
- C is a child of B.
- C.in depends on B.in, which is an inherited attribute of the parent B.
- According to L-attributed rules, an inherited attribute of child X_j CAN depend on inherited attributes of parent A.
- Is there any dependency on right siblings? No (C has no right siblings).
- In rule (1): S.val depends on children A.val and B.val (valid synthesized rule).
- In rule (4): C.val = C.in * z.lexval (valid synthesized rule depending on own inherited attribute and terminal lexval).
Conclusion: The SDD is L-attributed, but NOT S-attributed.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
GATE-focused with worked FIRST/FOLLOW and LR parsing table numericals.
Exam-oriented explanations of ambiguous grammars and parser conflicts.
University-depth treatment of the full compiler pipeline — build a real compiler.