Parsing Theory

Volume I Languages and Parsing

Seppo Sippu, Eljas Soisalon-Soininen (Autoren)

Buch | Softcover

VIII, 228 Seiten

2014 | 1. Softcover reprint of the original 1st ed. 1988
Springer Berlin (Verlag)
978-3-642-64801-4 (ISBN)

Artikel merken

The theory of parsing is an important application area of the theory of formal languages and automata. The evolution of modem high-level programming languages created a need for a general and theoretically dean methodology for writing compilers for these languages. It was perceived that the compilation process had to be "syntax-directed", that is, the functioning of a programming language compiler had to be defined completely by the underlying formal syntax of the language. A program text to be compiled is "parsed" according to the syntax of the language, and the object code for the program is generated according to the semantics attached to the parsed syntactic entities. Context-free grammars were soon found to be the most convenient formalism for describing the syntax of programming languages, and accordingly methods for parsing context-free languages were devel oped. Practical considerations led to the definition of various kinds of restricted context-free grammars that are parsable by means of efficient deterministic linear-time algorithms.

1. Elements of Language Theory.- 1.1 Mathematical Preliminaries.- 1.2 Languages.- 1.3 Random Access Machines.- 1.4 Decision Problems.- 1.5 Computational Complexity.- 1.6 Rewriting Systems.- Exercises.- Bibliographic Notes.- 2. Algorithms on Graphs.- 2.1 Basic Algorithms.- 2.2 Finding Strongly Connected Components.- 2.3 Computing Functions Defined on Graphs.- 2.4 Computing Relational Expressions.- Exercises.- Bibliographic Notes.- 3. Regular Languages.- 3.1 Regular Expressions.- 3.2 Finite Automata.- 3.3 Regular Grammars.- 3.4 Deterministic Finite Automata.- 3.5 Decision Problems on Regular Languages.- 3.6 Applications to Lexical Analysis.- Exercises.- Bibliographic Notes.- 4. Context-free Languages.- 4.1 Context-free Grammars.- 4.2 Leftmost and Rightmost Derivations.- 4.3 Ambiguity of Grammars.- 4.4 Useless and Nullable Symbols.- 4.5 Canonical Two-form Grammars.- 4.6 Derivational Complexity.- 4.7 Context-free Language Recognition.- Exercises.- Bibliographic Notes.- 5. Parsing.- 5.1 Pushdown Automata.- 5.2 Left Parsers and Right Parsers.- 5.3 Strong LL(k) Parsing.- 5.4 Strong LL(k) Grammars.- 5.5 Construction of Strong LL(1) Parsers.- 5.6 Implementation of Strong LL(1) Parsers.- 5.7 Simple Precedence Parsing.- Exercises.- Bibliographic Notes.- Bibliography to Volume I.- Index to Volume I.

Erscheint lt. Verlag	23.8.2014
Reihe/Serie	Monographs in Theoretical Computer Science. An EATCS Series
Zusatzinfo	VIII, 228 p. 1 illus.
Verlagsort	Berlin
Sprache	englisch
Maße	170 x 244 mm
Gewicht	421 g
Themenwelt	Informatik ► Theorie / Studium ► Algorithmen
Schlagworte	algorithm • Algorithm analysis and problem complexity • algorithms • Analysis • Automat • Automata • Complexity • Computer • Regular Expressions
ISBN-10	3-642-64801-0 / 3642648010
ISBN-13	978-3-642-64801-4 / 9783642648014
Zustand	Neuware