000207235 001__ 207235
000207235 005__ 20181203023824.0
000207235 0247_ $$2doi$$a10.1145/2660193.2660241
000207235 022__ $$a0362-1340
000207235 02470 $$2ISI$$a000348907400036
000207235 037__ $$aARTICLE
000207235 245__ $$aStaged Parser Combinators for Efficient Data Processing
000207235 260__ $$aNew York$$bAssoc Computing Machinery$$c2014
000207235 269__ $$a2014
000207235 300__ $$a17
000207235 336__ $$aJournal Articles
000207235 520__ $$aParsers 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 nondeterministic 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.
000207235 6531_ $$aParser combinators
000207235 6531_ $$amulti-stage programming
000207235 6531_ $$aalgebraic dynamic programming
000207235 700__ $$0246590$$aJonnalagedda, Manohar$$g170823$$uEPFL, LAMP, Zurich, Switzerland
000207235 700__ $$aCoppey, Thierry
000207235 700__ $$0246677$$aStucki, Sandro$$g152185$$uEPFL, LAMP, Zurich, Switzerland
000207235 700__ $$0243345$$aRompf, Tiark$$g185682$$uEPFL, LAMP, Zurich, Switzerland
000207235 700__ $$0241835$$aOdersky, Martin$$g126003$$uEPFL, LAMP, Zurich, Switzerland
000207235 773__ $$j49$$k10$$q637-653$$tAcm Sigplan Notices
000207235 909C0 $$0252187$$pLAMP$$xU10409
000207235 909CO $$ooai:infoscience.tind.io:207235$$pIC$$particle
000207235 917Z8 $$x166927
000207235 937__ $$aEPFL-ARTICLE-207235
000207235 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000207235 980__ $$aARTICLE