Muutke küpsiste eelistusi

E-raamat: Compiler Construction Using Java, JavaCC and Yacc [Wiley Online]

(State University of New York New Paltz)
  • Formaat: 664 pages, Drawings: 10 B&W, 0 Color
  • Ilmumisaeg: 20-Jan-2012
  • Kirjastus: John Wiley & Sons Inc
  • ISBN-10: 1118112768
  • ISBN-13: 9781118112762
Teised raamatud teemal:
  • Wiley Online
  • Hind: 116,25 €*
  • * hind, mis tagab piiramatu üheaegsete kasutajate arvuga ligipääsu piiramatuks ajaks
Compiler Construction Using Java, JavaCC and YaccSuurem pilt
  • Formaat: 664 pages, Drawings: 10 B&W, 0 Color
  • Ilmumisaeg: 20-Jan-2012
  • Kirjastus: John Wiley & Sons Inc
  • ISBN-10: 1118112768
  • ISBN-13: 9781118112762
Teised raamatud teemal:
Wiley Online e-raamatudRohkem infot Wiley Online kohta
Raamatu kodulehekülg: https://onlinelibrary.wiley.com/doi/book/10.1002/9781118112762

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.

Preface xv
Chapter 1 Strings, Languages, and Compilers
1(18)
1.1 Introduction
1(1)
1.2 Basic Language Concepts
1(2)
1.3 Basic Compiler Concepts
3(1)
1.4 Basic Set Theory
4(2)
1.5 Null String
6(1)
1.6 Concatenation
7(1)
1.7 Exponent Notation
7(1)
1.8 Star Operator
8(1)
1.9 Concatenation of Sets of Strings
9(2)
1.10 Plus Operator
11(1)
1.11 Question Mark Operator
11(1)
1.12 Shorthand Notation for a Set Containing a Single String
12(1)
1.13 Operator Precedence
12(1)
1.14 Regular Expressions
13(2)
1.15 Limitations of Regular Expressions
15(4)
Problems
16(3)
Chapter 2 Context-Free Grammars, Part 1
19(30)
2.1 Introduction
19(1)
2.2 What is a Context-Free Grammar?
20(1)
2.3 Derivations Using a Context-Free Grammar
21(2)
2.4 Language Defined by a Context-Free Grammar
23(2)
2.5 Different Ways of Representing Contet-Free Grammars
25(1)
2.6 Some Simple Grammars
26(3)
2.7 Techniques for Generating Languages with Context-Free Grammars
29(6)
2.8 Regular and Right Linear Grammars
35(2)
2.9 Counting with Regular Grammars
37(2)
2.0 Grammars for Lists
39(5)
2.10 An Important Language that is Not Context Free
44(5)
Problems
45(4)
Chapter 3 Context-Free Grammars, Part 2
49(34)
3.1 Introduction
49(1)
3.2 Parse Trees
49(2)
3.3 Leftmost and Rightmost Derivations
51(1)
3.4 Substitution
52(2)
3.5 Ambiguous Grammars
54(5)
3.6 Determining Nullable Nonterminals
59(1)
3.7 Eliminating Lambda Productions
60(4)
3.8 Eliminating Unit Productions
64(2)
3.9 Eliminating Useless Nonterminals
66(5)
3.10 Recursion Conversions
71(5)
3.11 Adding the Null String to a Language
76(7)
Problems
77(6)
Chapter 4 Context-Free Grammars, Part 3
83(24)
4.1 Introduction
83(1)
4.2 Grammars for Arithmetic Expressions
83(7)
4.3 Specifying Associativity and Precedence in Grammars
90(2)
4.4 Backus-Naur Form
92(2)
4.5 Syntax Diagrams
94(2)
4.6 Abstract Syntax Trees and Three-Address Code
96(1)
4.7 Noncontracting Grammars
97(1)
4.8 Essentially Noncontracting Grammars
97(1)
4.9 Converting a Context-Free Grammar to an Essentially Noncontracting Grammar
98(3)
4.10 Pumping Property of Context-Free Languages
101(6)
Problems
104(3)
Chapter 5 Chomsky's Hierarchy
107(8)
5.1 Introduction
107(1)
5.2 Context-Sensitive Productions
107(3)
5.3 Context-Sensitive Grammars
110(1)
5.4 Unrestricted Grammars
111(4)
Problems
112(3)
Chapter 6 Top-Down Parsing
115(22)
6.1 Introduction
115(1)
6.2 Top-Down Construction of a Parse Tree
115(2)
6.3 Parses that Fail
117(1)
6.4 A Bad Grammar for Top-Down Parsing
118(1)
6.5 Deterministic Parsers
119(1)
6.6 A Parser that Uses a Stack
120(4)
6.7 Table Representation of a Stack Parser
124(2)
6.8 Handling Productions with Nonleading Terminal
126(1)
6.9 Writing a Stack Parser in Java
127(10)
Problems
134(3)
Chapter 7 LL(1) Grammars
137(34)
7.1 Introduction
137(1)
7.2 FIRST Set of the Right Side of a Production
137(3)
7.3 Determining Operation Sequences
140(2)
7.4 Determining Selection Sets of Lambda Productions
142(3)
7.5 Whatever-Follows-Left-Follows-Rightmost Rule
145(2)
7.6 Selection Sets for Productions with Nullable Right Sides
147(2)
7.7 Selection Sets Containing End-of-Input Symbol
149(3)
7.8 A Stack Parser for a Grammar with Lambda Productions
152(1)
7.9 Converting a Non-LL(1) Grammar to an LL(1) Grammar
153(7)
7.10 Parsing with an Ambiguous Grammar
160(3)
7.11 Computing FIRST and FOLLOW Sets
163(8)
Problems
165(6)
Chapter 8 Table-Driven Stack Parser
171(14)
8.1 Introduction
171(1)
8.2 Unifying the Operations of a Stack Parser
172(3)
8.3 Implementing a Table-Driven Stack Parser
175(5)
8.4 Improving Our Table-Driven Stack Parser
180(1)
8.5 Parsers that are Not Deterministic---A Digression on Theory
181(4)
Problems
183(2)
Chapter 9 Recursive-Descent Parsing
185(30)
9.1 Introduction
185(1)
9.2 Simple Recursive-Descent Parser
185(7)
9.3 Handling Lambda Productions
192(5)
9.4 A Common Error
197(1)
9.5 Java Code for Productions
198(1)
9.6 Left Factoring in a Recursive-Descent Parser
199(5)
9.7 Eliminating Tail Recursion
204
9.8 Translating the Star, Plus, and Question Mark Operators
108(102)
9.9 Doing Things Backward
210(5)
Problems
211(4)
Chapter 10 Recursive-Descent Translation
215(50)
10.1 Introduction
215(1)
10.2 A Simple Translation Grammar
215(2)
10.3 Converting a Translation Grammar to Java Code
217(1)
10.4 Specifications for a Translation Grammar
218(13)
10.5 Passing Information During a Parse
231(5)
10.6 L-Attributed Grammars
236(2)
10.7 New Token Manager
238(3)
10.8 Solving the Token Lookahead Problem
241(1)
10.9 Code for the New Token Manager
241(12)
10.10 Translation Grammar for Prefix Expression Compiler
253(4)
10.11 An Interesting Use of Recursion
257(8)
Problems
261(4)
Chapter 11 Assembly Language
265(24)
11.1 Introduction
265(1)
11.2 Structure of the J1 Computer
265(1)
11.3 Machine Language Instructions
266(2)
11.4 Assembly Language Instructions
268(1)
11.5 Pushing Characters
269(1)
11.6 Aout Instruction
270(1)
11.7 Using Labels
270(2)
11.8 Using the Assembler
272(3)
11.9 Stav Instruction
275(2)
11.10 Compiling an Assignment Statement
277(3)
11.11 Compiling print and println
280(1)
11.12 Outputting Strings
281(2)
11.13 Inputting Decimal Numbers
283(1)
11.14 Entry Directive
284(1)
11.15 More Assembly Language
285(4)
Problems
285(4)
Chapter 12 S1---A Simple Compiler
289(42)
12.1 Introduction
289(1)
12.2 The Source Language
289(1)
12.3 Grammar for Source Language
290(1)
12.4 The Target Language
291(1)
12.5 Symbol Table
292(1)
12.6 Code Generator
293(1)
12.7 Token Class
293(1)
12.8 Writing the Translation Grammar
294(5)
12.9 Implementing the S1 Compiler
299(16)
12.10 Trying Out S1
315(3)
12.11 Advice on Extending the S1 Compiler
318(2)
12.12 Specifications for S2
320(11)
Problems
324(7)
Chapter 13 JavaCC
331(52)
13.1 Introduction
331(2)
13.2 JavaCC Extended Regular Expressions
333(4)
13.3 JavaCC Input File
337(7)
13.4 Specifying Actions for Regular Expressions
344(4)
13.5 JavaCC Input File for S1j
348(7)
13.6 Files Produced by JavaCC
355(4)
13.7 Using the Star and Plus Operators
359(3)
13.8 Choice Points and the Lookahead Directive
362(5)
13.9 JavaCC's Choice Algorithm
367(4)
13.10 Syntactic and Semantic Lookahead
371(1)
13.11 Using JavaCC to Create a Token Manager Only
372(1)
13.12 Using the Token Chain
373(4)
13.13 Suppressing Warning Messages
377(6)
Problems
387
Chapter 14 Building on S2
383(16)
14.1 Introduction
383(1)
14.2 Extending println and print
383(5)
14.3 Cascaded Assignment Statement
388
14.4 Unary Plus and Minus
313(80)
14.5 Readint Statement
393(2)
14.6 Controlling the Token Trace from the Command Line
395(1)
14.7 Specifications for S3
396(3)
Problems
396(3)
Chapter 15 Compiling Control Structures
399(36)
15.1 Introduction
399(1)
15.2 While Statement
399(4)
15.3 If Statement
403(4)
15.4 do-while Statement
407(1)
15.5 Range Checking of Numerical Constants
408(2)
15.6 Handling Backslash-Quote in a String
410(1)
15.7 Handling Backslash-Quote with JavaCC
411(5)
15.8 Universal Blocks in JavaCC
416(2)
15.9 Handling Strings that Span Lines
418(1)
15.10 Handling Strings that Span Lines Using JavaCC
419(3)
15.11 SPECIAL_TOKEN Block in JavaCC
422(2)
15.12 Error Recovery
424(5)
15.13 Error Recovery in JavaCC
429(1)
15.14 Specifications for S4
430(5)
Problems
431(4)
Chapter 16 Compiling Programs in Functional Form
435(30)
16.1 Introduction
435(1)
16.2 Separate Assembly and Linking
435(4)
16.3 Calling and Returning from Fuctions
439(4)
16.4 Source Language for S5
443(2)
16.5 Symbol Table for S5
445(1)
16.6 Code Generator for S5
446(1)
16.7 Translation Grammar for S5
447(10)
16.8 Linking with a Library
457(1)
16.9 Specifications for S5
458(1)
16.10 Extending S5
458(7)
Problems
461(4)
Chapter 17 Finite Automata
465(34)
17.1 Introduction
465(1)
17.2 Deterministic Finite Automata
466(2)
17.3 Converting a DFA to a Regular Expression
468(4)
17.4 Java Code for a DFA
472(2)
17.5 Nondeterministic Finite Automata
474(2)
17.6 Using an NFA as an Algorithm
476(2)
17.7 Converting an NFA to a DFA with the Subset Algorithm
478(1)
17.8 Converting a DFA to a Regular Grammar
479(3)
17.9 Converting a Regular Grammar to an NFA
482(2)
17.10 Converting a Regular Expression to an NFA
484(4)
17.11 Finding the Minimal DFA
488(5)
17.12 Pumping Property of Regular Languages
493(6)
Problems
495(4)
Chapter 18 Capstone Project: Implementing Grep Using Compiler Technology
499(16)
18.1 Introduction
499(2)
18.2 Regular Expressions for Our Grep Program
501(1)
18.3 Token Manager for Regular Expression
501(2)
18.4 Grammar for Regular Expressions
503(1)
18.5 Target Language for Our Regular Expression Compiler
503(5)
18.6 Using an NFA for Pattern Matching
508(7)
Problems
513(2)
Chapter 19 Compiling to a Register-Oriented Architecture
515(14)
19.1 Introduction
515(1)
19.2 Using the Register Instruction Set
516(1)
19.3 Modifications to the Symbol Table for R1
517(1)
19.4 Parser and Code Generator for R1
518(11)
Problems
526(3)
Chapter 20 Optimization
529(18)
20.1 Introduction
529(2)
20.2 Using the ldc Instruction
531(1)
20.3 Reusing Temporary Variables
532(3)
20.4 Constant Folding
535(2)
20.5 Register Allocation
537(3)
20.6 Peephole Optimization
540(7)
Problems
543(4)
Chapter 21 Interpreters
547(14)
21.1 Introduction
547(2)
21.2 Converting S1 to 11
549(3)
21.3 Interpreting Statements that Transfer Control
552(1)
21.4 Implementing the Compiler-Interpreter C11
553(5)
21.5 Advantages of Interpreters
558(3)
Problems
559(2)
Chapter 22 Bottom-Up Parsing
561(26)
22.1 Introduction
561(1)
22.2 Principles of Bottom-Up Parsing
561(4)
22.3 Parsing with Right-Versus Left-Recursive Grammars
565(1)
22.4 Bottom-Up Parsing with an Ambiguous Grammar
566(3)
22.5 Do-Not-Reduce Rule
569(1)
22.6 SLR(1) Parsing
570(7)
22.7 Shift/Reduce Conflicts
577(2)
22.8 Reduce/Reduce Conflicts
579(1)
22.9 LR(1) Parsing
579(8)
Problems
584(3)
Chapter 23 yacc
587(34)
23.1 Introduction
587(1)
23.2 Yacc Input and Output Files
587(1)
23.3 A Simple yacc-Generated Parser
588(8)
23.4 Passing Values Using the Value Stack
596(6)
23.5 Using yacc With an Ambiguous Grammar
602(2)
23.6 Passing Values down the Parse Tree
604(2)
23.7 Implementing S1y
606(6)
23.8 jflex
612(9)
Problems
618(3)
Appendix A Stack Instruction Set 621(4)
Appendix B Register Instruction Set 625(4)
References 629(2)
Index 631
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.
Püsilink: https://www.kriso.ee/db/9781118112762_pe.html
Märksõnad: