Drawtomata / Annotated parse tree and syntax-directed translation
Annotated parse tree and syntax-directed translation
Type a grammar with semantic rules, such as E -> E1 + T { E.val = E1.val + T.val }, and an input string. Drawtomata parses the string, evaluates every attribute and draws the annotated parse tree, the dependency graph and the syntax tree.
Synthesized and inherited attributes
A synthesized attribute of a node is computed from its children, as in E.val = E1.val + T.val. An inherited attribute is computed from the parent and siblings, as in L.inh = T.type in a declaration. An SDD with only synthesized attributes is S-attributed and can be evaluated bottom-up during LR parsing. It is L-attributed when every inherited attribute of Xᵢ in A → X₁ … Xₙ uses only inherited attributes of A and attributes of X₁ … Xᵢ₋₁, so one depth-first, left-to-right pass evaluates it.
Example: 3 * 5 + 4 n
With the desk-calculator example (press Load the example above), the annotated parse tree has F.val = 3 and F.val = 5 at the bottom, T.val = 15 above them, then E.val = 19 and finally L.val = 19 at the root.
| Production | Semantic rule |
|---|---|
| L → E n | L.val = E.val |
| E → E1 + T | E.val = E1.val + T.val |
| E → T | E.val = T.val |
| T → T1 * F | T.val = T1.val * F.val |
| T → F | T.val = F.val |
| F → ( E ) | F.val = E.val |
| F → digit | F.val = digit.lexval |
Dependency graph and evaluation order
Each attribute of each parse-tree node is a node of the dependency graph, with an edge from X.a to Y.b whenever the rule for Y.b reads X.a. Any topological sort of the graph is a valid evaluation order; if the graph has a cycle, no order exists. The tool numbers one order and lists the value computed at each step.
Syntax trees
Rules such as E.node = new Node('+', E1.node, T.node) and T.node = new Leaf(id, id.entry) build a syntax tree while the attributes are evaluated. For a - 4 + c the tool shows the five steps p1 … p5 and draws the tree.