×

Syntax checking either way. (English) Zbl 07699968

Summary: 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 \(L_k\), for \(k \geq 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 \(\varrho \), but the gain in economy of description eventually exceeds \(\varrho\) 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.

MSC:

68Qxx Theory of computing
Full Text: DOI

References:

[1] Autebert, J.-M.; Berstel, J.; Boasson, L., Context-free languages and pushdown automata, (Rozenberg, G.; Salomaa, A., Handbook of Formal Languages, vol. 1 (1997), Springer: Springer Berlin), 111-174, Chapter 3
[2] Geller, M. M.; Hunt, H. B.; Szymanski, T. G.; Ullman, J. D., Economy of description by parsers, DPDA’s, and PDA’s, Theor. Comput. Sci., 4, 143-153 (1977) · Zbl 0357.68086
[3] Ginsburg, S.; Greibach, S. A., Deterministic context-free languages, Inf. Control, 9, 620-648 (1966) · Zbl 0145.00802
[4] Ginsburg, S.; Spanier, E. H., Finite-turn pushdown automata, SIAM J. Control, 4, 429-453 (1966) · Zbl 0147.25302
[5] Goldstine, J.; Leung, H.; Wotschke, D., Measuring nondeterminism in pushdown automata, J. Comput. Syst. Sci., 71, 440-466 (2005) · Zbl 1101.68653
[6] Goldstine, J.; Price, J. K.; Wotschke, D., A pushdown automaton or a context-free grammar – which is more economical?, Theor. Comput. Sci., 18, 33-40 (1982) · Zbl 0486.68082
[7] Greibach, S. A., The unsolvability of the recognition of linear context-free languages, J. ACM, 13, 582-587 (1966) · Zbl 0148.00901
[8] Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading · Zbl 0411.68058
[9] Hartmanis, J., Context-free languages and Turing machine computations, Proc. Symp. Appl. Math., 19, 42-51 (1967) · Zbl 0189.29101
[10] Holzer, M.; Kutrib, M., Descriptional complexity – an introductory survey, (Martín-Vide, C., Scientific Applications of Language Methods (2010), Imperial College Press), 1-58 · Zbl 1227.68033
[11] Holzer, M.; Lange, K., On the complexities of linear LL(1) and LR(1) grammars, (Ésik, Z., Fundamentals of Computation Theory. Fundamentals of Computation Theory, FCT, 1993. Fundamentals of Computation Theory. Fundamentals of Computation Theory, FCT, 1993, LNCS, vol. 710 (1993), Springer), 299-308 · Zbl 0794.68085
[12] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, Massachusetts · Zbl 0426.68001
[13] Knuth, D. E., On the translation of languages from left to right, Inf. Control, 8, 607-639 (1965) · Zbl 0231.68027
[14] Knuth, D. E., Top-down syntax analysis, Acta Inform., 1, 79-110 (1971) · Zbl 0233.68022
[15] Kutrib, M., The phenomenon of non-recursive trade-offs, Int. J. Found. Comput. Sci., 16, 957-973 (2005) · Zbl 1090.68058
[16] Kutrib, M.; Malcher, A., Context-dependent nondeterminism for pushdown automata, Theor. Comput. Sci., 376, 101-111 (2007) · Zbl 1111.68060
[17] Kutrib, M.; Meyer, U., Syntax checking either way, (Caron, P.; Mignot, L., Implementation and Application of Automata (CIAA 2022). Implementation and Application of Automata (CIAA 2022), LNCS, vol. 13266 (2022), Springer), 128-139 · Zbl 07572317
[18] Leung, H.; Wotschke, D., On the size of parsers and LR(k)-grammars, Theor. Comput. Sci., 242, 59-69 (2000) · Zbl 0944.68083
[19] Semenov, A. L., Algorithmic problems for power series and context-free grammars, Sov. Math. Dokl.. Sov. Math. Dokl., Dokl. Akad. Nauk SSSR, 212, 50-52 (1973), (English translation), in Russian: · Zbl 0322.68052
[20] Ukkonen, E., Lower bounds on the size of deterministic parsers, J. Comput. Syst. Sci., 26, 153-170 (1983) · Zbl 0536.68071
[21] Valiant, L. G., A note on the succinctness of descriptions of deterministic languages, Inf. Control, 32, 139-145 (1976) · Zbl 0338.68059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.