Compiler Construction Using Java, JavaCC, and Yacc

Compiler Construction Using Java, JavaCC, and Yace......Page 5
Contents......Page 9
Preface......Page 17
1.2 Basic Language Concepts......Page 21
1.3 Basic Compiler Concepts......Page 23
1.4 Basic Set Theory......Page 24
1.5 Null String......Page 26
1.7 Exponent Notation......Page 27
1.8 Star Operator......Page 28
1.9 Concatenation of Sets of Strings......Page 29
1.11 Question Mark Operator......Page 31
1.13 Operator Precedence......Page 32
1.14 Regular Expressions......Page 33
1.15 Limitations of Regular Expressions......Page 35
Problems......Page 36
2.1 Introduction......Page 39
2.2 What is a Context-Free Grammar?......Page 40
2.3 Derivations Using a Context-Free Grammar......Page 41
2.4 Language Defined by a Context-Free Grammar......Page 43
2.5 Different Ways of Representing Contet-Free Grammars......Page 45
2.6 Some Simple Grammars......Page 46
2.7 Techniques for Generating Languages with Context-Free Grammars......Page 49
2.8 Regular and Right Linear Grammars......Page 55
2.9 Counting with Regular Grammars......Page 57
2.10 Grammars for Lists......Page 59
2.11 An Important Language that is Not Context Free......Page 64
Problems......Page 65
3.2 Parse Trees......Page 69
3.3 Leftmost and Rightmost Derivations......Page 71
3.4 Substitution......Page 72
3.5 Ambiguous Grammars......Page 74
3.6 Determining Nullable Nonterminals......Page 79
3.7 Eliminating Lambda Productions......Page 80
3.8 Eliminating Unit Productions......Page 84
3.9 Eliminating Useless Nonterminals......Page 86
3.10 Recursion Conversions......Page 91
3.11 Adding the Null String to a Language......Page 96
Problems......Page 97
4.2 Grammars for Arithmetic Expressions......Page 103
4.3 Specifying Associativity and Precedence in Grammars......Page 110
4.4 Backus…Naur Form......Page 112
4.5 Syntax Diagrams......Page 114
4.6 Abstract Syntax Trees and Three-Address Code......Page 116
4.8 Essentially Noncontracting Grammars......Page 117
4.9 Converting a Context-Free Grammar to an Essentially Noncontracting Grammar......Page 118
4.10 Pumping Property of Context-Free Languages......Page 121
Problems......Page 125
5.2 Context-Sensitive Productions......Page 127
5.3 Context-Sensitive Grammars......Page 130
5.4 Unrestricted Grammars......Page 131
Problems......Page 132
6.2 Top-Down Construction of a Parse Tree......Page 135
6.3 Parses that Fail......Page 137
6.4 A Bad Grammar for Top-Down Parsing......Page 138
6.5 Deterministic Parsers......Page 139
6.6 A Parser that Uses a Stack......Page 140
6.7 Table Representation of a Stack Parser......Page 144
6.8 Handling Productions with Nonleading Terminal......Page 146
6.9 Writing a Stack Parser in Java......Page 147
Problems......Page 154
7.2 FIRST Set of the Right Side of a Production......Page 157
7.3 Determining Operation Sequences......Page 160
7.4 Determining Selection Sets of Lambda Productions......Page 162
7.5 Whatever-Follows-Left-Follows-Rightmost Rule......Page 165
7.6 Selection Sets for Productions with Nullable Right Sides......Page 167
7.7 Selection Sets Containing End-of-Input Symbol......Page 169
7.8 A Stack Parser for a Grammar with Lambda Productions......Page 172
7.9 Converting a Non-LL(l) Grammar to an LL(1) Grammar......Page 173
7.10 Parsing with an Ambiguous Grammar......Page 180
7.11 Computing FIRST and FOLLOW Sets......Page 183
Problems......Page 185
8.1 Introduction......Page 191
8.2 Unifying the Operations of a Stack Parser......Page 192
8.3 Implementing a Table-Driven Stack Parser......Page 195
8.4 Improving Our Table-Driven Stack Parser......Page 200
8.5 Parsers that are Not Deterministic„A Digression on Theory......Page 201
Problems......Page 203
9.2 Simple Recursive-Descent Parser......Page 205
9.3 Handling Lambda Productions......Page 212
9.4 A Common Error......Page 217
9.5 Java Code for Productions......Page 218
9.6 Left Factoring in a Recursive-Descent Parser......Page 219
9.7 Eliminating Tail Recursion......Page 224
9.8 Translating the Star, Plus, and Question Mark Operators......Page 228
9.9 Doing Things Backward......Page 230
Problems......Page 231
10.2 A Simple Translation Grammar......Page 235
10.3 Converting a Translation Grammar to Java Code......Page 237
10.4 Specifications for a Translation Grammar......Page 238
10.5 Passing Information During a Parse......Page 251
10.6 L-Attributed Grammars......Page 256
10.7 New Token Manager......Page 258
10.9 Code for the New Token Manager......Page 261
10.10 Translation Grammar for Prefix Expression Compiler......Page 273
10.11 An Interesting Use of Recursion......Page 277
Problems......Page 281
11.2 Structure of the J1 Computer......Page 285
11.3 Machine Language Instructions......Page 286
11.4 Assembly Language Instructions......Page 288
11.5 Pushing Characters......Page 289
11.7 Using Labels......Page 290
11.8 Using the Assembler......Page 292
11.9 stav Instruction......Page 295
11.10 Compiling an Assignment Statement......Page 297
11.11 Compiling print and printIn......Page 300
11.12 Outputting Strings......Page 301
11.13 Inputting Decimal Numbers......Page 303
11.14 Entry Directive......Page 304
Problems......Page 305
12.2 The Source Language......Page 309
12.3 Grammar for Source Language......Page 310
12.4 The Target Language......Page 311
12.5 Symbol Table......Page 312
12.7 Token Class......Page 313
12.8 Writing the Translation Grammar......Page 314
12.9 Implementing the S1 Compiler......Page 319
12.10 Trying Out S1......Page 335
12.11 Advice on Extending the S1 Compiler......Page 338
12.12 Specifications for S2......Page 340
Problems......Page 344
13.1 Introduction......Page 351
13.2 JavaCC Extended Regular Expressions......Page 353
13.3 JavaCC Input File......Page 357
13.4 Specifying Actions for Regular Expressions......Page 364
13.5 JavaCC Input File for S1j......Page 368
13.6 Files Produced by JavaCC......Page 375
13.7 Using the Star and Plus Operators......Page 379
13.8 Choice Points and the Lookahead Directive......Page 382
13.9 JavaCC\'s Choice Algorithm......Page 387
13.10 Syntactic and Semantic Lookahead......Page 391
13.11 Using JavaCC to Create a Token Manager Only......Page 392
13.12 Using the Token Chain......Page 393
13.13 Suppressing Warning Messages......Page 397
Problems......Page 398
14.2 Extending printIn and print......Page 403
14.3 Cascaded Assignment Statement......Page 408
14.4 Unary Plus and Minus......Page 411
14.5 readint Statement......Page 413
14.6 Controlling the Token Trace from the Command Line......Page 415
Problems......Page 416
15.2 while Statement......Page 419
15.3 if Statement......Page 423
15.4 do-while Statement......Page 427
15.5 Range Checking of Numerical Constants......Page 428
15.6 Handling Backslash-Quote in a String......Page 430
15.7 Handling Backslash-Quote with JavaCC......Page 431
15.8 Universal Blocks in JavaCC......Page 436
15.9 Handling Strings that Span Lines......Page 438
15.10 Handling Strings that Span Lines Using JavaCC......Page 439
15.11 SPECIAL_TOKEN Block in JavaCC......Page 442
15.12 Error Recovery......Page 444
15.13 Error Recovery in JavaCC......Page 449
15.14 Specifications for S4......Page 450
Problems......Page 451
16.2 Separate Assembly and Linking......Page 455
16.3 Calling and Returning from Fuctions......Page 459
16.4 Source Language for S5......Page 463
16.5 Symbol Table for S5......Page 464
16.6 Code Generator for S5......Page 466
16.7 Translation Grammar for S5......Page 467
16.8 Linking with a Library......Page 477
16.10 Extending S5......Page 478
Problems......Page 481
17.1 Introduction......Page 485
17.2 Deterministic Finite Automata......Page 486
17.3 Converting a DFA to a Regular Expression......Page 488
17.4 Java Code for a DFA......Page 492
17.5 Nondeterministic Finite Automata......Page 494
17.6 Using an NFA as an Algorithm......Page 496
17.7 Converting an NFA to a DFA with the Subset Algorithm......Page 498
17.8 Converting a DFA to a Regular Grammar......Page 499
17.9 Converting a Regular Grammar to an NFA......Page 502
17.10 Converting a Regular Expression to an NFA......Page 504
17.11 Finding the Minimal DFA......Page 508
17.12 Pumping Property of Regular Languages......Page 513
Problems......Page 515
18.1 Introduction......Page 519
18.3 Token Manager for Regular Expression......Page 521
18.5 Target Language for Our Regular Expression Compiler......Page 523
18.6 Using an NFA for Pattern Matching......Page 528
Problems......Page 533
19.1 Introduction......Page 535
19.2 Using the Register Instruction Set......Page 536
19.3 Modifications to the Symbol Table for Rl......Page 537
19.4 Parser and Code Generator for R1......Page 538
Problems......Page 546
20.1 Introduction......Page 549
20.2 Using the 1dc Instruction......Page 551
20.3 Reusing Temporary Variables......Page 552
20.4 Constant Folding......Page 555
20.5 Register Allocation......Page 557
20.6 Peephole Optimization......Page 560
Problems......Page 563
21.1 Introduction......Page 567
21.2 Converting S1 to I1......Page 569
21.3 Interpreting Statements that Transfer Control......Page 572
21.4 Implementing the Compiler-Interpreter CI1......Page 573
21.5 Advantages of Interpreters......Page 578
Problems......Page 579
22.2 Principles of Bottom-Up Parsing......Page 581
22.3 Parsing with Right- versus Left-Recursive Grammars......Page 585
22.4 Bottom-Up Parsing with an Ambiguous Grammar......Page 586
22.5 Do-Not-Reduce Rule......Page 589
22.6 SLR(1) Parsing......Page 590
22.7 Shift/Reduce Conflicts......Page 597
22.9 LR(1) Parsing......Page 599
Problems......Page 604
23.2 yacc Input and Output Files......Page 607
23.3 A Simple yacc-Generated Parser......Page 608
23.4 Passing Values Using the Value Stack......Page 616
23.5 Using yacc With an Ambiguous Grammar......Page 622
23.6 Passing Values down the Parse Tree......Page 624
23.7 Implementing S1y......Page 626
23.8 jflex......Page 632
Problems......Page 638
Appendix A Stack Instruction Set......Page 641
Appendix B Register Instruction Set......Page 645
References......Page 649
Index......Page 651