Abstract
Parsers for context-free grammars can be implemented directly and naturally in a functional style known as “combinator parsing”, using recursion following the structure of the grammar rules. Traditionally parser combinators have struggled to handle all features of context-free grammars, such as left recursion.
Previous work introduced novel parser combinators that could be used to parse all context-free grammars. A parser generator built using these combinators was proved both sound and complete in the HOL4 theorem prover. Unfortunately the performance was not as good as other parsing methods such as Earley parsing.
In this paper, we build on this previous work, and combine it in novel ways with existing parsing techniques such as Earley parsing. The result is a sound-and-complete combinator parsing library that can handle all context-free grammars, and has good performance.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Happy, a parser generator for Haskell, http://www.haskell.org/happy/
Aho, A.V., Ullman, J.D.: The theory of parsing, translation, and compiling. Prentice-Hall, Inc. (1972)
Atkey, R.: The semantics of parsing with semantic actions. In: LICS 2012, pp. 75–84. IEEE (2012)
Barthwal, A., Norrish, M.: A mechanisation of some context-free language theory in HOL4. Journal of Computer and System Sciences (2013)
Earley, J.: An efficient context-free parsing algorithm. Commun. ACM 13(2), 94–102 (1970)
Ford, B.: Packrat parsing: simple, powerful, lazy, linear time, functional pearl. In: ICFP 2002, pp. 36–47. ACM (2002)
Frost, R.A., Hafiz, R., Callaghan, P.: Parser combinators for ambiguous left-recursive grammars. In: Hudak, P., Warren, D.S. (eds.) PADL 2008. LNCS, vol. 4902, pp. 167–181. Springer, Heidelberg (2008)
Hafiz, R., Frost, R.A.: Lazy combinators for executable specifications of general attribute grammars. In: Carro, M., Peña, R. (eds.) PADL 2010. LNCS, vol. 5937, pp. 167–182. Springer, Heidelberg (2010)
Kasami, T.: An efficient recognition and syntax analysis algorithm for context-free languages. Tech. Rep. AFCRL-65-758, Air Force Res. Lab., Massachusetts (1965)
Leijen, D., Meijer, E.: Parsec: A practical parser library. Electronic Notes in Theoretical Computer Science 41(1), 1–20 (2001)
Ljunglöf, P.: Pure functional parsing. Göteborg University and Chalmers University of Technology, Gothenburg (2002)
Pratt, V.R.: Top down operator precedence. In: Proceedings ACM Symposium on Principles Prog. Languages (1973)
Ridge, T.: Simple, functional, sound and complete parsing for all context-free grammars. In: Jouannaud, J.-P., Shao, Z. (eds.) CPP 2011. LNCS, vol. 7086, pp. 103–118. Springer, Heidelberg (2011)
Scott, E., Johnstone, A.: GLL parsing. Electronic Notes in Theoretical Computer Science 253(7), 177–189 (2010)
Scott, E., Johnstone, A.: GLL parse-tree generation. Science of Computer Programming 78(10), 1828–1844 (2013)
Tomita, M.: LR parsers for natural languages. In: Proc. of the 10th Int. Conf. on Computational linguistics, pp. 354–357. ACL (1984)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Ridge, T. (2014). Simple, Efficient, Sound and Complete Combinator Parsing for All Context-Free Grammars, Using an Oracle. In: Combemale, B., Pearce, D.J., Barais, O., Vinju, J.J. (eds) Software Language Engineering. SLE 2014. Lecture Notes in Computer Science, vol 8706. Springer, Cham. https://doi.org/10.1007/978-3-319-11245-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-11245-9_15
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11244-2
Online ISBN: 978-3-319-11245-9
eBook Packages: Computer ScienceComputer Science (R0)