Figuring out grammars from examples

John R Levine <>
Fri, 12 Apr 2024 18:39:51 -0400

          From comp.compilers

Related articles
Figuring out grammars from examples (John R Levine) (2024-04-12)
Re: Figuring out grammars from examples (Derek) (2024-04-13)
Re: Figuring out grammars from examples (Derek) (2024-04-15)
| List of all articles for this month |

From: John R Levine <>
Newsgroups: comp.compilers
Date: Fri, 12 Apr 2024 18:39:51 -0400
Organization: Compilers Central
Injection-Info:; posting-host=""; logging-data="68172"; mail-complaints-to=""
Keywords: parse
Posted-Date: 12 Apr 2024 18:48:31 EDT

There's been a surprising amount of work on taking language strings and
feeding them to a box that infers a grammar for them. One of the harder
bits is figuring out nesting constructs, which in the past has often
required hints.

In this paper, a Visibly Pushdown Grammar is large but more tractable
subset of context free grammars.

V-Star: Learning Visibly Pushdown Grammars from Program Inputs
Xiaodong Jia, Gang Tan

Accurate description of program inputs remains a critical challenge in the
field of programming languages. Active learning, as a well-established
field, achieves exact learning for regular languages. We offer an
innovative grammar inference tool, V-Star, based on the active learning of
visibly pushdown automata. V-Star deduces nesting structures of program
input languages from sample inputs, employing a novel inference mechanism
based on nested patterns. This mechanism identifies token boundaries and
converts languages such as XML documents into VPLs. We then adapted
Angluin's L-Star, an exact learning algorithm, for VPA learning, which
improves the precision of our tool. Our evaluation demonstrates that
V-Star effectively and efficiently learns a variety of practical grammars,
including S-Expressions, JSON, and XML, and outperforms other
state-of-the-art tools.

John Levine,, Taughannock Networks, Trumansburg NY
Please consider the environment before reading this e-mail.

Post a followup to this message

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