|
本章解决的问题
我们如何使用形式化语法来描述无限的句子集合的结构？我们如何使用句法树来表示句子结构？语法分析器如何分析一个句子并自动构建句法树？
这里写目录标题
1 一些语法困境1.1 语言数据和无限可能性1.2 普遍存在的歧义
2 文法有什么用？2.1 超越 n-grams
3 上下文无关文法3.1 一种简单的文法3.2 写你自己的文法3.3 句法结构中的递归
4 上下文无关文法分析4.2 4.2 移进-归约分析4.3 左角落分析器4.4 符合语句规则的子串表 WFST
5 依存关系和依存文法5.1 配价与词汇5.2 扩大规模
6 文法开发6.1 树库和文法6.2 有害的歧义6.3 加权文法
7 小结
1 一些语法困境
1.1 语言数据和无限可能性
1.2 普遍存在的歧义
#让我们仔细看看短语 I shot an elephant in my pajamas 中的歧义。
#首先，我们需要定义一个简单的文法:
import nltk
groucho_grammar = nltk.CFG.fromstring("""
S -> NP VP
PP -> P NP
NP -> Det N | Det N PP | 'I'
VP -> V NP | VP PP
Det -> 'an' | 'my'
N -> 'elephant' | 'pajamas'
V -> 'shot'
P -> 'in'
""")
#这个文法允许以两种方式分析句子，取决于介词短语 in my pajamas 是描述大象还是枪击事件。
sent = ['I', 'shot', 'an', 'elephant', 'in', 'my', 'pajamas']
parser = nltk.ChartParser(groucho_grammar)
for tree in parser.parse(sent):
print(tree)
tree.draw()
"""
(S
(NP I)
(VP
(VP (V shot) (NP (Det an) (N elephant)))
(PP (P in) (NP (Det my) (N pajamas)))))
(S
(NP I)
(VP
(V shot)
(NP (Det an) (N elephant) (PP (P in) (NP (Det my) (N pajamas))))))
"""
本章介绍文法和分析，以形式化可计算的方法调查和建模我们一直在讨论的语言现象正如我们所看到的,词序列中符合语法规则的和不符合语法规则的模式相对于短语结构和依赖是可以被理解的。我们可以开发使用文法和分析的这些结构的形式化模型。与以前一样，一个重要的动机是自然语言理解。当我们能可靠地识别一个文本所包含的语言结构时，我们从中可以获得多少文本的含义?
2 文法有什么用？
2.1 超越 n-grams
成分结构基于对词与其他词结合在一起形成单元的观察。一个词序列形成这样一个单元的证据是它是可替代的——也就是说,在一个符合语法规则的句子中的词序列可以被一个更小的序列替代而不会导致句子不符合语法规则。   
3 上下文无关文法
3.1 一种简单的文法
"""
#首先，让我们看一个简单的上下文无关文法
# 按照惯例， 第一条生产式的左端是文法的开始符号，通常是 S(句子)，所有符合语法规则的树都必须有这个符 号作为它们的根标签。
# NLTK中，上下文无关文法定义在 nltk.grammar 模块。
"""
#上下文无关文法
grammar1 = nltk.CFG.fromstring("""
S -> NP VP
VP -> V NP | V NP PP
PP -> P NP
V -> "saw" | "ate" | "walked"
NP -> "John" | "Mary" | "Bob" | Det N | Det N PP
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.parse(sent):
print(tree)
tree.draw()
文法组成部分的不同提取方式会产生不一样的意思： 
3.2 写你自己的文法
import nltk
def yours_grammar(gram):
sent = "Mary saw Bob".split()
rd_parser = nltk.RecursiveDescentParser(gram)
for tree in rd_parser.parse(sent):
print(tree)
tree.draw()
grammar1 =nltk.data.load('file:mygrammar.cfg') # #确保你的文件名后缀为.cfg，并且字符串'file:mygrammar.cfg中'间没有空格符
print(yours_grammar(grammar1))
3.3 句法结构中的递归
#一个文法被认为是递归的，如果文法类型出现在产生式左侧也出现在右侧，
#如例 8-2 所 示。产生式 Nom -> Adj Nom(其中 Nom 是名词性的类别)包含 Nom 类型的直接递归，
#而 S 上的间接递归来自于两个产生式的组合:S -> NP VP 与 VP -> V S。
#例. 递归的上下文无关文法。
grammar2 = nltk.CFG.fromstring("""
S -> NP VP
NP -> Det Nom | PropN
Nom -> Adj Nom | N
VP -> V Adj | V NP | V S | V NP PP
PP -> P NP
PropN -> 'Buster' | 'Chatterer' | 'Joe'| 'Today'
Det -> 'the' | 'a'
N -> 'bear' | 'squirrel' | 'tree' | 'fish' | 'log' | 'Sunday'
Adj -> 'angry' | 'frightened' | 'little' | 'tall' | 'sunny'
V -> 'chased' | 'saw' | 'said' | 'thought' | 'was' | 'put' | 'is'
P -> 'on'
""")
def yours_grammar(sent, gram):
rd_parser = nltk.RecursiveDescentParser(gram)
for tree in rd_parser.parse(sent):
print(tree)
tree.draw()
sent1 = "the angry bear chased the frightened little squirrel".split()
sent2 = "Chatterer said Buster thought the tree was tall".split()
sent3 = "Today is sunny".split()
print("sent1: ")
print(yours_grammar(sent1, grammar2))
print("sent2: ")
print(yours_grammar(sent2, grammar2))
print("sent3: ")
print(yours_grammar(sent3, grammar2)) # 不添加会报错 Grammar does not cover some of the input words: "'Today', 'is', 'Sunday'".
4 上下文无关文法分析
分析器根据文法产生式处理输入的句子，并建立一个或多个符合文法的组成结构。文法 是一个格式良好的声明规范——它实际上只是一个字符串，而不是程序。分析器是文法的解释程序。它搜索符合文法的所有树的空间找出一棵边缘有所需句子的树。分析器允许使用一组测试句子评估一个文法，帮助语言学家发现在他们的文法分析中存 在的错误。分析器可以作为心理语言处理模型，帮助解释人类处理某些句法结构的困难。 
"""
1 一种最简单的分析器将一个文法作为如何将一个高层次的目标分解成几个低层次的子目标的规范来解释。
2 递归下降分析器在上述过程中建立分析树。带着最初的目标(找到一个 S)，创建 S 根节点。
3 随着上述过程使用文法的产生式递归扩展，分析树不断向下延伸(故名为递归下降)
4 我们可以在图形化示范 nltk.app.rdparser()中看到这个过程
"""
nltk.app.rdparser()
grammar1 = nltk.CFG.fromstring("""
S -> NP VP
VP -> V NP | V NP PP
PP -> P NP
V -> "saw" | "ate" | "walked"
NP -> "John" | "Mary" | "Bob" | Det N | Det N PP
Det -> "a" | "an" | "the" | "my"
N -> "man" | "dog" | "cat" | "telescope" | "park"
P -> "in" | "on" | "by" | "with"
""")
#NLTK 提供了一个递归下降分析器:
rd_parser = nltk.RecursiveDescentParser(grammar1)
sent = "Mary saw a dog".split()
for tree in rd_parser.parse(sent):
print(tree)
"""
递归下降分析有三个主要的缺点。
1 首先，左递归产生式，如:NP -> NP PP，会进入死循环。
2 第二，分析器浪费了很多时间处理不符合输入句子的词和结构。
3 第三，回溯过程中可 能会丢弃分析过的成分，它们将需要在之后再次重建。
#例如:从VP -> V NP上回溯将放 弃为 NP 创建的子树。
#如果分析器之后处理 VP -> V NP PP，那么 NP 子树必须重新创建。
"""
4.2 4.2 移进-归约分析
简单的自下而上分析器是移进-归约分析器。 
"""
1 简单的自下而上分析器是移进-归约分析器。
2 尝试找到对应文法生产式右侧的词和短语的序列，用左侧的替换它们，直到整个句子归约为一个 S。
3 移进-归约分析器的六个阶段:分析器一开始把输入的第一个词转移到堆栈;
4 一旦堆 栈顶端的项目与一个文法产生式的右侧匹配，就可以将它们用那个产生式的左侧替换;
5 当所有输入都被使用过且堆栈中只有剩余一个项目 S 时，分析成功。
6 用nltk.app.srparser()示意流程
"""
nltk.app.srparser()
#NLTK 中提供了 ShiftReduceParser()，移进-归约分析器的一个简单的实现。
sr_parse = nltk.ShiftReduceParser(grammar1)
sent = 'Mary saw a dog'.split()
for tree in sr_parse.parse(sent):
print(tree)
移进-规约分析器缺点可能会到达一个死胡同，而不能找到任何解析，即使输入的句子是符合语法的。这种情况发生时，没有剩余的输入，而堆栈包含不能被规约到一个S的项目。
问题出现的原因是:较早前做出的选择不能被分析器撤销(虽然图形演示中用户可以撤消它们的选择)。
分析器可以做两种选择:(a）当有多种规约可能时选择哪个规约，(b)当移进和规约都可以时选择哪个动作。
移进-规约分析器可以改进执行策略来解决这些冲突。例如:它可以通过只有在不能规约时才移进，解决移进-规约冲突;它可以通过优先执行规约操作，解决规约-规约冲突;它可以从堆栈移除更多的项目。(一个通用的移进-规约分析器，是一个“超前LR分析器”，普遍使用在编程语言编译器中。)
移进-规约分析器相比递归下降分析器的好处是，它们只建立与输入中的词对应的结构。此外，每个结构它们只建立一次。例如:NP(Det(the)，N(man))只建立和压入栈一次，不管以后VP -> V NPPP规约或者NP ->NPPP规约会不会用到。
4.3 左角落分析器
4.4 符合语句规则的子串表 WFST
"""
#运用动态 规划算法设计技术分析问题
#动态规划存储中间结果，并在 适当的时候重用它们，能显著提高效率。
#这种技术可以应用到句法分析，使我们能够存储分析任务的部分解决方案，
#然后在必要的时候查找它们，直到达到最终解决方案。这种分析方法被称为图表分析。
#动态规划使我们能够只建立一次 PP in my pajamas。
#第一次我们建立时就把它存入一 个表格中，然后在我们需要作为对象 NP 或更高的 VP 的组成部分用到它时我们就查找表格。
#这个表格被称为符合语法规则的子串表 或简称为 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 p in grammar.productions())
numtokens = len(tokens)
for span in range(2, numtokens+1):
for start in range(numtokens+1-span):
end = start + span
for mid in 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, end=" ")
for j in range(1, len(wfst)):
print("%-4s" % (wfst[i][j] or '.'), end=" ")
print()
tokens = "I shot an elephant in my pajamas".split()
wfst0 = init_wfst(tokens, groucho_grammar)
display(wfst0, tokens)
wfst1 = complete_wfst(wfst0, tokens, groucho_grammar)
display(wfst1, tokens)
wfst1 = complete_wfst(wfst0, tokens, groucho_grammar, trace=True) # 找出过程 设置参数trace
5 依存关系和依存文法
短语结构文法是关于词和词序列如何结合起来形成句子成分的。一个独特的和互补的方式，依存文法，集中关注的是词与其他词之间的关系。依存关系是一个中心词与它的依赖之间的二元对称关系。一个句子的中心词通常是动词，所有其他词要么依赖于中心词，要么依 赖路径与它联通。依存关系表示是一个加标签的有向图，其中节点是词汇项，加标签的弧表示依赖关系，从中心词到依赖。 
"""#下面是 NLTK 为依存文法编码的一种方式 ——注意它只能捕捉依存关系信息，不能指定依存关系类型:"""
groucho_dep_grammar = nltk.DependencyGrammar.fromstring("""
'shot' -> 'I' | 'elephant' | 'in'
'elephant' -> 'an' | 'in'
'in' -> 'pajamas'
'pajamas' -> 'my'
""")
print(groucho_dep_grammar)
 
