Abstract
A systematic approach for addressing various problems related to context-free grammars involves employing the \({ pre}^*\)-method. This method calculates, for a given regular language L (given as an NFA), the language of all strings \(\alpha \) (represented by an NFA) for which there exists a \(\beta \in L\) such that \(\alpha {\mathop {\Rightarrow }\limits ^{*}}\beta \). The range of admissible problems encompasses, inter alia, the word problem, the emptiness problem, the finiteness problem, and the identification of useless symbols.
Efficient algorithms have been developed to compute \({ pre}^*(L)\), but they assume that the grammar adheres to a restricted normal form. In this context, we introduce a novel algorithm that is both straightforward and efficient, while working with general context-free grammars.
In addition to the computation of \({ pre}^*\), this algorithm proves valuable for the construction of parse trees. The running time is in general cubic, but quadratic for parsing unambiguous context-free languages. We provide some evidence suggesting the running times cannot be improved significantly with current techniques.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The reason for the \(\epsilon \)-self-loops becomes clear later. They are needed to preserve the invariant that the NFA is “saturated.”
- 2.
It is in fact the token \((1,\texttt{IDENT},2)\) and contains an “attribute” that the actual identifier is k. To construct the parse tree it is not important what the underlying name of the identifier is.
References
Aho, A.V., Peterson, T.G.: A minimum distance error-correcting parser for context-free languages. SIAM J. Comput. 1(4), 305–312 (1972). https://doi.org/10.1137/0201022
Aho, A.V., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools. Addison-Wesley Series in Computer Science. World Student Series Edition. Addison-Wesley (1986). https://www.worldcat.org/oclc/12285707
Aho, A.V., Ullman, J.D.: Principles of Compiler Design. Pearson, London (1977)
Alman, J., Vassilevska Williams, V.: A refined laser method and faster matrix multiplication. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 522–539. SIAM (2021). https://doi.org/10.1137/1.9781611976465.32
Alur, R., Bouajjani, A., Esparza, J.: Model checking procedural programs. In: Clarke, E., Henzinger, T., Veith, H., Bloem, R. (eds.) Handbook of Model Checking, pp. 541–572. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-10575-8_17
Baier, C., Katoen, J.: Principles of Model Checking. MIT Press, Cambridge (2008)
Balasubramanian, A.R., Esparza, J., Lazić, M.: Complexity of verification and synthesis of threshold automata. In: Hung, D.V., Sokolsky, O. (eds.) ATVA 2020. LNCS, vol. 12302, pp. 144–160. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-59152-6_8
Bernardy, J., Claessen, K.: Efficient divide-and-conquer parsing of practical context-free languages. In: Morrisett, G., Uustalu, T. (eds.) ACM SIGPLAN International Conference on Functional Programming, pp. 111–122. ACM (2013). https://doi.org/10.1145/2500365.2500576
Book, R.V., Otto, F.: String-Rewriting Systems. Texts and Monographs in Computer Science. Springer, Heidelberg (1993). https://doi.org/10.1007/978-1-4613-9771-7
Bouajjani, A., et al.: An efficient automata approach to some problems on context-free grammars. Inf. Process. Lett. 74(5–6), 221–227 (2000). https://doi.org/10.1016/S0020-0190(00)00055-7
Brázdil, T., Esparza, J., Kiefer, S., Kučera, A.: Analyzing probabilistic pushdown automata. Formal Methods Syst. Des. 43(2), 124–163 (2013). https://doi.org/10.1007/S10703-012-0166-0
Cocke, J.: Global common subexpression elimination. In: Northcote, R.S. (ed.) Proceedings of a Symposium on Compiler Optimization, Urbana-Champaign, Illinois, USA, pp. 20–24. ACM (1970). https://doi.org/10.1145/800028.808480
Earley, J.: R68–46 use of transition matrices in compiling. IEEE Trans. Comput. 17(11), 1098 (1968). https://doi.org/10.1109/TC.1968.226868
Earley, J.: An efficient context-free parsing algorithm. Commun. ACM 13(2), 94–102 (1970). https://doi.org/10.1145/362007.362035
Esparza, J.: An automata-theoretic approach to software verification. In: Ésik, Z., Fülöp, Z. (eds.) DLT 2003. LNCS, vol. 2710, p. 21. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45007-6_2
Esparza, J.: Back to the future: a fresh look at linear temporal logic. In: Maneth, S. (ed.) CIAA 2021. LNCS, vol. 12803, pp. 3–13. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-79121-6_1
Esparza, J., Blondin, M.: Automata Theory: An Algorithmic Approach. The MIT Press, Cambridge (2023)
Esparza, J., Hansel, D., Rossmanith, P., Schwoon, S.: Efficient algorithms for model checking pushdown systems. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 232–247. Springer, Heidelberg (2000). https://doi.org/10.1007/10722167_20
Esparza, J., Kupferman, O., Vardi, M.Y.: Verification. In: Pin, J. (ed.) Handbook of Automata Theory, pp. 1415–1456. European Mathematical Society Publishing House, Zürich (2021). https://doi.org/10.4171/AUTOMATA-2/16
Esparza, J., Kučera, A., Schwoon, S.: Model checking LTL with regular valuations for pushdown systems. Inf. Comput. 186(2), 355–376 (2003). https://doi.org/10.1016/S0890-5401(03)00139-1
Esparza, J., Křetínský, J., Raskin, J.-F., Sickert, S.: From LTL and limit-deterministic Büchi automata to deterministic parity automata. In: Legay, A., Margaria, T. (eds.) TACAS 2017. LNCS, vol. 10205, pp. 426–442. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54577-5_25
Esparza, J., Křetínský, J., Sickert, S.: One theorem to rule them all: a unified translation of LTL into \(\omega \)-automata. In: Dawar, A., Grädel, E. (eds.) Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, pp. 384–393. ACM (2018). https://doi.org/10.1145/3209108.3209161
Esparza, J., Lammich, P., Neumann, R., Nipkow, T., Schimpf, A., Smaus, J.: A fully verified executable LTL model checker. Arch. Formal Proofs 2014 (2014). https://www.isa-afp.org/entries/CAVA_LTL_Modelchecker.shtml
Esparza, J., Podelski, A.: Efficient algorithms for pre\(^*\) and post\(^*\) on interprocedural parallel flow graphs. In: Wegman, M.N., Reps, T.W. (eds.) Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2000, pp. 1–11. ACM (2000). https://doi.org/10.1145/325694.325697
Esparza, J., Rossmanith, P.: An automata approach to some problems on context-free grammars. In: Freksa, C., Jantzen, M., Valk, R. (eds.) Foundations of Computer Science. LNCS, vol. 1337, pp. 143–152. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052083
Esparza, J., Rossmanith, P., Schwoon, S.: A uniform framework for problems on context-free grammars. Bull. EATCS 72, 169–177 (2000)
Ganty, P., Valero, P.: Regular expression search on compressed text. In: Bilgin, A., Marcellin, M.W., Serra-Sagristà, J., Storer, J.A. (eds.) Data Compression Conference, DCC, pp. 528–537. IEEE (2019). https://doi.org/10.1109/DCC.2019.00061
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Boston (1979)
Kasami, T.: An efficient recognition and syntax-analysis algorithm for context-free languages. Technical report, R-257, University of Illinois-Urbana, March 1966
Lange, M., Leiß, H.: To CNF or not to CNF? An efficient yet presentable version of the CYK algorithm. Informatica Didact. 8 (2009). http://www.informatica-didactica.de/cmsmadesimple/index.php?page=LangeLeiss2009
Luttenberger, M., Palenta, R., Seidl, H.: Computing the longest common prefix of a context-free language in polynomial time. In: Niedermeier, R., Vallée, B. (eds.) 35th Symposium on Theoretical Aspects of Computer Science, STACS. LIPIcs, vol. 96, pp. 48:1–48:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018). https://doi.org/10.4230/LIPICS.STACS.2018.48
Valiant, L.G.: General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10(2), 308–315 (1975). https://doi.org/10.1016/S0022-0000(75)80046-8
Wirth, N.: Algorithms + Data Structures = Programs. Prentice-Hall (1975)
Younger, D.H.: Recognition and parsing of context-free languages in time \(n^3\). Inf. Control 10(2), 189–208 (1967). https://doi.org/10.1016/S0019-9958(67)80007-X
Yu, H.: An improved combinatorial algorithm for Boolean matrix multiplication. Inf. Comput. 261, 240–247 (2018). https://doi.org/10.1016/J.IC.2018.02.006
Acknowledgments
I like to thank Daniel Mock for suggesting changes in the implementation of the new \( pre^*\)-program that improved the running time. I also like to thank anonymous referees for numerous suggestions to improve the writeup of this paper. In particular, one referee found a typo in Algorithm 2 that was already present in [10]. Another referee pointed me to the recent interesting application of \({ pre}^*\) by Ganty and Valero [27], which has not been known to me. Most of all I like to thank Javier Esparza for the pleasure and privilege to work for and with him in Munich during several years. His great way to do science and his open and cheerful personality have been a great influence on my life.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Ethics declarations
Disclosure of Interests
I have no competing interests.
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Rossmanith, P. (2024). Computing \(\textit{pre}^{*}\) for General Context Free Grammars. In: Kiefer, S., Křetínský, J., Kučera, A. (eds) Taming the Infinities of Concurrency. Lecture Notes in Computer Science, vol 14660. Springer, Cham. https://doi.org/10.1007/978-3-031-56222-8_15
Download citation
DOI: https://doi.org/10.1007/978-3-031-56222-8_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-56221-1
Online ISBN: 978-3-031-56222-8
eBook Packages: Computer ScienceComputer Science (R0)