Formal languages and compilation

✍ Scribed by Reghizzi S.C

• Publisher: Springer
• Year: 2019
• Tongue: English
• Leaves: 509
• Edition: 3
• Category: Library

✦ Table of Contents

Preface......Page 6
Reference......Page 8
Contents......Page 9
1.1 Intended Scope and Readership......Page 14
1.2 Compiler Parts and Corresponding Concepts......Page 15
2.1.1 Artificial and Formal Languages......Page 18
2.1.2 Language Types......Page 19
2.1.3 Chapter Outline......Page 20
2.2.1 Alphabet and Language......Page 21
2.2.2 Language Operations......Page 24
2.2.3 Set Operations......Page 26
2.2.4 Star and Cross......Page 27
2.3 Regular Expressions and Languages......Page 30
2.3.1 Definition of Regular Expression......Page 31
2.3.2 Derivation and Language......Page 33
2.3.3 Other Operators......Page 37
2.3.4 Closure Properties of Family REG......Page 38
2.4 Linguistic Abstraction: Abstract and Concrete Lists......Page 39
2.4.1 Lists with Separators and Opening/Closing Marks......Page 40
2.4.2 Language Substitution......Page 41
2.4.3 Hierarchical or Precedence Lists......Page 42
2.5.1 Limits of Regular Languages......Page 44
2.5.2 Introduction to Context-Free Grammars......Page 45
2.5.3 Conventional Grammar Representations......Page 47
2.5.4 Derivation and Language Generation......Page 50
2.5.5 Erroneous Grammars and Useless Rules......Page 52
2.5.6 Recursion and Language Infinity......Page 54
2.5.7 Syntax Tree and Canonical Derivation......Page 56
2.5.8 Parenthesis Languages......Page 60
2.5.9 Regular Composition of Context-Free Languages......Page 64
2.5.10 Ambiguity in Grammars......Page 65
2.5.11 Catalogue of Ambiguous Forms and Remedies......Page 67
2.5.12 Weak and Structural Equivalence......Page 75
2.5.13 Grammar Transformations and Normal Forms......Page 78
2.6 Grammars of Regular Languages......Page 94
2.6.1 From Regular Expression to Grammar......Page 95
2.6.2 Linear and Unilinear Grammars......Page 97
2.6.3 Linear Language Equations......Page 100
2.7 Comparison of Regular and Context-Free Languages......Page 102
2.7.1 Limits of Context-Free Languages......Page 106
2.7.2 Closure Properties of Families REG and CF......Page 108
2.7.3 Alphabetic Transformations......Page 110
2.7.4 Grammars with Regular Expressions......Page 113
2.8 More General Grammars and Language Families......Page 117
2.8.1 Chomsky Classification of Grammars......Page 118
2.8.2 Further Developments and Final Remarks......Page 122
3.1 Introduction......Page 127
3.2 Recognition Algorithms and Automata......Page 128
3.2.1 A General Automaton......Page 129
3.3 Introduction to Finite Automata......Page 132
3.4 Deterministic Finite Automata......Page 133
3.4.1 Error State and Total Automaton......Page 135
3.4.2 Clean Automaton......Page 136
3.4.3 Minimal Automaton......Page 137
3.4.4 From Automaton to Grammar......Page 141
3.5 Nondeterministic Automata......Page 142
3.5.1 Motivation of Nondeterminism......Page 143
3.5.2 Nondeterministic Recognizers......Page 145
3.5.3 Automata with Spontaneous Moves......Page 147
3.5.4 Correspondence Between Automata and Grammars......Page 148
3.5.5 Ambiguity of Automata......Page 149
3.5.6 Left-Linear Grammars and Automata......Page 150
3.6 From Automaton to Regular Expression: BMC Method......Page 151
3.7 Elimination of Nondeterminism......Page 153
3.7.1 Elimination of Spontaneous Moves......Page 154
3.7.2 Construction of Accessible Subsets......Page 156
3.8 From Regular Expression to Recognizer......Page 159
3.8.1 Thompson Structural Method......Page 160
3.8.2 Berry–Sethi Method......Page 162
3.9.1 Trees for Ambiguous r.e. and Their Phrases......Page 177
3.9.3 The Berry–Sethi Parser......Page 184
3.10 Expressions with Complement and Intersection......Page 200
3.10.1 Product of Automata......Page 202
3.11 Summary of the Relations Between Regular Expressions, Grammars and Automata......Page 206
4.1 Introduction......Page 210
4.2 Pushdown Automaton......Page 211
4.2.1 From Grammar to Pushdown Automaton......Page 212
4.2.2 Definition of Pushdown Automaton......Page 216
4.2.3 One Family for Context-Free Languages and Pushdown Automata......Page 220
4.2.4 Intersection of Regular and Context-Free Languages......Page 224
4.3 Deterministic Pushdown Automata and Languages......Page 225
4.3.1 Closure Properties of Deterministic Languages......Page 227
4.3.2 Nondeterministic Languages......Page 229
4.3.3 Determinism and Language Unambiguity......Page 231
4.3.4 Subclasses of Deterministic Pushdown Automata and Languages......Page 232
4.4 Syntax Analysis: Top-Down and Bottom-Up Constructions......Page 241
4.5 Grammar as Network of Finite Automata......Page 244
4.5.1 Syntax Charts......Page 248
4.5.2 Derivation for Machine Nets......Page 250
4.5.3 Initial and Look-Ahead Characters......Page 252
4.6 Bottom-Up Deterministic Analysis......Page 255
4.6.1 From Finite Recognizers to Bottom-Up Parser......Page 256
4.6.2 Construction of ELR (1) Parsers......Page 261
4.6.3 ELR (1) Condition......Page 264
4.6.4 Simplifications for BNF Grammars......Page 278
4.6.5 Parser Implementation Using a Vector Stack......Page 282
4.6.6 Lengthening the Look-Ahead......Page 286
4.7 Deterministic Top-Down Parsing......Page 293
4.7.1 ELL (1) Condition......Page 297
4.7.2 Step-by-Step Derivation of ELL (1) Parsers......Page 299
4.7.3 Direct Construction of Top-Down Predictive Parsers......Page 316
4.7.4 A Graphical Method for Computing Guide Sets......Page 325
4.7.5 Increasing Look-Ahead in Top-Down Parsers......Page 333
4.8 Operator-Precedence Grammars and Parallel Parsing......Page 336
4.8.1 Floyd Operator-Precedence Grammars and Parsers......Page 337
4.8.2 Sequential Operator-Precedence Parser......Page 341
4.8.3 Comparisons and Closure Properties......Page 344
4.8.4 Parallel Parsing Algorithm......Page 350
4.9 Deterministic Language Families: A Comparison......Page 357
4.10 Discussion of Parsing Methods......Page 361
4.11 A General Parsing Algorithm......Page 363
4.11.1 Introductory Presentation......Page 364
4.11.2 Earley Algorithm......Page 368
4.11.3 Syntax Tree Construction......Page 377
4.12.1 Errors......Page 384
4.12.2 Incremental Parsing......Page 390
5.1 Introduction......Page 393
5.2 Translation Relation and Function......Page 396
5.3 Transliteration......Page 398
5.4 Purely Syntactic Translation......Page 399
5.4.1 Infix and Polish Notation......Page 401
5.4.2 Ambiguity of Source Grammar and Translation......Page 405
5.4.3 Translation Grammar and Pushdown Transducer......Page 407
5.4.4 Syntax Analysis with Online Translation......Page 412
5.4.5 Top-Down Deterministic Translation by Recursive Procedures......Page 413
5.4.6 Bottom-Up Deterministic Translation......Page 416
5.5 Regular Translation......Page 424
5.5.1 Two-Input Automaton......Page 426
5.5.2 Translation Function and Finite Transducer......Page 431
5.5.3 Closure Properties of Translation......Page 436
5.6 Semantic Translation......Page 437
5.6.1 Attribute Grammars......Page 439
5.6.2 Left and Right Attributes......Page 441
5.6.3 Definition of Attribute Grammar......Page 445
5.6.4 Dependence Graph and Attribute Evaluation......Page 447
5.6.5 One-Sweep Semantic Evaluation......Page 452
5.6.6 Other Evaluation Methods......Page 456
5.6.7 Combined Syntax and Semantic Analysis......Page 457
5.6.8 Typical Applications of Attribute Grammar......Page 467
5.7 Static Program Analysis......Page 477
5.7.1 A Program as an Automaton......Page 478
5.7.2 Liveness Intervals of a Variable......Page 481
5.7.3 Reaching Definition......Page 487
Index......Page 497