依存关系图是一个投影，当所有的词都按线性顺序书写 ，边可以在词上绘制而不会交叉。这等于是说一个词及其所有后代依赖(依赖及其依赖的依赖，等等)在句子中形成一个连续 的词序列
#依存关系图是一个投影，当所有的词都按线性顺序书写 ，边可以在词上绘制而不会交叉。
#这等于是说一个词及其所有后代依赖(依赖及其依赖的依赖，等等)在句子中形成一个连续 的词序列
pdp = nltk.ProjectiveDependencyParser(groucho_dep_grammar)
sent = 'I shot an elephant in my pajamas'.split()
trees = pdp.parse(sent)
for tree in trees:
print(tree)
tree.draw()
5.1 配价与词汇
动词和它们的依赖 依赖 ADJ、NP、PP 和 S 通常被称为各自动词的补语，什么动词可以和什么补语一起出现 具有很强的约束。  在依存文法的传统中,在表 8-3 中的动词被认为具有不同的配价。配价限制不仅适用于 动词，也适用于其他类的中心词。 介词短语、形容词和副词通常充当修饰语。与补充不同修饰语是可选的，经常可以进行 迭代，不会像补语那样被中心词选择。
5.2 扩大规模
到目前为止，我们只考虑了“玩具文法”，演示分析的关键环节的少量的文法,但有一个明显的问题就是这种做法是否可以扩大到覆盖自然语言的大型语料库。
很难将文法模块化，每部分文法可以独立开发。反过来这意味着，在一个语言学家团队中分配编写文法的任 务是很困难的。
另一个困难是当文法扩展到包括更加广泛的成分时，适用于任何一个句子的分析的数量也相应增加。 换句话说，歧义随着覆盖而增加。
6 文法开发
分析器根据短语结构文法在句子上建立树。现在，我们上面给出的所有例子只涉及玩具文法包含少数的产生式。如果我们尝试扩大这种方法的规模来处理现实的语言语料库会发生什么?在本节中，我们将看到如何访问树库，并看看开发广泛覆盖的文法的挑战。
6.1 树库和文法
# corpus 模块定义了树库语料的阅读器，其中包含了宾州树库语料的 10%的样本。
from nltk.corpus import treebank
t = treebank.parsed_sents('wsj_0001.mrg')[0]
print(t)
#我们可以利用这些数据来帮助开发一个文法。
#搜索树库找出句子的补语。
def filter(tree):
child_nodes = [child.label() for child in tree if isinstance(child, nltk.Tree)]
return (tree.label() == 'VP') and ('S' in child_nodes)
from nltk.corpus import treebank
print([subtree for tree in treebank.parsed_sents() for subtree in tree.subtrees(filter)][1])
#NLTK 语料库也收集了中央研究院树库语料，包括 10000 句已分析的句子，来自现代汉 语中央研究院平衡语料库。
#让我们加载并显示这个语料库中的一棵树。
print(nltk.corpus.sinica_treebank.parsed_sents()[3449].draw())
6.2 有害的歧义
不幸的是,随着文法覆盖范围的增加和输入句子长度的增长,分析树的数量也迅速增长事实上，它以天文数字的速度增长。
grammar = nltk.CFG.fromstring("""
S -> NP V NP
NP -> NP Sbar
Sbar -> NP V
NP -> 'fish'
V -> 'fish'
""")
tokens = ['fish'] * 5
cp = nltk.ChartParser(grammar)
for tree in cp.parse(tokens):
print(tree)
#随着句子长度增加到(3，5，7，...)，我们得到的分析树的数量是:1; 2; 5; 14; 42; 132; 429; 1,430; 4,862; 16,796; 58,786; 208,012; ....
6.3 加权文法
处理歧义是开发广泛覆盖的分析器的主要挑战。图表分析器提高 了计算一个句子的多个分析的效率，但它们仍然因可能的分析的数量过多而不堪重负。加权文法和概率分析算法为这些问题提供了一个有效的解决方案。
#宾州树库样本中give和gave的用法。
def give(t):
return t.label() == 'VP' and len(t) > 2 and t[1].label() == 'NP'\
and (t[2].label() == 'PP-DTV' or t[2].label() == 'NP')\
and ('give' in t[0].leaves() or 'gave' in t[0].leaves())
def sent(t):
return ' '.join(token for token in t.leaves() if token[0] not in '*-0')
def print_node(t, width):
output = "%s %s: %s / %s: %s" %\
(sent(t[0]), t[1].label(), sent(t[1]), t[2].label(), sent(t[2]))
if len(output) > width:
output = output[:width] + "..."
print(output)
for tree in nltk.corpus.treebank.parsed_sents():
for t in tree.subtrees(give):
print_node(t, 72)
概率上下文无关文法(probabilistic context-free grammar，PCFG)
概率上下文无关文法(probabilistic context-free grammar，PCFG)是一种上下文无关文 法，它的每一个产生式关联一个概率。它会产生与相应的上下文无关文法相同的文本解析， 并给每个解析分配一个概率。PCFG 产生的一个解析的概率仅仅是它用到的产生式的概率的乘积。
#概率上下文无关文法(probabilistic context-free grammar，PCFG)是一种上下文无关文 法，
#它的每一个产生式关联一个概率。它会产生与相应的上下文无关文法相同的文本解析， 并给每个解析分配一个概率。
#PCFG 产生的一个解析的概率仅仅是它用到的产生式的概率的乘积。
grammar = nltk.PCFG.fromstring("""
S -> NP VP [1.0]
VP -> TV NP [0.4]
VP -> IV [0.3]
VP -> DatV NP NP [0.3]
TV -> 'saw' [1.0]
IV -> 'ate' [1.0]
DatV -> 'gave' [1.0]
NP -> 'telescopes' [0.8]
NP -> 'Jack' [0.2]
""")
print(grammar)
viterbi_parser = nltk.ViterbiParser(grammar)
for tree in viterbi_parser.parse(['Jack', 'saw', 'telescopes']):
print(tree)
# 现在，分析树被分配了概率，一个给定的句子可能有数量庞大的可能的解析就不再是问题。分析器将负责寻找最有可能的解析。
7 小结
|