|
#!/usr/bin/perl
use strict;
use warnings;
my %P; #用来存储规则库
my %V; #用来存储填表过程中所产生的每个格子里的规则
my $i; #普通变量
my $k; #表示句子结构的划分处
my $j; #普通变量
my @words; #存放将被作句法剖析的句子，数组的每个元素依次为句子里的单词
my $cache; #普通变量
my $cache1; #普通变量
my $cache2; #普通变量
my @line; #普通数组
my $n; #表示句子长度，即单词数，目的仅仅是为了方便书写
my $tree; #用在子函数Tree里面，作用是：在回溯建立树的过程中存放已经遍历过的部分，为“分歧处理”服务。属于全局变量
my $p; #表示概率，属于全局变量
my @p = ""; #存放每个树的概率值
my @tree = ""; #存放每个树的打印输出形式
my $words; #普通变量
#将规则库里的规则存进哈希表%P中
#往后注释里说提及的规则的左（右）半部分指的是，例如规则A->B C，则左半部分是A，右半部分是B C
open FILE, "<", "pp.txt" || die "Cannot open file: $!";
while (<FILE>) {
chomp;
@line = split /->/; #以符号“->” 分割每行的字符串，得到规则的左右部分以及该规则的概率
$P{$line[1]}{$line[0]} = $line[2]; #哈希表的第一维key存放规则的右半部分，第二维存放规则的左半部分，value存放该规则的概率。之所以要将规则的右
#半部分放在左半部分之前，是因为，cyk算法是按自底向上的顺序遍历的，先知道规则的右半部分，然后到规则库里找相应的左半部分。
}
close(FILE);
#输入并存放将被作句法剖析的句子
print "Please input a sentence in English:\n";
$words = <STDIN>; #在终端输入待剖析句子，要求以空格隔开每个单词
chomp($words); #去掉句子尾部的换行符
@words = split (/ /, $words); #将句子切成每个单词，存到数组@words
$n = @words; #表示句子长度，即单词数
#从句子里的单词出发，找到每个词可以对应的语法，填进表格中，在表格中它们所在格子连起来是一条对角线。
for ($i = 0; $i < $n; ++ $i) {
if (exists $P{$words[$i]}) { #如果规则库中有这个单词，则继续后面的步骤
foreach $cache (keys %{$P{$words[$i]}}) { #对于每个右半部分是该单词的规则，获得其左半部分
$V{($i + 1) * 11}{$cache}{$words[$i]} = 0; #哈希表%V的第一维key存放的是表格中格子的下标，这里用十进制两位数表示，如果句子长度或者数的
} #层数超过10也应该无所谓，不同的$i和$j经过这一表达式，相当于将下标用映射到某个整数，仍然可以用来
} #区分格子。哈希表的第二维key存放的是规则的左半部分，第三维key存放的是规则的右半部分。之所以要这
#样子，是因为，回溯部分是按自上向下的顺序遍历的，先知道规则的左半部分，找其合适的右半部分。哈希表
#的value存放的应该是$k值，在这行代码中每个格子都只表示一个单词，$k没有意义，故都用0赋值
else { #如果规则库中没有该单词，则输出错误信息，并且结束程序
print "error: there is some words in the sentence that not in the Rule base!\n";
exit(0); #结束程序
}
}
#cyk算法自底向上遍历同时填表的过程，所操作的是表格的下三角部分
for ($j = 1; $j < $n; ++ $j) { #这里$j表示，在剖析句子时，划分出来待处理的句子某部分的长度
for ($i = 1; $i <= $n - $j; ++ $i) { #这里$i表示表格里的横坐标，即待剖析句子里单词的下标，也可以理解为，剖析句子时划分出来待处理的部分的最左
#边单词的下标
%{$V{$i * 10 + ($i + $j)}} = (); #待填的格子里的哈希表初始化为空，该格子的下标是“i,i+j”, i+j是纵坐标，表示剖析句子时划分部分的最后边单词下标
for ($k = $i; $k < $i + $j; ++ $k) { # $k表示，对剖析句子时划分出来待处理的部分作再分割处理的分割位置，即距离$i的长度
#下面，找到所有符合要求的规则填到格子"i,i+j"中。所谓符合要求，就是，找到规则库中存在的规则X->YZ,Y属于格子“i,k”中的，而Z属于格子"k+1,i+j"中的
foreach $cache1 (keys %{$V{$i * 10 + $k}}) { #找出格子"i,k"中的每个规则的左半部分
foreach $cache2 (keys %{$V{($k + 1) * 10 + ($i +$j)}}) { #找出格子"k+1,i+j"中的每个规则的左半部分
if (exists $P{"$cache1 $cache2"}) { #从上述两个格子中找出$cache1和$cache2后，对于其每种可能的组合都到规则库中查找看是否存在
foreach $cache (keys %{$P{"$cache1 $cache2"}}) { #由于某种语法组合BC可能有多种语法指向，即可能A->BC，也可能D->BC，故需要考
#虑完所有的情况
$V{$i * 10 + ($i + $j)}{$cache}{"$cache1 $cache2"} = $k; #value值为$k，$k的作用在于表明树的父节点跟子节点的位置关系，即“某
#个格子里的规则是有哪两个格子的规则得到的”
}
}
}
}
}
}
}
#回溯遍历同时建立并打印输出符合要求的树，这个过程中还要计算每个树的概率以在最后得到一棵最优树。
#注意，打印输出结果中的树是以这样的形式表示的：整体上树是横着的，左子节点在右子节点的上方并跟父节点在同一行，同一层的左右子节点是列对齐的。
if (!(exists $V{$n + 10}{"S"})) {
print "error: there is no tree that meets the requirements!\n" ;
exit(0);
}
foreach $cache (keys %{$V{$n + 10}}) { #在格子“1,n”里找到根结点是S的情况继续后面的操作
if ($cache eq "S") {
print "\n\nThe result is: \n";
$tree = ""; #初始化$tree为空字符串
$p = 1; #初始化概率$p为1
Tree($cache, 1, $n, $tree, "", $p); #调用子函数Tree，参数里，第一个参数是树的根节点；第二个参数是格子的横坐标；第三个参数是纵坐标；第四个
} #参数是$tree，表示前面回溯过程中已经遍历过部分，这是一个全局变量；第五个参数是制表符"\t"，随着程序每次递归
} #该参数里的"\t"的个数将相应的变化，目的是让树的每层节点对齐输出；第六个参数是概率，这个也是全局变量
#比较各个树的概率，输出最优树
$cache = 0; #初始化为0
$j = 0; #初始化为0
for ($i = 0; $i != @p; ++ $i) { #这里目的是判断出哪个树的概率最大，获得该树在数组中的下标
if ($p[$i] gt $cache) {
$cache = $p[$i];
$j = $i;
}
}
print "\n\nThe best tree is : \n"; #输出最优树及其概率
print $tree[$j];
print "\np = $p[$j]\n";
#为回溯服务的子函数Tree，大致上是一个递归算法
sub Tree{
my $cache1 = $_[0]; #接收第一个参数，即树的根结点
my $i = $_[1]; #接收第二个参数，即格子横坐标
my $j = $_[2]; #接收第三个参数，即格子纵坐标
my $temp = $_[3]; #接收第四个参数，即$tree，在每个父节点缓存此前已经遍历过的部分，协助处理分歧点的打印输出操作
my $pp; #局部变量，用来缓存在分歧点的概率
my $cache2; #普通变量
my @temp; #普通数组
my $k; #提取哈希表%V里的value，即表征了父节点和子节点之间的位置关系的分割点
my @cache; #普通数组
my $m = 0; #用在岐义出现处，$m ==0时表示后面的操作是对分歧点的第一次操作，否则，就不是第一次操作了，那么就得先将缓存$temp打印输出，
#然后才继续后面的操作，这样才可以避免打印输出时，到分歧点丢失了已遍历部分的情况出现
my $tt; #用来接收第五个参数的，即用来保证友好输出的制表符
if ($i == $j) { #如果到了叶节点，则直接输出
@temp = keys %{$V{$i * 10 + $j}{$cache1}}; #这行代码是为了将格子"i,i"跟$cache1对应的单词，结果是数组@temp只存有一个单词
print "$cache1\t", $temp[0]; #打印输出终极节点以及其对应的单词
$tree = $tree."$cache1\t".$temp[0]; #将该部分接到标量$tree的后面
$p *= $P{$temp[0]}{$cache1}; #将该规则的概率乘到该树的概率里
if ($j == $n) { #如果这个终极节点对应的单词是句子的最后一个单词了，那么说明这棵树已经遍历完成，概率$p也已经计算完毕,可以输出了
print "\np = $p\n";
push(@p, $p);
push(@tree, $tree);
}
}
else { #如果是非终极节点，那么就得找到其左右子树
foreach $cache2 (keys %{$V{$i * 10 + $j}{$cache1}}) { #这里是一个潜在的分歧点，也就是说，如果存在两种以上的情况，则产生了岐义
$tt = $_[4]; # $tt在这里接收第五个参数，放到这里可以达到一个目的是，对于分歧的每种情况，都初始化一次$tt
if ($m != 0) { #如果$m != 0，说明在产生岐义的格子里，已经不是第一次操作了，于是在开始后续操作前，得先输出缓存$temp
print "\n\n",$temp; #打印输出缓存$temp
$tree = $temp; #由于$tree是全局变量，会随着调用函数里的操作改变，所以当循环回到分歧节点时，需要把$tree还原为第一次经过该节点
#时所保留下来的缓存$temp
$p = $pp; #跟$tree一样的思路，将全局变量$p还原为第一次经过该节点的概率$p的值
}
$pp = $p; #这行代码主要作用是，在回溯遍历过程第一次经过这里时，将概率$p的值保留下来
$p *= $P{$cache2}{$cache1}; #计算概率，即将原来得到的$p乘以本次遇到的规则所对应的概率
$k = $V{$i * 10 + $j}{$cache1}{$cache2}; #获取分割点$k
@cache = split(/ /, $cache2); #将规则右半部分以空格分割开，并将得到的两个字节点存进数组中，供后面的操作使用
print "$cache1\t"; #将父节点打印输出
$tree = $tree."$cache1\t"; #将遍历过的该父节点接到$tree的后面
$tt = $tt."\t"; #制表符操作，层数也高，那么$tt里的"\t"个数就应该越多
Tree($cache[0], $i, $k, $tree, $tt, $p); #对左子树递归调用本函数
print "\n$tt"; #制表符操作，目的是为了让树的输出形式比较友好
$tree = $tree."\n$tt"; #依然要把前面打印输出过的部分接到$tree后，因为不管前面打印了什么，都是树的一部分
Tree($cache[1], $k + 1, $j, $tree, $tt, $p); #对右子树递归调用本函数
if ($cache1 eq "S") { #为了打印输出结果好看些
print "\n";
}
$m = 1; #在分歧点已经处理过一次后，将$m设置为不等于0
}
}
}
|
