Syntax-Directed Translation for Infix → Prefix Arithmetic Expressions Annotated Parse Trees | AI Research

Syntax-Directed Translation for Infix → Prefix Arithmetic Expressions (Annotated Parse Trees)

Verified Sources

Nov 4, 2026

To translate arithmetic expressions from infix (e.g., $9 - 5 + 2$ ) into prefix (Polish) notation (e.g., $+\, -\, 9\, 5\, 2$ ), a standard approach in compiler construction is to use a syntax-directed translation scheme 2. The key idea is to attach semantic actions to productions of a grammar so that, as the parse tree is constructed, we compute the corresponding prefix string.

We will use a grammar with precedence encoded via nonterminals for addition/subtraction vs. multiplication/division. Then we define synthesized attributes that compute a string .val representing the prefix form of each subtree 2.

Mermaid view of the translation concept:

(Compiler Construction) Syntax-directed translation overview and attribute evaluation: https://en.wikipedia.org/wiki/Syntax-directed_translation - Defines SDT and attributes. ↩ ↩²
(Compiler Construction) Attribute grammars and synthesized attributes: https://en.wikipedia.org/wiki/Attribute_grammar - Covers synthesized vs inherited attributes and evaluation on parse trees. ↩ ↩²

Grammar (with precedence) and translation attributes

Let the grammar generate expressions with correct precedence and left associativity:

$E \to E + T \mid E - T \mid T$
$T \to T * F \mid T / F \mid F$
$F \to (E) \mid id$

Here:

$E$ handles + and -
$T$ handles * and /
$F$ handles parentheses and identifiers/numbers

We define a synthesized attribute 2val for each nonterminal; the attribute is computed from children nodes in the parse tree:

For $E \to E_1 + T$ :
- E.val = "+" + " " + E1.val + " " + T.val
For $E \to E_1 - T$ :
- E.val = "-" + " " + E1.val + " " + T.val
For $E \to T$ :
- E.val = T.val
For $T \to T_1 * F$ :
- T.val = "*" + " " + T1.val + " " + F.val
For $T \to T_1 / F$ :
- T.val = "/" + " " + T1.val + " " + F.val
For $T \to F$ :
- T.val = F.val
For $F \to (E)$ :
- F.val = E.val
For $F \to id$ :
- F.val = lexeme(id) (or just the number token as a string)

keyword="Attribute computed at a node from the values of its children"}
keyword="A translation scheme that computes output values via grammar-attached semantic actions"}
keyword="Tree representation of how input tokens match grammar productions"}
keyword="Notation where the operator precedes its operands (e.g., + a b)"}

(Compiler Construction) Syntax-directed translation overview and attribute evaluation: https://en.wikipedia.org/wiki/Syntax-directed_translation - Defines SDT and attributes. ↩
(Compiler Construction) Attribute grammars and synthesized attributes: https://en.wikipedia.org/wiki/Attribute_grammar - Covers synthesized vs inherited attributes and evaluation on parse trees. ↩

Constructing the syntax-directed translation scheme (SDT) for infix→prefix

1
Step 1
Use nonterminals like $E$ (for $+,-$ ), $T$ (for $*,/)$ , and $F$ (for parentheses/ids) so the parse tree structure matches operator precedence.
2
Step 2
For each nonterminal ( $E,T,F$ ), define a synthesized attribute val that will contain the prefix representation of that subtree.
3
Step 3
For each binary operator production (e.g., $E \to E + T$ ), set the parent’s val to the operator followed by the child prefixes in the correct order: op left right.
4
Step 4
For $F \to id$ , set F.val to the token lexeme; for parentheses, forward the inner expression value.
5
Step 5
Because the attributes are synthesized, once the parse tree is built the prefix strings are computed bottom-up, yielding the final result in E.val at the root.

Annotated parse tree for $9 - 5 + 2$

Given the grammar $E \\to E - T$ and $E \\to E + T$ , with left associativity, the expression $9 - 5 + 2$ parses as:

First compute $(9 - 5)$ , then add $2$

