第2章语言分析基础 (2)精选PPT.ppt

《第2章语言分析基础 (2)精选PPT.ppt》由会员分享，可在线阅读，更多相关《第2章语言分析基础 (2)精选PPT.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2章语言分析基础章语言分析基础(2)1第1页，此课件共41页哦语言分析基础语言分析基础l文法和语言概述文法和语言概述l字母表和符号串字母表和符号串l文法和语言的形式定义文法和语言的形式定义l文法的类型文法的类型l上下文无关文法及其语法树上下文无关文法及其语法树l句型的分析句型的分析l有关文法实用中的说明有关文法实用中的说明2第2页，此课件共41页哦对于同一个句型或句子，可以通过不同的推导序列推导出来，对于同一个句型或句子，可以通过不同的推导序列推导出来，这是因为在推导过程中所选择的非终结符的次序不同。这是因为在推导过程中所选择的非终结符的次序不同。GEGE：EE+E|E*E|(E)|iEE

2、+E|E*E|(E)|i i+i*i i+i*i的推导序列有哪些？的推导序列有哪些？2.6 2.6 句型的分析句型的分析l什么是句型分析什么是句型分析就是识别一个符号串是否为某文法的句型，是就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。某个推导的构造过程。3第3页，此课件共41页哦 最左最左(右右)推导指对于一个推导序列中的每一直接推导指对于一个推导序列中的每一直接推导，被替换的总是当前符号串中的最左推导，被替换的总是当前符号串中的最左(右右)非终结非终结符号。最右推导也称为符号。最右推导也称为规范推导（规范推导（=|=）。规范推导的逆过程，称为最左归约，也称为规范推导的逆过程，

3、称为最左归约，也称为规范归约规范归约。用最左推导所推导出的句型称为用最左推导所推导出的句型称为最左句型最左句型 用最右推导所推导出的句型称为用最右推导所推导出的句型称为最右句型最右句型，通常称为，通常称为规范规范句型。句型。规范推导和规范规约规范推导和规范规约2.6 2.6 句型的分析句型的分析4第4页，此课件共41页哦句型推导过程句型推导过程句型语法树的生长过程句型语法树的生长过程 由推导构造语法树由推导构造语法树1从从开始符号开始符号开始，开始，逐步逐步建立建立推导推导序列。序列。由由根结点根结点开始，开始，自上而下自上而下建立建立语法树语法树。2.6 2.6 句型的分析句型的分析自上而下

4、分析法自上而下分析法自上而下分析法自上而下分析法5第5页，此课件共41页哦 由语法树构造推导由语法树构造推导2自下而上自下而上地修剪子树的末端结点，直至把整棵树剪地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次规约。掉（留根），每剪一次对应一次规约。从句型开始，从句型开始，自右向左自右向左地逐步进行地逐步进行规约规约，建立推导序列。，建立推导序列。2.6 2.6 句型的分析句型的分析自下而上分析法自下而上分析法句型推导过程句型推导过程句型语法树的生长过程句型语法树的生长过程6第6页，此课件共41页哦l从推导的角度看从推导的角度看 从从文法的开始符号出发文法的开始符号出发，反复使

5、用文法的产生式，反复使用文法的产生式，寻找寻找与与输输入符号串匹配入符号串匹配的的推导推导。l从语法树的角度看从语法树的角度看 从根结点从根结点(文法的开始符号文法的开始符号)出发，出发，试图向下生长出试图向下生长出 一棵语法树一棵语法树，其叶结点组成的句子恰为输入符号串。，其叶结点组成的句子恰为输入符号串。2.6 2.6 句型的分析句型的分析1 1、自上而下分析法、自上而下分析法、自上而下分析法、自上而下分析法7第7页，此课件共41页哦自上而下分析过程示例自上而下分析过程示例自上而下分析过程示例自上而下分析过程示例文法文法GZ:GZ:Z aBd Z aBd B d B d B c B c B

6、 bB B bBZ Z aBdaBd ZaBdZaBd abBdabBd BbBBbB abcdabcdBcBc输入串输入串abcdabcd推导过程如下：推导过程如下：2.6 2.6 句型的分析句型的分析b bB BZ ZB Bd da ac c8第8页，此课件共41页哦【例例】文法文法G:S cAdG:S cAd A ab A ab A a A a 识别串识别串w=cabdw=cabd是否该文法的句子？是否该文法的句子？abcAdS推导过程：推导过程：S S cAd cAd cabd cabd自上而下分析过程示例自上而下分析过程示例自上而下分析过程示例自上而下分析过程示例2.6 2.6 句型

7、的分析句型的分析9第9页，此课件共41页哦例：例：G句型句型10=0 0=0=110=规范推导规范推导2.6 2.6 句型的分析句型的分析G：|0 0|1|2|3|910第10页，此课件共41页哦l从推导的角度看从推导的角度看从从输入符号串输入符号串开始，逐步进行归约，试图开始，逐步进行归约，试图归约归约为文法为文法的的开始符号开始符号。l从语法树的角度看从语法树的角度看从输入符号串开始，以它做为语法树的结果从输入符号串开始，以它做为语法树的结果(叶结点叶结点)，试图自底向上地构造一棵根为文法开始符号的语法试图自底向上地构造一棵根为文法开始符号的语法树。树。2.6 2.6 句型的分析句型的分析

8、2 2、自下而上分析法、自下而上分析法11第11页，此课件共41页哦【例例】文法文法G G：S cAdS cAd A ab A ab A a A a识别输入串识别输入串w=cabdw=cabd是否该文法的句子？是否该文法的句子？AabcdS归约过程：归约过程：cabdcabd cAdcAd S S对应的推导过程：对应的推导过程：S S cAd cAd cabd cabd自下而上分析过程示例自下而上分析过程示例自下而上分析过程示例自下而上分析过程示例2.6 2.6 句型的分析句型的分析12第12页，此课件共41页哦01=0=10 0=规范规约与规范推导互为逆过程规范规约与规范推导互为逆过程=2.

9、6 2.6 句型的分析句型的分析13第13页，此课件共41页哦l自上而下分析中的问题自上而下分析中的问题左递归左递归：当文法中出现左递归时，会使分析过程陷入无限循环。：当文法中出现左递归时，会使分析过程陷入无限循环。回溯回溯：假定要被代换的非终结符号是：假定要被代换的非终结符号是V V，且有，且有n n条规则：条规则：VAVA1 1|A|A2 2|A|An n，那么如何确定用哪个右部，那么如何确定用哪个右部A Ai i去替代去替代V V呢？呢？这会造成回溯。这会造成回溯。自下而上分析中的问题自下而上分析中的问题可归约串可归约串：在分析程序工作的每一步，都是从当前串中选择一个子串，将它：在分析程

10、序工作的每一步，都是从当前串中选择一个子串，将它归约到一个句型，该子串称为归约到一个句型，该子串称为“可归约串可归约串”（也叫短语）。（也叫短语）。如何确定可归约的串？把它归约为哪个非终结符号串？如何确定可归约的串？把它归约为哪个非终结符号串？2.6 2.6 句型的分析句型的分析14第14页，此课件共41页哦自上而下分析中的问题示例自上而下分析中的问题示例自上而下分析中的问题示例自上而下分析中的问题示例【例例】文法文法G G：S cAdS cAd A Ab A Ab A a A a 识别输入串识别输入串w=cadw=cad是否该文法的句子。是否该文法的句子。【解解】试探推导过程：试探推导过程：

11、ScAdAbS cAd cAbd左递归文法的自上而下分析过程左递归文法的自上而下分析过程2.6 2.6 句型的分析句型的分析 cAbbd AbAb cAbbbd15第15页，此课件共41页哦自上而下分析中的问题示例自上而下分析中的问题示例自上而下分析中的问题示例自上而下分析中的问题示例【例例】文法文法G G：S cAdS cAd A ab A ab A a A a 识别输入串识别输入串w=cadw=cad是否该文法的句子。是否该文法的句子。回朔回朔:试探推导过程：试探推导过程：S S cAd cAd cad cad，匹配匹配【解解】试探推导过程：试探推导过程：ScAdabaS cAd cabd

