《第2章语言分析基础 (2)优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第2章语言分析基础 (2)优秀PPT.ppt（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第2章语言分析基础章语言分析基础(2)1现在学习的是第1页，共41页语言分析基础语言分析基础l文法和语言概述文法和语言概述l字母表和符号串字母表和符号串l文法和语言的形式定义文法和语言的形式定义l文法的类型文法的类型l上下文无关文法及其语法树上下文无关文法及其语法树l句型的分析句型的分析l有关文法实用中的说明有关文法实用中的说明2现在学习的是第2页，共41页对于同一个句型或句子，可以通过不同的推导序列推导出来，对于同一个句型或句子，可以通过不同的推导序列推导出来，这是因为在推导过程中所选择的非终结符的次序不同。这是因为在推导过程中所选择的非终结符的次序不同。GEGE：EE+E|E*E|(E)
2、|iEE+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、自上而下分析法、自上而下分析法、自上而下分析法、自上而下分析法7现在学习的是第7页，共41页自上而下分析过程示例自上而下分析过程示例自上而下分析过程示例自上而下分析过程示例文法文法GZ:GZ:Z aBd Z aBd B d B d B c B c B b
6、B 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=规范规约与规范推导互为逆过程规范规约与规范推
9、导互为逆过程=2.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，匹配匹配【解解】试探推导过程：试探推导过程：Sc
12、AdabaS cAd cabd不匹配不匹配带回溯的自上而下分析过程带回溯的自上而下分析过程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
13、页l短语短语若若S SA A且且A A，则称，则称是是句型句型相对于非相对于非终结符终结符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 句型的分析句型
14、的分析aAcBeaAcdeaAbcdeabbcde（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
16、句型的分析句型的分析20现在学习的是第20页，共41页句型句型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棵子树，棵子树，短语和直接短语如下：短语和直接短语如下：直接短语：直接短语
17、：i i1 1，i i2 2 ，i i3 3句柄：句柄：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页有关文法的实用限制有关文法的实用限制有关文法的实用限制有关文法的实用限制在实用中，
18、文法中不应含有有害规则和多余规则。2.7 2.7 有关文法实用中的说明有关文法实用中的说明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 有关文
21、法实用中的说明有关文法实用中的说明26现在学习的是第26页，共41页 对于文法对于文法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页上下文无关文法中的上下文无关文法中的上下文无关文法中的上
22、下文无关文法中的规则规则规则规则l规则规则上下文无关文法中形式如上下文无关文法中形式如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
24、、试判断下述文法是否具有二义性：、试判断下述文法是否具有二义性：E Ei i（E E）EAEEAE A A+-*/3 3、把下面的文法改写为无二义性、把下面的文法改写为无二义性的文法：的文法：S SSSSS（S S）（）（）教科书第教科书第39页：页：6、8、1229现在学习的是第29页，共41页l 语法描述图语法描述图l 语言文法的语言文法的EBNFEBNF表示表示l 程序示例程序示例模拟程序设计语言模拟程序设计语言30现在学习的是第30页，共41页内的文字表示非终结符内的文字表示非终结符或或内的文字或符号表示终结符内的文字或符号表示终结符语法描述图语法描述图语法图符号约定语法图符号约定31
25、现在学习的是第31页，共41页语法描述图语法描述图程序Constidentnumber=,;Varident,;语句字母数字串，字母数字串，大小写不分。大小写不分。无符号数值无符号数值（整数或实数）（整数或实数）32现在学习的是第32页，共41页语法描述图语法描述图ident:=表达式条件语句Whiledo;begin语句end条件语句ifthen()readident,()write表达式语句33现在学习的是第33页，共41页条件表达式表达式=!=语法描述图语法描述图+-表达式项.+-项34现在学习的是第34页，共41页语法描述图语法描述图.项因子*/因子identnumber表达式因子()
26、35现在学习的是第35页，共41页1 1、EBNFEBNF表示的符号说明表示的符号说明 ：是非终结符：是非终结符 ：左部由右部定义：左部由右部定义|：表示：表示或或 ：表示为可以重复部分：表示为可以重复部分 ：表示为任选项：表示为任选项 ()()：表示成分优先：表示成分优先文法的文法的EBNFEBNF表示表示36现在学习的是第36页，共41页2 2、文法的、文法的EBNFEBNF表示为：表示为：CONSTCONST ,=VARVAR,文法的文法的EBNFEBNF表示表示37现在学习的是第37页，共41页|：=beginbegin；endend文法的文法的EBNFEBNF表示表示38现在学习的是
27、第38页，共41页 +|-+|-|()+|-+|-*|/*|/!=!=|=|=文法的文法的EBNFEBNF表示表示39现在学习的是第39页，共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页