So the parse tree shape is:

Root: $E$ producing $(E + T)$
Left child: $E$ producing $(E - T)$
Right child: $T$ for 2

Annotated parse tree (with prefix values):

A more explicit tree (ASCII-style) with synthesized attributes:

$E$ $E$
- $E + T$ $E + T$
  - $E - T$ $E - T$
    - $E$ $E$
      - $T$
        
        $F$
        
        id(9) ⇒ $F.val = "9"$
        
        $T.val = "9"$
    - -
    - $T$ $T$
      - $F$
        
        id(5) ⇒ $F.val = "5"$
      - $T.val = "5"$
    - Apply $E \to E - T$ $E \to E - T$ :
      - $E.val = "-\ " + E_1.val + "\ " + T.val = "-\ 9\ 5"$
  - +
  - $T$ $T$
    - $F$ $F$
      - id(2) ⇒ $F.val = "2"$
    - $T.val = "2"$
  - Apply $E \to E + T$ $E \to E + T$ :
    - $E.val = "+\ " + E_1.val + "\ " + T.val = "+\ -\ 9\ 5\ 2"$

Final prefix output:
$E.val = "+\ -\ 9\ 5\ 2"$

Annotated parse tree for $9 - 5 * 2$

Because $*$ has higher precedence than $-$ , the parse is:

First compute $(5 * 2)$ , then subtract from $9$

So we expect:

Root: $E$ producing $(E - T)$
Left child: $E$ for 9
Right child: $T$ producing $(T * F)$

Annotated parse tree:

$E$ $E$
- $E - T$ $E - T$
  - $E$ $E$
    - $T$ $T$
      - $F$
        
        id(9) ⇒ $F.val="9"$
      - $T.val="9"$
    - $E.val="9"$
  - -
  - $T$ $T$
    - $T * F$ $T * F$
      - $T$
        
        $F$
        
        id(5) ⇒ $F.val="5"$
        
        $T.val="5"$
      - *
      - $F$
        
        id(2) ⇒ $F.val="2"$
      - Apply $T \to T * F$ :
        
        $T.val = "*\ 5\ 2"$
  - Apply $E \to E - T$ $E \to E - T$ :
    - $E.val = "-\ 9\ ( *\ 5\ 2 ) = "-\ 9\ *\ 5\ 2"$

Final prefix output:
$E.val = "-\ 9\ *\ 5\ 2"$

Tip: Use synthesized attributes for prefix strings

If val is synthesized, you only need bottom-up evaluation on the parse tree: each operator production prepends the operator and concatenates child prefix strings.

Warning: Parentheses must forward the inner expression

For $F \to (E)$ , do not add extra operator symbols—set $F.val = E.val$ so grouping in the infix expression is preserved in the parse tree.

From infix tokens to prefix string

Tokenize

1) Lexing

Read numbers/ids and operators: 9, -, 5, +, 2 or *."

Build parse tree

2) Parsing

Use $E/T/F$ grammar so precedence is reflected in tree shape."

Apply semantic actions

3) Translation

Compute val at each node using rules like E.val = "+" + E1.val + T.val."

Return root attribute

4) Output

The final prefix expression is the synthesized attribute at the start symbol ( $E.val$ )."

Expected prefix forms (using correct precedence/associativity)

Compare the two infix inputs and their computed prefix outputs.

Common pitfalls and checks

Syntax-Directed Translation (SDT) for Expression Grammars

Knowledge Check

Question 1 of 4

Q1Single choice

For the production $E \to E + T$ , what is a correct synthesized-attribute semantic rule to compute the prefix string?

E.val = "+ " + E1.val + " " + T.val

E.val = "+ " + T.val + " " + E1.val

E.val = "- " + E1.val + " " + T.val

E.val = E1.val

Explore Related Topics

Operator Precedence Parser: Theory, Construction, and Parsing Mechanics

Translate $A = -b * (c + d)/e$ into Quadruples and Triples

Type Checking, Error Reporting, and Expression Graphs in Compilers

Browse all research articles