Aho - Chapter 2.1 to 2.2 Summary

  1. Introduction to Syntax-Directed Translator
  2. Syntax Definition

1.0 - Introduction to Syntax-Directed Translator

2.0 - Syntax Definition

Aho et al, Chapter 2.2

1.1 - Definition of Grammars

Aho et al, Chapter 2.2.1


We often want to create expressions consisting of digits, plus and minus signs, such as 9−5+2+3−1−79-5+2+3-1-7. Since a plus or a minus sign must appear between two digits, we refer to such expressions as “lists of digits separated by a plus or minus sign”.

list→list + digitlist→list − digitlist→digitdigit→0 ∣ 1 ∣ 2 ∣ 3 ∣ 4 ∣ 5 ∣ 6 ∣ 7 ∣ 8 ∣ 9 \textit{list}\rightarrow\textit{list}\ +\ \textit{digit}\\ \textit{list}\rightarrow\textit{list}\ -\ \textit{digit}\\ \textit{list}\rightarrow\textit{digit}\\ \textit{digit}\rightarrow 0\ |\ 1\ |\ 2\ |\ 3\ |\ 4\ |\ 5\ |\ 6\ |\ 7\ |\ 8\ |\ 9

1.2 - Grammar Derivations

Aho et al, Chapter 2.2.2


1.2.1 - List Production Example 1 - Productions & Lists

list→list + digit  ∣  digit  −  list  ∣  digitdigit→0 ∣ 1 ∣ 2 ∣ 3 ∣ 4 ∣ 5 ∣ 6 ∣ 7 ∣ 8 ∣ 9 \textit{list}\rightarrow\textit{list}\ +\ \textit{digit}\ \ |\ \ \textit{digit} \ \ - \ \ \textit{list}\ \ | \ \ \textit{digit}\\ \textit{digit}\rightarrow 0\ |\ 1\ |\ 2\ |\ 3\ |\ 4\ |\ 5\ |\ 6\ |\ 7\ |\ 8\ |\ 9

1.2.2 - List Production Example 2 - List of Parameters

1.3 - Parse Trees

Figure 1: Parse tree for A→XYZA\rightarrow XYZ

1.4 - Ambiguity


Suppose that in the example above, we used a single non-terminal, string\textit{string} and did not distinguish between digits and lists. Then, we could have written the grammar:

string→string+string  ∣  string−string  ∣ 0 ∣ 1 ∣ 2 ∣ 3 ∣ 4 ∣ 5 ∣ 6 ∣ 7 ∣ 8 ∣ 9 \textit{string}\rightarrow\textit{string}+\textit{string}\ \ |\ \ \textit{string}-\textit{string}\ \ |\ 0\ |\ 1\ |\ 2\ |\ 3\ |\ 4\ |\ 5\ |\ 6\ |\ 7\ |\ 8\ |\ 9

1.5 - Associativity

1.6 - Precedence of Operators