Compiler Design in C

Contents

Preface.................................................... xiii
1. Basic Concepts.............................................. 1
1.1 The Parts of a Compiler........................................ 1
1.1.1 The Lexical Analyzer.......................................3
1.1.2 The Parser.............................................. 3
1.1.3 The Code Generator........................................ 5
1.2 Representing Computer Languages................................ 6
1.2.1 Grammars and Parse Trees...................................7
1.2.2 An Expression Grammar.....................................9
1.2.3 Syntax Diagrams.......•................................. 12
1.3 A Recursive-Descent Expression Compiler.......................... 13
1.3.1 TheLexical Analyzer...................................... 13
1.3.2 The Basic Parser......................................... 17
1.3.3 Improving the Parser...................................... 21
1.3.4 Code Generation......................................... 24
1.4 Exercises.................................................30

2. Input and Lexical Analysis.................................. 32
2.1 The Lexical Analyzer as Part of a Compiler*......................... 32
2.2 Error Recovery in Lexical Analysis*.............................. 34
2.3 Input Systems*.............................................35
2.3.1 An Example Input System*.................................. 36
2.3.2 An Example Input System-Implementation...................... 39
2.4 Lexical Analysis*...........................................50
2.4.1 Languages*.............................................52
2.4.2 Regular Expressions*...................................... 54
2.4.3 Regular Definitions*...................................... 56
2.4.4 Finite Automata*......................................... 56
2.4.5 State-Machine-Driven Lexical Analyzers*....................... 60
2.4.6 Implementing a State-Machine-Driven Lexical Analyzer............. 63
2.5 l!'X-A Lexical-Analyzer Generator*.............................81
2.5.1 Thompson'sConstruction: From a Regular Expression to an NFA*...... 81
2.5.2 Implementing Thompson's Construction.........................83
2.5.2.1 Data Structures.......................................83
2.5.2.2 A Regular-Expression Grammar...........................87
2.5.2.3 File Header.......................................... 87
2.5.2.4 Error-Message Processing................................ 88
2.5.2.5 Memory Management...................................88
2.5.2.6 Macro Support........................................ 93
2.5.2.7 I§X's Lexical Analyzer.................................. 95
2.5.2.8 Parsing............................................ 101
2.5.3 Interpreting an NFA-Theory*.............................. 113
2.5.4 Interpreting an NFA-Implementation.........................115
2.5.5 Subset Construction: Converting an NFA to a DFA-Theory*......... 122
2.5.6 Subset Construction: Converting an NFA to a DFA-Implementation... 124
2.5.7 DFAMinimization-Theory*...............................132
2.5.8 DFA Minimization-Implementation.......................... 135
2.5.9 Compressing and Printing the Tables.......................... 140
2.5.9.1 Uncompressed Tables.................................. 140
2.5.9.2 Pair-Compressed Tables................................ 141
2.5.9.3 Redundant-Row-and-Column-Compressed Tables.............. 146
2.5.10 Tying It All Together.................................... 152
2.6 Exercises................................................ 162

3. Context-Free Grammars...................................166
3.1 Sentences, Phrases, and Context-Free Grammars.....................166
3.2 Derivations and Sentential Forms................................ 168
3.2.1 LLand LR Grammars.....................................170
3.3 Parse Trees and Semantic Difficulties.............................170
3.4 E Productions.............................................. 173
3.5 The End-of-Input Marker.....................................173
3.6 Right-Linear Grammars...................................... 174
3.7 Lists, Recursion, and Associativity...............................175
3.7.1 SimpleLists...........................................175
3. 7.2 The Number of Elements in a List............................ 178
3.7.3 Lists with Delimiters.....................................179
3.8 Expressions...............................................180
3.9 Ambiguous Grammars.......................................182
3.10 Syntax-Directed Translation.................................. 183
3.10.1 AugmentedGrammars...................................183
3.10.2 Attributed Grammars.................................... 186
3.11 Representing Generic Grammars...............................192
3.12 Exercises................................................ 193

4. Top-Down Parsing........................................195
4.1 Push-Down Automata*.......................................195
4.1.1 Recursive-Descent Parsers as Push-Down Automata*............... 198
4.2 Using a PDA for a Top-Down Parse*.............................201
4.3 Error Recovery in a Top-Down Parser*............................ 201
4.4 Augmented Grammars and Table-Driven Parsers*.................... 202
4.4.1 Implementing Attributed Grammars in a PDA *................... 203
4.5 Automating the Top-Down Parse Process*.........................208
4.5.1 Top-Down Parse Tables*.................................. 208
4.6 LL(l) Grammars and Their Limitations*........................... 211
4.7 Making the Parse Tables*..................................... 213
4.7.1 FIRSTSets*........................................... 213
4.7.2 FOLLOW Sets*......................................... 215
4.7.3 LL(l)Selection Sets*..................................... 217
4.8 Modifying Grammars*....................................... 218
4.8.1 Unreachable Productions*.................................. 219
4.8.2 Left Factoring*......................................... 219
4.8.3 Comer Substitution*...................................... 221
4.8.4 Singleton Substitution*.................................... 223
4.8.5 Eliminating Ambiguity*................................... 223
4.8.6 Eliminating Left Recursion*................................ 226
4.9 Implementing LL(l) Parsers................................... 229
4.9.1 Top-Down, Table-Driven Parsing-The LLama Output File.......... 229
4.9.2 Occs and LLama Debugging Support-yydebug.c................. 242
4.10 Llama-Implementing an LL(l) Parser-Generator.................. 270
4.10.1 LLama'sParser........................................ 270
4.1 0.2 Creating The Tables..................................... 304
4.10.2.1 Computing FIRST, FOLLOW, and SELECT Sets............. 304
4.1 0.3 The Rest of LLama..................................... 304
4.11 Exercises................................................ 333

