1、Introduction 简介
This on-line document accompanies the slides and other material available for the courses
It describes the project of a complete compiler for a real programming language and is organized to demonstrate how to incrementally design and implement the successive phases of the compilation process.
All the used tools are freely available on the Internet:
1. the front end of the compiler has been developed by means of ,& a lexical analyzer generator, and , an LALR parser generator, both based on the
2. the back end is made by the
retargettable code generator, which currently supports X86, X86-64, PowerPC, PowerPC-64, ARM, Thumb, SPARC, Alpha, and IA-64 architectures.
2、Source Language 源语言
The source language for the compiler is mjava, a subset of Java which mainly differs from the standard language in the following points:
1. all classes in a program are declared in a single file (linking is not needed)
2. multiple inheritance is not supported (interface declarations are not allowed)
3. abstract classes are not admitted
4. static fields and static methods are not allowed
5. overloading is not supported
6. basic only flow-of-control statements ( if, if-else and while ) are implemented
7. basic input/output operations on the I/O standard devices are performed by invoking the C-like functions printf and scanf.
This is an example of mjava source program: /********************************************************************
* Sample mjava source program
*********************************************************************/
public class String {
} // end of class String
public class Int {
public Int(int i) {
public int f() {
return fact(n);
int fact(int n) {
return n & 2 ? n * fact(n - 1) :
} // end of class Int
public class Test {
public void main(){
while(n & 1 || n & 16) {
printf (&Enter an integer greater than 0 and less than 17: &);
scanf (&%d&, &n);
t = new Int(n);
f = t.f();
printf(&factorial(%d)= %d\n&, n, f);
} // end of class Test
3、Lexical Analysis 词法分析
First of all we have to specify the lexical elements of our source language by means of a lexical-analyzer generator.
transforms the specification of a scanner (regular definitions, actions to be executed when a matching occurs, ...) into a Java program that implements a minimum state Deterministic
Finite Automaton accepting the specified lexemes.
The lexical specification of the mjava language is reported in the
file, that uses& the interface
to declare integer constants for the terminal tokens in the language.
From these files JFlex generates a
file with one class that contains code for the scanner. The class will have a constructor taking a java.io.Reader from which the input is read.
The %debug directive in
also creates a main function in the generated class that expects the name of an input file on the command line and then runs the scanner on this input file, by printing information about each returned token.
The information includes: line number (if line counting is enabled), column (if column counting is enabled), the matched text, the executed action (with line number in the specification), and the integer value of the token declared in
You can generate a scanner for mjava and run it on an input program such as
by means of the Windows batch file
or the Linux shell script
1. put the , ,
files in a same directory and “cd”& into it
3. you will get something like
printed to your Java console.
4、Parsing 解析
Now we have to specify the syntactic structure of
mjava well-formed programs.
By means of , we’ll then transform the parser specification (grammar, conflict resolution directives, ...) into a Java program implementing an LALR parser.
The parser specification of the mjava language is reported in the
file, that uses the scanner generated by
to perform lexical analysis and then generates the interface
and the parser .
We have slightly modified the previous version of mjava.flex, by introducing the class
to retrieve more detailed information about lexical tokens.
You can generate a parser for mjava and run it on an input program such as
by means of the Windows batch file
or the Linux& shell script :
1. put the , , ,
files in a same directory and “cd”& into it
2. run mjava.bat / mjava.spt
3. the files ,
will be generated
4. you will get something like
printed to your Java console.
5、Error handling 错误处理
The parser produced so far has a major drawback: on receiving an input program with syntactic errors, such as
, it will stop with a Fatal Syntax Error Exception on the first error occurrence, as shown in
This behavior is quite unkind to the user, who would like to have all the errors reported, not just the first one.
Cup supports a local error recovery mechanism, based on a special
error symbol, to allow the parser to continue when a syntactic error occurs: whenever the
error symbol appears in a grammar rule, it can match a sequence of erroneous input symbols.
On encountering an error action, the parser:
1. pops the stack until a state including an item obtained from an error rule&
A ::= error a is reached
2. shifts a fictitious
error& token onto the stack, as though error
was found on input
3. skips ahead on the input, discarding symbols until a substring is found that can be reduced to&
4. reduces error
5. emits a diagnostic message
6. resumes normal parsing.
Unfortunately this error recovery mechanism is not powerful enough to correctly report any kind of syntactic error:& error rules cannot be inserted anywhere into an LALR grammar because they may introduce both shift/reduce and reduce/reduce conflicts.
A parser with error rules for mjava is specified in
When run on the input program , it will produce the output reported in
on the Java console.
6、Symbol table 语法表
Once completed the syntax analysis, we can start to develop the semantic analysis phase.
First of all we have to design the symbol table organization, in order to hold information about source-program constructs.
Information will be collected incrementally by the analysis phase and used by the synthesis phase to generate the code.
Entries in the symbol table will contain information about every identifier, such as its lexeme, its type, its position in storage, and any other information relevant to the translation process.
Since mjava admits nested environments, where identifiers can be redeclared, we support multiple declarations of a same identifier by setting up a separate symbol table for each scope.
The most-closely nested rule will be implemented by chaining the symbol tables so that the table for a nested scope points to the table for its enclosing scope.
An example of multiple declarations, their scopes, and the corresponding chained symbol tables is shown in the figure:
The implementation of chained symbol tables is defined by the class
This class models an environment by means of an HashMap (table) and a reference (prev) to the table of the static variables
top and root
maintain the references to the current environment and to the root environment respectively.
Entries in a table are key-value pairs, where the key is the lexeme of an identifier and the value is an instance of the class
Symb, declared in , that will contain information about the identifier (in this first implementation
Symb is empty).
The following static methods are declared in class Env
1. put adds a new entry in the current environment if its lexeme is not already there
2. get retrieves an entry in the chain of tables starting from the current environment
3. putClass adds a new entry in the root environment if its lexeme (a class name) is not already there and its super class (if any) has already been declared
4. push creates a new environment and makes& it the current environment
5. pop restores the previous environment.
The current environment is printed on the Java console anytime it is modified.
The construction of symbol tables for mjava is specified in
You can generate the parser and run it on the input program
by means of
should be stored in a subdirectory named
The output reported in&
will be printed on the Java console.
7、Types 数据类型
The structure of a type in mjava is represented by a type expression defined as:
? a basic type ( integer, floating, character, boolean, void, error )
? the expression formed by applying a type constructor (name, array, product, method, constructor, reference ) to a type expression.
Types are implemented by the class hierarchy in package
type : the superclass Type in , declares a field (tag) corresponding to either a basic type or a type constructor, and a field (width) containing the number of bytes required to store variables
of that type.
Each type constructor is implemented by a corresponding subclass of
Type defined, respectively, in , , , , , and .
Type expressions are strings formed by:
? just a tag (for basic types)
? the tag of a type constructor followed by the type expression to which it applies (for constructed types).
In order to efficiently check type equivalence, we maintain a dictionary of the types declared in a source program by means of the HashMap
table in class Type
: entries in the dictionary are key-value pairs where the key is a type expression and the value is the corresponding Type object.
When a type is encountered in the source program, its type expression is searched for in the dictionary: if present, the corresponding
Type object is retrieved and used, otherwise a new
Type object is created and a new entry is added to the dictionary.
In this way two types are equivalent if and only if they are represented by the same
Type object.
To complete the construction of symbol tables, we have to specify the information we want to collect about identifiers in the class&
we have declared the following fields:
? a reference (type) to a
Type object
? a reference (ownerClass) to the
Name object of the class where the identifier is declared
? a boolean value (pub), indicating whether the identifier is public or private.
In order to admit forward references, it is necessary to postpone type checking until all the identifiers have been inserted into the symbol table, and therefore to organize the front end in two passes: the first one to create the symbol table, the second one
to perform type checking and intermediate code generation.
The front end for mjava specified in
implements two passes by reading and processing the source file two times .
The& static variables parser.first and
parser.second indicate the current pass.
In the second pass the parser moves through the chains of symbol tables, following the same path followed in the first pass.
This behavior is obtained by saving, in the first pass, the current (top) environment into the ArrayList
newEnvs (in class
Env ) anytime it is going to be changed by push
and pop operations.
In the second pass the sequence of environments saved in
newEnvs is restored by invoking& method next
of class Env in ,& in place of push and
You can generate the parser and run it on the input program
by means of
(the type package should be stored in a subdirectory named
The output reported in&
will be printed on the Java console.
8、Type Checking 类型检查
In the second pass, the compiler front end must firstly perform type checking, to assure that the type of a construct matches the type expected by its context.
Type checking rules have to verify that operators and functions are applied to the right number and types of operands.
Actual types must match with expected types even when coercion occurs (the type of an operand is automatically converted to the type expected by an operator).
The type checker for mjava is specified in .
You can generate the parser and run it on the input program
by means of the files in .
The output reported in&
will be printed on the Java console.
9、Code generation 代码生成
Finally the front end of a compiler has to generate intermediate code.
Since we don't aim at developing a new back end for our compiler, the choice of an intermediate representation& language is determined by the choice of an already available back end.
compiler infrastructure is a collection of source code that implements static back ends for the X86, X86-64, PowerPC, PowerPC-64, ARM, Thumb, SPARC, Alpha, and IA-64 architectures.
LLVM uses a
that provides type safety, low-level operations and flexibility.
We have installed LLVM-2.7 revision on the Linux
platform and used the shell script
to perform the following steps:
1. assemble a LLVM program ( .ll file ) into LLVM bitcode (
.bc file )
2. compile LLVM bitcode into Intel assembly language for the x86 architecture (
3. run LLVM bitcode .
The LLVM code generator for mjava is specified in
In this first implementation, we have only considered non object-oriented mjava programs, such as
, where no class instance is created and all the methods are called internally to their declaring classes.
You can generate the front end, run it on the input program
to produce the LLVM program , and finally launch llvm& by means of
and the files in .
The x86 assembly program
will be emitted and the output reported in&
will be printed on your terminal.
You can also try to compile and run the other mjava
programs stored in the CodeGenerator/source directory, or to write and test your own mjava programs.
10、Object oriented code generation 面向对象的代码生成
In object oriented languages such as Java (and mjava), array and object variables behave like pointers whose values are assigned when new instances are created.
When a method is called externally to its declaring class, the following operations must be performed:
1. determine the class in which the method is declared and look for the method in that class
2. pass the object on which the method is called as an extra argument of the method call.
The translation of method declarations must avoid name clashes among methods declared with the same name in different classes: for this reason the name of the translated method is the concatenation of the class name and the method name.
The final version of the LLVM code generator for mjava is specified in
You can generate the front end, run it on the input program
to produce the LLVM program
and finally launch llvm& by means of
and the files in .
The x86 assembly program
will be emitted and the output reported in&
will be printed on your terminal.
You can also try to compile and run the other mjava programs stored in the
OOCodeGenerator/source directory, or to write and test your own
mjava programs.
本文原文来自：，转载请注明原始出处。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：75964次
排名：千里之外
原创：25篇
(3)(4)(6)(4)(4)(5)2005年5月 Java大版内专家分月排行榜第三2005年3月 Java大版内专家分月排行榜第三
2005年5月 Java大版内专家分月排行榜第三2005年3月 Java大版内专家分月排行榜第三
本帖子已过去太久远了，不再提供回复功能。