grammar - 我怎样才能证明这个语法是模棱两可的？

Question

我想证明这个语法是模棱两可的，但我不确定我应该怎么做。我必须使用解析树吗？

  S -> if E then S | if E then S else S | begin S L | print E
  L -> end | ; S L
  E -> i

Answer 1

如果你能找到一个解析不止一种方式的字符串，你可以证明它是模棱两可的：

if i then ( if i then print i   else print i ; )
if i then ( if i then print i ) else print i ;

这恰好是经典的“悬而未决”的歧义。谷歌搜索你的标签、标题和语法会得到其他结果。

但是，如果您没有碰巧猜到一个模棱两可的字符串，那么使用谷歌搜索您的标签和标题：

我怎样才能证明这个语法是模棱两可的？

没有简单的方法可以证明上下文无关文法的歧义——事实上， 通过简化为Post 对应问题，这个问题是不可判定的。

Answer 2

您可以将语法放入支持所有上下文无关语法的解析器生成器，一个上下文无关的通用解析器生成器。生成解析器，然后解析一个您认为不明确的字符串，并通过查看解析器的输出来找出答案。

无上下文的通用解析器生成器生成在多项式时间内产生所有推导的解析器。这种解析器生成器的示例包括 SDF2、Rascal、DMS、Elkhound、ART。还有一个 yacc (btyacc) 的回溯版本，但我认为它不会在多项式时间内完成。通常输出被编码为一个图，其中子句的替代树用一组嵌套的替代树编码。