Red Shift: procedural shift-reduce parsing (vision paper)
Pages 38 - 42
Abstract
Red Shift is a new design pattern for implementing parsers. The pattern draws ideas from traditional shift-reduce parsing as well as procedural PEG parsers. Red Shift parsers behaves like shift-reduce parsers, but eliminate ambiguity by always prioritizing reductions over shifts. To compensate the resulting lack of expressivity, reducers are not simple reduction rules but full-blown procedures written in a general-purpose host language. I found many advantages to this style of parser. In particular, we can generate high-quality error messages more easily; and compose different style of parsers. I also speculate about how Red Shift parsers may improve partial compilation in the context of an IDE.
References
[1]
Sebastian Erdweg, Tijs van der Storm, Markus Völter, Meinte Boersma, Remi Bosman, William R. Cook, Albert Gerritsen, Angelo Hulshout, Steven Kelly, Alex Loh, Gabriël D. P. Konat, Pedro J. Molina, Martin Palatnik, Risto Pohjonen, Eugen Schindler, Klemens Schindler, Riccardo Solmi, Vlad A. Vergu, Eelco Visser, Kevin van der Vlist, Guido H. Wachsmuth, and Jimi van der Woning. 2013. The State of the Art in Language Workbenches . Springer International Publishing, Cham, 197–217.
[2]
Bryan Ford. 2004. Parsing Expression Grammars: A Recognition-based Syntactic Foundation. SIGPLAN Notices 39, 1 (Jan. 2004), 111–122.
[3]
Graham Hutton. 1992. Higher-order Functions for Parsing. Journal of Functional Programming 2, 3 (July 1992), 323–343.
[4]
Nicolas Laurent and Kim Mens. 2015. Parsing Expression Grammars Made Practical. In Proceedings of the ACM SIGPLAN International Conference on Software Language Engineering (SLE 2015) . ACM, 167–172.
[5]
Nicolas Laurent and Kim Mens. 2016. Taming context-sensitive languages with principled stateful parsing. In Proceedings of the 2016 ACM SIGPLAN International Conference on Software Language Engineering, Amsterdam, The Netherlands, October 31 - November 1, 2016 . 15–27. http://dl.acm.org/citation.cfm?id=2997370
[6]
André Murbach Maidl, Fabio Mascarenhas, Sérgio Medeiros, and Roberto Ierusalimschy. 2016. Error reporting in Parsing Expression Grammars. Science of Computer Programming 132 (2016), 129 – 140.
[7]
Theodore Norvell. 2001. Parsing expressions by recursive descent. (2001). https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
Index Terms
- Red Shift: procedural shift-reduce parsing (vision paper)
Recommendations
Faster shift-reduce constituent parsing with a non-binary, bottom-up strategy
Highlights- Bottom-up shift-reduce constituent parsers require prior binarization.
- We ...
AbstractAn increasingly wide range of artificial intelligence applications rely on syntactic information to process and extract meaning from natural language text or speech, with constituent trees being one of the most widely used syntactic ...
Shift-reduce CCG parsing
HLT '11: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1CCGs are directly compatible with binary-branching bottom-up parsing algorithms, in particular CKY and shift-reduce algorithms. While the chart-based approach has been the dominant approach for CCG, the shift-reduce method has been little explored. In ...
Left recursion in Parsing Expression Grammars
Parsing Expression Grammars (PEGs) are a formalism that can describe all deterministic context-free languages through a set of rules that specify a top-down parser for some language. PEGs are easy to use, and there are efficient implementations of PEG ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2017
267 pages
ISBN:9781450355254
DOI:10.1145/3136014
- General Chair:
- Benoit Combemale,
- Program Chairs:
- Marjan Mernik,
- Bernhard Rumpe
Copyright © 2017 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 the author(s) 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
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 23 October 2017
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
SPLASH '17
Sponsor:
SPLASH '17: Conference on Systems, Programming, Languages, and Applications: Software for Humanity
October 23 - 24, 2017
BC, Vancouver, Canada
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 84Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in