Reproduce “Inferring Attributed Grammars from Parser Implementations” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Andreas Pointner, Josef Pichler, Herbert Prähofer

Researchers from Austrian universities developed a method to automatically infer attributed grammars from recursive descent parser implementations. This approach uses dynamic analysis and tree mapping to extract semantic actions directly from program code, embedding them into corresponding syntactic grammar rules to generate comprehensive, executable specifications. Preliminary evaluations showed 100% accuracy for four out of seven parser examples in replicating the original program's output.

Key insights

  • Attributed grammars offer a robust formalism for unifying both syntactic structure and semantic processing into a single, executable specification of a parser's behavior.
  • Dynamic analysis of program execution, combined with systematic mapping of runtime observations to grammar elements, can effectively expose and capture the implicit semantic actions within imperative parser code.
  • The systematic transfer of code segments identified as semantic actions into the appropriate grammar rule positions enables comprehensive specification recovery from existing implementations.
  • Input generation guided by coverage strategies is essential to adequately exercise grammar rules and ensure sufficient observations for accurate semantic action extraction.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.