Log In
Or create an account ->
Imperial Library
Home
About
News
Upload
Forum
Help
Login/SignUp
Index
Cover
Half Title page
Title page
Copyright page
Dedication
Preface
Notable Features
Software Package
Projects
Useful References
Acknowledgments
Chapter 1: Strings, Languages, and Compilers
1.1 Introduction
1.2 Basic Language Concepts
1.3 Basic Compiler Concepts
1.4 Basic Set Theory
1.5 Null String
1.6 Concatenation
1.7 Exponent Notation
1.8 Star Operator (Also Known as the Zero-or-More Operator)
1.9 Concatenation of Sets of Strings
1.10 Plus Operator (Also Known as the One-or-More Operator)
1.11 Question Mark Operator (Also Known as Zero-or-One Operator)
1.12 Shorthand Notation for a Set Containing a Single String
1.13 Operator Precedence
1.14 Regular Expressions
1.15 Limitations of Regular Expressions
Problems
Chapter 2: Context-Free Grammars, Part 1
2.1 Introduction
2.2 What is a Context-Free Grammar?
2.3 Derivations Using a Context-Free Grammar
2.4 Language Defined by a Context-Free Grammar
2.5 Different Ways of Representing Context-Free Grammars
2.6 Some Simple Grammars
2.7 Techniques for Generating Languages with Context-Free Grammars
2.8 Regular and Right Linear Grammars
2.9 Counting with Regular Grammars
2.10 Grammars for Lists
2.11 An Important Language that is not Context-Free
Problems
Chapter 3: Context-Free Grammars, Part 2
3.1 Introduction
3.2 Parse Trees
3.3 Leftmost and Rightmost Derivations
3.4 Substitution
3.5 Ambiguous Grammars
3.6 Determining Nullable Nonterminals
3.7 Eliminating Lambda Productions
3.8 Eliminating Unit Productions
3.9 Eliminating Useless Nonterminals
3.10 Recursion Conversions
3.11 Adding the Null String to a Language
Problems
Chapter 4: Context-Free Grammars, Part 3
4.1 Introduction
4.2 Grammars for Arithmetic Expressions
4.3 Specifying Associativity and Precedence in Grammars
4.4 Backus-Naur Form
4.5 Syntax Diagrams
4.6 Abstract Syntax Trees and Three-Address Code
4.7 Noncontracting Grammars
4.8 Essentially Noncontracting Grammars
4.9 Converting a Context-Free Grammar to an Essentially Noncontracting Grammar
4.10 Pumping Property of Context-Free Languages (Optional)
Problems
Chapter 5: Chomsky’s Hierarchy (Optional)
5.1 Introduction
5.2 Context-Sensitive Productions
5.3 Context-Sensitive Grammars
5.4 Unrestricted Grammars
Problems
Chapter 6: Top-Down Parsing
6.1 Introduction
6.2 Top-Down Construction of a Parse Tree
6.3 Parses that Fail
6.4 A Bad Grammar for Top-Down Parsing
6.5 Deterministic Parsers
6.6 A Parser that Uses a Stack
6.7 Table Representation of a Stack Parser
6.8 Handling Productions with Nonleading Terminals
6.9 Writing a Stack Parser in Java
Problems
Chapter 7: LL(1) Grammars
7.1 Introduction
7.2 FIRST Set of the Right Side of a Production
7.3 Determining Operation Sequences
7.4 Determining Selection Sets of Lambda Productions
7.5 Whatever-Follows-Left-Follows-Rightmost Rule
7.6 Selection Sets for Productions with Nullable Right Sides
7.7 Selection Sets Containing the End-of-Input Marker
7.8 A Stack Parser for a Grammar with Lambda Productions
7.9 Converting a Non-LL(1) Grammar to an LL(1) Grammar
7.10 Parsing with an Ambiguous Grammar
7.11 Computing FIRST and FOLLOW Sets
Problems
Chapter 8: Table-Driven Stack Parser (Optional)
8.1 Introduction
8.2 Unifying the Operations of a Stack Parser
8.3 Implementing a Table-Driven Stack Parser
8.4 Improving Our Table-Driven Stack Parser
8.5 Parsers that are Not Deterministic—A Digression on Theory (Optional)
Problems
Chapter 9: Recursive-Descent Parsing
9.1 Introduction
9.2 A Simple Recursive-Descent Parser
9.3 Handling Lambda Productions
9.4 A Common Error
9.5 Java Code for Productions
9.6 Left Factoring in a Recursive-Descent Parser
9.7 Eliminating Tail Recursion
9.8 Translating the Star, Plus, and Question Mark Operators
9.9 Doing Things Backward
Problems
Chapter 10: Recursive-Descent Translation
10.1 Introduction
10.2 A Simple Translation Grammar
10.3 Converting a Translation Grammar to Java Code
10.4 Specifications for a Translation Grammar
10.5 Passing Information During the Parse
10.6 L-Attributed Grammars
10.7 A New Token Manager
10.8 Solving the Token Lookahead Problem
10.9 Code for the New Token Manager
10.10 Translation Grammar for Prefix Expression Compiler
10.11 An Interesting Use of Recursion (Optional)
Problems
Chapter 11: Assembly Language
11.1 Introduction
11.2 Structure of the J1 Computer
11.3 Machine Language Instructions
11.4 Assembly Language Instructions
11.5 Pushing Characters
11.6 aout Instruction
11.7 Using Labels
11.8 Using the Assembler
11.9 stav Instruction
11.10 Compiling an Assignment Statement
11.11 Compiling Print and Println
11.12 Outputting Strings
11.13 Inputting Decimal Numbers
11.14 Entry Directive
11.15 More Assembly Language
Problems
Chapter 12: S1—A Simple Compiler
12.1 Introduction
12.2 The Source Language
12.3 Grammar for Source Language
12.4 The Target Language
12.5 Symbol Table
12.6 Code Generator
12.7 token Class
12.8 Writing the Translation Grammar
12.9 Implementing the S1 Compiler
12.10 Trying Out S1
12.11 Advice on Extending the S1 Compiler
12.12 Specifications for S2
Problems
Chapter 13: JavaCC (Optional)
13.1 Introduction
13.2 JavaCC Extended Regular Expressions
13.3 JavaCC Input File
13.4 Specifying Actions for Regular Expressions
13.5 JavaCC Input File for S1j
13.6 Files Produced by JavaCC
13.7 Using the Star and Plus Operators
13.8 Choice Points and Lookahead
13.9 JavaCC’s Choice Algorithm
13.10 Syntactic and Semantic Lookahead (Optional)
13.11 Using JAVACC to Create a Token Manager Only
13.12 Using the Token Chain
13.13 Suppressing Warning Messages
Problems
Chapter 14: Building on S2
14.1 Introduction
14.2 Extending println and print
14.3 Cascaded Assignment Statement
14.4 Unary Plus and Minus
14.5 readint Statement
14.6 Controlling the Token Trace from the Command Line
14.7 Specifications for S3
Problems
Chapter 15: Compiling Control Structures
15.1 Introduction
15.2 while Statement
15.3 if Statement
15.4 do-while Statement
15.5 Range Checking of Numerical Constants
15.6 Handling Backslash-Quote in a String
15.7 Handling Backslash-Quote with JavaCC (Optional)
15.8 Univeral Blocks in javaCC (Optional)
15.9 Handling Strings that Span Lines
15.10 Handling Strings that Span Lines Using javaCC (Optional)
15.11 SPECIAL_TOKEN Block in javaCC (Optional)
15.12 Error Recovery
15.13 Error Recovery in JavaCC (Optional)
15.14 Specifications for S4
Problems
Chapter 16: Compiling Programs in Functional Form
16.1 Introduction
16.2 Separate Assembly and Linking
16.3 Calling and Returning from Functions
16.4 Source Language for S5
16.5 Symbol Table for S5
16.6 Code Generator for S5
16.7 Translation Grammar for S5
16.8 Linking with a Library
16.9 Specifications for S5
16.10 Extending S5 (Optional)
Problems
Chapter 17: Finite Automata
17.1 Introduction
17.2 Deterministic Finite Automata
17.3 Converting a DFA to a Regular Expression
17.4 JAVA Code for a DFA
17.5 Nondeterministic Finite Automata
17.6 Using an NFA as an Algorithm
17.7 Converting an NFA to a DFA with the Subset Algorithm
17.8 Converting a DFA to a Regular Grammar
17.9 Converting a Regular Grammar to an NFA
17.10 Converting a Regular Expression to an NFA
17.11 Finding the Minimal DFA
17.12 Pumping Property of Regular Languages
Problems
Chapter 18: Capstone Project: Implementing Grep Using Compiler Technology
18.1 Introduction
18.2 Regular Expressions for Our Grep Program
18.3 Token Manager for Regular Expressions
18.4 Grammar for Regular Expressions
18.5 Target Language for Our Regular Expression Compiler
18.6 Using an NFA for Pattern Matching
Problems
Chapter 19: Compiling to a Register-Oriented Architecture
19.1 Introduction
19.2 Using the Register Instruction Set
19.3 Modifications to the Symbol Table for R1
19.4 Parser and Code Generator for R1
Problems
Chapter 20: Optimization
20.1 Introduction
20.2 Using the ldc Instruction
20.3 Reusing Temporary Variables
20.4 Constant Folding
20.5 Register Allocation
20.6 Peephole Optimization
Problems
Chapter 21: Interpreters
21.1 Introduction
21.2 Converting S1 to I1
21.3 Interpreting Statements that Transfer Control
21.4 Implementing the Compiler-Interpreter CI1
21.5 Advantages of Interpreters
Problems
Chapter 22: Bottom-up Parsing
22.1 Introduction
22.2 Principles of Bottom-Up Parsing
22.3 Parsing with Right- Versus Left-Recursive Grammars
22.4 Bottom-Up Parsing with Ambiguous Grammars
22.5 Do-Not-Reduce Rule
22.6 SLR(1) Parsing
22.7 Shift/Reduce Conflicts
22.8 Reduce/Reduce Conflicts
22.9 LR(1) Parsing
Problems
Chapter 23: yacc
23.1 Introduction
23.2 yacc Input and Output Files
23.2 A Simple yacc-Generated Parser
23.4 Passing Values Using the Value Stack
23.5 Using yacc with an Ambiguous Grammar
23.6 Passing Values Down the Parse Tree
23.7 Implementing Sly
23.8 jflex
Problems
Appendix A: Stack Instruction Set
Appendix B: Register Instruction Set
References
Index
← Prev
Back
Next →
← Prev
Back
Next →