Paper: Grammar Repair with Examples and Tree Automata

A tool that helps fix ambiguous grammars


Abstract


Context-free grammars (CFGs) are the de-facto formalism for declaratively
describing concrete syntax for programming languages and generating
parsers. One of the major challenges in defining a desired syntax is
ruling out all possible ambiguities in the CFG productions that determine
scoping rules as well as operator precedence and associativity. Practical
tools for parser generation typically apply ad-hoc approaches for
resolving such ambiguities, which might result in a parser's behavior that
contradicts the intents of the language designer. In this work, we present
a user-friendly approach to soundly repair grammars with ambiguities,
which is inspired by the programming by example line of research in
automated program synthesis. At the heart of our approach is the
interpretation of both the initial CFG and additional examples that define
the desired restrictions in precedence and associativity, as tree automata
(TAs). The technical novelties of our approach are (1) a new TA learning
algorithm that constructs an automaton based on the original grammar and
examples that encode the user's preferred ways of resolving ambiguities
all in a single TA, and (2) an efficient algorithm for TA intersection
that utilises reachability analysis and optimizations that significantly
reduce the size of the resulting automaton, which results in idiomatic
CFGs amenable to parser generators. We have proven the soundness of the
algorithms, and implemented our approach in a tool called Greta,
demonstrating its effectiveness on a series of case studies.


https://arxiv.org/abs/2602.18166


Regards,
John Levine, johnl@taugh.com, Taughannock Networks, Trumansburg NY
Please consider the environment before reading this e-mail. https://jl.ly

Return to the comp.compilers page.
Search the comp.compilers archives again.