{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T23:04:04Z","timestamp":1784675044166,"version":"3.55.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","license":[{"start":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T00:00:00Z","timestamp":1697414400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62072267, 62021002"],"award-info":[{"award-number":["62072267, 62021002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62072267, 62021002"],"award-info":[{"award-number":["62072267, 62021002"]}],"id":[{"id":"10.13039\/501100001809","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":[[2023,10,16]]},"abstract":"<jats:p>\n            Layout-sensitive grammars have been adopted in many modern programming languages.  \nIn a serious language design phase, the specified syntax\u2014typically a grammar\u2014must be unambiguous.  \nAlthough checking ambiguity is undecidable for context-free grammars and (trivially also) layout-sensitive grammars,\n            <jats:italic>ambiguity detection<\/jats:italic>\n            , on the other hand, is possible and can benefit language designers from\n            <jats:italic>exposing potential design flaws<\/jats:italic>\n            .  \n  \nIn this paper, we tackle the ambiguity detection problem in layout-sensitive grammars.  \nInspired by a previous work on checking the\n            <jats:italic>bounded ambiguity<\/jats:italic>\n            of context-free grammars via\n            <jats:italic>SAT solving<\/jats:italic>\n            , we intensively extend their approach to support layout-sensitive grammars but via\n            <jats:italic>SMT solving<\/jats:italic>\n            to express the ordering and quantitative relations over line\/column numbers.  \nOur key novelty lies in a\n            <jats:italic>reachability<\/jats:italic>\n            condition, which takes the impact of layout constraints on ambiguity into careful account.  \nWith this condition in hand, we propose an equivalent ambiguity notion called\n            <jats:italic>local ambiguity<\/jats:italic>\n            for the convenience of SMT encoding.  \nWe translate local ambiguity into an SMT formula and developed a\n            <jats:italic>bounded ambiguity checker<\/jats:italic>\n            that\n            <jats:italic>automatically<\/jats:italic>\n            finds a\n            <jats:italic>shortest<\/jats:italic>\n            nonempty ambiguous sentence (if exists) for a user-input grammar.  \nThe\n            <jats:italic>soundness<\/jats:italic>\n            and\n            <jats:italic>completeness<\/jats:italic>\n            of our SMT encoding are mechanized in the Coq proof assistant.  \nWe conducted an evaluation on both grammar fragments and\n            <jats:italic>full<\/jats:italic>\n            grammars extracted from the language manuals of domain-specific languages like YAML as well as general-purpose languages like Python, which reveals the effectiveness of our approach.\n          <\/jats:p>","DOI":"10.1145\/3622838","type":"journal-article","created":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T15:41:29Z","timestamp":1697470889000},"page":"1150-1175","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Automated Ambiguity Detection in Layout-Sensitive Grammars"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6525-4659","authenticated-orcid":false,"given":"Jiangyi","family":"Liu","sequence":"first","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4219-0837","authenticated-orcid":false,"given":"Fengmin","family":"Zhu","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China \/ CISPA Helmholtz Center for Information Security, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4266-875X","authenticated-orcid":false,"given":"Fei","family":"He","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,10,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429069.2429129"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814228.2814242"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892234"},{"key":"e_1_2_1_4_1","volume-title":"Compilers: Principles, Techniques, and Tools. Addison wesley, 7, 8","author":"Aho Alfred V","year":"1986","unstructured":"Alfred V Aho , Ravi Sethi , and Jeffrey D Ullman . 1986 . Compilers: Principles, Techniques, and Tools. Addison wesley, 7, 8 (1986), 9. Alfred V Aho, Ravi Sethi, and Jeffrey D Ullman. 1986. Compilers: Principles, Techniques, and Tools. Addison wesley, 7, 8 (1986), 9."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276604.3276607"},{"key":"e_1_2_1_6_1","volume-title":"Analyzing Context-Free Grammars Using an Incremental SAT Solver","author":"Axelsson Roland","unstructured":"Roland Axelsson , Keijo Heljanko , and Martin Lange . 2008. Analyzing Context-Free Grammars Using an Incremental SAT Solver . In Automata, Languages and Programming, Luca Aceto, Ivan Damg\u00e5rd, Leslie Ann Goldberg, Magn\u00fas M. Halld\u00f3rsson, Anna Ing\u00f3lfsd\u00f3ttir, and Igor Walukiewicz (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg . 410\u2013422. isbn:978-3-540-70583-3 Roland Axelsson, Keijo Heljanko, and Martin Lange. 2008. Analyzing Context-Free Grammars Using an Incremental SAT Solver. In Automata, Languages and Programming, Luca Aceto, Ivan Damg\u00e5rd, Leslie Ann Goldberg, Magn\u00fas M. Halld\u00f3rsson, Anna Ing\u00f3lfsd\u00f3ttir, and Igor Walukiewicz (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 410\u2013422. isbn:978-3-540-70583-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062349"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53132-7_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983990.2984026"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_2_1_11_1","volume-title":"Studies in Logic and the Foundations of Mathematics. 35","author":"Chomsky N","unstructured":"N Chomsky and MP Sch\u00fctzenberger . 1963. The Algebraic Theory of Context-Free Languages . In Studies in Logic and the Foundations of Mathematics. 35 , Elsevier , 118\u2013161. N Chomsky and MP Sch\u00fctzenberger. 1963. The Algebraic Theory of Context-Free Languages. In Studies in Logic and the Foundations of Mathematics. 35, Elsevier, 118\u2013161."},{"key":"e_1_2_1_12_1","unstructured":"Chris Coyier. 2012. https:\/\/css-tricks.com\/poll-results-popularity-of-css-preprocessors\/ \t\t\t\t  Chris Coyier. 2012. https:\/\/css-tricks.com\/poll-results-popularity-of-css-preprocessors\/"},{"key":"e_1_2_1_13_1","volume-title":"Layout-Sensitive Generalized Parsing","author":"Erdweg Sebastian","unstructured":"Sebastian Erdweg , Tillmann Rendel , Christian K\u00e4stner , and Klaus Ostermann . 2013. Layout-Sensitive Generalized Parsing . In Software Language Engineering, Krzysztof Czarnecki and G\u00f6rel Hedin (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg . 244\u2013263. isbn:978-3-642-36089-3 Sebastian Erdweg, Tillmann Rendel, Christian K\u00e4stner, and Klaus Ostermann. 2013. Layout-Sensitive Generalized Parsing. In Software Language Engineering, Krzysztof Czarnecki and G\u00f6rel Hedin (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 244\u2013263. isbn:978-3-642-36089-3"},{"key":"e_1_2_1_14_1","volume-title":"Yaml: Yaml ain\u2019t markup language.","author":"Evans Clark C","year":"2014","unstructured":"Clark C Evans . 2014 . Yaml: Yaml ain\u2019t markup language. Clark C Evans. 2014. Yaml: Yaml ain\u2019t markup language."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375607"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE43902.2021.00070"},{"key":"e_1_2_1_17_1","volume-title":"Markdown: Syntax. URL http:\/\/daringfireball.net\/projects\/markdown\/syntax. Retrieved on June, 24","author":"Gruber John","year":"2012","unstructured":"John Gruber . 2012 . Markdown: Syntax. URL http:\/\/daringfireball.net\/projects\/markdown\/syntax. Retrieved on June, 24 (2012), 640. John Gruber. 2012. Markdown: Syntax. URL http:\/\/daringfireball.net\/projects\/markdown\/syntax. Retrieved on June, 24 (2012), 640."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1926385.1926423"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2362793.2362831"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/568438.568455"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1706299.1706347"},{"key":"e_1_2_1_22_1","volume-title":"Proc. ASMICS Workshop on Parsing Theory. 1\u201320","author":"Klint Paul","year":"1994","unstructured":"Paul Klint and Eelco Visser . 1994 . Using filters for the disambiguation of context-free grammars . In Proc. ASMICS Workshop on Parsing Theory. 1\u201320 . Paul Klint and Eelco Visser. 1994. Using filters for the disambiguation of context-free grammars. In Proc. ASMICS Workshop on Parsing Theory. 1\u201320."},{"key":"e_1_2_1_23_1","volume-title":"On the translation of languages from left to right. Information and control, 8, 6","author":"Knuth Donald E","year":"1965","unstructured":"Donald E Knuth . 1965. On the translation of languages from left to right. Information and control, 8, 6 ( 1965 ), 607\u2013639. Donald E Knuth. 1965. On the translation of languages from left to right. Information and control, 8, 6 (1965), 607\u2013639."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/365230.365257"},{"key":"e_1_2_1_25_1","first-page":"1","article-title":"To CNF or not to CNF? An efficient yet presentable version of the CYK algorithm","volume":"8","author":"Lange Martin","year":"2009","unstructured":"Martin Lange and Hans Lei\u00df . 2009 . To CNF or not to CNF? An efficient yet presentable version of the CYK algorithm . Informatica Didactica , 8 , 2009 (2009), 1 \u2013 21 . Martin Lange and Hans Lei\u00df. 2009. To CNF or not to CNF? An efficient yet presentable version of the CYK algorithm. Informatica Didactica, 8, 2009 (2009), 1\u201321.","journal-title":"Informatica Didactica"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738002"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1085130.1085132"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814304"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321631.1321653"},{"key":"e_1_2_1_30_1","volume-title":"Haskell 2010 language report. Available online http:\/\/www.haskell.org\/(May","author":"Marlow Simon","year":"2011","unstructured":"Simon Marlow . 2010. Haskell 2010 language report. Available online http:\/\/www.haskell.org\/(May 2011 ). Simon Marlow. 2010. Haskell 2010 language report. Available online http:\/\/www.haskell.org\/(May 2011)."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314651"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/952532.952740"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858965.2814310"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3540250.3549139"},{"key":"e_1_2_1_35_1","unstructured":"Don Syme Luke Hoban Tao Liu Dmitry Lomov James Margetson Brian McNamara Joe Pamer Penny Orwick Daniel Quirk and Chris Smith. 2010. The F# 2.0 language specification. Microsoft August. \t\t\t\t  Don Syme Luke Hoban Tao Liu Dmitry Lomov James Margetson Brian McNamara Joe Pamer Penny Orwick Daniel Quirk and Chris Smith. 2010. The F# 2.0 language specification. Microsoft August."},{"key":"e_1_2_1_36_1","series-title":"SIAM journal on computing, 1, 2","volume-title":"Depth-first search and linear graph algorithms","author":"Tarjan Robert","year":"1972","unstructured":"Robert Tarjan . 1972. Depth-first search and linear graph algorithms . SIAM journal on computing, 1, 2 ( 1972 ), 146\u2013160. Robert Tarjan. 1972. Depth-first search and linear graph algorithms. SIAM journal on computing, 1, 2 (1972), 146\u2013160."},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1007\/BF03036460","article-title":"Disambiguating grammars by exclusion of sub-parse trees","volume":"33","author":"Thorup Mikkel","year":"1996","unstructured":"Mikkel Thorup . 1996 . Disambiguating grammars by exclusion of sub-parse trees . Acta Informatica , 33 , 6 (1996), 511 \u2013 522 . Mikkel Thorup. 1996. Disambiguating grammars by exclusion of sub-parse trees. Acta Informatica, 33, 6 (1996), 511\u2013522.","journal-title":"Acta Informatica"},{"key":"e_1_2_1_38_1","volume-title":"The python language reference manual","author":"Rossum Guido Van","unstructured":"Guido Van Rossum and Fred L Drake . 2011. The python language reference manual . Network Theory Ltd .. Guido Van Rossum and Fred L Drake. 2011. The python language reference manual. Network Theory Ltd.."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-02654-1_9"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993532"},{"key":"e_1_2_1_41_1","volume-title":"Recognition and parsing of context-free languages in time n3. Information and control, 10, 2","author":"Younger Daniel H","year":"1967","unstructured":"Daniel H Younger . 1967. Recognition and parsing of context-free languages in time n3. Information and control, 10, 2 ( 1967 ), 189\u2013208. Daniel H Younger. 1967. Recognition and parsing of context-free languages in time n3. Information and control, 10, 2 (1967), 189\u2013208."},{"key":"e_1_2_1_42_1","unstructured":"Andreas Zeller Rahul Gopinath Marcel B\u00f6hme Gordon Fraser and Christian Holler. 2019. The fuzzing book. \t\t\t\t  Andreas Zeller Rahul Gopinath Marcel B\u00f6hme Gordon Fraser and Christian Holler. 2019. The fuzzing book."},{"key":"e_1_2_1_43_1","unstructured":"Fengmin Zhu and Jiangyi Liu. 2023. Artifact of paper \"Automated Ambiguity Detection in Layout-Sensitive Grammars\". https:\/\/archive.softwareheritage.org\/swh:1:rev:6a08a4b9a6321aeb44d5bde19c1a62dd4e5fd2a2;origin=https:\/\/github.com\/lay-it-out\/OOPSLA23-Artifact;visit=swh:1:snp:2135b15883c8028549ce5a460c745b782bdc2544 \t\t\t\t  Fengmin Zhu and Jiangyi Liu. 2023. Artifact of paper \"Automated Ambiguity Detection in Layout-Sensitive Grammars\". https:\/\/archive.softwareheritage.org\/swh:1:rev:6a08a4b9a6321aeb44d5bde19c1a62dd4e5fd2a2;origin=https:\/\/github.com\/lay-it-out\/OOPSLA23-Artifact;visit=swh:1:snp:2135b15883c8028549ce5a460c745b782bdc2544"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.8329981"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3622838","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3622838","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:04Z","timestamp":1750178224000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3622838"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,16]]},"references-count":44,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2023,10,16]]}},"alternative-id":["10.1145\/3622838"],"URL":"https:\/\/doi.org\/10.1145\/3622838","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,16]]},"assertion":[{"value":"2023-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}