Journalartikel
Autorenliste: Kutrib, Martin; Meyer, Uwe
Jahr der Veröffentlichung: 2023
Zeitschrift: Theoretical Computer Science
Bandnummer: 966
ISSN: 0304-3975
eISSN: 1879-2294
DOI Link: https://doi.org/10.1016/j.tcs.2023.114000
Verlag: Elsevier
Abstract:
We consider parsers of deterministic context-free languages and study the sizes of their syntax checking components. More precisely, we allow the input processing from left to right or, alternatively, from right to left, whatever is best for the given language. As practical examples, we establish an infinite sequence of deterministic context-free languages Lk, for k & GE; 1, such that there is an exponential size trade-off between a deterministic pushdown automaton that reads its input from right to left and another one that reads its input from left to right. Concerning the constructibility of such a parser out of a given deterministic context-free language, it is shown that it is undecidable whether the reversal of a given deterministic context-free language is again deterministic context free. Related to decidability questions, it turns out that the size trade-offs between deterministic pushdown automata that represent the reversals of their accepted languages and deterministic pushdown automata that represent their accepted languages are non -recursive. That is, one can choose an arbitrarily large recursive function p, but the gain in economy of description eventually exceeds p when changing from the former system to the latter. Furthermore, we study the expressive capacity of the family of languages whose reversals are deterministic context free. Finally, we turn to the family of deterministic context-free languages whose reversals are also deterministic context free and collect several of their closure properties.& COPY; 2023 Elsevier B.V. All rights reserved.
Zitierstile
Harvard-Zitierstil: Kutrib, M. and Meyer, U. (2023) Syntax checking either way, Theoretical Computer Science, 966, Article 114000. https://doi.org/10.1016/j.tcs.2023.114000
APA-Zitierstil: Kutrib, M., & Meyer, U. (2023). Syntax checking either way. Theoretical Computer Science. 966, Article 114000. https://doi.org/10.1016/j.tcs.2023.114000
Schlagwörter
Closure properties; Decidability; DESCRIPTIONAL COMPLEXITY; Deterministic pushdown automata; Expressive capacity; LANGUAGES; NONDETERMINISM; Reversals of deterministic context-free; Syntax checking
