Tom*_*m O 5 theory algorithm grammar context-free-grammar
为了序言,我对这种东西的了解是微不足道的.
无论如何,我一直在开发一个无上下文的语法来描述alegbraic表达式的结构,所以我可以自学一下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之间做出决定吗？这样的语法上下文了吗？最重要的是,由于编程语言可以处理二进制和一元减号的语言,我应该如何合理地解析它？
这似乎是一个与有限状态自动机有关的问题,我不记得我的课程中的所有内容,但我在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!