Compiler Construction
using Flex and Bison
Anthony A. Aaby
Walla Walla College
cs.wwc.edu
aabyan@wwc.edu
Version of February 25, 2004
Copyright 2003 Anthony A. Aaby
Walla Walla College
204 S. College Ave.
College Place, WA 99324
E-mail: aabyan@wwc.edu
LaTeX sources available by request.
This material may be distributed only subject to the terms and conditions
set forth in the Open Publication License, v1.0 or later (the latest version is
presently available at http://www.opencontent.org/openpub
This book is distributed in the hope it will b e useful, but without any war-
ranty; without even the implied warranty of merchantability or fitness for a
particular purpose.
The author encourages wide distribution of this book for personal and com-
mercial use, provided the above copyright notice remains intact and the method
adheres to the provisions of the Open Publication Liscense located at
http://www.opencontent.org/openpub
In summary, you may copy and distribute this book free of charge or for a
profit. No explicit permission is required from the author for reproduction of
this book in any medium, physical or electronic.
Note, derivative works and translations of this document must include the
original copyright notice must remain intact.
To Pame la Aaby
i
ii
Contents
1 Introduction 1
2 The Parser 5
3 The Scanner 9
4 The Context 13
5 Optimization 19
6 Virtual Machines 21
7 Code Generation 27
8 Peephole Optimization 37
9 Further Reading 39
10 Exercises 41
A Simple - The complete implementation 47
A.1 The parser: Simple.y . . . . . . . . . . . . . . . . . . . . . . . . . 47
A.2 Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
A.3 The scanner: Simple.lex . . . . . . . . . . . . . . . . . . . . . . . 52
A.4 The symbol table: ST.h . . . . . . . . . . . . . . . . . . . . . . . 53
A.5 The code generator: CG.h . . . . . . . . . . . . . . . . . . . . . . 54
A.6 The stack machine: SM.h . . . . . . . . . . . . . . . . . . . . . . 55
A.7 Sample program: test simple . . . . . . . . . . . . . . . . . . . . 57
B Lex/Flex 59
B.1 Lex/Flex Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 59
B.2 The Lex/Flex Input File . . . . . . . . . . . . . . . . . . . . . . . 61
B.3 The Generated Scanner . . . . . . . . . . . . . . . . . . . . . . . 66
B.4 Interfacing with Yacc/Bison . . . . . . . . . . . . . . . . . . . . . 67
iii
评论15