research-article

Parsing reflective grammars

Authors:

Paul Stansifer,

Mitchell WandAuthors Info & Claims

LDTA '11: Proceedings of the Eleventh Workshop on Language Descriptions, Tools and Applications

Article No.: 10, Pages 1 - 7

https://doi.org/10.1145/1988783.1988793

Published: 26 March 2011 Publication History

Abstract

Existing technology can parse arbitrary context-free grammars, but only a single, static grammar per input. In order to support more powerful syntax-extension systems, we propose reflective grammars, which can modify their own syntax during parsing. We demonstrate and prove the correctness of an algorithm for parsing reflective grammars. The algorithm is based on Earley's algorithm, and we prove that it performs asymptotically no worse than Earley's algorithm on ordinary context-free grammars.

References

[1]

K. Atkinson, M. Flatt, and G. Lindstrom. ABI compatibility through a customizable language. Proceedings of the Ninth International Conference on Generative Programming and Component Engineering - GPCE '10, page 147, 2010.

Digital Library

[2]

J. Aycock. Practical Earley parsing. The Computer Journal, 45(6):620--630, June 2002.

[3]

J. Aycock and N. Horspool. Directly-executable Earley parsing. In R. Wilhelm, editor, Compiler Construction, volume 2027 of Lecture Notes in Computer Science, pages 229--243. Springer Berlin/Heidelberg, 2001. 10.1007/3-540-45306-7_16.

Digital Library

[4]

J. Bachrach and K. Playford. D-expressions: Lisp power, Dylan style. http://people.csail.mit. edu/jrb/Projects/dexprs.htm, 1999.

[5]

C. Brabrand, M. I. Schwartzbach, and M. Vanggaard. The metafront system: Extensible parsing and transformation. Electronic Notes in Theoretical Computer Science, 82(3):592--611, Dec. 2003.

[6]

L. Cardelli, F. Matthes, and M. Abadi. Extensible syntax with lexical scoping. http://lucacardelli.name/Papers/SRC-121.ps, 1994.

[7]

D. de Rauglaudre. Camlp4 - reference manual. http://caml.inria.fr/pub/docs/manual-camlp4/, 2003.

[8]

J. Earley. An efficient context-free parsing algorithm. Communications of the ACM, 26(1), 1970.

[9]

J. Falcon and W. Cook. Gel: A generic extensible language. In Domain-Specific Languages, pages 58--77. Springer, 2009.

Digital Library

[10]

B. Ford. Parsing expression grammars: a recognition-based syntactic foundation. In Proceedings ACM Symposium on Principles of Programming Languages, pages 111--122, 2004.

Digital Library

[11]

T. Jim, Y. Mandelbaum, and D. Walker. Semantics and algorithms for data-dependent grammars. Annual Symposium on Principles of Programming Languages, 45(1), 2010.

Digital Library

[12]

L. Kats, E. Visser, and G. Wachsmuth. Pure and declarative syntax definition: Paradise lost and regained. Proceedings of Onward! 2010, 2010.

Digital Library

[13]

D. M. Kolbly. Extensible Language Implementation. Ph.D., University of Texas at Austin, 2002.

Digital Library

[14]

Y. Mandelbaum and T. Jim. Efficient Earley parsing with regular right-hand sides. Workshop on Language Descriptions Tools and Applications, 2009.

Digital Library

[15]

P. McLean and R. Horspool. A faster Earley parser. In T. Gyimóthy, editor, Compiler Construction, volume 1060 of Lecture Notes in Computer Science, pages 281--293. Springer Berlin/Heidelberg, 1996. 10.1007/3-540-61053-7_68.

Digital Library

[16]

S. McPeak and G. C. Necula. Elkhound: A fast, practical GLR parser generator. Compiler Construction, 2004.

[17]

M. Might and D. Darais. Yacc is dead. http://arxiv.org/abs/1010.5023, Oct. 2010.

[18]

A. C. Schwerdfeger and E. R. Van Wyk. Verifiable composition of deterministic grammars. Conference on Programming Language Design and Implementation, 44(6), 2009.

Digital Library

[19]

E. Scott. SPPF-style parsing from Earley recognisers. Electron. Notes Theor. Comput. Sci., 203:53--67, April 2008.

Digital Library

