Compiler Construction
Libby Rasnick
Christopher Newport University
CPSC 560
Spring 2003
Defining Compiler Construction Tools (aka CCTs)
Uses for CCTs
CCTs in the Compiler Structure
Lexical Analyzer
Syntax Analyzer
Semantic Analyzer
Intermediate Code Generator
Code Optimizer
Code Generator
Compiler Construction Kit - Cocktail
Defining CCTs
programs or environments that assist
in the creation of an entire compiler or
its parts
Uses for CCTs
generate lexical analyzers,
syntax analyzers,
semantic analyzers,
intermediate code,
optimized target code
CCTs in the Compiler Structure
Lexical Analyzer
scanner generators
input: source program
output: lexical analyzer
task of reading characters from source
program and recognizing tokens or basic
syntactic components [3]
maintains a list of reserved words
Lexical Analyzer
Flex (fast lexical analyzer generator)
Example which specifies a scanner which
replaces the string “username” with the
user’s login name
username printf(“%s”, getlogin());
Syntax Analyzer
parser generators
input: context-free grammar
output: syntax analyzer
the task of the syntax analyzer is to
produce a representation of the source
program in a form directly representing its
syntax structure. This representation is
usually in the form of a binary tree or similar
data structure [3]
Syntax Analyzer
Bison (Yacc-compatible parser gen.) [5]
a general purpose parser generator that converts
grammar description for an LALR(1) CFG into a C
Bison grammar example (reverse polish notation)
#define YYSTYPE double
#include <math.h>
%token NUM
Semantic Analyzer
syntax-directed translators
input: parse tree
output: routines to generate I-code
“The role of the semantic analyzer is to derive
methods by which the stuctures constructed by the
syntax analyzer may be evaluate or executed.“ [3]
type checker
two common tactics:
~ flatten the semantic analyzer’s parse tree
~ embed semantic analyzer w/in syntax analyzer
(syntax-driven translation)
Intermediate Code Generator
Automatic code generators
input: I-code rules
output: crude target machine program
“The task of the code generator is to
traverse this tree, producing functionally
equivalent object code.” [3]
three address code is one type
Intermediate Code Generator
Example 7 + (8 * y) / 2
a := 8
b := y
c := a * b
a := c
b := 2
c := a / b
a := 7
b := c
c := a + b
expr /
expr )
Code Optimizer
Data flow engines
input: I-code
output: transformed code
“This improvement is achieved by program
transformations that are traditionally called
optimizations, although the term
‘optimization’ is a misnomer because there
is rarely a guarantee that the resulting code
is the best possible.” [1]
Code Optimizer
Peephole Optimization
machine or assembly code is used along
with knowledge of target machine’s
instruction set to replace I-code instructions
with shorter or more quickly executed
instructions - this is repeated as much as is
necessary [3]
Code Optimizer
Common Optimizing Transformations [2]
Optim. Name
constant folding
dead code elim.
loop unrolling
linearizing arrays
load/store optim.
branch chaining
Required Analysis
simulated exec.
simulated exec.
loop struct., stat.s
loop structure
motion (replic.)
selection (dec)
math identities
common subexp.
simulated exec.
selection, elimination
Code Optimizer
Example 7 + (8 * y) / 2
a := y
a := a * 8
a := a / 2
a := + 7
expr /
expr )
Code Generator
Automatic code generators
input: optimized (transformed) I-code
output: target machine program
Example 7 + (8 * y) / 2
Load a, y
Mult a, 8
Div a, 2
Add a, 7
Compiler Construction Tool Kits
tool kits contain all (or almost all) phases of
a compiler
Example: Cocktail [7]
Developed until 1993 at Karlsruhe research
lab, the German National Research Center
for Information Technology.
Compiler Construction Tool Kits
Rex (Regular EXpression tool)
- scanner generator
Lalr - an LALR(1) parser generator accepting
grammars in extended BNF
Ell - an LL(1) parser generator accepting same
grammars as Lalr, but must obey LL(1) property
Ast - generator for abstract syntax trees
Ag - attribute evaluator generator
Puma - transformation tool based on pattern
1 Aho, Alfred V., Sethi, Ravi and Ullman, Jeffrey
D. Compilers: principles, techniques, and
tools. (1986). Reading: Addison-Wesley.
2 Peters, James, Pittman, Thomas. The art of
compiler design: theory and practice. (1992).
Englewood Cliffs: Prentice Hall.
3 Watson, Des. High-level languages and their
compilers. (1989). Wokingham: AddisonWesley.
4 Heng, Christopher. (2003). Free Compiler
Construction Tools.
lercontructiontools (01 March 2003).
5 The Lex & Yacc Page. (01 March 2003).
6 Compiler Construction Kits. (01 March 2003).
7 The Cocktail Compiler Toolbox. (01 March 2003).

Compiler Construction Tools