SPLASH 2023
Sun 22 - Fri 27 October 2023 Cascais, Portugal
Fri 27 Oct 2023 15:12 - 15:30 at Room II - compilation and optimization 1 Chair(s): Will Crichton

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 Oct

Displayed time zone: Lisbon change

14:00 - 15:30
compilation and optimization 1OOPSLA at Room II
Chair(s): Will Crichton Brown University
14:00
18m
Talk
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
18m
Talk
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
18m
Talk
Hardware-Aware Static Optimization of Hyperdimensional Computations
OOPSLA
Pu (Luke) Yi Stanford University, Sara Achour Stanford University
DOI
14:54
18m
Talk
Rapid: Region-Based Pointer Disambiguation
OOPSLA
Khushboo Chitre IIIT Delhi, Piyus Kedia IIIT Delhi, Rahul Purandare University of Nebraska-Lincoln
DOI
15:12
18m
Talk
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