第3章 语法与语法剖析

第三章语法与语法剖析厦门大学计算机科学系

李堂秋第一节语法与句子结构表示句子结构的最常用的表示法是语法树：Joneatethecat.表结构表示：

(S(NP(NAMEJone))

(VP(Vate)

(NP(ARTthe)

(Ncat))))简单的上下文无关规则： SNPVPNAMEVNPJohnateARINthecat相关术语：树结点链接根叶子

父亲子女祖先后代

1S-->NPVP5NAME-->John2VP-->VNP6V-->ate3NP-->NAME7ART-->the4NP-->ARTN8N-->cat相关术语：上下文无关文法重写规则非终结符起始符词类符号终结符可以用语法推导出合法的句子（所以又叫做生成语法）：有两个过程是基于推导的：生成与剖析S

==>NPVP （重写S）

==>NAMEVP （重写NP)

==>JohnVP （重写NAME）

==>JohnVNP （重写VP）

==>JohnateNP （重写V）

==>JohnateARTN （重写NP）

==>JohnatetheN （重写ART）

==>Johnatethecat （重写N）==>NAMEatethecat （重写John）==>NAMEVthecat （重写ate）

==>NAMEVARTcat （重写the）

==>NAMEVARTN （重写cat）

==>NPVARTN （重写NAME）

==>NPVNP （重写ARTN）==>NPVP （重写VNP)

==>S （重写NPVP）

相关概念：

自顶向下的语法剖析自底向上的语法剖析

语法树：可以通过把语法剖析

过程记录起来形成第二节什么是好的语法好语法应具有如下的性质：普遍性选择性易理解性判断文法的正确性，有几种方法：如果决定有一类词可以形成句子的某一成分，试试看这类成分的并列词组是否可以做同样的成分，如果不行可能就有问题。NP-NP Iateahamburgerandahotdog.VP-VP Iwilleatthehamburgerandthrowawaythehotdog.S-S IateahambergerandJohnateahotdog.ADJP-ADJP Iateacoldandwellburnedhotdog.ADVP-ADVP Iatethehotdogslowlyandverycarefully.N-N IateahamburgerandhotdogV-V Iwillcookandburnahamburger.AUX-AUX Icanandwilleatthehotdog.ADJ-ADJ Iatetheverycoldandburnedhotdog.如果认为某一类词可以做句子的某一类成分，看一看是否可以出现在句子需要同一类成分的其它地方：当提出一条规则的时候，要考虑它对其它规则的相互影响。John’shitingofMaryalarmedSue.

IcannotexplainJohn’shittingofMary.

SuewasalarmedbyJohn’shittingofMary.确实可以当NPIlookupJohn’sphonenumber.Up..是否是PP？

IlookupJohn’schimney.

*IlookupJohn’sphonenumberandinhiscupboards.可见不都是

IlookupJohn’schimneyandinhiscupboards.第三节自上而下的语法剖析语法分析是一种AI中搜索过程，下面判断句子是否被语法所接受为例下面是使用一个简单的自顶向下的语法剖析算法分析结果：算法：从初始状态((s)1)开始，重复以下过程：1。选择当前状态：从可能状态表中取出第一个状态，叫它为C。如果可能表为空，算法失败（不可能得到正确的剖析）2。如果C包含一个空符号，且词的位置是处于句子的结尾，算法成功3。否则，生成下一个状态：

3。1如果C符号表中的第一个符号是词类符，而当前位置上的词可以作为这种词类，则形成一个新的状态，办法是：去掉符号表中的第一个符号，并把词的位置加一。把新状态放入可能状态表

3。2否则，如果当前状态符号表中的第一个符号是一个非终结状态，把语法规则表中所有可以重写这个符号的规则重写这个符号，形成新的状态。把形成的所有可能的状态加入到可能状态表中。语法：

1. S-->NPVP 4.VP-->V

2. NP-->ARTN 5.VP-->VNP

3. NP-->ARTADJN词汇：

cried:V

dogs:NV

the:ART步数当前状态 回朔状态 注解

1. ((s)1) 初始位置

2. ((NPVP)1) 用规则1重写S

3. ((ARTNVP)1) 用规则2、3重写NP

((ARTADJNVP)1)

4. ((NVP)2) ART与the匹配

((ARTADJNVP)1)

