{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T10:19:30Z","timestamp":1780827570572,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":10,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,6,2]],"date-time":"2017-06-02T00:00:00Z","timestamp":1496361600000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["ARFL FA8750-15-2-0092, FA8750-12-2-0106"],"award-info":[{"award-number":["ARFL FA8750-15-2-0092, FA8750-12-2-0106"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1350344"],"award-info":[{"award-number":["1350344"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,6,2]]},"DOI":"10.1145\/2908080.2908128","type":"proceedings-article","created":{"date-parts":[[2016,6,2]],"date-time":"2016-06-02T15:23:42Z","timestamp":1464881022000},"page":"224-236","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["On the complexity and performance of parsing with derivatives"],"prefix":"10.1145","author":[{"given":"Michael D.","family":"Adams","sequence":"first","affiliation":[{"name":"University of Utah, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Celeste","family":"Hollenbeck","sequence":"additional","affiliation":[{"name":"University of Utah, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthew","family":"Might","sequence":"additional","affiliation":[{"name":"University of Utah, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/362007.362035"},{"issue":"1","key":"e_1_3_2_1_3_1","first-page":"R8","article-title":"URL https:\/\/github. com\/Engelberg\/instaparse. Abraham Flaxman, Aram W. Harrow, and Gregory B. Sorkin. Strings with maximally many distinct subsequences and substrings","volume":"11","author":"Engelberg Mark","year":"2015","unstructured":"Mark Engelberg. instaparse, 2015. URL https:\/\/github. com\/Engelberg\/instaparse. Abraham Flaxman, Aram W. Harrow, and Gregory B. Sorkin. Strings with maximally many distinct subsequences and substrings. The Electronic Journal of Combanatorics, 11(1):R8, 2004. ISSN 1077-8926. URL http:\/\/www.combinatorics. org\/ojs\/index.php\/eljc\/article\/view\/v11i1r8. Bryan Ford. Parsing expression grammars: a recognition-based syntactic foundation. In Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL \u201904, pages 111\u2013122, New York, NY, USA, January 2004. ACM. ISBN 1-58113-729-X. doi: 10.1145\/ 964001.964011.","journal-title":"The Electronic Journal of Combanatorics"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/512927.512945"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994"},{"key":"e_1_3_2_1_6_1","unstructured":"1037."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380230803"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2034773.2034801"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796808007090"},{"key":"e_1_3_2_1_10_1","volume-title":"parser","author":"Vognsen Per","year":"2012","unstructured":"Per Vognsen. parser, 2012. URL https:\/\/gist.github.com\/ pervognsen\/815b208b86066f6d7a00. Introduction Background The bzd Derivative Parsing Expressions Derivatives of Parsing Expressions Nullability Derivatives of Context-free Languages Representation Computation Performance Complexity Analysis Total Running Time in Terms of Grammar Nodes Grammar Nodes in Terms of Input Length Running Time in Terms of Input Length Improving Performance in Practice Benchmarks Computing Fixed Points Compaction Right-hand Children of Sequence Nodes Canonicalizing Chains of Sequence Nodes Avoiding Separate Passes Hash Tables and Memoization Conclusion References"}],"event":{"name":"PLDI '16: ACM SIGPLAN Conference on Programming Language Design and Implementation","location":"Santa Barbara CA USA","acronym":"PLDI '16","sponsor":["SIGPLAN ACM Special Interest Group on Programming Languages"]},"container-title":["Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2908080.2908128","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2908080.2908128","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2908080.2908128","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:19:33Z","timestamp":1763457573000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2908080.2908128"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,2]]},"references-count":10,"alternative-id":["10.1145\/2908080.2908128","10.1145\/2908080"],"URL":"https:\/\/doi.org\/10.1145\/2908080.2908128","relation":{"is-identical-to":[{"id-type":"doi","id":"10.1145\/2980983.2908128","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2016,6,2]]},"assertion":[{"value":"2016-06-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}