Pushdown Automata and Parsing
| Autor: | Luca Breveglieri, Angelo Morzenti, Stefano Crespi Reghizzi |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Nested word
Parsing Computer science Programming language Deterministic context-free grammar Context-free language Pushdown automaton Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) computer.software_genre Embedded pushdown automaton Deterministic pushdown automaton TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Regular expression computer Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Texts in Computer Science ISBN: 9783030048785 Texts in Computer Science ISBN: 9781447155133 |
| DOI: | 10.1007/978-3-030-04879-2_4 |
| Popis: | This chapter covers pushdown automata and parsing algorithms with emphasis on the application to syntax analysis. We start by introducing general and deterministic pushdown automata as recognizers of context-free and deterministic context-free languages defined by grammars. Then we present the classical deterministic bottom-up (LR(1)) and top-down (LL(1)) parsing methods, by adopting a novel approach that allows for the analysis of the languages defined by Extended BNF (EBNF) grammars, i.e., grammars that admit a regular expression in the right part of the rules. The EBNF grammars are here represented by a network of recursive finite automata. The extended LL(1) (ELL(1)) parsers are presented as a special case of the ELR(1) algorithms, such that simpler and more compact parser implementations by means of recursive procedures are possible. The classical Earley method for parsing general context-free grammars is also presented in a form generalized to EBNF. The chapter continues with an innovative parallel parsing technique based on operator-precedence grammars, suitable for parsing large files. At the end, we outline simple methods for parser error recovery and we mention incremental parsing. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|