Grammars for Indentation-Sensitive Parsing

Nestra, Härmel

doi:10.4230/LIPIcs.MFCS.2017.45

File

LIPIcs.MFCS.2017.45.pdf

Filesize: 0.49 MB
13 pages

Document Identifiers

DOI: 10.4230/LIPIcs.MFCS.2017.45
URN: urn:nbn:de:0030-drops-80788

Author Details

Härmel Nestra

Cite AsGet BibTex

Härmel Nestra. Grammars for Indentation-Sensitive Parsing. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 45:1-45:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.45

Abstract

Adams' extension of parsing expression grammars enables specifying indentation sensitivity using two non-standard grammar constructs - indentation by a binary relation and alignment. This paper is a theoretical study of Adams' grammars. It proposes a step-by-step transformation of well-formed Adams' grammars for elimination of the alignment construct from the grammar. The idea that alignment could be avoided was suggested by Adams but no process for achieving this aim has been described before. This paper also establishes general conditions that binary relations used in indentation constructs must satisfy in order to enable efficient parsing.

Keywords

Parsing expression grammars
indentation
grammar transformation

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Michael D. Adams. The indentation package. URL: http://hackage.haskell.org/package/indentation.
Michael D. Adams. Principled parsing for indentation-sensitive languages: Revisiting Landin’s offside rule. In Roberto Giacobazzi and Radhia Cousot, editors, The 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'13, Rome, Italy - January 23 - 25, 2013, pages 511-522. ACM, 2013. URL: http://dx.doi.org/10.1145/2429069.2429129.
Michael D. Adams and Ömer S. Aŭgacan. Indentation-sensitive parsing for Parsec. In Wouter Swierstra, editor, Proceedings of the 2014 ACM SIGPLAN symposium on Haskell, Gothenburg, Sweden, September 4-5, 2014, pages 121-132. ACM, 2014. URL: http://dx.doi.org/10.1145/2633357.2633369.
Alfred V. Aho and Jeffrey D. Ullman. The Theory of Parsing, Translation, and Compiling. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1972.
Alexander Birman and Jeffrey D. Ullman. Parsing algorithms with backtrack. Information and Control, 23(1):1-34, 1973. URL: http://dx.doi.org/10.1016/S0019-9958(73)90851-6.
Bryan Ford. Parsing expression grammars: A recognition-based syntactic foundation. In Neil D. Jones and Xavier Leroy, editors, Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2004, Venice, Italy, January 14-16, 2004, pages 111-122. ACM, 2004. URL: http://dx.doi.org/10.1145/964001.964011.
Tetsuro Matsumura and Kimio Kuramitsu. A declarative extension of parsing expression grammars for recognizing most programming languages. JIP, 24(2):256-264, 2016. URL: http://dx.doi.org/10.2197/ipsjjip.24.256.
Sérgio Medeiros, Fabio Mascarenhas, and Roberto Ierusalimschy. Left recursion in parsing expression grammars. In Francisco Heron de Carvalho Junior and Luís Soares Barbosa, editors, Programming Languages - 16th Brazilian Symposium, SBLP 2012, Natal, Brazil, September 23-28, 2012. Proceedings, volume 7554 of Lecture Notes in Computer Science, pages 27-41. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33182-4_4.
Härmel Nestra. Alignment elimination from Adams' grammars, 2017. URL: http://arxiv.org/abs/1706.06497.