Buch, Englisch, Band 242, 158 Seiten, Paperback, Format (B × H): 160 mm x 240 mm, Gewicht: 298 g
Reihe: The Springer International Series in Engineering and Computer Science
Buch, Englisch, Band 242, 158 Seiten, Paperback, Format (B × H): 160 mm x 240 mm, Gewicht: 298 g
Reihe: The Springer International Series in Engineering and Computer Science
ISBN: 978-1-4613-6397-2
Verlag: Springer US
The Functional Treatment of Parsing provides a functional framework within which the different traditional techniques are restated and unified. The resulting theory provides new recursive implementations of parsers for context-free grammars. The new implementations, called recursive ascent parsers, avoid explicit manipulation of parse stacks and parse matrices, and are in many ways superior to conventional implementations. They are applicable to grammars for programming languages as well as natural languages.
The book has been written primarily for students and practitioners of parsing technology. With its emphasis on modern functional methods, however, the book will also be of benefit to scientists interested in functional programming. The Functional Treatment of Parsing is an excellent reference and can be used as a text for a course on the subject.
Zielgruppe
Research
Autoren/Hrsg.
Fachgebiete
- Geisteswissenschaften Sprachwissenschaft Computerlinguistik, Korpuslinguistik
- Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Numerische Mathematik
- Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Compiler
- Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
Weitere Infos & Material
1 Context-Free Grammars.- 2 Bunch Notation.- 2.1 Bunches.- 2.2 Algorithmic interpretation.- 3 Grammar Interpretations.- 3.1 The natural interpretation.- 3.2 Derivation.- 3.3 The Lambek types.- 3.4 Recognition functions.- 3.5 Generation.- 3.6 Summary of interpretations.- 4 Recursive Descent.- 4.1 The functional interpretation.- 4.2 Termination.- 4.3 Complexity and memoization.- 4.4 Look ahead.- 4.5 Error recovery.- 5 Grammar Transformations.- 5.1 Making grammars bilinear.- 5.2 Recursive descent for Eg.- 5.3 Partial elimination of left recursion.- 5.4 Recursive descent for FG.- 6 Recursive Ascent.- 6.1 The algorithm.- 6.2 Termination.- 6.3 A variant that works with strings.- 6.4 Complexity.- 6.5 EBNF grammars.- 7 Parse Forest.- 7.1 Informal introduction.- 7.2 The grammar E’G.- 7.3 Forest for bilinear grammars.- 7.4 The set Q.- 7.5 Standard Earley parser.- 7.6 Earley versus Earley.- 8 Attribute Grammars.- 8.1 Notational conventions.- 8.2 Attribute functions.- 8.3 Example.- 8.4 Function graphs.- 8.5 Attribute grammar parser.- 8.6 Direct attribute evaluation.- 9 Lr Parsers.- 9.1 LR(0) recognizer.- 9.2 The deterministic case.- 9.3 Implementation with stacks.- 9.4 Some variants.- 9.5 Look ahead.- 9.6 Attributes.- 9.7 Continuations.- 9.8 Error recovery.- 9.9 The methods by Lang and Tornita.- 9.10 Evaluation w.r.t. standard approaches.- 9.11 Earley versus LR.- 10 Some Notes.- 10.1 Context-free grammars.- 10.2 Names.- 10.3 Bunches.- 10.4 Functional programming.- 10.5 Grammar transformations.- 10.6 Memo-functions.- 10.7 Parse forests.- 10.8 Earley.- 10.9 Attribute grammars.- 10.10 Natural language.- 10.11 Other applications.- 10.12 LR parsing.- 10.13 EBNF.- 10.14 Conclusion.- References.