Abstract
For languages whose syntax is fixed, parsers are usually built with a static structure. The implementation of features like macro mechanisms or extensible languages requires the use of parsers that may be dynamically extended. In this work, we discuss a mixed approach for building efficient top-down dynamically extensible parsers. Our view is based on the fact that a large part of the parser code can be statically compiled and only the parts that are dynamic should be interpreted for a more efficient processing. We propose the generation of code for the base parser, in which hooks are included to allow efficient extension of the underlying grammar and activation of a grammar interpreter whenever it is necessary to use an extended syntax. As a proof of concept, we present a prototype implementation of a parser generator using Adaptable Parsing Expression Grammars (APEG) as the underlying method for syntax definition. We show that APEG has features which allow an efficient implementation using the proposed mixed approach.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aycock, J.: A brief history of just-in-time. ACM Comput. Surv. 35(2), 97–113 (2003)
Bravenboer, M., Visser, E.: Parse Table Composition – Separate Compilation and Binary Extensibility of Grammars. In: Gašević, D., Lämmel, R., Van Wyk, E. (eds.) SLE 2008. LNCS, vol. 5452, pp. 74–94. Springer, Heidelberg (2009)
Cramer, T., Friedman, R., Miller, T., Seberger, D., Wilson, R., Wolczko, M.: Compiling java just in time. IEEE Micro 17(3), 36–43 (1997)
Dakin, R.J., Poole, P.C.: A mixed code approach. Comput. J. 16(3), 219–222 (1973)
Dawson, J.L.: Combining interpretive code with machine code. Comput. J. 16(3), 216–219 (1973)
Erdweg, S., Rendel, T., Kästner, C., Ostermann, K.: Sugarj: library-based syntactic language extensibility. In: Proceedings of the 2011 ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA 2011, pp. 391–406. ACM, New York (2011)
Ford, B.: Parsing expression grammars: a recognition-based syntactic foundation. SIGPLAN Not. 39(1), 111–122 (2004)
Hansen, C.P.: An Efficient, Dynamically Extensible ELL Parser Library. Master’s thesis, Aarhus Universitet (2004)
Jim, T., Mandelbaum, Y., Walker, D.: Semantics and algorithms for data-dependent grammars. In: Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2010, pp. 417–430. ACM, New York (2010)
Johnson, S.C.: Yacc: Yet Another Compiler Compiler. In: UNIX Programmer’s Manual, vol. 2, pp. 353–387. Holt, Rinehart, and Winston, New York (1979)
Jung, D.-H., Moon, S.-M., Oh, H.-S.: Hybrid compilation and optimization for java-based digital tv platforms. ACM Trans. Embed. Comput. Syst. 13(2s), 62:1–62:27 (2014)
Knuth, D.E.: An empirical study of fortran programs. Software – Practice and Experience 1(2), 105–133 (1971)
Muller, G., Moura, B., Bellard, F., Consel, C.: Harissa: A flexible and efficient java environment mixing bytecode and compiled code. In: Proceedings of the 3rd Conference on USENIX Conference on Object-Oriented Technologies (COOTS 1997), vol. 3, p. 1. USENIX Association, Berkeley (1997)
Muller, G., Schultz, U.P.: Harissa: A hybrid approach to java execution. IEEE Softw. 16(2), 44–51 (1999)
Plezbert, M.: Continuous Compilation for Software Development and Mobile Computing. Master’s thesis, Washington University, Saint Louis, Missouri (1996)
Plezbert, M.P., Cytron, R.K.: Does “just in time” = “better late than never”? In: Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 1997, pp. 120–131. ACM, New York (1997)
Reis, L.V.S., Di Iorio, V.O., Bigonha, R.S.: Defining the syntax of extensible languages. In: Proceedings of the 29th Annual ACM Symposium on Applied Computing, SAC 2014, pp. 1570–1576 (2014)
dos Santos Reis, L.V., da Silva Bigonha, R., Di Iorio, V.O., de Souza Amorim, L.E.: Adaptable parsing expression grammars. In: de Carvalho Junior, F.H., Barbosa, L.S. (eds.) SBLP 2012. LNCS, vol. 7554, pp. 72–86. Springer, Heidelberg (2012)
Reis, L.V.S., Bigonha, R.S., Di Iorio, V.O., Amorim, L.E.S.: The formalization and implementation of adaptable parsing expression grammars. Science of Computer Programming (to appear, 2014)
Schwerdfeger, A., Van Wyk, E.: Verifiable parse table composition for deterministic parsing. In: van den Brand, M., Gašević, D., Gray, J. (eds.) SLE 2009. LNCS, vol. 5969, pp. 184–203. Springer, Heidelberg (2010)
Schwerdfeger, A.C., Van Wyk, E.R.: Verifiable composition of deterministic grammars. In: Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2009, pp. 199–210. ACM, New York (2009)
Suganuma, T., Ogasawara, T., Takeuchi, M., Yasue, T., Kawahito, M., Ishizaki, K., Komatsu, H., Nakatani, T.: Overview of the ibm java just-in-time compiler. IBM Syst. J. 39(1), 175–193 (2000)
Thompson, K.: Regular expression search algorithm. Commun. ACM 11(6), 419–422 (1968)
Tomita, M.: Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems. Kluwer Academic Publishers, Norwell (1985)
Visser, E.: Syntax Definition for Language Prototyping. PhD thesis, University of Amsterdam (1997)
Warth, A., Piumarta, I.: OMeta: An Object-oriented Language for Pattern Matching. In: Proceedings of the 2007 Symposium on Dynamic Languages, DLS 2007, pp. 11–19. ACM, New York (2007)
Watt, D.A., Madsen, O.L.: Extended attribute grammars. Comput. J. 26(2), 142–153 (1983)
Wilson, G.V.: Extensible programming for the 21st century. Queue 2(9), 48–57 (2004)
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
dos Santos Reis, L.V., Di Iorio, V.O., Bigonha, R.S. (2014). A Mixed Approach for Building Extensible Parsers. In: Quintão Pereira, F.M. (eds) Programming Languages. SBLP 2014. Lecture Notes in Computer Science, vol 8771. Springer, Cham. https://doi.org/10.1007/978-3-319-11863-5_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-11863-5_1
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11862-8
Online ISBN: 978-3-319-11863-5
eBook Packages: Computer ScienceComputer Science (R0)