-
【说话处理惩罚与Python】8.2文法有什么用？\8.3高低文无关文法\8.4高低文无关文法解析
添加时间:2013-6-2 点击量:8.2文法有什么用？
超出n-grams
用bigrams中的频率信息生成句子，短的时辰可以接管，然则长的时辰就显得无法接管。
我们体系地可以用较短的序列调换较长的序列，并使其依然合适语律例则。
例如下面这句话：
我们可认为这幅图上添上文法类别标签。
NP为名词短语；VP为动词短语；PP为介词短语；
用树来默示：
句子可以有随便率性的长度。短语布局树可以有随便率性深度。
鄙人一节中，将看到一个指定的文法如何将句子细分成它的直接成分，以及如何将这些进一步细分，直到达到零丁词汇层面。
8.3高低文无关文法
context-free grammar，CFG高低文无关文法（更多关于高低文无关文法请自行懂得）
grammar1= nltk.parse_cfg（"""
S -> NPVP
VP-> VNP| VNPPP
PP-> P NP
V-> "saw" | "ate" | "walked"
NP-> "John" | "Mary" | "Bob" | DetN| DetNPP
Det-> "a" | "an" | "the" | "my"
N-> "man" | "dog" | "cat" | "telescope" | "park"
P-> "in" | "on" | "by" | "with"
"""）
>>>sent = "Mary saw Bob".split（）
>>>rd_parser =nltk.RecursiveDescentParser（grammar1）
>>>for tree in rd_parser.nbest_parse（sent）:
... print tree
（S （NP Mary）（VP （V saw） （NP Bob）））
写本身的文法
我们可以写本身的文法，保存在cfg的文件中。
>>>grammar1= nltk.data.load（file:mygrammar.cfg）
>>>sent = "Mary saw Bob".split（）
>>>rd_parser =nltk.RecursiveDescentParser（grammar1）
>>>for tree in rd_parser.nbest_parse（sent）:
print tree
若是没有任何输出，可能是sent也就是句子不合适文法，可以打开追踪，进行调试和搜检。
rd_parser =nltk.RecursiveDescentParser（grammar1， trace=2）
句法布局中的递归
句法递归请参考文法相干材料。
递归深度是没有限制的，我们可以测验测验解析更深层次的嵌套布局的句子。
RecursiveDescentParser是无法处理惩罚形如X-> XY的左递归。
8.4高低文无关文法解析
在这里介绍两种简单的解析办法，一种自上而下的办法成为递归降落解析，一种自下而上的办法成为移近-归约解析。同样，也会看到更错杂的算法，一种带自下而上过滤的自上而下的办法称为左角落解析。
一种动态规划技巧成为图表解析。
递归降落解析
我们可以应用图形化师范nltk.app.rdparser（）中看到递归降落的过程。
&＃160;
从S节点开端匹配。
NLTK供给了一个递归降落解析器：
>>>rd_parser =nltk.RecursiveDescentParser（grammar1）
>>>sent = Mary saw a dog.split（）
>>>for t in rd_parser.nbest_parse（sent）:
... print t
（S （NP Mary）（VP （V saw） （NP （Det a） （N dog））））
递归降落是有毛病的：
1、左递归产生式会进入死轮回。
2、解析器浪费了很多时候处理惩罚不合适输入句子的词和布局
3、回溯过程中可能丢弃解析过的成分，他们须要在之后从头建树
移进-归约解析（简单的自下而上解析）
移位：解析看重复将下一个输入词推到客栈中，这是移位操纵。
归约：若是客栈上的前N项匹配一些产生式右侧的N个项目，那么就把他们弹出栈，并把产生式左边的项目压入栈。这种调换的操纵就是归约操纵。
同样，可以应用图形化示范nltk.app.srparser（）
相干代码：
>>>sr_parse= nltk.ShiftReduceParser（grammar1）
>>>sent = Mary saw a dog.split（）
>>>print sr_parse.parse（sent）
（S （NP Mary）（VP （V saw） （NP （Det a） （N dog））））
左角落解析器
递归降落解析器的题目之一就是不克不及处理惩罚左递归，会进入无穷轮回。左角落解析器是我们已经看到的自下而上与自上而下的办法的混淆体。
他不会陷入左递归产生式的陷阱。在开端工作之前，左角落解析器预处理惩罚高低文无关文法建树一个表，此中每行包含两个单位。第一个存放非终结符，第二个存放那个非终结符可能的左角落凑集。
例如，grammar2的文法：
grammar2= nltk.parse_cfg（"""
S -> NP VP
NP-> Det Nom| PropN
Nom-> Adj Nom| N
VP-> V Adj| VNP| VS| VNPPP
PP-> P NP
PropN-> Buster | Chatterer | Joe
Det-> the | a
N-> bear | squirrel | tree | fish | log
Adj -> angry | frightened | little | tall
V-> chased | saw | said | thought | was | put
P-> on
"""）
他的左角落为：
解析器每次推敲产生式时，他会搜检下一个输入词是否与左角落表格中至少一种非终结符的类别相容。
合适语句规矩的字串表
上方评论辩论的简单的解析器在完全性和效力上都有限制，为了弥补这些，我们将应用动态规划算法设计技巧解决题目。
这里介绍图表解析。有一个表格须要我们重视，合适语律例则的字串表，简称为WFST。
以这句话为例子：
>>>text = [I， shot， an， elephant， in， my， pajamas]
如何构建WFST:
def init_wfst（tokens， grammar）:
numtokens= len（tokens）
wfst= [[None for i in range（numtokens+1）] for j in range（numtokens+1）]
for i in range（numtokens）:
productions = grammar.productions（rhs=tokens[i]）
wfst[i][i+1]= productions[0].lhs（）
return wfst
def complete_wfst（wfst，tokens， grammar，trace=False）:
index = dict（（p.rhs（），p.lhs（）） for pin grammar.productions（））
numtokens= len（tokens）
for span in range（2， numtokens+1）:
for start in range（numtokens+1-span）:
end = start + span
for midin range（start+1， end）:
nt1，nt2 = wfst[start][mid]，wfst[mid][end]
if nt1 and nt2 and （nt1，nt2） in index:
wfst[start][end]= index[（nt1，nt2）]
if trace:
print "[％s] ％3s[％s] ％3s[％s] ==>[％s] ％3s[％s]" ％
（start， nt1， mid，nt2，end， start， index[（nt1，nt2）]， end）
return wfst
def display（wfst，tokens）:
print \nWFST + .join（[（"％-4d" ％i） for i in range（1， len（wfst））]）
for i in range（len（wfst）-1）:
print "％d " ％i，
for j in range（1， len（wfst））:
print "％-4s" ％（wfst[i][j] or .），
print
>>>tokens = "I shot an elephant in mypajamas".split（）
>>>wfst0= init_wfst（tokens， groucho_grammar）
>>>display（wfst0，tokens）
WFST1 2 3 4 5 6 7
0 NP . . . . . .
1 . V . . . . .
2 . . Det . . . .
3 . . . N . . .
4 . . . . P . .
5 . . . . . Det .
6 . . . . . . N
>>>wfst1= complete_wfst（wfst0， tokens， groucho_grammar）
>>>display（wfst1，tokens）
WFST1 2 3 4 5 6 7
0 NP . . S . . S
1 . V . VP . . VP
2 . . Det NP . . .
3 . . . N . . .
4 . . . . P . PP
5 . . . . . Det NP
6 . . . . . . N
在此中，要重视index的内容：
要构建index中的内容，须要有下面的步调，这里把那段代码提取了出来，零丁演示：
＃对应的文法
>>> groucho_grammar= nltk.parse_cfg（"""
S -> NP VP
PP -> P NP
NP -> Det N| DetN PP| I
VP -> V NP| VP PP
Det -> an | my
N -> elephant | pajamas
V -> shot
P ->in
"""）
＃文法的内容
>>> grammar，productions（）
[S -> NP VP， PP -> P NP， NP -> Det N， NP -> DetN PP， NP -> I， VP -> V NP， VP -> VP PP， Det -> an， Det -> my， N -> elephant， N -> pajamas， V -> shot， P -> in]
＃index的内容
pprint.pprint（dict（（p.rhs（），p.lhs（）） for p in groucho_grammar.productions（）））
{（Det， N）: NP，
（DetN， PP）: NP，
（NP， VP）: S，
（P， NP）: PP，
（V， NP）: VP，
（VP， PP）: VP，
（I，）: NP，
（an，）: Det，
（elephant，）: N，
（in，）: P，
（my，）: Det，
（pajamas，）: N，
（shot，）: V}
>>>
信赖，读完这个代码，若是懂得了，必定懂得了构建过程的核心思惟。
无论对感情还是对生活，“只要甜不要苦”都是任性而孩子气的，因为我们也不完美，我们也会伤害人。正因为我们都不完美，也因为生活从不是事事如意，所以对这些“瑕疵”的收纳才让我们对生活、对他人的爱变得日益真实而具体。—— 汪冰《世界再亏欠你，也要敢于拥抱幸福》
