NDLI: Staged parser combinators for efficient data processing

Content Provider	ACM Digital Library
Author	Odersky, Martin Rompf, Tiark Jonnalagedda, Manohar Stucki, Sandro Coppey, Thierry
Abstract	Parsers are ubiquitous in computing, and many applications depend on their performance for decoding data efficiently. Parser combinators are an intuitive tool for writing parsers: tight integration with the host language enables grammar specifications to be interleaved with processing of parse results. Unfortunately, parser combinators are typically slow due to the high overhead of the host language abstraction mechanisms that enable composition. We present a technique for eliminating such overhead. We use staging, a form of runtime code generation, to dissociate input parsing from parser composition, and eliminate intermediate data structures and computations associated with parser composition at staging time. A key challenge is to maintain support for input dependent grammars, which have no clear stage distinction. Our approach applies to top-down recursive-descent parsers as well as bottom-up non-deterministic parsers with key applications in dynamic programming on sequences, where we auto-generate code for parallel hardware. We achieve performance comparable to specialized, hand-written parsers.
Starting Page	637
Ending Page	653
Page Count	17
File Format	PDF
ISSN	03621340 15581160
DOI	10.1145/2714064.2660241
Journal	ACM SIGPLAN Notices (SIGP)
Volume Number	49
Issue Number	10
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1983-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Parser combinators Multi-stage programming Algebraic dynamic programming
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Staged parser combinators for efficient data processing

Sneaking around concatMap:efficient combinators for dynamic programming

Mint:Java multi-stage programming using weak separability

Total parser combinators

Tagless staged interpreters for typed languages

Multi-stage programming (poster)

Scalaness/nesT:type specialized staged programming for sensor networks

Terra:a multi-stage language for high-performance computing

Parsing with first-class derivatives

Staged parser combinators for efficient data processing

Similar Documents

Staged parser combinators for efficient data processing

Sneaking around concatMap:efficient combinators for dynamic programming

Mint:Java multi-stage programming using weak separability

Total parser combinators

Tagless staged interpreters for typed languages

Multi-stage programming (poster)

Scalaness/nesT:type specialized staged programming for sensor networks

Terra:a multi-stage language for high-performance computing

Parsing with first-class derivatives

Staged parser combinators for efficient data processing