{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:25:14Z","timestamp":1750220714368,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":20,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,2,22]],"date-time":"2020-02-22T00:00:00Z","timestamp":1582329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,2,22]]},"DOI":"10.1145\/3377555.3377898","type":"proceedings-article","created":{"date-parts":[[2020,2,24]],"date-time":"2020-02-24T16:22:40Z","timestamp":1582561360000},"page":"155-166","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Is stateful packrat parsing really linear in practice? a counter-example, an improved grammar, and its parsing algorithms"],"prefix":"10.1145","author":[{"given":"Nariyoshi","family":"Chida","sequence":"first","affiliation":[{"name":"NTT, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuhei","family":"Kawakoya","sequence":"additional","affiliation":[{"name":"NTT, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dai","family":"Ikarashi","sequence":"additional","affiliation":[{"name":"NTT, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kenji","family":"Takahashi","sequence":"additional","affiliation":[{"name":"NTT, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Koushik","family":"Sen","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,2,24]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Supplementary material for this paper is available in the following github repository. URL: https:\/\/github.com\/NariyoshiChida\/cc2020.  Supplementary material for this paper is available in the following github repository. URL: https:\/\/github.com\/NariyoshiChida\/cc2020."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429129"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2714064.2660199"},{"key":"e_1_3_2_1_4_1","volume-title":"Regular expression denial of service - redos","author":"Adar W.","year":"2017","unstructured":"Adar , W. Regular expression denial of service - redos , 2017 . URL https:\/\/www.owasp.org\/index.php\/Regular_expression_Denial_of_ Service _-_ReDoS. Adar, W. Regular expression denial of service - redos, 2017. URL https:\/\/www.owasp.org\/index.php\/Regular_expression_Denial_of_ Service_-_ReDoS."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321488"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236024.3236027"},{"key":"e_1_3_2_1_7_1","first-page":"47","volume-title":"Proceedings of the Seventh ACM SIGPLAN International Conference on Functional Programming","author":"Ford B.","year":"2002","unstructured":"Ford , B. Packrat parsing :: Simple, powerful, lazy, linear time, functional pearl . In Proceedings of the Seventh ACM SIGPLAN International Conference on Functional Programming ( New York, NY, USA , 2002 ), ICFP \u201902, ACM, pp. 36\u2013 47 . Ford, B. Packrat parsing:: Simple, powerful, lazy, linear time, functional pearl. In Proceedings of the Seventh ACM SIGPLAN International Conference on Functional Programming (New York, NY, USA, 2002), ICFP \u201902, ACM, pp. 36\u201347."},{"key":"e_1_3_2_1_8_1","volume-title":"Master\u2019s thesis","author":"Ford B.","year":"2002","unstructured":"Ford , B. A practical linear-time algorithm with backtracking . In Master\u2019s thesis ( 2002 ), MIT. Ford, B. A practical linear-time algorithm with backtracking. In Master\u2019s thesis (2002), MIT."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/964001.964011"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1133987"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706299.1706347"},{"key":"e_1_3_2_1_12_1","first-page":"37","volume-title":"Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering (New York, NY, USA, 2017), SLE 2017, ACM","author":"Kuramitsu K.","unstructured":"Kuramitsu , K. A symbol-based extension of parsing expression grammars and context-sensitive packrat parsing . In Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering (New York, NY, USA, 2017), SLE 2017, ACM , pp. 26\u2013 37 . Kuramitsu, K. A symbol-based extension of parsing expression grammars and context-sensitive packrat parsing. In Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering (New York, NY, USA, 2017), SLE 2017, ACM, pp. 26\u201337."},{"key":"e_1_3_2_1_13_1","first-page":"27","volume-title":"Proceedings of the 2016 ACM SIGPLAN International Conference on Software Language Engineering (New York, NY, USA, 2016), SLE 2016, ACM","author":"Laurent N.","unstructured":"Laurent , N. , and Mens , K . Taming context-sensitive languages with principled stateful parsing . In Proceedings of the 2016 ACM SIGPLAN International Conference on Software Language Engineering (New York, NY, USA, 2016), SLE 2016, ACM , pp. 15\u2013 27 . Laurent, N., and Mens, K. Taming context-sensitive languages with principled stateful parsing. In Proceedings of the 2016 ACM SIGPLAN International Conference on Software Language Engineering (New York, NY, USA, 2016), SLE 2016, ACM, pp. 15\u201327."},{"key":"e_1_3_2_1_14_1","volume-title":"lex &amp","author":"Levine J. R.","year":"1992","unstructured":"Levine , J. R. lex &amp ; yacc. O\u2019Reilly , 1992 . Levine, J. R. lex & yacc. O\u2019Reilly, 1992."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(79)90362-0"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660193.2660202"},{"key":"e_1_3_2_1_17_1","first-page":"235","volume-title":"Proceedings of the 33rd ACM\/IEEE International Conference on Automated Software Engineering (New York, NY, USA, 2018), ASE 2018, ACM","author":"Shen Y.","unstructured":"Shen , Y. , Jiang , Y. , Xu , C. , Yu , P. , Ma , X. , and Lu , J . Rescue: Crafting regular expression dos attacks . In Proceedings of the 33rd ACM\/IEEE International Conference on Automated Software Engineering (New York, NY, USA, 2018), ASE 2018, ACM , pp. 225\u2013 235 . Shen, Y., Jiang, Y., Xu, C., Yu, P., Ma, X., and Lu, J. Rescue: Crafting regular expression dos attacks. In Proceedings of the 33rd ACM\/IEEE International Conference on Automated Software Engineering (New York, NY, USA, 2018), ASE 2018, ACM, pp. 225\u2013235."},{"key":"e_1_3_2_1_18_1","volume-title":"10th USENIX Workshop on Offensive Technologies (WOOT 16)","author":"Sp\u00e4th C.","year":"2016","unstructured":"Sp\u00e4th , C. , Mainka , C. , Mladenov , V. , and Schwenk , J . Sok: XML parser vulnerabilities . In 10th USENIX Workshop on Offensive Technologies (WOOT 16) (Austin, TX, Aug. 2016 ), USENIX Association. Sp\u00e4th, C., Mainka, C., Mladenov, V., and Schwenk, J. Sok: XML parser vulnerabilities. In 10th USENIX Workshop on Offensive Technologies (WOOT 16) (Austin, TX, Aug. 2016), USENIX Association."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1188966.1188972"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1297081.1297086"}],"event":{"name":"CC '20: 29th International Conference on Compiler Construction","sponsor":["SIGPLAN ACM Special Interest Group on Programming Languages"],"location":"San Diego CA USA","acronym":"CC '20"},"container-title":["Proceedings of the 29th International Conference on Compiler Construction"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3377555.3377898","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3377555.3377898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:18Z","timestamp":1750199598000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3377555.3377898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,22]]},"references-count":20,"alternative-id":["10.1145\/3377555.3377898","10.1145\/3377555"],"URL":"https:\/\/doi.org\/10.1145\/3377555.3377898","relation":{},"subject":[],"published":{"date-parts":[[2020,2,22]]},"assertion":[{"value":"2020-02-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}