Syntax-Directed Translation: Infix to Prefix Notation

Verified Sources

May 18, 2026

In compiler design, translating high-level program expressions into machine-friendly intermediate representations is a core task of the front-end parser. One common task is converting infix notation into prefix notation. This conversion is governed by rules of operator precedence and associativity .

To perform this translation systematically, we construct a Syntax-Directed Translation Scheme (SDTS) based on a context-free grammar (CFG) . By defining structural attributes for grammar symbols, we can perform translation in a single pass.

In this section, we will define a robust context-free grammar that handles basic arithmetic operators ( $+$ , $-$ , $*$ ) while respecting operator precedence. We will establish a Syntax-Directed Definition (SDD) that uses synthesized attributes to construct the prefix string.

Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd Edition). Addison-Wesley. (Sections on Syntax-Directed Translation and Parser design). ↩
Cooper, K. D., & Torczon, L. (2011). Engineering a Compiler. Morgan Kaufmann. (Analysis of expression grammars, operator precedence, and syntax trees). ↩

Syntax Directed Translation (SDT) | Scheme & Implementation

The Grammar & Semantic Rules

To handle addition ( $+$ ), subtraction ( $-$ ), and multiplication ( $*$ ), we must design a grammar that naturally implements operator precedence (multiplication has higher precedence than addition and subtraction) and left-associativity (operations of equal precedence are evaluated from left to right) .

We use the standard unambiguous expression grammar:

\begin{aligned} E &\to E_1 + T \mid E_1 - T \mid T \\ T &\to T_1 * F \mid F \\ F &\to \text{digit} \end{aligned}

To translate this grammar into prefix notation, we associate a synthesized string attribute, val, with each non-terminal ( $E$ , $T$ , and $F$ ). The token $\text{digit}$ has a lexical attribute $\text{lexval}$ which represents its character value.

The Syntax-Directed Translation Scheme (SDTS) for this conversion is defined below:

Production	Semantic Rule / Action
$E \to E_1 + T$	$E.\text{val} = \text{strcat}("+ ", E_1.\text{val}, " ", T.\text{val})$
$E \to E_1 - T$	$E.\text{val} = \text{strcat}("- ", E_1.\text{val}, " ", T.\text{val})$
$E \to T$	$E.\text{val} = T.\text{val}$
$T \to T_1 * F$	$T.\text{val} = \text{strcat}("* ", T_1.\text{val}, " ", F.\text{val})$
$T \to F$	$T.\text{val} = F.\text{val}$
$F \to \text{digit}$	$F.\text{val} = \text{digit}.\text{lexval}$

Parse Tree Construction and Evaluation

When a parser processes an input string, it builds a parse tree. In an S-attributed definition like ours, the synthesized attributes are evaluated bottom-up, starting from the leaf nodes ( $\text{digit}$ ) and propagating up to the root ( $E$ ) .

Cooper, K. D., & Torczon, L. (2011). Engineering a Compiler. Morgan Kaufmann. (Analysis of expression grammars, operator precedence, and syntax trees). ↩
Grune, D., van Reeuwijk, K., Bal, H. E., Jacobs, C. J., & Langendoen, K. (2012). Modern Compiler Design. Springer. (Detailed explanation of S-attributed and L-attributed Definitions). ↩

Why Use Synthesized Attributes?

Synthesized attributes are perfect for bottom-up parsing algorithms (like LR parsers). Since the attributes of a parent node depend entirely on the attributes of its children, the parser can execute the semantic translation action immediately upon reducing a production rule.

Parsing & Translating 9 - 5 + 2

1
Step 1
The input string 9 - 5 + 2 is tokenized into three digits and two operators: $\text{digit}_1 (9)$ , $-$ , $\text{digit}_2 (5)$ , $+$ , and $\text{digit}_3 (2)$ .
2
Step 2
First, reduce individual digits to factors ( $F$ ) and then terms ( $T$ ):

$F_1 \to \text{digit}_1 (9) \implies F_1.\text{val} = '9'$

$T_1 \to F_1 \implies T_1.\text{val} = '9'$

$E_1 \to T_1 \implies E_1.\text{val} = '9'$
3
Step 3
Next, parse the digit $5$ :

$F_2 \to \text{digit}_2 (5) \implies F_2.\text{val} = '5'$

$T_2 \to F_2 \implies T_2.\text{val} = '5'$

Apply the reduction $E_2 \to E_1 - T_2$ :

$E_2.\text{val} = \text{strcat}('- ', '9', ' ', '5') = '- 9 5'$
4
Step 4
Parse the final digit $2$ :

$F_3 \to \text{digit}_3 (2) \implies F_3.\text{val} = '2'$

$T_3 \to F_3 \implies T_3.\text{val} = '2'$

Apply the final reduction at the root $E \to E_2 + T_3$ :

$E.\text{val} = \text{strcat}('+ ', '- 9 5', ' ', '2') = '+ - 9 5 2'$

Parsing & Translating 9 - 5 * 2

1
Step 1
The input is 9 - 5 * 2. Because multiplication ( $*$ ) has a higher precedence than subtraction ( $-$ ), the grammar forces $5 * 2$ to be grouped together under a term ( $T$ ) before resolving the subtraction under an expression ( $E$ ).
2
Step 2
Reduce the first digit:

$F_1 \to \text{digit}_1 (9) \implies F_1.\text{val} = '9'$

$T_1 \to F_1 \implies T_1.\text{val} = '9'$

