{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:27:24Z","timestamp":1750220844497,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2019,10,10]],"date-time":"2019-10-10T00:00:00Z","timestamp":1570665600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA8750-16-2-0004, FA8650-15-C-7563"],"award-info":[{"award-number":["FA8750-16-2-0004, FA8650-15-C-7563"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1406355, 1618425, 1705092, 1725322"],"award-info":[{"award-number":["1406355, 1618425, 1705092, 1725322"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2019,10,10]]},"abstract":"<jats:p>\n            We present a novel approach to context-free grammar parsing that is based on generating a sequence of grammars called\n            <jats:italic>derivative grammars<\/jats:italic>\n            from a given context-free grammar and input string. The generation of the derivative grammars is described by a few simple inference rules. We present an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) space and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            ) time recognition algorithm, which can be extended to generate parse trees in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            ) time and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) space. Derivative grammars can be viewed as a\n            <jats:italic>symbolic<\/jats:italic>\n            approach to implementing the notion of\n            <jats:italic>derivative languages<\/jats:italic>\n            , which was introduced by Brzozowski.\n          <\/jats:p>\n          <jats:p>\n            Might and others have explored an\n            <jats:italic>operational<\/jats:italic>\n            approach to implementing derivative languages in which the context-free grammar is encoded as a collection of recursive algebraic data types in a functional language like Haskell. Functional language implementation features like knot-tying and lazy evaluation are exploited to ensure that parsing is done correctly and efficiently in spite of complications like left-recursion. In contrast, our symbolic approach using inference rules can be implemented easily in any programming language and we obtain better space bounds for parsing.\n          <\/jats:p>\n          <jats:p>Reifying derivative languages by encoding them symbolically as grammars also enables formal connections to be made for the first time between the derivatives approach and classical parsing methods like the Earley and LL\/LR parsers. In particular, we show that the sets of Earley items maintained by the Earley parser implicitly encode derivative grammars and we give a procedure for producing derivative grammars from these sets. Conversely, we show that our derivative grammar recognizer can be transformed into the Earley recognizer by optimizing some of its bookkeeping. These results suggest that derivative grammars may provide a new foundation for context-free grammar recognition and parsing.<\/jats:p>","DOI":"10.1145\/3360553","type":"journal-article","created":{"date-parts":[[2019,10,11]],"date-time":"2019-10-11T14:53:33Z","timestamp":1570805613000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Derivative grammars: a symbolic approach to parsing with derivatives"],"prefix":"10.1145","volume":"3","author":[{"given":"Ian","family":"Henriksen","sequence":"first","affiliation":[{"name":"University of Texas at Austin, USA"}]},{"given":"Gianfranco","family":"Bilardi","sequence":"additional","affiliation":[{"name":"University of Padua, Italy"}]},{"given":"Keshav","family":"Pingali","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,10,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908128"},{"key":"e_1_2_1_2_1","volume-title":"Ullman","author":"Aho Alfred V.","year":"1986","unstructured":"Alfred V. Aho , Ravi Sethi , and Jeffrey D . Ullman . 1986 . Compilers: principles, techniques, and tools. Addison Wesley . Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. 1986. Compilers: principles, techniques, and tools. Addison Wesley."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2984026"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1932681.1863585"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/362007.362035"},{"key":"e_1_2_1_7_1","volume-title":"Reference: Racket. Technical Report PLT-TR-2010-1","author":"Flatt Matthew","year":"2010","unstructured":"Matthew Flatt and PLT. 2010 . Reference: Racket. Technical Report PLT-TR-2010-1 . PLT Design Inc . https:\/\/racket- lang.org\/tr1\/ . Matthew Flatt and PLT. 2010. Reference: Racket. Technical Report PLT-TR-2010-1. PLT Design Inc. https:\/\/racket- lang.org\/tr1\/ ."},{"key":"e_1_2_1_8_1","volume-title":"Ullman","author":"Hopcroft John E.","year":"1979","unstructured":"John E. Hopcroft and Jeffrey D . Ullman . 1979 . Introduction to Automata Theory, Languages and Computability (1st ed.). Addison-Wesley Publishing Co. , Inc., Boston, MA, USA. John E. Hopcroft and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages and Computability (1st ed.). Addison-Wesley Publishing Co., Inc., Boston, MA, USA."},{"key":"e_1_2_1_9_1","unstructured":"Jeffrey Kegler. 2017. Marpa\u2013R2. https:\/\/github.com\/jeffreykegler\/Marpa- - R2 .  Jeffrey Kegler. 2017. Marpa\u2013R2. https:\/\/github.com\/jeffreykegler\/Marpa- - R2 ."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90180-A"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2034773.2034801"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993548"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.03.044"},{"volume-title":"Parsing theory","author":"Sippu Seppo","key":"e_1_2_1_14_1","unstructured":"Seppo Sippu and Eljas Soisalon-Soininen . 1988. Parsing theory . Springer-Verlag . Seppo Sippu and Eljas Soisalon-Soininen. 1988. Parsing theory. Springer-Verlag."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54458-7_15"},{"key":"e_1_2_1_16_1","volume-title":"Programming Perl","author":"Wall Larry","unstructured":"Larry Wall . 2000. Programming Perl ( 3 rd ed.). O\u2019Reilly & amp; Associates, Inc., Sebastopol, CA, USA. Larry Wall. 2000. Programming Perl (3rd ed.). O\u2019Reilly &amp; Associates, Inc., Sebastopol, CA, USA.","edition":"3"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3360553","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3360553","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3360553","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:22:58Z","timestamp":1750202578000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3360553"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,10]]},"references-count":16,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2019,10,10]]}},"alternative-id":["10.1145\/3360553"],"URL":"https:\/\/doi.org\/10.1145\/3360553","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2019,10,10]]},"assertion":[{"value":"2019-10-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}