5. ((VP)3) N与dog匹配

((ARTADJNVP)1)

6. ((V)3) 用规则4、5重写VP

((VNP)3)

((ARTADJNVP)1)

7. V与cried匹配，成功如果把这个例子扩大一点：

句子：Theoldmancried.

词典：the:ARTold:ADJN

man:NV

cried:V语法：

1. S-->NPVP 4.VP-->V

2. NP-->ARTN 5.VP-->VNP

3. NP-->ARTADJN词汇：

cried:V

dogs:NV

the:ART步数 当前状态 回朔状态 注解

1. ((s)1) 初始位置

2. ((NPVP)1) 用规则1重写S成NPVP

3. ((ARTNVP)1) 用规则2、3重写NP

((ARTADJNVP)1)

4. ((NVP)2) ART与the匹配

((ARTADJNVP)1)

5. ((VP)3) ((ARTADJNVP)1)

6. ((V)3) 用规则4、5重写VP

((VNP)3)((ARTADJNVP)1)

7. (()4) V与man匹配，不成功

((VNP)3)((ARTADJNVP)1)

8. ((VNP)3) 第一次回朔

((ARTADJNVP)1)

9. ((NP)4)

((ARTADJNVP)1)

10. ((ARTN)4) 找ART失败回朔

((ARTADJN)4)((ARTADJNVP)1) 11. ((ARTADJN)4)

((ARTADJNVP)1) 再一次失败，回朔

12. ((ARTADJNVP)1)

13. ((ADJNVP)2) 14. ((NVP)3) 15. ((VP)4)

16. ((V)4)

((VNP)4)

17. (()5)句子：1The2old3man4cried5.词典：the:ARTold:ADJN

man:NV

cried:V语法：

1.S-->NPVP2.NP-->ARTN3.NP-->ARTADJN4.VP-->V5.VP-->VNP对比一下语法分析和Ai的搜索过程：重复如下过程直到成果或失败：从可能状态表中取出第一个状态从这个选择的状态生成所有可能的后续状态（可能一个也没有）把生成的状态加入到可能状态表中如果把生成的后续状态放在可能状态表的前面，执行的是深度优先搜索。如果把生成的后续状态放在可能状态表的后面，执行的是广度优先搜索。可以看出语法分析的过程就是搜索的过程。注意：对于深度优先搜索，遇到左递归的规则可能引起无限循环：

NP-->NP’sN对于广度优先搜索，在有左递归规则的语法，如果句子是合法的，不会陷入无限循环，但是如果句子是不合文法时，也会引起无限循环。上述过程实际上是一个深度优先搜索的过程：((s)1)成功！((NPVP)1)((ARTNVP)1)((ARTADJNVP)1)((NVP)2)((VP)3)((V)3)((VNP)3)(()4)((NP)4)((ARTN)4)((ARTADJN)4)((ADJNVP)2)((NVP)3)((VP)4)((V)4)((VNP)4)(()4)广度优先搜索的过程：((s)1)((ARTADJNVP)1)((ARTNVP)1)((NVP)2)((VP)3)((VNP)3)((V)3)(()4)((NP)4)((ARTN)4)((ARTADJN)4)((ADJNVP)2)((NVP)3)((VP)4)(()4)((V)4)((VNP)4)成功！((NPVP)1)第四节自底向上的图剖析器自顶向下和自底向上语法分析不同的地方在于：前这使用规则在句子中找规则描述的成分后者是使用规则把句子中已经归结出来的成分归结成更大的成分最简单的自底向上的语法分析可用下述简单步骤：把单词重写成它可能的词类把与任何一条规则右部相匹配的符号序列重写成匹配规则的坐部但是这样的过程太低效，实际上无法使用。主要原因是在分析的过程中会对同一个成分进行多次重复的分析，现在研究使用一种称为图的数据结构以避免重复的工作图剖析器的工作的原理为：有一个记事表记录遇到的词的类符或已经分析完成的成分，称它们为关键成分，取出一个关键成分在语法中找出右部以这个关键成分打头的语法规则，将之激活或找出已经由别的关键成分开始并刚好需要这个关键成分接续下去，以便扩展规则的匹配。这样一直进行下去或一个完整的句子剖析已得到，或记事表空（失败）下面是使用一个简单的自上而下的语法剖析算法分析结果：算法：从((s)1)，重复以下过程：1。选择当前状态：从可能状态表中取出第一个状态，叫它为C。如果可能表为空，算法失败（不可能得到正确的剖析）2。如果C包含一个空符号，且词的位置是处于句子的结尾，算法成功3。否则，生成下一个状态：

