Chapter 2:

A Simple
Compiler
陳奇業 成功 學資訊 程系

1
大
工
Outlines
▪ 2.1 An Informal Definition of the ac Language
▪ 2.2 Formal Definition of ac
▪ 2.3 Phases of a Simple Compiler
▪ 2.4 Scanning
▪ 2.5 Parsing
▪ 2.6 Abstract Syntax Trees
▪ 2.7 Semantic Analysis
▪ 2.8 Code Generation

2
 Source
Program Tokens Syntactic Semantic
Scanner Parser
(Character Structure Routines
Stream)
Intermediate
Representation

Symbol and Optimizer

Attribute
Tables

(Used by all
Phases of
The Compiler) Code
Generator

The structure of a Syntax-Directed Compiler

Target Machine
Code
3
4
An Informal Definition of the ac (adding
calculator) Language
▪ Types: There are only two data types: integer and float. An integer type is a sequence of
decimal numerals, as found in most programming languages. A float type allows five
fractional digits after the decimal point.
▪ Keywords: There are three reserved keywords, each limited for simplicity to a single
letter: f (declares a float variable), i (declares an integer variable), and p (prints the value
of a variable).
▪ Variables: The ac language offers only 23 possible variable names, drawn from the
lowercase Roman alphabet and excluding the three reserved keywords f, i, and p.
Variables must be declared prior to using them.

5
An Informal Definition of the ac
Language
▪ In some cases, such type conversion is handled automatically by the compiler, while
other cases require explicit syntax (such as casts) to allow the type conversion.

▪ In ac, conversion from integer type to float type is accomplished automatically.

Conversion in the other direction is not allowed under any circumstances.

6
An Informal Definition of the ac
Language
▪ For the target of translation, we use the widely available program dc (for desk calculator),
which is a stack-based calculator that uses reverse Polish notation (RPN逆波蘭表 法、
後序表 法).

▪ When an ac program is translated into a dc program, the resulting instructions must be

acceptable to the dc program and must faithfully represent the operations specified in an
ac program.

7
示
示
Formal Definition of ac
▪ Before translating ac to dc we must first understand the syntax and semantics of the ac
language.

▪ We use a context-free grammar (CFG) to specify our language’s syntax and regular
expressions to specify the basic symbols of the language.

8
The Syntax of ac
▪ Ac’s syntax is defined by a context-free grammar (CFG)
▪ CFG is also called BNF (Backus-Naur Form 巴科斯範式) grammar
▪ CFG consists of a set of production rules,

A→B C D… Z

LHS must be a single nonterminal LHS RHS

RHS consists 0 or more terminals or nonterminals

9
Syntax
Specification

10
11
12
Token
Specification

13
An ac Scanner
▪ The ac Scanner will be a function of no arguments that returns token values
▪ There are 10 tokens.

typedef enum token_types {

floatdcl, intdcl, print, id, assign, plus,
minus, inum, fnum, blank
} token;

Extern token scanner(void);

14
An ac Scanner (Cont’d)
▪ The scanner returns the longest string that constitutes a token, e.g., in
abcdef
ab, abc, abcdef are all valid tokens.
The scanner will return the
longest one (i.e., abcdef).

15
Phases of a Simple Compiler
1. The scanner reads a source ac program as a text file and produces a stream of tokens.
2. The parser processes tokens produced by the scanner, determines the syntactic validity of the
token stream, and creates an abstract syntax tree (AST) suitable for the compiler’s subsequent
activities.
3. The AST created by the parsing task is next traversed to create a symbol table. This table
associates type and other contextual information with variables used in an ac program.
4. The AST is next traversed to perform semantic analysis.
5. Finally, the AST is traversed to generate a translation of the original program.

16
Scanning
▪ The scanner’s job is to translate a stream of characters into a stream of tokens, where each token
represents an instance of some terminal symbol.
▪ Each token found by the scanner has the following two components:
1. A token’s type explains the token’s membership in the terminal alphabet. All instances of a given
terminal have the same token type.
2. A token’s semantic value provides additional information about the token.

For terminals such as plus, no semantic information is required, because only one token (+) can
correspond to that terminal. Other terminals, such as id and num, require semantic information so
that the compiler can record which identifier or number has been scanned.

17
Scanning
▪ For most programming languages, the scanner’s job is not so easy. Some tokens (+) can
be prefixes of other tokens (++); other tokens such as comments and string constants
have special symbols involved in their recognition.

18
Scanner for
the ac
language.

19
Finding inum or
fnum tokens for
the ac language

20
Parsing
▪ The parser is responsible for determining if the stream of tokens provided by the scanner
conforms to the language’s grammar specification.
▪ We build a parser for ac using a well-known parsing technique called recursive descent.

