000203076 001__ 203076
000203076 005__ 20190317000038.0
000203076 0247_ $$2doi$$a10.1145/2660193.2660241
000203076 037__ $$aCONF
000203076 245__ $$aStaged parser combinators for efficient data processing
000203076 269__ $$a2014
000203076 260__ $$bACM Press$$c2014$$aNew York, New York, USA
000203076 336__ $$aConference Papers
000203076 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.
000203076 6531_ $$aParser combinators
000203076 6531_ $$amulti-stage programming
000203076 6531_ $$aalgebraic dynamic programming
000203076 700__ $$0246590$$g170823$$aJonnalagedda, Manohar
000203076 700__ $$0247456$$g170226$$aCoppey, Thierry
000203076 700__ $$0246677$$g152185$$aStucki, Sandro
000203076 700__ $$aRompf, Tiark$$g185682$$0243345
000203076 700__ $$aOdersky, Martin$$g126003$$0241835
000203076 7112_ $$d20-24 October 2014$$cPortland, Oregon, USA$$aObject Oriented Programming Systems Languages & Applications (OOPSLA)
000203076 773__ $$tProceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications - OOPSLA '14$$q637-653
000203076 8564_ $$uhttps://infoscience.epfl.ch/record/203076/files/p637-jonnalagedda.pdf$$zPublisher's version$$s671506$$yPublisher's version
000203076 909C0 $$xU10409$$0252187$$pLAMP
000203076 909C0 $$pDATA$$xU12327$$0252342
000203076 909CO $$qGLOBAL_SET$$pconf$$pIC$$ooai:infoscience.tind.io:203076
000203076 917Z8 $$x170823
000203076 937__ $$aEPFL-CONF-203076
000203076 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000203076 980__ $$aCONF