Compiler Construction Using Java, JavaCC, and Yacc

Front Cover
John Wiley & Sons, Feb 28, 2012 - Computers - 664 pages
0 Reviews
Broad in scope, involving theory, the application of that theory, and programming technology, compiler construction is a moving target, with constant advances in compiler technology taking place. Today, a renewed focus on do-it-yourself programming makes a quality textbook on compilers, that both students and instructors will enjoy using, of even more vital importance. This book covers every topic essential to learning compilers from the ground up and is accompanied by a powerful and flexible software package for evaluating projects, as well as several tutorials, well-defined projects, and test cases.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

CHAPTER 12
123 GRAMMAR FOR SOURCE LANGUAGE
124 THE TARGET LANGUAGE
125 SYMBOL TABLE
127 token CLASS
128 WRITING THE TRANSLATION GRAMMAR
129 IMPLEMENTING THE S1 COMPILER
1210 TRYING OUT S1

15 NULL STRING
16 CONCATENATION
18 STAR OPERATOR ALSO KNOWN AS THE ZEROORMORE OPERATOR
19 CONCATENATION OF SETS OF STRINGS
110 PLUS OPERATOR ALSO KNOWN AS THE ONEORMORE OPERATOR
111 QUESTION MARK OPERATOR ALSO KNOWN AS ZEROORONE OPERATOR
112 SHORTHAND NOTATION FOR A SET CONTAINING A SINGLE STRING
114 REGULAR EXPRESSIONS
115 LIMITATIONS OF REGULAR EXPRESSIONS
PROBLEMS
CHAPTER 2
22 WHAT IS A CONTEXTFREE GRAMMAR?
23 DERIVATIONS USING A CONTEXTFREE GRAMMAR
24 LANGUAGE DEFINED BY A CONTEXTFREE GRAMMAR
25 DIFFERENT WAYS OF REPRESENTING CONTEXTFREE GRAMMARS
26 SOME SIMPLE GRAMMARS
27 TECHNIQUES FOR GENERATING LANGUAGES WITH CONTEXTFREE GRAMMARS
28 REGULAR AND RIGHT LINEAR GRAMMARS
29 COUNTING WITH REGULAR GRAMMARS
210 GRAMMARS FOR LISTS
211 AN IMPORTANT LANGUAGE THAT IS NOT CONTEXTFREE
PROBLEMS
CHAPTER 3
33 LEFTMOST AND RIGHTMOST DERIVATIONS
34 SUBSTITUTION
35 AMBIGUOUS GRAMMARS
36 DETERMINING NULLABLE NONTERMINALS
37 ELIMINATING LAMBDA PRODUCTIONS
38 ELIMINATING UNIT PRODUCTIONS
39 ELIMINATING USELESS NONTERMINALS
310 RECURSION CONVERSIONS
311 ADDING THE NULL STRING TO A LANGUAGE
PROBLEMS
CHAPTER 4
43 SPECIFYING ASSOCIATIVITY AND PRECEDENCE IN GRAMMARS
44 BACKUSNAUR FORM
45 SYNTAX DIAGRAMS
46 ABSTRACT SYNTAX TREES AND THREEADDRESS CODE
47 NONCONTRACTING GRAMMARS
49 CONVERTING A CONTEXTFREE GRAMMAR TO AN ESSENTIALLY NONCONTRACTING GRAMMAR
410 PUMPING PROPERTY OF CONTEXTFREE LANGUAGES OPTIONAL
PROBLEMS
CHAPTER 5
52 CONTEXTSENSITIVE PRODUCTIONS
53 CONTEXTSENSITIVE GRAMMARS
54 UNRESTRICTED GRAMMARS
PROBLEMS
CHAPTER 6
63 PARSES THAT FAIL
64 A BAD GRAMMAR FOR TOPDOWN PARSING
65 DETERMINISTIC PARSERS
66 A PARSER THAT USES A STACK
67 TABLE REPRESENTATION OF A STACK PARSER
68 HANDLING PRODUCTIONS WITH NONLEADING TERMINALS
69 WRITING A STACK PARSER IN JAVA
PROBLEMS
CHAPTER 7
73 DETERMINING OPERATION SEQUENCES
74 DETERMINING SELECTION SETS OF LAMBDA PRODUCTIONS
75 WHATEVERFOLLOWSLEFTFOLLOWSRIGHTMOST RULE
76 SELECTION SETS FOR PRODUCTIONS WITH NULLABLE RIGHT SIDES
77 SELECTION SETS CONTAINING THE ENDOFINPUT MARKER
78 A STACK PARSER FOR A GRAMMAR WITH LAMBDA PRODUCTIONS
79 CONVERTING A NONLL1 GRAMMAR TO AN LL1 GRAMMAR
710 PARSING WITH AN AMBIGUOUS GRAMMAR
711 COMPUTING FIRST AND FOLLOW SETS
PROBLEMS
CHAPTER 8
82 UNIFYING THE OPERATIONS OF A STACK PARSER
83 IMPLEMENTING A TABLEDRIVEN STACK PARSER
84 IMPROVING OUR TABLEDRIVEN STACK PARSER
85 PARSERS THAT ARE NOT DETERMINISTICA DIGRESSION ON THEORY OPTIONAL
PROBLEMS
CHAPTER 9
92 A SIMPLE RECURSIVEDESCENT PARSER
93 HANDLING LAMBDA PRODUCTIONS
94 A COMMON ERROR
95 JAVA CODE FOR PRODUCTIONS
96 LEFT FACTORING IN A RECURSIVEDESCENT PARSER
97 ELIMINATING TAIL RECURSION
98 TRANSLATING THE STAR PLUS AND QUESTION MARK OPERATORS
99 DOING THINGS BACKWARD
PROBLEMS
CHAPTER 10
102 A SIMPLE TRANSLATION GRAMMAR
103 CONVERTING A TRANSLATION GRAMMAR TO JAVA CODE
104 SPECIFICATIONS FOR A TRANSLATION GRAMMAR
105 PASSING INFORMATION DURING THE PARSE
106 LATTRIBUTED GRAMMARS
107 A NEW TOKEN MANAGER
108 SOLVING THE TOKEN LOOKAHEAD PROBLEM
1010 TRANSLATION GRAMMAR FOR PREFIX EXPRESSION COMPILER
1011 AN INTERESTING USE OF RECURSION OPTIONAL
PROBLEMS
CHAPTER 11
112 STRUCTURE OF THE J1 COMPUTER
113 MACHINE LANGUAGE INSTRUCTIONS
114 ASSEMBLY LANGUAGE INSTRUCTIONS
115 PUSHING CHARACTERS
117 USING LABELS
118 USING THE ASSEMBLER
119 stav INSTRUCTION
1110 COMPILING AN ASSIGNMENT STATEMENT
1111 COMPILING print AND println
1112 OUTPUTTING STRINGS
1113 INPUTTING DECIMAL NUMBERS
1114 ENTRY DIRECTIVE
1115 MORE ASSEMBLY LANGUAGE
1211 ADVICE ON EXTENDING THE S1 COMPILER
1212 SPECIFICATIONS FOR S2
PROBLEMS
CHAPTER 13
132 JavaCC EXTENDED REGULAR EXPRESSIONS
133 JavaCC INPUT FILE
134 SPECIFYING ACTIONS FOR REGULAR EXPRESSIONS
135 JavaCC INPUT FILE FOR S1j
136 FILES PRODUCED BY JavaCC
137 USING THE STAR AND PLUS OPERATORS
138 CHOICE POINTS AND LOOKAHEAD
139 JavaCCS CHOICE ALGORITHM
1310 SYNTACTIC AND SEMANTIC LOOKAHEAD OPTIONAL
1311 USING JavaCC TO CREATE A TOKEN MANAGER ONLY
1312 USING THE TOKEN CHAIN
1313 SUPPRESSING WARNING MESSAGES
PROBLEMS
CHAPTER 14
142 EXTENDING println AND print
143 CASCADED ASSIGNMENT STATEMENT
144 UNARY PLUS AND MINUS
145 readint STATEMENT
147 SPECIFICATIONS FOR S3
PROBLEMS
CHAPTER 15
152 while STATEMENT
153 if STATEMENT
154 dowhile STATEMENT
155 RANGE CHECKING OF NUMERICAL CONSTANTS
156 HANDLING BACKSLASHQUOTE IN A STRING
157 HANDLING BACKSLASHQUOTE WITH JAVACC OPTIONAL
158 UNIVERAL BLOCKS IN JAVACC OPTIONAL
159 HANDLING STRINGS THAT SPAN LINES
1510 HANDLING STRINGS THAT SPAN LINES USING JAVACC OPTIONAL
1511 SPECIAL_TOKEN BLOCK IN JAVACC OPTIONAL
1512 ERROR RECOVERY
1513 ERROR RECOVERY IN JavaCC OPTIONAL
1514 SPECIFICATIONS FOR S4
PROBLEMS
CHAPTER 16
162 SEPARATE ASSEMBLY AND LINKING
163 CALLING AND RETURNING FROM FUNCTIONS
164 SOURCE LANGUAGE FOR S5
165 SYMBOL TABLE FOR S5
166 CODE GENERATOR FOR S5
167 TRANSLATION GRAMMAR FOR S5
168 LINKING WITH A LIBRARY
169 SPECIFICATIONS FOR S5
1610 EXTENDING S5 OPTIONAL
PROBLEMS
CHAPTER 17
172 DETERMINISTIC FINITE AUTOMATA
173 CONVERTING A DFA TO A REGULAR EXPRESSION
174 JAVA CODE FOR A DFA
175 NONDETERMINISTIC FINITE AUTOMATA
176 USING AN NFA AS AN ALGORITHM
177 CONVERTING AN NFA TO A DFA WITH THE SUBSET ALGORITHM
178 CONVERTING A DFA TO A REGULAR GRAMMAR
179 CONVERTING A REGULAR GRAMMAR TO AN NFA
1710 CONVERTING A REGULAR EXPRESSION TO AN NFA
1711 FINDING THE MINIMAL DFA
1712 PUMPING PROPERTY OF REGULAR LANGUAGES
PROBLEMS
CHAPTER 18
182 REGULAR EXPRESSIONS FOR OUR GREP PROGRAM
183 TOKEN MANAGER FOR REGULAR EXPRESSIONS
184 GRAMMAR FOR REGULAR EXPRESSIONS
185 TARGET LANGUAGE FOR OUR REGULAR EXPRESSION COMPILER
186 USING AN NFA FOR PATTERN MATCHING
PROBLEMS
CHAPTER 19
192 USING THE REGISTER INSTRUCTION SET
193 MODIFICATIONS TO THE SYMBOL TABLE FOR R1
194 PARSER AND CODE GENERATOR FOR R1
PROBLEMS
CHAPTER 20
202 USING THE ldc INSTRUCTION
203 REUSING TEMPORARY VARIABLES
204 CONSTANT FOLDING
205 REGISTER ALLOCATION
206 PEEPHOLE OPTIMIZATION
PROBLEMS
CHAPTER 21
212 CONVERTING S1 TO I1
213 INTERPRETING STATEMENTS THAT TRANSFER CONTROL
214 IMPLEMENTING THE COMPILERINTERPRETER CI1
215 ADVANTAGES OF INTERPRETERS
PROBLEMS
CHAPTER 22
222 PRINCIPLES OF BOTTOMUP PARSING
223 PARSING WITH RIGHT VERSUS LEFTRECURSIVE GRAMMARS
224 BOTTOMUP PARSING WITH AMBIGUOUS GRAMMARS
225 DONOTREDUCE RULE
226 SLR1 PARSING
227 SHIFTREDUCE CONFLICTS
228 REDUCEREDUCE CONFLICTS
229 LR1 PARSING
PROBLEMS
CHAPTER 23
232 yacc INPUT AND OUTPUT FILES
232 A SIMPLE yaccGENERATED PARSER
234 PASSING VALUES USING THE VALUE STACK
235 USING yacc WITH AN AMBIGUOUS GRAMMAR
236 PASSING VALUES DOWN THE PARSE TREE
237 IMPLEMENTING Sly
238 jflex
PROBLEMS
Copyright

Other editions - View all

Common terms and phrases

About the author (2012)

Anthony J. Dos Reis is Associate Professor of Computer Science at the State University of New York at New Paltz. Before becoming a professor, Dr. Dos Reis worked at IBM as a systems programmer, creating IBM operating systems and compilers. His teaching interests include computer engineering, program translation, Java, and formal languages.

Bibliographic information