5. Bottom-Up Parsing........................................ 337
5.1 How Bottom-Up Parsing Works*................................ 338
5.2 Recursion in Bottom-Up Parsing*............................... 340
5.3 Implementing the Parser as a State Machine*....................... 343
5.4 Error Recovery in an LR Parser*................................ 348
5.5 The Value Stack and Attribute Processing*......................... 348
5.5.1 A Notation for Bottom-Up Attributes*......................... 353
5.5.2 Imbedded Actions*...................................... 354
5.6 Creating LR Parse Tables-Theory*............................. 354
5.6.1 LR(O) Grammars*....................................... 354
5.6.2 SLR(l) Grammars*...................................... 361
5.6.3 LR(l)Grammars*....................................... 361
5.6.4 LALR(l) Grammars*..................................... 365
5.7 Representing LR State Tables.................................. 368
5.8 Eliminating Single-Reduction States*............................. 373
5.9 Using Ambiguous Grammars*.................................. 375
5.10 Implementing an LALR(l) Parser-The Occs Output File.............. 381
5.11 Implementing an LALR(l) Parser Generator-Occs Internals........... 401
5.11.1 Modifying the Symbol Table for LALR(l) Grammars..............401
5.12 Parser-File Generation......................................408
5.13 Generating LALR(l) Parse Tables.............................. 408
5.14 Exercises................................................ 442

6. Code Generation.......................................... 445
6.1 Intermediate Languages...................................... 446
6.2 C-code: An Intermediate Language and Virtual Machine............... 449
6.2.1 Names and White Space................................... 450
6.2.2 Basic Types............................................ 450
6.2.3 The Virtual Machine: Registers, Stack, and Memory............... 451
6.2.4 Memory Organization: Segments............................. 455
6.2.5 Variable Declarations: Storage Classes and Alignment.............. 457
6.2.6 Addressing Modes....................................... 462
6.2. 7 Manipulating the Stack.................................... 465
6.2.8 Subroutines............................................ 466
6.2.9 Stack Frames: Subroutine Arguments and Automatic Variables........ 467
6.2.10 Subroutine Return Values.................................472
6.2.11 Operators............................................ 473
6.2.12 Type Conversions....................................... 473
6.2.13 Labels and Control Flow..................................474
6.2.14 Macros and Constant Expressions............................475
6.2.15 File Organization.......................................476
6.2.16 Miscellany...........................................476
6.2.17 Caveats.............................................. 478
6.3 The Symbol Table.......................................... 478
6.3.1 Symbol-Table Requirements................................ 478
6.3.2 Symbol-Table Data-Base Data Structures....................... 480
6.3.3 Implementing the Symbol Table..............................485
6.3.4 Representing Types-Theory...............................489
6.3.5 Representing Types-Implementation......................... 490
6.3.6 Implementing the Symbol-Table Maintenance Layer...............497
6.4 The Parser: Configuration..................................... 509
6.5 The Lexical Analyzer........................................ 518
6.6 Declarations.............................................. 522
6.6.1 Simple Variable Declarations............................... 522
6.6.2 Structure and Union Declarations............................. 543
6.6.3 Enumerated-Type Declarations.............................. 550
6.6.4 Function Declarations..................................... 552
6.6.5 Compound Statements and Local Variables...................... 559
6.6.6 Front-End/Back-End Considerations........................... 563
6.7 The gen () Subroutine....................................... 564
6.8 Expressions............................................... 572
6.8.1 Temporary-Variable Allocation.............................. 572
6.8.2 Lvalues and Rvalues...................................... 578
6.8.3 Implementing Values, Higher-Level Temporary-Variable Support...... 583
6.8.4 Unary Operators........................................ 593
6.8.5 Binary Operators........................................ 617
6.9 Statements and Control Flow................................... 637
6.9.1 Simple Statements and if/else............................. 637
6.9.2 Loops,break, and continue.............................. 642
6.9.3 The switch Statement.................................... 642
6.10 Exercises................................................ 651

