Crespi Reghizzi Formal Languages and Compilation

1. Auflage 2009
ISBN: 978-1-84882-050-0
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 368 Seiten

Reihe: Texts in Computer Science

State of books on compilers The book collects and condenses the experience of years of teaching compiler courses and doing research on formal language theory, on compiler and l- guage design, and to a lesser extent on natural language processing. In the turmoil of information technology developments, the subject of the book has kept the same fundamental principles over half a century, and its relevance for theory and practice is as important as in the early days. This state of a?airs of a topic, which is central to computer science and is based on consolidated principles, might lead us to believe that the acc- panying textbooks are by now consolidated, much as the classical books on mathematics. In fact this is rather not true: there exist ?ne books on the mathematical aspects of language and automata theory, but the best books on translators are sort of encyclopaedias of algorithms, design methods, and practical know-how used in compiler design. Indeed a compiler is a mic- cosm,featuring avarietyofaspectsrangingfromalgorithmicwisdomto CPU andmemoryexploitation.Asaconsequencethetextbookshavegrowninsize, and compete with respect to their coverage of the last developments on p- gramming languages, processor architectures and clever mappings from the former to the latter.

Autoren/Hrsg.

Crespi Reghizzi, Stefano

Inhaltsverzeichnis

1;Preface;5
2;Contents;9
3;Introduction;13
3.1;Intended Scope and Audience;13
3.2;Compiler Parts and Corresponding Concepts;14
4;Syntax ;16
4.1;Introduction;16
4.1.1;Artificial and Formal Languages;16
4.1.2;Language Types;17
4.1.3;Chapter Outline;18
4.2;Formal Language Theory;19
4.2.1;Alphabet and Language;19
4.2.2;Language Operations;22
4.2.3;Set Operations;24
4.2.4;Star and Cross;25
4.2.5;Quotient;28
4.3;Regular Expressions and Languages;28
4.3.1;Definition of Regular Expression;29
4.3.2;Derivation and Language;31
4.3.3;Other Operators;34
4.3.4;Closure Properties of REG Family;35
4.4;Linguistic Abstraction;36
4.4.1;Abstract and Concrete Lists;37
4.5;Context-Free Generative Grammars;41
4.5.1;Limits of Regular Languages;41
4.5.2;Introduction to Context-Free Grammars;42
4.5.3;Conventional Grammar Representations;44
4.5.4;Derivation and Language Generation;46
4.5.5;Erroneous Grammars and Useless Rules;48
4.5.6;Recursion and Language Infinity;50
4.5.7;Syntax Trees and Canonical Derivations;51
4.5.8;Parenthesis Languages;55
4.5.9;Regular Composition of Context-Free Languages;57
4.5.10;Ambiguity;58
4.5.11;Catalogue of Ambiguous Forms and Remedies;60
4.5.12;Weak and Structural Equivalence;68
4.5.13;Grammar Transformations and Normal Forms;70
4.6;Grammars of Regular Languages;78
4.6.1;From Regular Expressions to Context-Free Grammars;78
4.6.2;Linear Grammars;80
4.6.3;Linear Language Equations;82
4.7;Comparison of Regular and Context-Free Languages;84
4.7.1;Limits of Context-Free Languages;87
4.7.2;Closure Properties of REG and CF;89
4.7.3;Alphabetic Transformations;91
4.7.4;Grammars with Regular Expressions;94
4.8;More General Grammars and Language Families;98
4.8.1;Chomsky Classification;98
5;Finite Automata as Regular Language Recognizers;103
5.1;Introduction;103
5.2;Recognition Algorithms and Automata;104
5.2.1;A General Automaton;105
5.3;Introduction to Finite Automata;108
5.4;Deterministic Finite Automata;110
5.4.1;Error State and Total Automata;111
5.4.2;Clean Automata;111
5.4.3;Minimal Automata;113
5.4.4;From Automata to Grammars;116
5.5;Nondeterministic Automata;118
5.5.1;Motivation of Nondeterminism;118
5.5.2;Nondeterministic Recognizers;120
5.5.3;Automata with Spontaneous Moves;122
5.5.4;Correspondence between Automata and Grammars;124
5.5.5;Ambiguity of Automata;125
5.5.6;Left-Linear Grammars and Automata;126
5.6;Directly from Automata to Regular Expressions: BMC Method;127
5.7;Elimination of Nondeterminism;129
5.7.1;Construction of Accessible Subsets;131
5.8;From Regular Expression to Recognizer;134
5.8.1;Thompson Structural Method;134
5.8.2;Algorithm of Glushkov, McNaughton and Yamada;136
5.8.3;Deterministic Recognizer by Berry and Sethi Algorithm;144
5.9;Regular Expressions with Complement and Intersection;147
5.9.1;Product of Automata;148
5.10;Summary of Relations between Regular Languages, Grammars, and Automata;153
6;Pushdown Automata and Top-down Parsing;156
6.1;Introduction;156
6.1.1;Pushdown Automaton;157
6.1.2;From Grammar to Pushdown Automaton;158
6.1.3;Definition of Pushdown Automaton;161
6.2;One Family for Context-Free Languages and Pushdown Automata;166
6.2.1;Intersection of Regular and Context-Free Languages;169
6.2.2;Deterministic Pushdown Automata and Languages;169
6.3;Syntax Analysis;179
6.3.1;Top-Down and Bottom-Up Analysis;179
6.3.2;Grammar as Network of Finite Automata;181
6.3.3;Nondeterministic Recognition Algorithm;185
6.4;Top-Down Deterministic Syntax Analysis;187
6.4.1;Condition for LL(1) Parsing;188
6.4.2;How to Obtain LL(1) Grammars;201
6.4.3;Increasing Look-ahead;205
7;Bottom-Up and General Parsing;211
7.1;Introduction;211
7.2;Bottom-Up Deterministic Syntax Analysis;211
7.2.1;LR(0) Method;212
7.2.2; LR(0) Grammars;214
7.2.3;Shift-Reduce Parser;219
7.2.4;Syntax Analysis with LR(k) Look-Ahead;222
7.2.5;LR(1) Parsing Algorithm;234
7.2.6;Properties of LR(k) Language and Grammar Families;234
7.2.7;How to Obtain LR(1) Grammars;237
7.2.8;LR(1) Parsing with Extended Context-Free Grammars;240
7.2.9;Comparison of Deterministic Families REG, LL(k), and LR(k);249
7.3;A General Parsing Algorithm;250
7.3.1;Introductory Example;251
7.3.2;Earley Algorithm;255
7.3.3;Computational Complexity;260
7.3.4;Handling of Empty Rules;262
7.3.5;Further Developments;264
7.4;How to Choose a Parser;264
8;Translation Semantics and Static Analysis;267
8.1;Introduction;267
8.1.1;Chapter Outline;268
8.2;Translation Relation and Function;270
8.3;Transliteration;272
8.4;Regular Translations;272
8.4.1;Two-Input Automaton;274
8.4.2;Translation Functions and Finite Transducers;278
8.5;Purely Syntactic Translation;283
8.5.1;Infix and Polish Notations;285
8.5.2;Ambiguity of Source Grammar and Translation;289
8.5.3;Translation Grammars and Pushdown Transducers;290
8.5.4;Syntax Analysis with Online Translation;295
8.5.5;Top-Down Deterministic Translation;295
8.5.6;Bottom-Up Deterministic Translation;298
8.5.7;Comparisons;303
8.5.8;Closure Properties of Translations;304
8.6;Semantic Translations;305
8.6.1;Attribute Grammars;307
8.6.2;Left and Right Attributes;309
8.6.3;Definition of Attribute Grammar;313
8.6.4;Dependence Graph and Attribute Evaluation;315
8.6.5;One Sweep Semantic Evaluation;319
8.6.6;Other Evaluation Methods;323
8.6.7;Combined Syntax and Semantic Analysis;324
8.6.8;Typical Applications of Attribute Grammars;332
8.7;Static Program Analysis;342
8.7.1;A Program as an Automaton;342
8.7.2;Liveness Intervals of Variables;346
8.7.3;Reaching Definitions;353
9;References;361
10;Index;364