3。1如果C符号表中的第一个符号是词类符，而当前位置上的词可以作为这种词类，则形成一个新的状态，办法是：去掉符号表中的第一个符号，并把词的位置加一。把新状态放入可能状态表

3。2否则，如果当前状态符号表中的第一个符号是一个非终结状态，把语法规则表中所有可以重写这个符号的规则重写这个符号，形成新的状态。把形成的所有可能的状态加入到可能状态表中。例如：有如右的语法规则，并且正在分析

句子（第一个词是ART第二个词是ADJ…）用ART在规则集合中找出规则2、3，并将结构记成：

NP->ART。ADJN

NP->ART。Ｎ这两个弧成活动弧用ADJ在规则集合中找出规则４并写成

NP->ADJ。N以激活的弧也得到扩展：

NP->ARTADJ。N1.S->NPVP

2.NP->ARTADJN

3.NP->ARTN

4.NP->ADJN

5.VP->AUXVP6.VP->VNPARTADJNP->ART。ADJNNP->ART。ＮNP->ADJ。NNP->ARTADJ。N核心的算法有两个，即：弧扩展算法：为了添加一个从位置p1到p2的弧C：把这段弧C添加到图中从p1到p2的位置对于所有有如下公式:X->X1…。Ｃ…Xn从p0到p1的弧，在p0到p2之间加上一段新的活动弧，它有公式X->X1…Ｃ。…Xn对于所有有如下公式:X->X1…。Ｃ从p0到p1的弧，把一个新的成分X(从p0到p2）加到记事表中自底向上的图语法剖析算法：一直进行如下过程直到没有余下的输入词：如果记事表为空，看输入中下一个词的解释，并把之加如记事表从记事表中选出一个成分（称为从p1到p2的成分C）对于每一条形如X->CX1X2…Xn的规则，把一段活动弧加到图中的p1到p2的位置，它的公式是X->C。X1X2…Xn根据弧扩展算法把Ｃ加到图中去。输入句子图记录活动弧和分析完成的成分记事表语法规则表算法S(18)AUX(34)AUX(45）V(34)V(45)V(56)V(78)NP(14)VP(58)S(28)NP(24)VP(48)VP(38)N(45)4can5ART(12)1the2ADJ(23)2large3N(34)3can4N(56)5hold6N(78)7water8ART(67)6the7NP->ART。

ADJNNP->ART。NNP->ADJ。NNP->ARTADJ。NS->NP。VPS->NP。VPVP->AUX。VPVP->AUX。VPVP->V。NPVP->V。NPVP->V。NPNP->ART。

ADJNNP->ART。NNP(68)S->NP。VPVP->V。NP1.S->NPVP

2.NP->ARTADJN

3.NP->ARTN

4.NP->ADJN

5.VP->AUXVP6.VP->VNP

the:ART

large:ADJ

can:N,AUX,V

hold:N,V

water:N,V第五节转移网络语法转移网络是另一种表示语法的方法，它有以下两个元素主成的：带标号的结点，其中有一个结点称为起始初始或结点带标号的弧最简单的是有限状态机，但表达能力也有限，无法表达自然语言的语法。也一种称为递归转移网络的（RTN），与上下文无关文法等价，下面是简单的自然语言语法的网络表示法：上面小写字母串表示词类，大写字母串表示短语的类型，而且在实际应用中还有不少扩充，为了分别，加上前缀：类型 标识 应用CAT noun 如果当前的词的类型与标识符相同，成功通过当前弧

NPNP1NP2SS1S2S3artpopnounNPNPverbNPpopWRD of 如果当前的词与标识符相同，成功通过当前弧PUSH NP 如果从当前的词开始能通过标识符指定的子网络 相同，则成功通过当前弧JUMP 不管当前词是什么，总能通过当前弧POP 子网络通过成功，跳回上一层网络下面看如何用RTN分析句子的：

Thepurplecowatethegrass.NPNP1NP2artpopnounNPSS1S2S3NPverbNPpopSS1S2S3NPNP1NP2NPNP1NP2递归转移网络自顶向下的语法剖析：名称解释：当前位置：指句子中当前要分析的词当前结点：当前在网络中所处的结点位置返回点：如果从一个子网络中跳出，返回到哪个子网络的什么地方下一个状态：通过弧算法：如果是CAT符，并且当前位置的词类与标识符相同

则把当前位置加一，把当前结点换成弧所指的结点如果是PUSHＮ弧，把当前弧所指的结点设定加入到返回点表，把当前结点设为子网络Ｎ的首结点如果是POP弧，并且返回表非空，则弹出返回表中的第一个点，做为当前结点如果是POP弧，返回表为空且所有的词都分析完毕，则语法剖析成功下面是另一个语法的网络：分析：Theoldmancried.NPNP1NP2SS1S2PUSHNPCARverbPUSHNPPOPCATpronounCATartCATnumberCATadjPOPCATnoun3121211112步骤 当前结点当前位置返回点 要走的弧 注释1. S 1 NIL S/1 初始位置2. NP 1 (S1) NP/1 转到NP3. NP1 2 (S1) NP1/1 the4. NP1 3 (S1) NP1/2 old5. NP2 4 (S1) NP2/2 man6. S1 4 NIL S1/1 返回S17. S2 5 NIL S2/1 cried8. 成功

分析：Onesawtheman.NPNP1NP2SS1S2PUSHNPCARverbPUSHNPPOPCATpronounCATartCATnumberCATadjPOPCATnoun3121211112步骤 当前状态 要走的弧 回朔状态1. (S1NIL) S/1 2. (NP1(S1)) NP/2(NP3回朔用）

3. (NP12(S1)) NP1/2 (NP22(S1))4. (NP13(S1) NP2/1 (NP22(S1))5. (S13NIL) NO (NP22(S1)) 6. (NP22(S1)) NP2/1 7. (S12NIL) S1/1 8. (S23NIL) S2/2 9. (NP3(S2)) NP/110. (NP14(S2)) NP1/211. (NP25(S2)) NP2/112. (S25NIL) S2/113. 成功

RTN可以用图一样的数据结构提高

分析的效率--合法子结构表，其分

析效率与图语法剖析一样：K*N3第六节自顶向下图剖析自顶向下和自底向上语法分析各有优缺点：自顶向下的语法分析有高度的预见性，这有助于排除一些歧义，使得没有得到预见的结构不会生成。如：Thecanholdsthewater.中can有三种可能AUX、V、N。但是自顶向下语法分析中：S->NPVP,->ARTADJNVP,或ARTNVP,ADJNVP.先用第一个，the是ART，看can是否可以是ADJ时，失败用第二时，再次检查ART，然后看can是否可能是N时成功，此后AUX、V不再考虑而自底向上语法分析中三种可能全会考虑。从这种意义上说自顶向下分析法更高效相反，自顶向下的语法分析对the是否是ART要多次判断，对与复杂的语法，反复生成复杂的中间结构会造成低效的严重效果。而在自底向上语法分析中同一个机构可保证只生成一次。这样自底向上的看来效率更高。通过把两种方法结合起来，可以综合两者的优点--形成自上而下制导的自底向上的分析方法。这种方法与纯自底向上的比较如下：弧扩展算法一样不同的是这种方法引入自上而下的弧引入算法。不是引入所有以生成的成分为第一个元素的所有产生式。算法：自上而下的弧引入算法：要加入一条在位置j结尾的弧S->C1C2..。Ci…Cn，执行：对于语法中的每一条形如Ci->X1X2…Xk，递归地在从j到j的位置上加入形如

Ci->。X1X2…Xk的弧。自上而下的图剖析算法：初始化：对于语法中所有形如S->X1X2…Xk，应用弧引如算法往图中加入标

为S->。X1X2…Xn.分析算法：如果记事表为空，看输入中下一个词的解释，并把之加入记事表从记事表中选出一个成分（称为从p1到p2的成分C）根据弧扩展算法把Ｃ加到图中去，并与可能扩展的活动弧相结合。生成的

所有新成分要加到记事表中去。对于在步骤３中生成的每一条形活动弧，使用上述弧引入算法把它们加到

图中去。S(18)AUX(45）V(45)NP(14)VP(58)VP(48)ART(12)1the2ADJ(23)2large3N