7. Optimization Strategies.................................... 657
7.1 Parser Optimizations........................................ 657
7.2 Linear (Peephole) Optimizations................................ 658
7.2.1 Strength Reduction....................................... 658
7.2.2 Constant Folding and Constant Propagation...................... 659
7.2.3 Dead Variables and Dead Code.............................. 660
7.2.4 Peephole Optimization: An Example.......................... 665
7.3 Structural Optimizations...................................... 667
7.3.1 Postfix and Syntax Trees................................... 667
7.3.2 Common-Subexpression Elimination.......................... 672
7.3.3 Register Allocation...................................... 673
7.3.4 Lifetime Analysis........................................ 673
7.3.5 Loop Unwinding........................................ 675
7.3.6 Replacing Indexes with Pointers............................. 675
7.3.7 Loop-Invariant Code Motion................................ 676
7.3.8 Loop Induction......................................... 677
7.4 Aliasing Problems.......................................... 677
7.5 Exercises................................................ 678

Appendix A. Support Functions............................... 680
A.l Miscellaneous Include Files................................... 681
A.l.l debug.h-Miscellaneous Macros............................. 681
A.1.2 stack.h and yystack.h -Generic Stack Maintenance............... 686
A.1.3 l.h and compiler.h.......................................689
A.2 Set Manipulation........................................... 690
A.2.1 Using the Set Functions and Macros.......................... 690
A.2.2 Set Implementation...................................... 695
A.3 Database Maintenance-Hashing:............................... 710
A.3.1 Hashing-Implementation................................. 715
A.3.2 Two Hash Functions..................................... 723
A.4 The ANSI Variable-Argument Mechanism.......................... 724
A.5 Conversion Functions....................................... 726
A.6 Print Functions............................................ 731
A. 7 Sorting........ ·.......................................... 738
A. 7.I Shell Sort-Theory...................................... 739
A.7.2 Shell Sort-Implementation................................ 741
A.8 Miscellaneous Functions..................................... 741
A.9 Low-Level Video 1/0 Functions for the IBM PC..................... 746
A.9.1 IBM Video I/O-Overview................................ 749
A.9.2 Video I/O-Implementation................................ 753
A.IO Low-level-I/O, Glue Functions................................ 771
A. II Window Management: Curses................................. 774
A.ll.l Configuration and Compiling.............................. 775
A.ll.2 Using Curses.......................................... 776
A.ll.2.1 Initialization Functions................................ 776
A.ll.2.2 Comguration Functions............................... 776
A.ll.2.3 Creating and Deleting Windows......................... 777
A.ll.2.4 Subroutines That Affect Entire Windows................... 779
A.ll.2.5 Cursor Movement and Character 1/0...................... 781
A.11.3 Curses-Implementation................................. 783

Appendix B. Notes on Pascal Compilers........................ 802
B.1 Subroutine Arguments....................................... 802
B.2 Return Values............................................. 803
B.3 Stack Frames............................................. 803

Appendix C. A Grammar for C............................... 806
Appendix D. U:X............................................ 812
D.l Using IJX and Occs Together.................................. 812
D.2 The LEX Input File: Organization................................ 814
D.3 The LEX Rules Section....................................... 816
D.3.1 ~X Regular Expressions.................................. 816
D.3.2 The Code Part of the Rule.................................. 820
D.4 ~X Command-Line Switches.................................. 825
D.5 Limits and Bugs........................................... 826
D.6 Example: A Lexical Analyzer for C.............................. 829
D.7 Exercises................................................ 834

Appendix E. LLama and Occs................................ 836
E.1 Using The Compiler Compiler.................................. 836
E.2 The Input File............................................. 837
E.3 The Definitions Section...................................... 837
E.4 The Rules Section.......................................... 839
E.5 The Code Section.......................................... 842
E.6 Output Files.............................................. 842
E.7 Command-Line Switches..................................... 843
E.8 The Visible Parser.......................................... 845
E.9 Useful Subroutines and Variables............................... 852
E.IO Using Your Own Lexical Analyzer.............................. 855
E.11 Occs...................................................856
E.1l.l Using Ambiguous Grammars............................... 856
E.11.2 Attributes and the Occs Value Stack.......................... 858
E.11.3 Printing the Value Stack.................................. 863
E.11.4 Grammatical Transformations.............................. 865
E.11.5 The yyout.sym File...................................... 867
E.11.6 The yyout.doc File...................................... 868
E.11.7 Shift/Reduce and Reduce/Reduce Conflicts..................... 871
E.11.8 Error Recovery........................................ 875
E.11.9 Putting the Parser and Actions in Different Files.................. 875
E.1l.l0 Shifting a Token's Attributes.............................. 877
E.11.11 Sample Occs Input File.................................. 879
E.11.12 Hints and Warnings.................................... 881
E.12 LLama................................................. 883
E.12.1 Percent Directives...................................... 883
E.12.2 Top-Down Attributes.................................... 883
E.12.3 TheLLama Value Stack.................................. 884
E.l2.4 The llout.sym File...................................... 885
E.12.5 Sample LLama Input File................................. 885

Appendix F. A C-code Summary.............................. 889
Bibliography............................................... 894
Index...................................................... 897
Cross Reference by Symbol.................................. 913