Adaptable Parsing Expression Grammars | SpringerLink
Skip to main content
Springer Nature Link
Log in

Adaptable Parsing Expression Grammars

  • Conference paper
Programming Languages

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 7554))

  • 704 Accesses

Abstract

The term “extensible language” is especially used when a language allows the extension of its own concrete syntax and the definition of the semantics of new constructs. Most popular tools designed for automatic generation of syntactic analyzers do not offer any desirable resources for the specification of extensible languages. When used in the implementation of features like syntax macro definitions, these tools usually impose severe restrictions. We claim that one of the main reasons for these limitations is the lack of formal models that are appropriate for the definition of the syntax of extensible languages.

This paper presents the design and formal definition for Adaptable Parsing Expression Grammars (APEG), an extension to the PEG model that allows the manipulation of its own production rules during the analysis of an input string. It is shown that the proposed model may compare favorably with similar approaches for the definition of the syntax of extensible languages.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5262
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 6578
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Allen, E., Culpepper, R., Nielsen, J.D., Rafkind, J., Ryu, S.: Growing a syntax. In: Proceedings of FOOL 2009 (2009)

    Google Scholar 

  2. Boullier, P.: Dynamic grammars and semantic analysis. Rapport de recherche RR-2322, INRIA. Projet CHLOE (1994)

    Google Scholar 

  3. Bravenboer, M., Kalleberg, K.T., Vermaas, R., Visser, E.: Stratego/XT 0.17. A language and toolset for program transformation. Sci. Comput. Program. 72(1-2), 52–70 (2008)

    Article  MathSciNet  Google Scholar 

  4. Burshteyn, B.: Generation and recognition of formal languages by modifiable grammars. SIGPLAN Not. 25, 45–53 (1990)

    Article  Google Scholar 

  5. Burshteyn, B.: Ussa – universal syntax and semantics analyzer. SIGPLAN Not. 27, 42–60 (1992)

    Article  Google Scholar 

  6. Cabasino, S., Paolucci, P.S., Todesco, G.M.: Dynamic parsers and evolving grammars. SIGPLAN Not. 27, 39–48 (1992)

    Article  Google Scholar 

  7. Christiansen, H.: The Syntax and Semantics of Extensible Languages. Roskilde datalogiske skrifter. Computer Science, Roskilde University Centre (1987)

    Google Scholar 

  8. Christiansen, H.: A survey of adaptable grammars. SIGPLAN Not. 25, 35–44 (1990)

    Article  Google Scholar 

  9. Christiansen, H.: Adaptable Grammars for Non-Context-Free Languages. In: Cabestany, J., Sandoval, F., Prieto, A., Corchado, J.M. (eds.) IWANN 2009, Part I. LNCS, vol. 5517, pp. 488–495. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  10. Dinkelaker, T., Eichberg, M., Mezini, M.: Incremental concrete syntax for embedded languages. In: Proceedings of the 2011 ACM Symposium on Applied Computing, SAC 2011, pp. 1309–1316. ACM, New York (2011)

    Chapter  Google Scholar 

  11. Erdweg, S., Rendel, T., Kästner, C., Ostermann, K.: Sugarj: library-based syntactic language extensibility. In: Proceedings of OOPSLA 2011, pp. 391–406. ACM, New York (2011)

    Google Scholar 

  12. Ford, B.: Packrat parsing: simple, powerful, lazy, linear time, functional pearl. SIGPLAN Not. 37(9), 36–47 (2002)

    Article  Google Scholar 

  13. Ford, B.: Parsing expression grammars: a recognition-based syntactic foundation. SIGPLAN Not. 39(1), 111–122 (2004)

    Article  Google Scholar 

  14. Grimm, R.: Better extensibility through modular syntax. SIGPLAN Not. 41(6), 38–51 (2006)

    Article  Google Scholar 

  15. Jambon, M.: How to customize the syntax of ocaml, using camlp5 (2011), http://mjambon.com/extend-ocaml-syntax.html

  16. Jim, T., Mandelbaum, Y., Walker, D.: Semantics and algorithms for data-dependent grammars. SIGPLAN Not. 45, 417–430 (2010)

    Article  Google Scholar 

  17. Knuth, D.E.: Semantics of Context-Free Languages. Mathematical Systems Theory 2(2), 127–145 (1968)

    Article  MathSciNet  Google Scholar 

  18. Koster, C.H.A.: Affix grammars. In: Algol 68 Implementation, pp. 95–109. North-Holland (1971)

    Google Scholar 

  19. Minsky, Y.: Ocaml for the masses. Commun. ACM 54(11), 53–58 (2011)

    Article  Google Scholar 

  20. Parr, T., Fisher, K.: LL(*): the foundation of the ANTLR parser generator. SIGPLAN Not. 46(6), 425–436 (2011)

    Article  Google Scholar 

  21. Ryu, S.: Parsing fortress syntax. In: Proceedings of PPPJ 2009, pp. 76–84. ACM, New York (2009)

    Google Scholar 

  22. Shutt, J.N.: Recursive adaptable grammars. Master’s thesis, Worchester Polytechnic Institute (1998)

    Google Scholar 

  23. Shutt, J.N.: What is an adaptive grammar? (2001), http://www.cs.wpi.edu/~jshutt/adapt/adapt.html

  24. Stansifer, P., Wand, M.: Parsing reflective grammars. In: Proceedings of LDTA 2011, pp. 10:1–10:7. ACM, New York (2011)

    Google Scholar 

  25. Steele Jr., G.L.: Growing a language. In: Addendum to OOPSLA 1998, pp. 0.01–A1. ACM, New York (1998)

    Google Scholar 

  26. Watt, D.A., Madsen, O.L.: Extended attribute grammars. Comput. J. 26(2), 142–153 (1983)

    Article  Google Scholar 

  27. Wegbreit, B.: Studies in Extensible Programming Languages. Outstanding Dissertations in the Computer Sciences. Garland Publishing, New York (1970)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Brazil

    Leonardo Vieira dos Santos Reis & Roberto da Silva Bigonha

  2. Departamento de Informática, Universidade Federal de Viçosa, Brazil

    Vladimir Oliveira Di Iorio & Luis Eduardo de Souza Amorim

Authors
  1. Leonardo Vieira dos Santos Reis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Roberto da Silva Bigonha
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Vladimir Oliveira Di Iorio
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Luis Eduardo de Souza Amorim
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Universidade Federal do Ceará, Departamento de Computação, Campus Universitário do Pici, Bloco 910, 60356-001, Fortaleza, Brazil

    Francisco Heron de Carvalho Junior

  2. Departamento de Informática, Universidade do Minho, Campus de Gualtar, 4710-057, Braga, Portugal

    Luis Soares Barbosa

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

dos Santos Reis, L.V., da Silva Bigonha, R., Di Iorio, V.O., de Souza Amorim, L.E. (2012). Adaptable Parsing Expression Grammars. In: de Carvalho Junior, F.H., Barbosa, L.S. (eds) Programming Languages. Lecture Notes in Computer Science, vol 7554. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-33182-4_7

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-33182-4_7

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-33181-7

  • Online ISBN: 978-3-642-33182-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation