句法分析精选PPT.ppt

《句法分析精选PPT.ppt》由会员分享，可在线阅读，更多相关《句法分析精选PPT.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于句法分析关于句法分析第1页，讲稿共47张，创作于星期日句法分析句法分析前言：前言：因为句法分析在计算语言学这门学科中相对因为句法分析在计算语言学这门学科中相对来说是比较成熟的技术，有许多算法都比较好，来说是比较成熟的技术，有许多算法都比较好，应用实现效率也比较高，学好它也将有助于我们应用实现效率也比较高，学好它也将有助于我们将来学习编译原理的分析策略。将来学习编译原理的分析策略。第2页，讲稿共47张，创作于星期日句法分析的概念句法分析的概念n句法分析术语：句法分析术语：句法分析：句法分析：Parsing句法分析器：句法分析器：Parsern句法分析的概念：句法分析的概念：判断输入的单词序列

2、能不能构成合乎语法的判断输入的单词序列能不能构成合乎语法的句子，抽取出合乎语法的句子的句法结构。句子，抽取出合乎语法的句子的句法结构。即：将输入句子中单词之间的线性词序，变即：将输入句子中单词之间的线性词序，变成一个非线性的数据结构，如短语结构树。成一个非线性的数据结构，如短语结构树。第3页，讲稿共47张，创作于星期日采取什么样的算法来实现？采取什么样的算法来实现？是否所有的语言、语法形式都可以采用同一是否所有的语言、语法形式都可以采用同一种算法来实现？种算法来实现？第4页，讲稿共47张，创作于星期日不同的语法形式，对应的句法分析算法不同的语法形式，对应的句法分析算法也不尽相同！也不尽相同！第

3、5页，讲稿共47张，创作于星期日形式语法理论形式语法理论 形式语法理论的目的是试图用精确形式语法理论的目的是试图用精确的数学模型（形式语言）来刻划自然语的数学模型（形式语言）来刻划自然语言。言。第6页，讲稿共47张，创作于星期日采用什么语法？采用什么语法？n成熟的成熟的短语结构语法短语结构语法n逐渐流行的逐渐流行的依存语法依存语法n相对而言，主流的是短语结构语法相对而言，主流的是短语结构语法(特别是上下文无关语特别是上下文无关语法）应用得最为广泛，因此以法）应用得最为广泛，因此以短语结构树为目标的句法短语结构树为目标的句法分析器研究得最为彻底分析器研究得最为彻底；n 很多其他形式语法对应的句法

4、分析器都可以通过对短语很多其他形式语法对应的句法分析器都可以通过对短语结构语法的句法分析器进行简单的改造得到。结构语法的句法分析器进行简单的改造得到。n 本讲义将主要介绍本讲义将主要介绍上下文无关语法上下文无关语法的句法分析器，因的句法分析器，因为它具有高效的句法分析算法。为它具有高效的句法分析算法。第7页，讲稿共47张，创作于星期日短语结构语法短语结构语法n一般一般上下文无关文法上下文无关文法所代表的短语结构所代表的短语结构语法应用最为广泛。语法应用最为广泛。n经典乔理论：一个语法包括：经典乔理论：一个语法包括：短语结构短语结构(phrase structure)转换结构转换结构(trans

5、formational structure)形态音位形态音位(morphophononemics)例：例：S-NP VP XY-YX(掉位转化结构掉位转化结构)Hit-hit第8页，讲稿共47张，创作于星期日短语结构语法短语结构语法n乔的标准理论乔的标准理论范畴部分范畴部分:一些列改写规则一些列改写规则词库：提供每个词的语音、语法和语义信息词库：提供每个词的语音、语法和语义信息表层结构和深层结构：表层结构和深层结构：第9页，讲稿共47张，创作于星期日依存语法依存语法n又称从属关系语法，便于计算机对自然语又称从属关系语法，便于计算机对自然语言进行处理言进行处理法国语言学家特斯尼尔认为，句法的研究

6、对象法国语言学家特斯尼尔认为，句法的研究对象是句子，句子中的词语不是一盘散沙，而是有是句子，句子中的词语不是一盘散沙，而是有机的整体，句子中的词语之间是有关联的，句机的整体，句子中的词语之间是有关联的，句法关联建立起词语和词语之间的依存关系，这法关联建立起词语和词语之间的依存关系，这种依存关系由支配词和从属词连接起来。种依存关系由支配词和从属词连接起来。第10页，讲稿共47张，创作于星期日依存语法依存语法n所谓依存是指词与词之间支配与被支配所谓依存是指词与词之间支配与被支配的关系的关系,是一种有方向的不对等关系是一种有方向的不对等关系.处于支配地位的成分成为支配者处于支配地位的成分成为支配者(

7、government,head),处于被支配地位的成分成处于被支配地位的成分成为从属者为从属者(modifier,dependency)。在依存结构图中，依存语法的支配者和从属者在依存结构图中，依存语法的支配者和从属者被描述为被描述为head和和dependency，支配和被支配的，支配和被支配的关系用带有方向的边来表示。关系用带有方向的边来表示。第11页，讲稿共47张，创作于星期日依存语法依存语法n依存语法打破了传统句子中的依存语法打破了传统句子中的“主谓关系主谓关系”，提，提高了高了“谓语谓语”中动词的地位，平等了主语、宾语、中动词的地位，平等了主语、宾语、和其他句子补充成分的地位和其他句

8、子补充成分的地位n首先关注句子的动词首先关注句子的动词,再探讨其他成分与动词的关再探讨其他成分与动词的关系。系。n依存语法没有词组的概念，因而没有非终结点，依依存语法没有词组的概念，因而没有非终结点，依存语法的结构比较简单，层次和结点数比较少，因存语法的结构比较简单，层次和结点数比较少，因此，依存语法适合于中心词分析法。此，依存语法适合于中心词分析法。第12页，讲稿共47张，创作于星期日n一种形式文法一种形式文法G=VG=,P,S,其中其中,S,S表示起始表示起始符，符，S VS VN N，V VN N表示非终端语符集，表示非终端语符集，V VT T表示终端语表示终端语符集，符集，P P表示重

9、写规则（产生式）集，由有限表示重写规则（产生式）集，由有限个规则组成。个规则组成。V=VV=VN NV VT T 如果如果P P每个产生式可以描述为每个产生式可以描述为AxAx 其中其中A A是非终结符，是非终结符，x x是空或多个终结符和非终结符的序列是空或多个终结符和非终结符的序列 则则G G是上下文无关文法。是上下文无关文法。上下文无关文法上下文无关文法第13页，讲稿共47张，创作于星期日实例：一部可以用来生成若干自然语言句子的上下文实例：一部可以用来生成若干自然语言句子的上下文 无关文法的重写规则如下：无关文法的重写规则如下：S NP+VPS NP+VP NP DET+N NP DET

10、+N NP N NP N VP V+NP VP V+NP DETthe Nboys Napples VeatDETthe Nboys Napples Veat 在该例中，在该例中，S S是起始符；是起始符；the,boys,applesthe,boys,apples和和eateat是语言的终结符。是语言的终结符。第14页，讲稿共47张，创作于星期日 在自然语言处理程序中，上下文无关文法的一个重在自然语言处理程序中，上下文无关文法的一个重要特点是每个推导式都可方便的表示成一课树，这种树要特点是每个推导式都可方便的表示成一课树，这种树可以想象为被推导句子的句法结构。可以想象为被推导句子的句法结构。

11、如，使用上述文法，句子：如，使用上述文法，句子：the boys eat apples.the boys eat apples.可以用下图所示的推导树表示，同时也表明了该句是合可以用下图所示的推导树表示，同时也表明了该句是合法的句子。法的句子。SNPVPDETNtheVeatNPboysNapples第15页，讲稿共47张，创作于星期日面向短语结构语法的句法分析面向短语结构语法的句法分析第16页，讲稿共47张，创作于星期日句法分析例子句法分析例子1 1小王和小李的妹妹结婚了小王和小李的妹妹结婚了生成规则：生成规则：SNP VPNP NP C NPNP NNP NP de NVP V le词典：

12、词典：小王：小王：小李：小李：和：和：妹妹：妹妹：结婚：结婚：了：了：lele的：的：dede第17页，讲稿共47张，创作于星期日例例1 1句法分析结果句法分析结果第18页，讲稿共47张，创作于星期日句法分析的基本策略句法分析的基本策略n一个句法分析可以表述为一个搜索过程，搜索一个句法分析可以表述为一个搜索过程，搜索空间是语法规则，搜索过程是检查各种语法规空间是语法规则，搜索过程是检查各种语法规则所有可能的组合方式，目的是最终找到一种则所有可能的组合方式，目的是最终找到一种组合，其中的语法规则能够生成一棵用来表示组合，其中的语法规则能够生成一棵用来表示句子结构的句法树。句子结构的句法树。第19

13、页，讲稿共47张，创作于星期日句法分析的基本策略句法分析的基本策略句法分析通常采用的策略有：句法分析通常采用的策略有：自顶向下分析法；自顶向下分析法；自底向上分析法；自底向上分析法；左角分析法；左角分析法；其他策略。其他策略。第20页，讲稿共47张，创作于星期日自顶向下分析算法自顶向下分析算法 句法分析的过程也可以理解为句法树的构句法分析的过程也可以理解为句法树的构 造过程；造过程；所谓自顶向下分析法也就是先构造句法树所谓自顶向下分析法也就是先构造句法树 的根结点，再逐步向下扩展，直到叶结点；的根结点，再逐步向下扩展，直到叶结点；所所谓谓自自底底向向上上分分析析法法也也就就是是先先构构造造句句

14、法法树树的的叶叶结结点，再逐步向上合并，直到根结点。点，再逐步向上合并，直到根结点。请阅读请阅读P96-99该算法。该算法。第21页，讲稿共47张，创作于星期日自顶向下分析算法自顶向下分析算法n1.初始初始 当前状态为当前状态为(s)1)记为记为C，候选状态为空，候选状态为空n2.当算法未失败且算法未成功，重复：当算法未失败且算法未成功，重复：(1)若若C是空字符列且词位置到了句尾，则算法成功，返回。是空字符列且词位置到了句尾，则算法成功，返回。(2)若当前状态和候选状态都为空，且词未知未到句尾，则算若当前状态和候选状态都为空，且词未知未到句尾，则算法失败，返回。否则，产生新状态：法失败，返回

15、。否则，产生新状态：若若C中字符列的第一个字符是句子中下一个词的词类，则从字符列中中字符列的第一个字符是句子中下一个词的词类，则从字符列中移去第一个字符，并修改词位置，修改后的状态为当前状态，记为移去第一个字符，并修改词位置，修改后的状态为当前状态，记为C，转，转(2)。若若C中字符列的第一个字符是非终止符中字符列的第一个字符是非终止符，用语法中能重写，用语法中能重写的的每个规则产生新状态，产生的第一个状态为当前状态（记为每个规则产生新状态，产生的第一个状态为当前状态（记为C)，产生的其它状态加入到候选状态的栈顶，转（，产生的其它状态加入到候选状态的栈顶，转（2）.否则，回溯，从候选状态中取出

16、栈顶作为当前状态否则，回溯，从候选状态中取出栈顶作为当前状态.第22页，讲稿共47张，创作于星期日自顶向下分析算法示例自顶向下分析算法示例1分析句子：分析句子：“the dog cried”的句法结构的句法结构语法：上下文无法文法语法：上下文无法文法S-NP VP NP-ART N NP-ART ADJ NVP-V VP-V NP词典：词典：cried:V,dog:N,V,the:ART分析！分析！第23页，讲稿共47张，创作于星期日自顶向下分析算法示例自顶向下分析算法示例2分析句子：分析句子：“the old man cried”的句法结的句法结构构语法：上下文无法文法语法：上下文无法文法S

17、-NP VP NP-ART N NP-ART ADJ NVP-V VP-V NP词典：词典：the:ART,old:ADJ,N man:N,V,cried:V分析！分析！第24页，讲稿共47张，创作于星期日自顶向下分析算法示例自顶向下分析算法示例2q 要求：要求：对句子：对句子：“我是县长派来的我是县长派来的”进行句法分析。进行句法分析。q步骤：步骤：1 对句子进行分词；对句子进行分词；2 对分词后的句子进行词性标注；对分词后的句子进行词性标注；3 用自顶向下分析算法进行句法分析，最后得用自顶向下分析算法进行句法分析，最后得到一课句法树。到一课句法树。演示如下：演示如下：第25页，讲稿共47张

18、，创作于星期日第26页，讲稿共47张，创作于星期日第27页，讲稿共47张，创作于星期日第28页，讲稿共47张，创作于星期日第29页，讲稿共47张，创作于星期日第30页，讲稿共47张，创作于星期日第31页，讲稿共47张，创作于星期日第32页，讲稿共47张，创作于星期日第33页，讲稿共47张，创作于星期日第34页，讲稿共47张，创作于星期日第35页，讲稿共47张，创作于星期日第36页，讲稿共47张，创作于星期日第37页，讲稿共47张，创作于星期日第38页，讲稿共47张，创作于星期日第39页，讲稿共47张，创作于星期日第40页，讲稿共47张，创作于星期日第41页，讲稿共47张，创作于星期日第42页，讲稿共47张，创作于星期日第43页，讲稿共47张，创作于星期日第44页，讲稿共47张，创作于星期日第45页，讲稿共47张，创作于星期日第46页，讲稿共47张，创作于星期日感谢大家观看第47页，讲稿共47张，创作于星期日