Attribute grammars allow the association of semantic actions to the production rules in context-free grammars, providing a simple yet effective formalism to define the semantics of a language. However, drafting the semantic actions can be tricky and a large drain on developer time. In this work, we propose a synthesis methodology to automatically infer the semantic actions from a set of examples associating strings to their meanings. We also propose a new coverage metric, derivation coverage. We use it to build a sampler to effectively and automatically draw strings to drive the synthesis engine. We build our ideas into our tool, PANINI, and empirically evaluate it on twelve benchmarks, including a forward differentiation engine, an interpreter over a subset of Java bytecode, and a mini-compiler for C language to two-address code. Our results show that PANINI scales well with the number of actions to be synthesized and the size of the context-free grammar, significantly outperforming simple baselines.
翻译:属性语法允许将语义行动与无上下文语法中的生产规则联系起来,为定义一种语言的语义提供了简单而有效的形式主义。 但是, 起草语义行动可能会很棘手, 开发者的时间会耗费大量时间。 在这项工作中, 我们提出了一个综合方法, 从一组将字符串与其含义相联系的示例中自动推断出语义行动。 我们还提出了一个新的覆盖度, 引出覆盖范围。 我们用它来建立一个取样器, 以有效和自动地绘制字符串来驱动合成引擎。 我们把我们的想法建在工具PANNINI中, 并用12个基准对它进行实证性评估, 包括一个前方差异化引擎、 Java 字码组的翻译以及 C 语言对双方码的微型拼写器。 我们的结果显示, PANNI 与要合成的行动数量和无上下文语法的大小相比, 大大超过简单基准。