{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T20:20:21Z","timestamp":1784233221616,"version":"3.55.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T00:00:00Z","timestamp":1634256000000},"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":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2021,10,20]]},"abstract":"<jats:p>In this paper, 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 a popular parsing tool ANTLR and other popular hand-crafted parsers. The correctness of the core parsing algorithm is formally verified in the proof assistant Coq.<\/jats:p>","DOI":"10.1145\/3485528","type":"journal-article","created":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T19:18:28Z","timestamp":1634325508000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["A derivative-based parser generator for visibly Pushdown grammars"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2493-9111","authenticated-orcid":false,"given":"Xiaodong","family":"Jia","sequence":"first","affiliation":[{"name":"Pennsylvania State University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8773-2084","authenticated-orcid":false,"given":"Ashish","family":"Kumar","sequence":"additional","affiliation":[{"name":"Pennsylvania State University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6109-6091","authenticated-orcid":false,"given":"Gang","family":"Tan","sequence":"additional","affiliation":[{"name":"Pennsylvania State University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,15]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516518"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_2_2_3_1","volume-title":"Programming Languages and Their Compilers: Preliminary Notes","author":"Cocke John"},{"key":"e_1_2_2_4_1","unstructured":"F. L. Deremer. 1969. PRACTICAL TRANSLATORS FOR LR(K) LANGUAGES. USA.  F. L. Deremer. 1969. PRACTICAL TRANSLATORS FOR LR(K) LANGUAGES. USA."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/362007.362035"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385992"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/982962.964011"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360553"},{"key":"e_1_2_2_9_1","unstructured":"Xiaodong Jia Ashish Kuma and Gang Tan. 2021. A Derivative-based Parser Generator for Visibly Pushdown Grammars. arxiv:2109.04258.  Xiaodong Jia Ashish Kuma and Gang Tan. 2021. A Derivative-based Parser Generator for Visibly Pushdown Grammars. arxiv:2109.04258."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28869-2_20"},{"key":"e_1_2_2_11_1","volume-title":"An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages","author":"Kasami Tadao"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-7(2:18)2011"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITP.2019.24"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454053"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2034773.2034801"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2345156.2254111"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796808007090"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2714064.2660202"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.27"},{"key":"e_1_2_2_20_1","volume-title":"EverParse: Verified Secure Zero-Copy Parsers for Authenticated Message Formats. In 28th USENIX Security Symposium (USENIX Security 19)","author":"Ramananandro Tahina","year":"2019"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)80007-X"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485528","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485528","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485528","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:40Z","timestamp":1750191520000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485528"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,15]]},"references-count":21,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2021,10,20]]}},"alternative-id":["10.1145\/3485528"],"URL":"https:\/\/doi.org\/10.1145\/3485528","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,15]]},"assertion":[{"value":"2021-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}