5

作为序言，我对这类东西的了解是微不足道的。

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

作为参考，这是我在 CNF 中编写的语法（其中 S 是开始符号）：

S -> x
A -> OS
S -> LB
B -> SR
S -> KS
O -> +
O -> -
O -> *
O -> /
O -> ^
K -> -
L -> (
R - > )

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

4

3 回答 3

5

这似乎是一个与有限状态自动机有关的问题，我不记得我的课程中的所有内容，但我在 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规则吸收第二个，因为该生产规则允许任意长的 unary 链-。但是一旦你的算法意识到它被中间 parse 卡住了3 S，它就会意识到它没有可以用来解析它的生产符号。一旦它意识到这不再是可解析的，它将返回并尝试将其解析-为S -> O S规则并继续其愉快的方式。

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

于 2010-06-26T03:13:15.220 回答
2

语法不明确，解析器无法决定采用哪种情况。

您可能应该使用如下语法：

S -> EXPR
EXPR -> (EXPR)
EXPR -> - EXPR
EXPR -> EXPR + EXPR
EXPR -> EXPR - EXPR
// etc...
于 2010-06-26T01:50:45.313 回答
1

基于代数表达式的语法很难消除歧义。以下是一些需要解决的问题示例：

a+b+c 自然地创建了两个解析树。要解决这个问题，您需要解决 + 的关联性的歧义。您可能希望让从左到右的解析策略为您解决这个问题，但要小心：求幂可能应该从右到左关联。

a+b*c 自然地创建了两个解析树。要解决此问题，您需要处理运算符优先级。

如果允许，隐式乘法 (a+bc) 会产生各种噩梦，主要是在标记化时。

正如你提到的，一元减法是有问题的。

如果我们想解决这些问题，但仍然有一个专门用于代数的快速解析语法，一种方法是拥有 EXPR 的各种“级别”，一个用于优先级别所需的每个绑定级别。例如，

TERM -> (S)
EXPO -> TERM ^ EXPO
PROD -> PROD * EXPO
PROD -> PROD / EXPO
PROD -> -PROD
SUM -> SUM + PROD
SUM -> SUM - PROD
S -> SUM

这要求您还允许“提升”类型：SUM -> PROD、PROD -> EXP、EXP -> TERM 等，以便事情可以终止。

希望这可以帮助！

于 2010-06-26T04:54:02.963 回答