12、不匹配不匹配带回溯的自上而下分析过程带回溯的自上而下分析过程2.6 2.6 句型的分析句型的分析16第16页，此课件共41页哦【例例】文法文法G G：S cAdS cAd A ab A ab A a A a 识别输入串识别输入串w=cabdw=cabd是否该文法的句子。是否该文法的句子。【解解 】试探归约过程：试探归约过程：cabd无法归无法归约到约到S S！说明a不是该句型中的可归约串。2.6 2.6 句型的分析句型的分析 cAbd自下而上分析中的问题示例自下而上分析中的问题示例自下而上分析中的问题示例自下而上分析中的问题示例17第17页，此课件共41页哦l短语短语若若S SA A且且A A

13、，则称，则称是是句型句型相对于非终相对于非终结符结符A A的的短语短语。l简单短语（直接短语）简单短语（直接短语）若若S SAA且且A A，则称，则称是句型是句型相对于非相对于非终结符终结符A A的简单短语。的简单短语。l句柄句柄一个句型的最左简单短语。一个句型的最左简单短语。短语2.6 2.6 句型的分析句型的分析+*18第18页，此课件共41页哦文法文法 GSGS：(1)S aAcBe(1)S aAcBe (2)A b (2)A b (3)A Ab (3)A Ab (4)B d (4)B d短语、句柄示例短语、句柄示例2.6 2.6 句型的分析句型的分析aAcBeaAcdeaAbcdeab

14、bcde（1）（4）（3）（2）句子句子abbcdeabbcde的推导过程的推导过程S d d是句型是句型aAcdeaAcde的（相对的（相对B B）短语且为简单短语、句柄；）短语且为简单短语、句柄；AbAb是句型是句型aAbcdeaAbcde（相对（相对“aAcdeaAcde”中的中的A A）的简单短语，句柄；）的简单短语，句柄；bbbb是句型是句型abbcde abbcde（相对（相对“aAcdeaAcde”中的中的A A）的短语；）的短语；b b是句型是句型abbcde abbcde（相对（相对“aAbcdeaAbcde”中的中的A A）的短语，且）的短语，且是句柄。是句柄。不能离开句型

15、讨论这些概念19第19页，此课件共41页哦l子树：就是语法树的某个结点连同它的所有后代。子树：就是语法树的某个结点连同它的所有后代。l简单子树：只含有单层分枝的子树。简单子树：只含有单层分枝的子树。l子树与短语的关系子树与短语的关系 (1)(1)短语：子树的末端结点短语：子树的末端结点(即树叶即树叶)组成的符号串；组成的符号串；(2)(2)直接短语：简单子树的末端结点组成的符号串；直接短语：简单子树的末端结点组成的符号串；(3)(3)句柄：最左简单子树的末端结点组成的符号串。句柄：最左简单子树的末端结点组成的符号串。子树和短语的关系2.6 2.6 句型的分析句型的分析20第20页，此课件共41

16、页哦句型句型E+E*iE+E*i的语法树有的语法树有3 3棵子树，棵子树，即即3 3个短语。个短语。E+E*iE+E*i的语法树的语法树分别为分别为i i、E*iE*i和和E+E*iE+E*i；直接短语、句柄均为直接短语、句柄均为i i。从语法树中可以看出，所有树叶的组合就是其相对应的父结点的短语。子树和短语的关系示例2.6 2.6 句型的分析句型的分析21第21页，此课件共41页哦EFTT*Fi1i2Fi3ET+句型句型i*i+ii*i+i的语法树有的语法树有8 8棵子树，棵子树，短语和直接短语如下：短语和直接短语如下：直接短语：直接短语：i i1 1，i i2 2 ，i i3 3句柄：句柄

17、：i i1 1短语：短语：i i1 1，i i2 2，i i3 3，i i1 1*i*i2 2，i i1 1*i*i2 2+i+i3 3 i2+i3不是短语不是短语不是某棵子树的结果不是某棵子树的结果2.6 2.6 句型的分析句型的分析子树和短语的关系示例22第22页，此课件共41页哦2.7 2.7 有关文法实用中的说明有关文法实用中的说明l有关文法的实用限制有关文法的实用限制l上下文无关文法中的上下文无关文法中的规则规则23第23页，此课件共41页哦有关文法的实用限制有关文法的实用限制有关文法的实用限制有关文法的实用限制在实用中，文法中不应含有有害规则和多余规则。2.7 2.7 有关文法实用

18、中的说明有关文法实用中的说明1 1、若文法中有如、若文法中有如U:=UU:=U的规则，则这就是的规则，则这就是有害规则有害规则，它会引，它会引 起二义性，而无任何用处。起二义性，而无任何用处。例如存在例如存在U:=UU:=U，U:=a|b,U:=a|b,则则a a有两棵语法树：有两棵语法树：UaUUa24第24页，此课件共41页哦 2、多余规则多余规则：（1）某条规则）某条规则U:=u的左部非终结符的左部非终结符U（U不是开始符号），不在任何不是开始符号），不在任何 其他规则右部出现，即所有的推导始终不会用到此规则，该非终其他规则右部出现，即所有的推导始终不会用到此规则，该非终 结符称为结符称

19、为不可到达不可到达。（2）在推导句子的过程中，一旦使用了该规则，将推不出任何终结符）在推导句子的过程中，一旦使用了该规则，将推不出任何终结符 号串。即该规则中含有推不出任何终结符号串的非终结符。该非号串。即该规则中含有推不出任何终结符号串的非终结符。该非 终结符称为终结符称为不可终止。不可终止。例如给定例如给定GSGS，若其中关于，若其中关于U U的规则的规则只只有如下一条：有如下一条：U:=xUyU:=xUy 该规则是多余规则。该规则是多余规则。若还有若还有U:=aU:=a，则，则此规则并非多余。此规则并非多余。若某文法中无有害规则或多余规则，则称该文法是若某文法中无有害规则或多余规则，则称

20、该文法是压缩过的压缩过的。2.7 2.7 有关文法实用中的说明有关文法实用中的说明25第25页，此课件共41页哦文法中存在多余规则示例文法中存在多余规则示例文法中存在多余规则示例文法中存在多余规则示例【例例】GSGS：1)SBe1)SBe 2)BCe 2)BCe 3)BAf 3)BAf 4)AAe 4)AAe 5)Ae 5)Ae 6)CCf 6)CCf 7)Df 7)Df C C为不可终止为不可终止 产生式产生式2 2）,6,6）,7,7）为多余规则应去掉。）为多余规则应去掉。D D为不可到达为不可到达2.7 2.7 有关文法实用中的说明有关文法实用中的说明26第26页，此课件共41页哦 对于

21、文法对于文法GSGS，为了保证任一非终结符，为了保证任一非终结符A A在句子推导中在句子推导中出现，必须满足如下两个条件：出现，必须满足如下两个条件：1.A1.A必须在某句型中出现：即有必须在某句型中出现：即有S S=AA，其中，其中 ，属于属于V V*。2.2.必须能够从必须能够从A A推出终结符号串推出终结符号串t t来：即来：即A A=t t，其中其中tVtVT T*。2.7 2.7 有关文法实用中的说明有关文法实用中的说明*27第27页，此课件共41页哦上下文无关文法中的上下文无关文法中的上下文无关文法中的上下文无关文法中的规则规则规则规则l规则规则上下文无关文法中形式如上下文无关文法

22、中形式如AA的规则。的规则。文法中有无文法中有无规则的唯一差别是规则的唯一差别是句子在不在语言中。句子在不在语言中。l因为因为规则会使得有关文法的一些讨论和证明变得复杂，有时会限制这种规则的出规则会使得有关文法的一些讨论和证明变得复杂，有时会限制这种规则的出现。现。文法构思的启示是要找出语言的有穷描述，而如果语言文法构思的启示是要找出语言的有穷描述，而如果语言L L有一个有一个 有穷的描述，则有穷的描述，则L1=LL1=L也同样有一个有穷的描述，并且可以也同样有一个有穷的描述，并且可以 证明，若证明，若L L是上下文有关语言、上下文无关语言或正规语言，则：是上下文有关语言、上下文无关语言或正规

23、语言，则：LL和和L-L-分别是上下文有关语言、上下文无关语言和正分别是上下文有关语言、上下文无关语言和正 规语言。规语言。2.7 2.7 有关文法实用中的说明有关文法实用中的说明28第28页，此课件共41页哦 作业作业1 1、设文法、设文法G G：E ET T E+TE+T E-TE-T T TF F T*FT*F T/FT/F F F（E E）I I试给出关于（试给出关于（i i）与（）与（i+ii+i）/i/i的推导。的推导。证明证明E+T*F*i+iE+T*F*i+i是该文法的句型是该文法的句型 。2 2、试判断下述文法是否具有二义性：、试判断下述文法是否具有二义性：E Ei i（E

24、E）EAEEAE A A+-*/3 3、把下面的文法改写为无二义性、把下面的文法改写为无二义性的文法：的文法：S SSSSS（S S）（）（）教科书第教科书第39页：页：6、8、1229第29页，此课件共41页哦l 语法描述图语法描述图l 语言文法的语言文法的EBNFEBNF表示表示l 程序示例程序示例模拟程序设计语言模拟程序设计语言30第30页，此课件共41页哦内的文字表示非终结符内的文字表示非终结符或或内的文字或符号表示终结符内的文字或符号表示终结符语法描述图语法描述图语法图符号约定语法图符号约定31第31页，此课件共41页哦语法描述图语法描述图程序Constidentnumber=,;V

25、arident,;语句字母数字串，字母数字串，大小写不分。大小写不分。无符号数值无符号数值（整数或实数）（整数或实数）32第32页，此课件共41页哦语法描述图语法描述图ident:=表达式条件语句Whiledo;begin语句end条件语句ifthen()readident,()write表达式语句33第33页，此课件共41页哦条件表达式表达式=!=语法描述图语法描述图+-表达式项.+-项34第34页，此课件共41页哦语法描述图语法描述图.项因子*/因子identnumber表达式因子()35第35页，此课件共41页哦1 1、EBNFEBNF表示的符号说明表示的符号说明 ：是非终结符：是非终结

26、符 ：左部由右部定义：左部由右部定义|：表示：表示或或 ：表示为可以重复部分：表示为可以重复部分 ：表示为任选项：表示为任选项 ()()：表示成分优先：表示成分优先文法的文法的EBNFEBNF表示表示36第36页，此课件共41页哦2 2、文法的、文法的EBNFEBNF表示为：表示为：CONSTCONST ,=VARVAR,文法的文法的EBNFEBNF表示表示37第37页，此课件共41页哦|：=beginbegin；endend文法的文法的EBNFEBNF表示表示38第38页，此课件共41页哦 +|-+|-|()+|-+|-*|/*|/!=!=|=|=文法的文法的EBNFEBNF表示表示39第3

27、9页，此课件共41页哦 IfIfthenthen WhileWhileDODO ReadRead(，)WriteWrite(，)文法的文法的EBNFEBNF表示表示40第40页，此课件共41页哦 CONST A=10;CONST A=10;（*常量说明部分常量说明部分*）VAR X;VAR X;（*变量说明部分变量说明部分*）BEGINBEGIN READ(X);READ(X);WHILE A WHILE A!=0 DO0 DO BEGIN BEGIN X:=X+1;A:=A-1 X:=X+1;A:=A-1 END;END;WRITE(X);WRITE(X);END.END.程序示例程序示例41第41页，此课件共41页哦