2016
Context-free ambiguity detection using multi-stack pushdown automata
Publication
Publication
We propose a method for detecting ambiguity in context-free grammars using multi-stack pushdown automata. Since the ambiguity problem is undecidable in general, we use restricted MPDAs that have a limited configuration space. The analysis might thus not be complete, but it is able to detect both ambiguity and unambiguity. Our method is general in the type of automata used. We discuss the suitability of existing MPDAs in our setting and present a new class called bounded-balance MPDAs. These MPDAs allow for infinitely deep nesting/nesting intersection, as long as the nesting depth differences within each scope stay within the balance bound. We compare our contributions to various related MPDAs and ambiguity detection methods.
| Additional Metadata | |
|---|---|
| Basten Science & Software LLP, Zevenhuizen, The Netherlands | |
| doi.org/10.1007/978-3-662-53132-7_1 | |
| International Conference on Developments in Language Theory | |
|
Basten, B. (2016). Context-free ambiguity detection using multi-stack pushdown automata. In Developments in Language Theory: 20th International Conference, DLT 2016 (pp. 1–12). doi:10.1007/978-3-662-53132-7_1 |
|
