2

我知道有一种形式主义叫属性语法，还有一种非形式主义方法叫句法导向翻译，但前者效率低，后者难以自动化。

最近是否存在其他关于语义分析的形式主义？

4

1 回答 1

1

OP 认为“属性语法”效率低下，语法导向翻译难以自动化。我在下面提供了一个证明点，列举了一些其他语义系统，并建议了它们如何集成。

我们的DMS 软件再造工具包支持这两种活动以及更多。

它为完整的上下文无关文法提供解析器，并能够定义、编译和执行具有任意数据和操作的并行属性文法，以及跨语法节点的任意流。可以使用此类属性语法计算度量、构建符号表或计算语义分析。

给定一个（DMS）语法规则：

  LHS = RHS1 ... RHSN ;

为命名属性文法计算Pass1编写 DMS 属性文法规则（出于实际原因，可以有许多不同的通行证，有些甚至构建彼此的结果），格式如下：

  <<Pass1>>:  {  LHS.propertyI=fn1(RHSx.propertyY,...);
                 ...
                 RHSa.propertyB=fn2(RHSp.propertyQ,...);
                 ...
              }

对于与每个语法元素相关联的一组（任意类型）属性，在语法规则的左侧或右侧，使用在所涉及的类型上定义的任意函数fnI，在 DMS 的底层（并行）语言 PARLANSE 中实现。DMS 跨规则集计算数据流，并确定实现计算的偏序（并行）计算，并将其编译为 PARLANSE 代码以供执行。属性计算的结果是用计算的属性装饰的树。

小心，曾经应该能够定义由属性文法计算的语言的指称语义。DS 中的关键概念之一是“环境”，它将标识符映射到类型和可能的符号值。（前者传统上称为符号表）。在引入新范围的 AST 节点上，可以编写一个属性函数，通过将父环境与新引入的标识符组合来创建一个新环境，并将其从 AST 节点向下传递给它的子节点，例如，对于规则

exp = 'let' ID '=' exp1 'in' exp2;

可以编写属性语法规则：

<<Denotation>>: {
     exp2.env = augment_environment(exp.env,
                                    new_variable_and_value_pair(name(ID.),
                                                                exp1.value));
     exp.value=exp2.value;
               }

我不确定 OP 所说的（属性语法是）“低效”是什么意思。 我们已经使用 DMS 属性语法来计算所有C++14 的语义属性（名称和类型解析）。虽然从大多数学术论文标准来看，这样的定义是巨大的，但之所以如此，是因为 C++14 本身是巨大的，而且是一团糟（“委员会的骆驼”）。尽管如此，我们的属性语法似乎运行得很好。更重要的是，它的强大足以让一个非常小的团队来构建它（与支持 Clang 的“团队”的规模相比）。

DMS 还提供了使用源语言和目标语言（如果与源语言不同）的表面语法对源到源转换（“重写”）进行编码的能力，形式为“如果你看到这个，用那个替换它” . 这些重写应用于解析树以提供修改后的树；DMS 提供的漂亮打印机（“反解析器”）然后可以重新生成目标语言的源代码。如果一个人限制自己重写那个与原始 AST 完全相同的内容，那么就会得到“语法导向的翻译”。 OP 可能声称这（语法定向翻译）难以自动化；我同意，但工作已经完成并且可用。 OP 确实必须决定她想要定义和执行哪些规则。

DMS 重写规则采用以下形式：

 rule rule_name(parameter1:syntax_category1, ... parameterN...)
   :  source_syntax_category -> target_syntax_category
   "  <text in source language>  "
  ->
   "  <text in target language> "
  if  condition_of_matched_source_pattern;

其中参数是语法类型子树的占位符，规则映射类型为 source_syntax_category -> target_syntax_category 的树（通常相同），并且“...”是用“\”标记的表面语法包裹的元引号在需要时为参数嵌入转义。元引用的代码片段被解释为树的规范（使用读取源代码的相同解析引擎）；这不是字符串匹配。一个例子：

  rule simplify_if_then_else(c:condition,t:then_clause,e:else_clause)
     statement->statement
  =  " if \c then \t else \e "
  -> " \t "
  if c == "true";

更“语义”的（在纯句法之上）检查的概括将是

  ...
  if can_determine_is_true(c);

它假定自定义谓词咨询其他 DMS 可派生结果以确定实例化条件在找到它的点始终为真（匹配的树 c 带有其源位置，因此隐含上下文）。可以为所需语言构建控制和数据流，并使用生成的数据流来确定到达条件 c 的值，然后这可能总是以一种非平凡的方式证明是“真”的。

我假设了一个 DMS 定义的支持谓词“can_determine_if_true”。这只是一些自定义的 PARLANSE 代码。

但是，由于重写将一棵树转换为另一棵树，因此可以将任意长/复杂的一组转换规则重复应用于整个树。这使 DMS 重写了 Post（字符串 [泛化为树]）重写系统的功能，因此具有图灵能力。从技术上讲，您可以使用足够的变换对原始树进行任意变换。通常使用 DMS 的其他功能来简化转换的编写；例如，重写规则可以参考特定属性语法计算的结果，以便“轻松”使用来自“树中远处”的信息（各个重写规则始终具有固定的最大“半径”）。

DMS 提供了许多额外的支持机制，以帮助构建控制流图和/或使用高效的并行求解器计算数据流。DMS 还具有适用于各种语言（例如 C、C++14、Java1.8、IBM Enterprise COBOL 等）的各种可用前端，以便工具工程师可以专注于构建她想要的工具，而不是努力从头开始构建解析器（只是发现一个人必须在解析后生活）。

如果 OP 对最近对另一种（结构化操作）语义的概述感兴趣，他可能会查阅 Semantics of Programming Languages 的课程笔记。我们声称，如果愿意，这些论文中的技术可以在 DMS 之上实现。

人们可以列出一长串实现（某些）这些想法的各种学术工具。其中大部分是研究工具，并不成熟。一个这样的研究系统，JastAdd是一个属性语法评估系统，我听说它在能力和性能方面很突出，但我没有具体的经验。

于 2015-01-15T08:05:21.407 回答