21
Ambiguity (模稜兩可）
▪ Suppose we used a single nonterminal string and did not distinguish between digits and
lists. We could have written the grammar
string → string + string | string - string | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

22
Associativity of Operators
▪ By convention, 9+5+2 is equivalent to (9+5)+2 and 9-5-2 is equivalent to (9-5)-2. When
an operand like 5 has operators to its left and right, conventions are needed for deciding
which operator applies to that operand. We say that the operator + associates to the left,
because an operand with plus signs on both sides of it belongs to the operator to its left.
▪ Some common operators such as exponentiation are right-associative. As another
example, the assignment operator = in C and its descendants is right associative; that is,
the expression a=b=c is treated in the same way as the expression a= (b=c) .

23
Associativity of
Operators
▪ Left recursion => left-associative
▪ Right recursion => right-associative
▪ Strings like a=b=c with a right-associative
operator are generated by the following
grammar:
right → letter = right | letter
letter → a | b | … | z

24
Precedence of Operators
▪ Consider the expression 9+5*2. There are two possible interpretations of this expression:
(9+5) *2 or 9+ (5*2).
▪ Ex. : A grammar for arithmetic expressions can be constructed from a table showing the
associativity and precedence of operators.
expr → expr + term | expr - term | term
term → term * factor I term / factor | factor
factor → digit | ( expr )

25
Parse Tree Construction
▪ Most parsing methods fall into one of two classes, called the top-down and bottom-up
methods.
▪ In top-down parsers, construction starts at the root and proceeds towards the leaves,
while in bottom-up parsers, construction starts at the leaves and proceeds towards the
root.

26
 Top-Down
Parsing
▪ stmt → expr ;
| if ( expr ) stmt
| for ( optexpr ; optexpr ; optexpr ) stmt
| other
▪ optexpr → | expr

27
𝜀
Predicting a Parsing
Procedure
▪ Each procedure first examines the next input
token to predict which production should be
applied. For example, Stmt offers two
productions:
Stmt→id assign Val Expr
Stmt→print id

28
Recursive-
descent Parsing
▪ Recursive-descent parsing is a
top-down method of syntax
analysis in which a set of
recursive procedures is used to
process the input.
▪ FIRST(stmt) = {expr, if, for,
other}

29
 Left Recursion
▪ It is possible for a recursive-descent parser to loop forever. A problem arises with "left-
recursive" productions like
expr → expr + term
▪ A left-recursive production can be eliminated by rewriting the offending production.
Consider a nonterminal A with two productions
A→A |
▪ For example, A= expr, = + term, = term

30
𝛼𝛽𝛼𝛽
 Left Recursion
▪ We can convert left recursion to
right recursion in the following
manner, using a new
nonterminal R:
A→ R
R → R|ϵ

31
𝛽𝛼
Abstract Syntax Trees
▪ While the process of compilation begins with scanning and parsing, following are some
aspects of compilation that can be difficult or even impossible to perform during syntax
analysis:
▪ Most programming language specifications include prose that describes aspects of the language
that cannot be specified in a CFG. Ex: x.y.z in Java, operator overloading.
▪ For relatively simple languages, syntax-directed translation can perform almost all aspects of
program translation during syntax analysis. However, from a software engineering perspective,
the separation of activities and concerns into phases (such as syntax analysis, semantic
analysis, optimization, and code generation) makes the resulting compiler much easier to write
and maintain.
▪ In response to the above concerns, we might consider using the parse tree as the
structure that survives syntax analysis and is used for the remaining phases. 32
Abstract Syntax Trees
▪ However, such trees can be rather large and unnecessarily detailed, even for very simple
grammars and inputs.
▪ It is therefore common practice to create an artifact of syntax analysis known as the
abstract syntax tree (AST). This structure contains the essential information from a parse
tree, but inessential punctuation and delimiters (braces, semicolons, parentheses, etc.)
are not included.

33
Parse Tree Abstract Syntax Tree

34
Syntax-Directed Translation
▪ Two concepts related to syntax-directed translation:
▪ Attributes. An attribute is any quantity associated with a programming construct. Examples of
attributes are data types of expressions, the number of instructions in the generated code, or the
location of the first instruction in the generated code for a construct …
▪ Translation schemes. A translation scheme is a notation for attaching program fragments to the
productions of a grammar. The program fragments are executed when the production is used
during syntax analysis. The combined result of all these fragment executions, in the order
induced by the syntax analysis, produces the translation of the program to which this analysis/
synthesis process is applied.

35
Synthesized
Attributes

36
Tree Traversals
▪ Tree traversals will be used for describing attribute evaluation and for specifying the
execution of code fragments in a translation scheme.

depth-first traversal
37
Translation Schemes
▪ A syntax-directed translation scheme is a notation for specifying a translation by
attaching program fragments to productions in a grammar.
▪ The position at which an action is to be executed is shown by enclosing it between curly
braces and writing it within the production body, as in
rest → + term {print('+’)} rest1

38
Translation
Schemes
expr → expr1 + term {print('+’)}

expr → expr1 - term {print('-’)}

expr → term
term → 0 {print (‘0’)}
term → 1 {print (' 1’)}
...
term → 9 {print ('9’)}
39
Translation Schemes
▪ Let ▪ Then the left-recursion-eliminating
transformation produces the translation
scheme

40
Translation Schemes

41
Semantic
Analysis
▪ For the ac language, we focus
on two aspects of semantic
analysis: symbol table
construction and type checking.

42
Type Checking

43
AST after
semantic
analysis

44
Code
Generation

45
Code Generation

46