Restricting grammars with tree automata
| Autor: | Matthew Might, Michael D. Adams |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Tree (data structure)
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Theoretical computer science Rule-based machine translation Binary operation Computer science Deterministic context-free grammar Safety Risk Reliability and Quality Object (computer science) Software Dangling else Associative property Automaton |
| Zdroj: | Proceedings of the ACM on Programming Languages. 1:1-25 |
| ISSN: | 2475-1421 |
| DOI: | 10.1145/3133906 |
| Popis: | Precedence and associativity declarations in systems like yacc resolve ambiguities in context-free grammars (CFGs) by specifying restrictions on allowed parses. However, they are special purpose and do not handle the grammatical restrictions that language designers need in order to resolve ambiguities like dangling else, the interactions between binary operators and functional if expressions in ML, and the interactions between object allocation and function calls in JavaScript. Often, language designers resort to restructuring their grammars in order to encode these restrictions, but this obfuscates the designer's intent and can make grammars more difficult to read, write, and maintain. In this paper, we show how tree automata can modularly and concisely encode such restrictions. We do this by reinterpreting CFGs as tree automata and then intersecting them with tree automata encoding the desired restrictions. The results are then reinterpreted back into CFGs that encode the specified restrictions. This process can be used as a preprocessing step before other CFG manipulations and is well behaved. It performs well in practice and never introduces ambiguities or LR( k ) conflicts. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|