0

从以下语法中删除歧义

S −−> 如果 E 则 S | 如果 E 则 S 否则 S | 其他

4

1 回答 1

1

您可以删除 dangling-else 歧义。在“编译器：原理、技术和工具”第 2 版，第 211-212 页中有这样的语法。但是，这本书有语法，但没有解释（或者我没有找到它）。

在 ABNF 元语法中，语法是：

statement = matched / open
matched   = "if" expr "then" matched "else" matched 
          / other
open      = "if" expr "then" statement
          / "if" expr "then" matched "else" open

expr      = ...
other     = ...

它是如何工作的？

这里的想法是通过使用非确定性来避免歧义（无论如何已经提出，因为每个模棱两可的语法也是非确定性的；最后我写了关于差异，我发现（太）经常被误解） . 这意味着在成功解析后，任何输入都只有一个语法树（这意味着您要求的非歧义性）。但是您将需要一个解析器，它可以使用比确定性 LL(1) 解析器更复杂的机器。

规则matched确保子树内的每个else直接嵌套的 if 语句都具有. 换句话说，then将有一个匹配的else.

规则open确保每个子 if 语句本身没有else，或者如果它有，那么它的 else 语句open依次是。换句话说，规则open确保使用的关键字少于 else使用的 then关键字。换句话说，子树内的数量将小于else（或 s ，如果你喜欢）的数量。这与确保两者数量相等的规则形成对比。这意味着在解析器中实现的and永远不会接受相同的输入，从第一次使用 rule开始计数。thenifmatchedmatchedopenstatement

此外，由于matched "else" open在规则open中，else将“附加”到最近的if. 这在解析器识别出第一个 used之前解决了 dangling-else 歧义。statement

例子

为了说明将要发生的步骤，我升级了语法以允许更“自然”的输入。这意味着更多的标点符号和空格。首先是词法分析器：

keyword = %s"if" / %s"then" / %s"else"

它尽可能将输入字符分组，未分组的字符本身成为标记。对于输入：

if(x)then if(x)then y else y

你有这些字节： 输入字节

对于这些字节，您将拥有以下令牌： 代币

然后你有解析器语法，它允许解析器接受这些标记（区分大小写）并明确放置空格。还是可以看原版的，大体流程是一样的。解析器语法：

statement = matched / open
matched   = {keyword, %s"if"} *ws "(" *ws expr *ws ")" *ws {keyword, %s"then"} 1*ws matched {keyword, %s"else"} 1*ws matched 
          / other *ws
open      = {keyword, %s"if"} *ws "(" *ws expr *ws ")" *ws {keyword, %s"then"} 1*ws statement
          / {keyword, %s"if"} *ws "(" *ws expr *ws ")" *ws {keyword, %s"then"} 1*ws matched {keyword, %s"else"} 1*ws open

expr      = %s"x"
other     = %s"y" 
ws        = %s" "

在你开始解析之后，一个深入探索语法规则的解析机会这样执行：

  • 它将进入开始规则statement
  • 然后进入第一个引用 rule 的串联matched。
  • 它将接受具有字符的第一个令牌if(x)then
  • 然后它将再次使用该matched规则
  • 它将接受所有其他令牌，直到输入结束if(x)then y else y。
  • 然后将移出matched规则并期望其匹配else，但没有这样的，因为输入已经结束。这意味着解析器必须回去寻找另一种方式。此时，您将拥有这个（部分构造的）语法树： 中间树
  • 它将回到解析的最开始并尝试规则中的第二个连接statement，即一个引用规则open。
  • 它将按其步骤工作，并最终使用此树成功到达输入的末尾： 最终语法树
  • 那么解析机可能会继续探索更多，但不会找到任何其他语法树。

相关理论

确定性、非确定性、模糊性和非模糊性常常被误解。我想举一个例子，因为我认为写出来的内容可能对每个人都不是很清楚。

从解析器的角度来看，确定性与给定状态下可能的操作数量有关。当解析器中的所有可能状态最多可能有一个动作时，解析器是确定性的。我在很多地方都看到过这样的措辞：“语法主要是确定性的，而在少数地方是非确定性的”。这是误导性的，因为语法的确定性是基于整个语法的——更准确地说，它是最坏的确定性情况。例如，下一个语法是确定性的，当被解析器使用时，解析器也将是确定性的：

rule = "a" / "b"

非确定性意味着对于至少一个输入序列，解析器至少存在一种可能的状态，其中可能有多个动作。例如，以下语法是不确定的：

rule = "a" / "a"

显然，您可以将其重写为 justrule = "a"但这不是相同的语法。两种语法都只生成相同的语言。语法正在生成语言的有效字符串。该语言 由其有效字符串组成。解析器正在接受有效的语言字符串并拒绝无效的语言字符串。

歧义意味着输入可以以不止一种方式被识别。这反过来意味着对于至少一个有效输入可能有不止一个语法树。例如，前面的语法 ( ) 是模棱两可的，因为两个连接都有.rule = "a" / "a"a

非歧义意味着任何有效的输入都将以一种方式被识别。这反过来意味着每个有效输入都存在一个语法树。显然，对于无效输入，没有语法树。

您可能有一个非确定性和非歧义的语法，例如：

rule = "a" "b" / "a" "c"

您在输入字符规则的开头有一个不确定的选择a，但在下一个输入字符中，哪个连接是正确的连接将变得清晰。这是不可能的，在输入被完全处理后具有多个语法树：这意味着语法是无歧义的。

显然，每个确定性文法也是明确的，因为不存在可能导致第二棵树的第二个动作的状态。

此外，每一种模棱两可的语法都是非确定性的，因为为了能够拥有不止一个语法树，在某处存在一种状态，对于至少一个输入序列，该状态具有多个可能的动作。

本书语法的“窍门”是让非确定性存在（实际上是“使用”），但不让非确定性传播到规则之外statement，有效防止语法出现歧义。

现在，当解析器一次处理一个字符的输入时，所有这些都是有效的。但我不会离开这里。还有不同类型的歧义。有些你可以数，有些你不能数。但我也不会去那里。

免责声明：我使用了我开发的工具的截图和语法语法：Tunnel Grammar Studio。

于 2021-10-15T08:29:31.803 回答