algorithm - 这是一个有歧义的语法吗？我该如何解决？

Question

首先，我对这类东西的了解微不足道。

无论如何，我一直在开发一种上下文无关语法来描述代数表达式的结构，这样我就可以自学 CYK 解析算法的工作原理。我明白这样的结构如何只与中缀代数表达式一起工作，但我不明白如何开发一种语法来处理“-”运算符的一元和二元定义。

作为引用，这是我在 CNF 中编写的语法(其中 S 是开始符号):

S -> x
A -> O S
S -> L B
B -> S R
S -> K S
O -> +
O -> -
O -> *
O ->/
O -> ^
K -> -
大号 -> (
R -> )

问题是，CYK解析算法在遇到“-”运算符时，如何提前知道是在S -> K S还是A -> O S之间做出选择呢？这样的语法不再是上下文无关的了吗？最重要的是，由于编程语言可以处理带有二进制和一元负号的语言，我应该如何合理地解析它？

Answer 1

这似乎是一个与有限状态自动机相关的问题，我不记得我类(class)作业中的所有内容，但我用 OCaml 编写了一个 CYK 解析器，所以我会继续尝试 :)

例如，如果您尝试解析像 3- -4 这样的表达式，您可以让 S -> K S 规则使用 -4 然后您的 A -> O S 规则将吸收 - -4。这最终将适用于最顶层的 S 生产规则。你应该小心你正在使用的语法，因为你列出的 A 生产规则无法从 S 达到，你应该有一个 S -> S O S 某种规则。

CYK 解析算法的工作方式是通过回溯，而不是通过您在问题中提到的“提前知道”。你的 CYK 算法应该做的是将 -4 解析为 S -> K S 规则，然后它会尝试吸收第二个 -再次使用 S -> K S 规则，因为此产生式规则允许任意长的一元 - 链。但是一旦您的算法意识到它卡在了中间解析 3 S 上，它就会意识到它没有可用于解析它的生产符号。一旦它意识到这不再是可解析的，它将返回并尝试将 - 解析为 S -> O S 规则并继续其愉快的方式。

这意味着您的语法保持上下文无关，因为上下文相关语法意味着您在产生式规则的左侧有终端，所以您在这方面做得很好。 HTH!