Parsing with First-Class Derivatives

by Jonathan Brachthäuser, Till­mann Ren­del, and Klaus Os­ter­mann

In Pro­ceed­ings of the In­ter­na­tional Con­fer­ence on Ob­ject-Ori­ented Pro­gram­ming, Sys­tems, Lan­guages and Ap­pli­ca­tions (OOP­SLA). ACM Press, 2016.

Ab­stract

Br­zo­zowski de­riv­a­tives, well known in the con­text of reg­u­lar ex­pres­sions, have re­cently been re­dis­cov­ered to give a sim­pli­fied ex­pla­na­tion to parsers of con­text-free lan­guages. We add de­riv­a­tives as a novel first-class fea­ture to a stan­dard parser com­bi­na­tor lan­guage. First- class de­riv­a­tives en­able an in­ver­sion of the con­trol flow, al­low­ing to im­ple­ment mod­u­lar parsers for lan­guages that pre­vi­ously re­quired sep­a­rate pre-pro­cess­ing steps or cross- cut­ting mod­i­fi­ca­tions of the parsers. We show that our frame­work of­fers new op­por­tu­ni­ties for reuse and sup­ports a mod­u­lar de­f­i­n­i­tion of in­ter­est­ing use cases of lay­out-sen­si­tive pars­ing.