Thu 19 Jan 2023 14:20 - 14:45 at Grand Ballroom A - Program Analysis & Parsing Chair(s): David Pichardie

Traditionally, a grammar defining the syntax of a programming language is typically both context free and unambiguous. However, recent work suggests that an attractive alternative is to use ambiguous grammars,thus postponing the task of resolving the ambiguity to the end user. If all programs accepted by an ambiguous grammar can be rewritten unambiguously, then the parser for the grammar is said to be resolvably ambiguous. Guaranteeing resolvable ambiguity statically—for all programs—is hard, where previous work only solves it partially using techniques based on property-based testing. In this paper, we present the first efficient, practical, and proven correct solution to the statically resolvable ambiguity problem. Our approach introduces several key ideas, including splittable productions, operator sequences, and the concept of a grouper that works in tandem with a standard parser. We prove static resolvability using a Coq mechanization and demonstrate its efficiency and practical applicability by implementing and integrating resolvable ambiguity into an essential part of the standard OCaml parser.

Thu 19 Jan

Displayed time zone: Eastern Time (US & Canada) change

13:30 - 14:45
Program Analysis & ParsingPOPL at Grand Ballroom A
Chair(s): David Pichardie Meta
13:30
25m
Talk
SSA Translation Is an Abstract InterpretationDistinguished Paper
POPL
Matthieu Lemerre Université Paris-Saclay - CEA LIST
DOI Pre-print
13:55
25m
Talk
Dynamic Race Detection with O(1) SamplesDistinguished Paper
POPL
Mosaad Al Thokair University of Illinois at Urbana-Champaign, Minjian Zhang University of Illinois at Urbana-Champaign, Umang Mathur National University of Singapore, Mahesh Viswanathan University of Illinois at Urbana-Champaign
Link to publication DOI Pre-print
14:20
25m
Talk
Statically Resolvable Ambiguity
POPL
Viktor Palmkvist KTH Royal Institute of Technology, Elias Castegren Uppsala University, Philipp Haller KTH Royal Institute of Technology, David Broman KTH Royal Institute of Technology
DOI