$E_1 \to T_1 \implies E_1.\text{val} = '9'$
3
Step 3
Reduce the remaining terms:

$F_2 \to \text{digit}_2 (5) \implies F_2.\text{val} = '5'$

$T_2 \to F_2 \implies T_2.\text{val} = '5'$

$F_3 \to \text{digit}_3 (2) \implies F_3.\text{val} = '2'$

Apply the reduction $T_3 \to T_2 * F_3$ :

$T_3.\text{val} = \text{strcat}('* ', '5', ' ', '2') = '* 5 2'$
4
Step 4
Apply the subtraction reduction at the root $E \to E_1 - T_3$ :

$E.\text{val} = \text{strcat}('- ', '9', ' ', '* 5 2') = '- 9 * 5 2'$

Annotated Parse Trees

Below are the visual parse trees with annotated synthesized attributes showing exactly how the final prefix string is constructed from bottom-up attribute evaluation .

Annotated Parse Tree for $9 - 5 + 2$

Annotated Parse Tree for $9 - 5 * 2$

Grune, D., van Reeuwijk, K., Bal, H. E., Jacobs, C. J., & Langendoen, K. (2012). Modern Compiler Design. Springer. (Detailed explanation of S-attributed and L-attributed Definitions). ↩

Left-Recursion and Infix-to-Prefix Translation

While left-recursive grammars are perfectly suited for bottom-up parsers (like LALR/Yacc), they cannot be parsed directly by top-down LL(1) parsers. If you write a top-down translator, you must eliminate left recursion first, which changes the grammar structure and requires using inherited attributes to pass operands down the parse tree.

This tab displays the output generated by our synthesized SDTS:

Input: 9 - 5 + 2
Prefix Output: + - 9 5 2
Input: 9 - 5 * 2
Prefix Output: - 9 * 5 2

In synthesized attributes, strings are accumulated and concatenated as operations are completed up the parse tree.

Parse Tree Nodes and Traversal Step Count

Comparison of node allocations and evaluation overhead between addition/subtraction and multiplication precedence levels.

Deep Dive into Grammar Mechanics

Knowledge Check

Question 1 of 3

Q1Single choice

Which of the following is the correct prefix notation for the infix expression 7 * (3 + 2)?

7 + 3 2

- 7 3 2

- 7 3 2

7 3 + 2

Explore Related Topics

Ambiguity in the Grammar $S \rightarrow ABA,\; A \rightarrow aA \mid \epsilon,\; B \rightarrow bB \mid \epsilon$

The grammar (S\rightarrow ABA,;A\rightarrow aA\mid\epsilon,;B\rightarrow bB\mid\epsilon) is ambiguous because the two (A) nonterminals can distribute the same (a)-string in multiple ways, especially when (B) derives (\epsilon).

It generates the language (L(S)={a^i b^j a^k\mid i,j,k\ge0}=a^*b^a^).
The shortest string (a) has two distinct left‑most derivations (or parse trees), proving ambiguity.
Every string (a^n) with (n\ge1) can be split between the two (A) symbols in (n+1) ways, yielding multiple parse trees.
The ambiguity stems from both (A) producing (a^*) and (B) being able to vanish via (\epsilon).
An equivalent unambiguous grammar can be constructed, showing the ambiguity is a property of this grammar, not necessarily of the language.

Lexical Analyzer Output in Compiler Design

In compiler design, the lexical analyzer’s sole output is a stream of tokens derived from the source code character stream.

It scans characters left‑to‑right, grouping them into lexemes that match language patterns.
Each lexeme is classified into a token category (e.g., ID, NUM, PLUS) possibly with attributes.
The token stream is handed to the parser, which builds the parse tree or AST.
Machine code, intermediate code, and parse trees are produced in later compilation phases, not by the lexer.

Matrix Chain Multiplication with Dynamic Programming: Optimal Parenthesization for $\{4,10,3,12,20,7\}$

The lesson shows how dynamic programming determines the cheapest way to multiply the matrix chain with dimensions  $\{4,10,3,12,20,7\}$ .

The recurrence $m[i,j]=\min_{i\le k<j}\big(m[i,k]+m[k+1,j]+p_{i-1}p_kp_j\big)$ with $m[i,i]=0$ computes optimal sub‑costs.
Filling the cost table yields $m[1,5]=1344$ , and the split table gives the top‑level split $k=2$ .
The optimal parenthesization is  $(A_1A_2)\big((A_3A_4)A_5\big)$ , requiring $120+720+420+84=1344$ scalar multiplications.
The bottom‑up algorithm runs in $O(n^3)$ time and uses $O(n^2)$ space.

Browse all research articles

Syntax-Directed Translation: Infix to Prefix Notation

AI Summary

Footnotes

Syntax Directed Translation (SDT) | Scheme & Implementation

The Grammar & Semantic Rules

Parse Tree Construction and Evaluation

Footnotes

Why Use Synthesized Attributes?

Parsing & Translating 9 - 5 + 2

Parsing & Translating 9 - 5 * 2

Annotated Parse Trees

Annotated Parse Tree for 9−5+29 - 5 + 29−5+2

Annotated Parse Tree for 9−5∗29 - 5 * 29−5∗2

Footnotes

Left-Recursion and Infix-to-Prefix Translation

Parse Tree Nodes and Traversal Step Count

Deep Dive into Grammar Mechanics

Knowledge Check

Explore Related Topics

Annotated Parse Tree for $9 - 5 + 2$

Annotated Parse Tree for $9 - 5 * 2$