Layout-sensitive grammars have been adopted in many modern programming languages.
In a serious language design phase, the specified syntax—typically a grammar—must be unambiguous.
Although checking ambiguity is undecidable for context-free grammars and (trivially also) layout-sensitive grammars, <i>ambiguity detection</i>, on the other hand, is possible and can benefit language designers from <i>exposing potential design flaws</i>.
In this paper, we tackle the ambiguity detection problem in layout-sensitive grammars.
Inspired by a previous work on checking the <i>bounded ambiguity</i> of context-free grammars via <i>SAT solving</i>, we intensively extend their approach to support layout-sensitive grammars but via <i>SMT solving</i> to express the ordering and quantitative relations over line/column numbers.
Our key novelty lies in a <i>reachability</i> condition, which takes the impact of layout constraints on ambiguity into careful account.
With this condition in hand, we propose an equivalent ambiguity notion called <i>local ambiguity</i> for the convenience of SMT encoding.
We translate local ambiguity into an SMT formula and developed a <i>bounded ambiguity checker</i> that <i>automatically</i> finds a <i>shortest</i> nonempty ambiguous sentence (if exists) for a user-input grammar.
The <i>soundness</i> and <i>completeness</i> of our SMT encoding are mechanized in the Coq proof assistant.
We conducted an evaluation on both grammar fragments and <i>full</i> 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.
Fri 27 OctDisplayed time zone: Lisbon change
14:00 - 15:30 | |||
14:00 18mTalk | Formally Verifying Optimizations with Block Simulations OOPSLA Léo Gourdin Université Grenoble Alpes - CNRS - Grenoble INP - Verimag, Benjamin Bonneau Université Grenoble Alpes - CNRS - Grenoble INP - Verimag, Sylvain Boulmé Université Grenoble Alpes - CNRS - Grenoble INP - Verimag, David Monniaux Université Grenoble Alpes - CNRS - Grenoble INP - Verimag, Alexandre Bérard Université Grenoble Alpes - CNRS - Grenoble INP - Verimag DOI Pre-print | ||
14:18 18mTalk | Back to Direct Style: Typed and Tight OOPSLA Marius Müller University of Tübingen, Philipp Schuster University of Tübingen, Jonathan Immanuel Brachthäuser University of Tübingen, Klaus Ostermann University of Tübingen DOI Pre-print | ||
14:36 18mTalk | Hardware-Aware Static Optimization of Hyperdimensional Computations OOPSLA DOI | ||
14:54 18mTalk | Rapid: Region-Based Pointer Disambiguation OOPSLA DOI | ||
15:12 18mTalk | Automated Ambiguity Detection in Layout-Sensitive Grammars OOPSLA Jiangyi Liu Tsinghua University, Fengmin Zhu CISPA - Helmholtz Center for Information Security, Fei He Tsinghua University DOI Pre-print |