我使用CYK算法（已在 Java 中实现）来查看字符串是否根据特定语法进行识别。现在我需要为字符串生成一个解析树，是一种从使用算法时使用的矩阵生成树的方法吗CYK？
我正在阅读有关CYK算法的内容,并且有一部分我无法理解的伪代码.整个伪代码是:
let the input be a string S consisting of n characters: a1 ... an.
let the grammar contain r nonterminal symbols R1 ... Rr.
This grammar contains the subset Rs which is the set of start symbols.
let P[n,n,r] be an array of booleans. Initialize all elements of P to false.
for each i = 1 to n
for each unit production Rj -> ai
set P[i,1,j] = true
for each i = 2 to n -- …我开始学习Erlang，并且作为练习，我尝试实现CYK算法。
主要代码（cyk.erl）：
%%% An attempt for a CYK parser in Erlang
-module(cyk).
-export([
init_storage/0,
import_grammar_file/1,
add_grammar_rule/1,
analyze/1,
test_analyze/0
]).
%% Initialize the ets storage for grammar
init_storage() ->
ets:new(?MODULE, [bag, named_table]).
%%------------------------------------------
%%
%% Grammar
%%
%%------------------------------------------
%% Import a grammar file
import_grammar_file(File) ->
{ok, Device} = file:open(File, read),
import_file_rules(Device).
%% Import all the rules in the file
import_file_rules(Device) ->
case io:get_line(Device, "") of
eof ->
io:format("Grammar file imported~n"),
file:close(Device);
Line ->
add_grammar_rule(Line),
import_file_rules(Device)
end.
%% Add a …我必须检查字符串是否可以从 Chomsky 范式的给定上下文中派生出来。我正在使用 C++。
维基百科文章上有很好的伪代码，介绍了 CYK 算法，但我不太明白。
有人会通过给我另一个 CYK 算法的伪代码来帮助我，或者在 wiki 文章中解释那个？
我已经阅读了许多地方,CYK/CKY算法要求语法采用乔姆斯基范式(CNF),例如
标准版本的CYK仅在Chomsky normal form(CNF)~ Wikipedia中给出的无上下文语法中运行
但是,我也看到了一些CKY算法的例子,其中语法不在CNF中.克里斯托弗·曼宁使用的一个常见例子是"鱼人鱼缸"(参考:PPT幻灯片#19),其中包含一元规则:
S -> NP VP [0.9]
S -> VP [0.1]
VP -> V NP [0.4]
Vp -> V [0.6]
...
我还看到了其他证明CKY在生产的RHS中使用三个非终端的例子(例如VP -> Verb NP NP 参考).为什么会出现差异？
我目前正在做一个涉及NLP的项目。我已经实现了 Jurafsky 和 Martin（第 450 页的算法）中给出的 CKY 标识符。如此生成的表实际上将非终结符存储在表中（而不是通常的布尔值）。然而，我遇到的唯一问题是检索解析树。
下面是我的 CKY 标识符的作用的说明：
这是我的语法
S -> NP VP
S -> VP
NP -> MODAL PRON | DET NP | NOUN VF | NOUN | DET NOUN | DET FILENAME
MODAL -> 'MD'
PRON -> 'PPSS' | 'PPO'
VP -> VERB NP
VP -> VERB VP
VP -> ADVERB VP
VP -> VF
VERB -> 'VB' | 'VBN'
NOUN -> 'NN' | 'NP'
VF -> VERB FILENAME
FILENAME -> 'NN' | 'NP'
ADVERB …