{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T21:01:14Z","timestamp":1751662874590,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,5,15]],"date-time":"2023-05-15T00:00:00Z","timestamp":1684108800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000185","name":"DARPA","doi-asserted-by":"crossref","award":["HR0011-19-C-0073"],"award-info":[{"award-number":["HR0011-19-C-0073"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>In this article, we present a derivative-based, functional recognizer and parser generator for visibly pushdown grammars. The generated parser accepts ambiguous grammars and produces a parse forest containing all valid parse trees for an input string in linear time. Each parse tree in the forest can then be extracted also in linear time. Besides the parser generator, to allow more flexible forms of the visibly pushdown grammars, we also present a translator that converts a tagged CFG to a visibly pushdown grammar in a sound way, and the parse trees of the tagged CFG are further produced by running the semantic actions embedded in the parse trees of the translated visibly pushdown grammar. The performance of the parser is compared with popular parsing tools, including ANTLR, GNU Bison, and other popular hand-crafted parsers. The correctness and the time complexity of the core parsing algorithm are formally verified in the proof assistant Coq.<\/jats:p>","DOI":"10.1145\/3591472","type":"journal-article","created":{"date-parts":[[2023,4,8]],"date-time":"2023-04-08T10:31:31Z","timestamp":1680949891000},"page":"1-68","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A Derivative-based Parser Generator for Visibly Pushdown Grammars"],"prefix":"10.1145","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2493-9111","authenticated-orcid":false,"given":"Xiaodong","family":"Jia","sequence":"first","affiliation":[{"name":"The Pennsylvania State University, Pennsylvania, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8773-2084","authenticated-orcid":false,"given":"Ashish","family":"Kumar","sequence":"additional","affiliation":[{"name":"The Pennsylvania State University, Pennsylvania, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6109-6091","authenticated-orcid":false,"given":"Gang","family":"Tan","sequence":"additional","affiliation":[{"name":"The Pennsylvania State University, Pennsylvania, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,5,15]]},"reference":[{"unstructured":"Rajeev Alur. 2016. Nested Words. Retrieved from https:\/\/www.cis.upenn.edu\/alur\/nw.html.","key":"e_1_3_4_2_2"},{"doi-asserted-by":"publisher","key":"e_1_3_4_3_2","DOI":"10.1145\/1516512.1516518"},{"unstructured":"ANTLR. 2014. Grammars-v4. Retrieved from https:\/\/github.com\/antlr\/grammars-v4.","key":"e_1_3_4_4_2"},{"key":"e_1_3_4_5_2","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1007\/978-3-642-00590-9_12","volume-title":"Programming Languages and Systems","author":"Barthwal Aditi","year":"2009","unstructured":"Aditi Barthwal and Michael Norrish. 2009. Verified, executable parsing. In Programming Languages and Systems, Giuseppe Castagna (Ed.). Springer Berlin, 160\u2013174."},{"doi-asserted-by":"publisher","key":"e_1_3_4_6_2","DOI":"10.2168\/LMCS-12(2:6)2016"},{"doi-asserted-by":"publisher","key":"e_1_3_4_7_2","DOI":"10.1145\/321239.321249"},{"doi-asserted-by":"publisher","key":"e_1_3_4_8_2","DOI":"10.5555\/1097042"},{"doi-asserted-by":"publisher","key":"e_1_3_4_9_2","DOI":"10.1145\/1863543.1863585"},{"doi-asserted-by":"publisher","key":"e_1_3_4_10_2","DOI":"10.1145\/3408990"},{"doi-asserted-by":"publisher","key":"e_1_3_4_11_2","DOI":"10.5555\/888578"},{"doi-asserted-by":"publisher","key":"e_1_3_4_12_2","DOI":"10.5555\/888578"},{"unstructured":"Justin Dorfman. 2015. awesome-json-datasets. Retrieved from https:\/\/github.com\/jdorfman\/awesome-json-datasets.","key":"e_1_3_4_13_2"},{"doi-asserted-by":"publisher","key":"e_1_3_4_14_2","DOI":"10.1007\/s002360000037"},{"doi-asserted-by":"publisher","key":"e_1_3_4_15_2","DOI":"10.1145\/362007.362035"},{"doi-asserted-by":"publisher","key":"e_1_3_4_16_2","DOI":"10.1145\/3385412.3385992"},{"unstructured":"Felix. 2010. Htmlparser2. Retrieved from https:\/\/github.com\/fb55\/htmlparser2.","key":"e_1_3_4_17_2"},{"doi-asserted-by":"publisher","key":"e_1_3_4_18_2","DOI":"10.1016\/j.jlamp.2014.09.002"},{"unstructured":"Free Software Foundation. 2021. GNU Bison. Retrieved from https:\/\/www.gnu.org\/software\/bison\/.","key":"e_1_3_4_19_2"},{"unstructured":"GoogleChromeLabs. 2019. json-parse-benchmark. Retrieved from https:\/\/github.com\/GoogleChromeLabs\/json-parse-benchmark.","key":"e_1_3_4_20_2"},{"unstructured":"Ian Henderson. 2017. Owl. Retrieved from https:\/\/github.com\/ianh\/owl.","key":"e_1_3_4_21_2"},{"doi-asserted-by":"publisher","key":"e_1_3_4_22_2","DOI":"10.1145\/3360553"},{"doi-asserted-by":"publisher","key":"e_1_3_4_23_2","DOI":"10.1145\/3485528"},{"doi-asserted-by":"publisher","key":"e_1_3_4_24_2","DOI":"10.1007\/978-3-642-28869-2_20"},{"key":"e_1_3_4_25_2","volume-title":"An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages","author":"Kasami Tadao","year":"1965","unstructured":"Tadao Kasami. 1965. An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages. Technical Report. Air Force Cambridge Research Laboratory."},{"doi-asserted-by":"publisher","key":"e_1_3_4_26_2","DOI":"10.1007\/978-3-642-11957-6_19"},{"doi-asserted-by":"publisher","key":"e_1_3_4_27_2","DOI":"10.4230\/LIPIcs.ITP.2019.24"},{"doi-asserted-by":"publisher","key":"e_1_3_4_28_2","DOI":"10.1145\/3453483.3454053"},{"unstructured":"libxmljs. 2009. Libxmljs. Retrieved from https:\/\/github.com\/libxmljs\/libxmljs.","key":"e_1_3_4_29_2"},{"doi-asserted-by":"publisher","key":"e_1_3_4_30_2","DOI":"10.1007\/978-3-319-29604-3_10"},{"doi-asserted-by":"publisher","key":"e_1_3_4_31_2","DOI":"10.1145\/2034773.2034801"},{"doi-asserted-by":"publisher","key":"e_1_3_4_32_2","DOI":"10.1145\/2254064.2254111"},{"unstructured":"NaturalIntelligence. 2017. fast-xml-parser. Retrieved from https:\/\/github.com\/NaturalIntelligence\/fast-xml-parser.","key":"e_1_3_4_33_2"},{"key":"e_1_3_4_34_2","volume-title":"Towards a Practical Programming Language Based on Dependent Type Theory","author":"Norell Ulf","year":"2007","unstructured":"Ulf Norell. 2007. Towards a Practical Programming Language Based on Dependent Type Theory. Vol. 32. Chalmers University of Technology."},{"doi-asserted-by":"publisher","key":"e_1_3_4_35_2","DOI":"10.1017\/S0956796808007090"},{"unstructured":"Terence Parr. 2022. ANTLR (ANother Tool for Language Recognition). Retrieved from https:\/\/www.antlr.org\/.","key":"e_1_3_4_36_2"},{"doi-asserted-by":"publisher","key":"e_1_3_4_37_2","DOI":"10.1145\/2714064.2660202"},{"doi-asserted-by":"publisher","key":"e_1_3_4_38_2","DOI":"10.1109\/SP.2017.27"},{"key":"e_1_3_4_39_2","first-page":"1465","volume-title":"Proceedings of the 28th USENIX Security Symposium (USENIX Security\u201919)","author":"Ramananandro Tahina","year":"2019","unstructured":"Tahina Ramananandro, Antoine Delignat-Lavaud, Cedric Fournet, Nikhil Swamy, Tej Chajed, Nadim Kobeissi, and Jonathan Protzenko. 2019. EverParse: Verified secure zero-copy parsers for authenticated message formats. In Proceedings of the 28th USENIX Security Symposium (USENIX Security\u201919). USENIX Association, 1465\u20131482. Retrieved from https:\/\/www.usenix.org\/conference\/usenixsecurity19\/presentation\/delignat-lavaud."},{"key":"e_1_3_4_40_2","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1007\/978-3-642-25379-9_10","volume-title":"Certified Programs and Proofs","author":"Ridge Tom","year":"2011","unstructured":"Tom Ridge. 2011. Simple, functional, sound and complete parsing for all context-free grammars. In Certified Programs and Proofs, Jean-Pierre Jouannaud and Zhong Shao (Eds.). Springer Berlin, 103\u2013118."},{"unstructured":"Isaac Z. Schlueter. 2010. sax-js. Retrieved from https:\/\/github.com\/isaacs\/sax-js.","key":"e_1_3_4_41_2"},{"unstructured":"JFlex Team. 2023. JFlex. Retrieved from https:\/\/jflex.de\/.","key":"e_1_3_4_42_2"},{"unstructured":"XimpleWare. 2004. VTD-XML Benchmark Report for Version 2.3. Retrieved from https:\/\/vtd-xml.sourceforge.io\/2.3\/benchmark_2.3_parsing_only.html.","key":"e_1_3_4_43_2"},{"unstructured":"Milo Yip. 2014. nativejson-benchmark. Retrieved from https:\/\/github.com\/miloyip\/nativejson-benchmark.","key":"e_1_3_4_44_2"},{"doi-asserted-by":"publisher","key":"e_1_3_4_45_2","DOI":"10.1016\/S0019-9958(67)80007-X"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591472","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3591472","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:47Z","timestamp":1750286927000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591472"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,15]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3591472"],"URL":"https:\/\/doi.org\/10.1145\/3591472","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2023,5,15]]},"assertion":[{"value":"2022-06-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}