ToolSphere

SDT Annotated Parse Tree

Computer science

Build annotated parse trees for S-attributed expression values and L-attributed declarations, with semantic rules and evaluation steps.

Choose an example or edit the input. The answer, annotated tree and evaluation order update as you type.

Expression value

19

S-attributed: values are computed after their children, in post-order.

Use whole numbers, +, * and parentheses. A final n means newline and is optional. Decimals, unary minus and division are not supported.

Annotated parse tree

Scroll sideways inside the tree to see all branches. Node IDs match the evaluation rows. Values stay at a readable size; no attributes are truncated.

Annotated parse tree. Full attribute values and actions also appear in the evaluation table.L · n1print 19E · n2val=19E · n3val=15T · n4val=15T · n5val=3F · n6val=3num · n7lexval=3* · n8F · n9val=5num · n10lexval=5+ · n11T · n12val=4F · n13val=4num · n14lexval=4n · n15

Semantic rules

These are fixed teaching definitions. A suffix 1 distinguishes another occurrence of the same symbol. Token values come from the lexer; print and addType are actions.

ProductionSemantic rule
L → E nprint(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 → numF.val = num.lexval (supplied by the lexer)
Evaluation order

Dependencies refer to earlier rows. Lexical rows show supplied token values. Synthesized attributes are computed after their children; inherited types are assigned before entering each list.

StepNode / kindAttribute or actionValueRule / dependencies
1n7
lexical
n7.lexval3The lexer supplies this numeric token value.
Needs: supplied token or constant
2n6
synthesized
n6.val3n6.val = n7.lexval
Needs: n7.lexval
3n5
synthesized
n5.val3n5.val = n6.val
Needs: n6.val
4n10
lexical
n10.lexval5The lexer supplies this numeric token value.
Needs: supplied token or constant
5n9
synthesized
n9.val5n9.val = n10.lexval
Needs: n10.lexval
6n4
synthesized
n4.val15n4.val = n5.val * n9.val
Needs: n5.val, n9.val
7n3
synthesized
n3.val15n3.val = n4.val
Needs: n4.val
8n14
lexical
n14.lexval4The lexer supplies this numeric token value.
Needs: supplied token or constant
9n13
synthesized
n13.val4n13.val = n14.lexval
Needs: n14.lexval
10n12
synthesized
n12.val4n12.val = n13.val
Needs: n13.val
11n2
synthesized
n2.val19n2.val = n3.val + n12.val
Needs: n3.val, n12.val
12n1
action
n1.print19print(n2.val)
Needs: n2.val

This visualizes fixed syntax-directed definitions; it does not run custom semantic code or compile a complete C program. Expression inputs are bounded to keep the tree usable, and integer attributes are exact.

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use SDT Annotated Parse Tree

  1. 1Start with the loaded arithmetic example and read its computed value above the controls.
  2. 2Edit the expression using whole numbers, +, * and parentheses, or choose Declared types to enter an int or float declaration.
  3. 3Open the annotated tree and scroll within it to inspect each numbered node and all its attribute values.
  4. 4Compare the semantic rules with the evaluation table; dependencies name attributes computed in earlier rows.
  5. 5Load another example or copy the current result, rules, node annotations and evaluation trace as text.

About SDT Annotated Parse Tree

Build an annotated parse tree from a worked input

An annotated parse tree adds meaning to a grammatical structure. This visualizer builds a concrete parse tree with the same parsing library as the site's grammar tools, then evaluates a fixed syntax-directed definition over that tree. The default arithmetic input already has an answer. Edit it to see the value, node annotations and evaluation order change together, or switch to a declaration example to study inherited type information.

The page is intended for compiler-design exercises about SDDs, S-attributed definitions, L-attributed definitions and semantic-rule dependencies. It is not a generator for arbitrary semantic programs. A syntax-directed definition describes attributes and rules; a translation scheme places executable actions in productions. Here, the displayed print and addType actions have a fixed educational meaning rather than running code supplied by a visitor.

Distinguish values supplied by the lexer from computed attributes

In arithmetic mode, num.lexval holds the integer represented by a numeric token. The lexer supplies that value. F.val, T.val and E.val then carry values computed from children. The grammar separates expressions, terms and factors so multiplication binds more tightly than addition, while parentheses can change the grouping. The top L production prints the expression value; print is displayed as an action, not invented as an inherited value.

Declaration mode works differently. T.type comes from the chosen type keyword. A list receives that type through its inh attribute before the list is visited. The type travels through the nested list nodes, and each addType action associates an identifier occurrence with it. Identifier leaves show their lexical entry names. They do not receive fabricated inherited attributes merely to make the diagram look fuller.

Work the desk-calculator example

For 3 * 5 + 4 n, the tool's library produces the following intermediate values. The final n represents a line ending; it does not mean multiplication by a variable.

Operation or propagation Value
First numeric token 3
Second numeric token 5
Multiplication term 15
Last numeric token and term 4
Addition expression 19
Printed result 19

The generated trace contains 12 rows, including reads of lexical values and the final print action. At each arithmetic node, its children have already provided the values needed by its rule. This is the post-order evaluation pattern for the shown S-attributed definition. Operators and the line-ending terminal have no numeric attributes of their own.

Try the parentheses example, (3+4)*(5+6) n. The same library returns 77. Its tree retains the grouping terminals as well as the intermediate expression, term and factor nodes; this is a concrete parse tree, not the smaller operator-only structure shown by the infix and expression-tree tool.

Walk declaration types from left to right

The loaded declaration int a, b, c gives a: int, b: int and c: int. Its trace contains 10 rows: computing the type, passing it into the list nodes, reading identifier entries and performing their declaration actions. Follow the row dependencies to see why the inherited type must be available before an identifier can be assigned that type.

The textbook-style input int id, id, id is also accepted. It displays three identifier occurrences; repeated spelling is not interpreted as proof of three different variables. This demonstration does not implement C redeclaration rules, scopes, storage allocation, pointer declarators or array declarators. For concrete names, use a, b and c to make the lexical entries easy to distinguish.

The declaration grammar is left-recursive. L-attributed describes which attribute dependencies are allowed; it does not assert that this grammar is LL(1). The tool constructs the full tree before evaluating it with a left-to-right depth-first walk. Compare grammar properties separately with the FIRST and FOLLOW calculator.

Read the numbered nodes and evaluation table

Every node has an ID that also appears in the evaluation rows. The table identifies an attribute or action, its current value, the rule used and its dependencies. A dependency always points to an earlier available value in this demonstration. Lexical rows show supplied token information; inherited rows pass information into a child; synthesized rows collect information from children.

The diagram keeps its text readable rather than shrinking a wide tree into a phone screen. Scroll inside its frame to see other branches. Long values wrap inside nodes, and the evaluation table provides the complete text as another way to inspect them. Nodes without attributes remain visible so the grammar structure is preserved.

Use exact integers within explicit limits

Arithmetic uses exact integers. For example, 9007199254740993 + 7 produces 9007199254741000 without passing the operands through floating-point arithmetic. This is useful when a numeric attribute is larger than the usual exact range of a JavaScript number. Only nonnegative whole-number literals, addition, multiplication and parentheses are supported. Unary minus, subtraction, division, decimals and identifier-valued expressions are rejected.

Inputs are limited to 600 characters. An expression may contain at most 31 tokens before the optional n; literals may have at most 40 digits, and a computed attribute may have at most 256 digits. A declaration supports at most 12 identifier occurrences with names of at most 24 ASCII letters, digits or underscores, beginning with a letter or underscore. These are visualizer limits, not language-standard restrictions.

Keep the working with the result

Copy analysis includes the normalized input, answer, semantic rules, numbered annotations and evaluation trace. Invalid input clears the previous answer rather than leaving old working under a new expression. The analysis runs in the browser and does not execute custom semantic code.

Use the general parse-tree generator for other grammars, the three-address code generator for intermediate-code translation, and the CS theory lab for the wider compiler sequence. For background on the attribute disciplines, see Aho's syntax-directed translation lecture and the NYU declaration-type example.

Frequently asked questions

What is an annotated parse tree?

It is a parse tree whose nodes also show attribute values computed or supplied for a syntax-directed definition. This tool keeps grammar nodes, terminals and numbered annotations visible, with a separate table explaining the evaluation order.

What is the difference between SDD and SDT?

An SDD specifies attributes and semantic rules associated with a grammar. An SDT embeds semantic actions within production bodies. This page evaluates fixed teaching definitions and shows their actions; it does not execute arbitrary action code.

How are S-attributed and L-attributed definitions different?

The arithmetic example computes synthesized values from children and can be evaluated in post-order. The declaration example also passes an inherited type into the list before visiting it. Its left-to-right dependencies allow the displayed depth-first evaluation.

What is the annotated result of 3 * 5 + 4 n?

The multiplication term has value 15, the final addition has value 19, and the line action prints 19. All of those values are generated from the current input by the library, with the numeric tokens retaining their own lexval attributes.

What does num.lexval mean in a semantic rule?

It is the numeric value supplied by the lexer for that occurrence of the num token. The grammar uses num so multi-digit whole numbers can be entered. Computed F.val, T.val and E.val attributes then use that lexical value.

Why does the calculator expression end in n?

The n terminal denotes a newline in this desk-calculator grammar. You can omit it in the input because the tool supplies the line-ending token. It is not an operand or a variable named n.

Can I enter my own grammar and semantic actions?

No, this visualizer has two fixed teaching definitions: arithmetic values and declaration types. Use the general parse-tree generator for other grammars. Custom semantic code is not interpreted or executed here.

Which arithmetic operators are supported?

You can use nonnegative whole numbers, addition, multiplication and parentheses. Integer values are exact within the displayed bounds. Decimals, unary minus, subtraction, division and identifier-valued expressions are not supported.

Can it annotate int id, id, id declarations?

Yes, it passes int through the list and shows a type action for each identifier occurrence. You can also use concrete names or the float keyword. Repeated names are shown as occurrences without checking the full redeclaration and scope rules of C.

Can I copy the annotated tree and evaluation order?

Copy analysis includes the current answer, semantic rules, every numbered node's attributes and the ordered dependency trace as text. The SVG can be inspected on the page with sideways scrolling inside its frame. There is no image or PDF export in this tool.

Have a suggestion for SDT Annotated Parse Tree?Share your feedback ↗