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.

ProductionSemantic rule
L → E nL.val = E.val
E → E1 + TE.val = E1.val + T.val
E → TE.val = T.val
T → T1 * FT.val = T1.val * F.val
T → FT.val = F.val
F → ( E )F.val = E.val
F → digitF.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.