Parsing - Introduction to Compiler Construction in a Java World - page 59

Chapter3
Parsing
3.1 Introduction
Once we have identified the tokens in our program, we then want to determine its syntactic
structure. That is, we want to put the tokens together to make the larger syntactic entities:
expressions, statements, methods, and class definitions. This process of determining the
syntactic structure of a program is called parsing.
First, we wish to make sure the program is syntactically valid|that it conforms to the
grammar that describes its syntax. As the parser parses the program it should identify
syntax errors and report them and the line numbers they appear on. Moreover, when the
parser does find a syntax error, it should not just stop, but it should report the error and
gracefully recover so that it may go on looking for additional errors.
Second, the parser should produce some representation of the parsed program that is
suitable for semantic analysis. In the j-- compiler, we produce an abstract syntax tree (AST).
For example, given the j-- program we saw in Chapter 2,
packagepass;f
importjava.lang.System;
publicclassFactorial{
//Twomethodsandafield
publicstaticintfactorial(intn){
if(n<=0)
return1;
else
returnn*factorial(n-1);
}
publicstaticvoidmain(String[]args){
intx=n;
System.out.println(x+"!="+factorial(x));
}
staticintn=5;
}
we would like to produce an abstract syntax tree such as that in Figure 3.1 (the boxes
represent ArrayList s).
Notice that the nodes in the AST represent our syntactic objects. The tree is rooted at
a JCompilationUnit , the syntactic object representing the program that we are compiling.
The directed edges are labeled by the names of the fields they represent; for example, the
JCompilationUnit has a package name, a list (an ArrayList ) of imported types, and a list
(an ArrayList ) of class declarations|in this case just one.
59