[20]

P. Stansifer and M. Wand. Parsing reflective grammars. Technical report, Northeastern University, 2011. http://arxiv.org/abs/1102.2003.

[21]

E. R. Van Wyk, D. Bodin, J. Gao, and L. Krishnan. Silver: an extensible attribute grammar system. Electronic Notes in Theoretical Computer Science, 203(2):103--116, Apr. 2008.

Digital Library

Cited By

Saikunas A(2019)Just-in-time Parsing with Scannerless Earley Virtual MachinesProceedings of the 3rd International Conference on Vision, Image and Signal Processing10.1145/3387168.3387216(1-10)Online publication date: 26-Aug-2019
https://dl.acm.org/doi/10.1145/3387168.3387216
Cardoso ERibeiro RReis LBigonha MBigonha RDi Iorio VHung CPapadopoulos G(2019)An attribute language definition for adaptable parsing expression grammarsProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3299738(1518-1525)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3299738
Régis-Gianas YJeannerod NTreinen RPearce DMayerhofer TSteimann F(2018)Morbig: a static parser for POSIX shellProceedings of the 11th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3276604.3276615(29-41)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276604.3276615
Show More Cited By

Index Terms

Parsing reflective grammars
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Parsers

Recommendations

SPPF-Style Parsing From Earley Recognisers

In its recogniser form, Earley's algorithm for testing whether a string can be derived from a grammar is worst case cubic on general context free grammars (CFG). Earley gave an outline of a method for turning his recognisers into parsers, but it turns ...
Recognition is not parsing - SPPF-style parsing from cubic recognisers

In their recogniser forms, the Earley and RIGLR algorithms for testing whether a string can be derived from a grammar are worst-case cubic on general context free grammars (CFG). Earley gave an outline of a method for turning his recognisers into ...
Parsing expression grammars: a recognition-based syntactic foundation
POPL '04: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages

For decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

LDTA '11: Proceedings of the Eleventh Workshop on Language Descriptions, Tools and Applications

March 2011

91 pages

ISBN:9781450306652

DOI:10.1145/1988783

Program Chairs:
Claus Brabrand
IT University of Copenhagen
,
Eric Van Wyk
University of Minnesota

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

University of Minnesota Software Engineering Center

In-Cooperation

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 March 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Division of Computing and Communication Foundations

Conference

LDTA '11

Sponsor:

LDTA '11: Language Descriptions, Tools, and Applications

March 26 - 27, 2011

Saarbrucken, Germany

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
110
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Saikunas A(2019)Just-in-time Parsing with Scannerless Earley Virtual MachinesProceedings of the 3rd International Conference on Vision, Image and Signal Processing10.1145/3387168.3387216(1-10)Online publication date: 26-Aug-2019
https://dl.acm.org/doi/10.1145/3387168.3387216
Cardoso ERibeiro RReis LBigonha MBigonha RDi Iorio VHung CPapadopoulos G(2019)An attribute language definition for adaptable parsing expression grammarsProceedings of the 34th ACM/SIGAPP Symposium on Applied Computing10.1145/3297280.3299738(1518-1525)Online publication date: 8-Apr-2019
https://dl.acm.org/doi/10.1145/3297280.3299738
Régis-Gianas YJeannerod NTreinen RPearce DMayerhofer TSteimann F(2018)Morbig: a static parser for POSIX shellProceedings of the 11th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3276604.3276615(29-41)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276604.3276615
Reis LBigonha RDi Iorio VAmorim L(2014)The formalization and implementation of Adaptable Parsing Expression GrammarsScience of Computer Programming10.1016/j.scico.2014.02.02096:P2(191-210)Online publication date: 15-Dec-2014
https://dl.acm.org/doi/10.1016/j.scico.2014.02.020
Cazzola WVacchi E(2014)On the incremental growth and shrinkage of LR goto-graphsActa Informatica10.1007/s00236-014-0201-251:7(419-447)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1007/s00236-014-0201-2
dos Santos Reis Lda Silva Bigonha RDi Iorio Vde Souza Amorim L(2012)Adaptable parsing expression grammarsProceedings of the 16th Brazilian conference on Programming Languages10.1007/978-3-642-33182-4_7(72-86)Online publication date: 23-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-33182-4_7

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents