编译原理课程设计之第三章上下文无关文法及分析.ppt

《编译原理课程设计之第三章上下文无关文法及分析.ppt》由会员分享，可在线阅读，更多相关《编译原理课程设计之第三章上下文无关文法及分析.ppt（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、w课程内容课程内容第一章第一章 概论概论第二章第二章 词法分析词法分析第三章第三章上下文无关文法及分析上下文无关文法及分析第四章第四章自上而下的语法分析自上而下的语法分析第五章第五章自下而上的语法分析自下而上的语法分析第六章第六章语义分析语义分析第七章第七章运行时环境运行时环境第八章第八章代码生成代码生成mcy1第三章第三章 上下文无关文法及分析上下文无关文法及分析本章的目的是为语言的语法本章的目的是为语言的语法描述寻求形式工具，要求该描述寻求形式工具，要求该工具对程序设计语言给出精工具对程序设计语言给出精确无二义的语法描述。确无二义的语法描述。mcy23.1 3.1 语法分析过程语法分析过程

2、3.2 3.2 上下文无关文法的形式定义上下文无关文法的形式定义3.3.3 3 二义性文法二义性文法形式形式工工具具作业作业第三章第三章 上下文无关文法及分析上下文无关文法及分析mcy3语法分析以词法分析程序输出的单词序列为输语法分析以词法分析程序输出的单词序列为输入，分析源程序的语法结构，判断它是否为相入，分析源程序的语法结构，判断它是否为相应程序设计语言的合法程序。应程序设计语言的合法程序。通常通常语法分析的结果是语法分析的结果是构造出表示该语法结构构造出表示该语法结构的的分析树（分析树（parsetree）或语法树或语法树(syntaxtree)。语法分析阶段可以确定单词流中违反源语言语

3、语法分析阶段可以确定单词流中违反源语言语法结构规则的错误。法结构规则的错误。语法分析程序的任务语法分析程序的任务：3.1 3.1 语法分析过程语法分析过程mcy4如何来描述一种语言如何来描述一种语言(符号串的集合符号串的集合)？如果语言是有穷的如果语言是有穷的(只含有有穷个句子只含有有穷个句子)，可以将句子逐一列出来表示。可以将句子逐一列出来表示。如果语言是无穷的，找出语言的有穷表示。如果语言是无穷的，找出语言的有穷表示。mcy5语言的有穷表示有两个途经：语言的有穷表示有两个途经：w生成方式生成方式(文法文法)：语言中的每个句子可以用：语言中的每个句子可以用严格定义的规则来构造。严格定义的规则

4、来构造。w识别方式识别方式(自动机自动机)：用一个过程，当输入的：用一个过程，当输入的一任意串属于语言时，该过程经有限次计一任意串属于语言时，该过程经有限次计算后就会停止并回答算后就会停止并回答“是是”，若不属于，若不属于，要么能停止并回答要么能停止并回答“不是不是”，要么永远继，要么永远继续下去续下去。mcy6Number=digitdigit*Digit=0|1|2|3|4|5|6|7|8|9正规表达式：？正规表达式：？有穷自动机：？有穷自动机：？寻求程序设计语言语法结构的形式化描述：寻求程序设计语言语法结构的形式化描述：mcy7Noam Chomsky研究了自然语言的结构，研究了自然语言

5、的结构，提出了一种用来描述语言的提出了一种用来描述语言的数学系统数学系统(Chomsky文法文法)，并以此定义了四类性质，并以此定义了四类性质不同的语言，称为不同的语言，称为语言（文法）的语言（文法）的Chomsky分类分类。mcy8wChomsky文法分为四个层次文法分为四个层次：0型，型，1型，型，2型和型和3型文法。型文法。其中其中2型型文法（或文法（或上下文无关文法上下文无关文法）被证明是程）被证明是程序设计语言中最有用的。序设计语言中最有用的。今天今天2型语言已代表着程序设计语言语法结构的型语言已代表着程序设计语言语法结构的标准方式。标准方式。mcy9Chomsky文法文法就是用就是

6、用生成方式来生成方式来描述语言的：语言描述语言的：语言中的每个句子可以用严格定义的规则来构造。中的每个句子可以用严格定义的规则来构造。文法示例：文法示例：简单句子的语法结构可有以下规则表示简单句子的语法结构可有以下规则表示:mcy10w问问:下面的语句是否是一个符合上述语法结构的简单句下面的语句是否是一个符合上述语法结构的简单句子？子？The big elephant ate the peanut.冠词冠词 形容词形容词 名词名词 动词动词 冠词冠词 名词名词w我们把上述两个字符串中间用一箭头分隔构成的有序我们把上述两个字符串中间用一箭头分隔构成的有序对称为对称为产生式产生式。其中，。其中，“

7、”表示表示“由由组成组成”,“”也可以用也可以用=，:=，:来代替。来代替。mcy11例如：包含加法、减法和乘法的简单整型算例如：包含加法、减法和乘法的简单整型算术表达式的语法结构可由下面的术表达式的语法结构可由下面的上下文无关上下文无关文法文法(2(2型文法型文法)给出：给出：exp exp exp op exp exp op expexp exp(expexp)exp exp numbernumberop op +|-|*mcy123.1 3.1 语法分析过程语法分析过程3.2 3.2 上下文无关文法的形式定义上下文无关文法的形式定义3.3.3 3 二义性文法二义性文法形式形式工工具具作业

8、作业第三章第三章 上下文无关文法及分析上下文无关文法及分析mcy133.2 3.2 上下文无关文法的形式定义上下文无关文法的形式定义1.1.上下文无关文法上下文无关文法(即即2 2型文法型文法)的形式定义的形式定义2.2.chomskychomsky文法的分类文法的分类3.3.推导和规约的定义推导和规约的定义4.4.句型和句子的定义句型和句子的定义5.5.最左和最右推导最左和最右推导6.6.文法定义的语言文法定义的语言7.7.递归产生式和递归文法递归产生式和递归文法8.8.文法和语言文法和语言mcy14终结符集合终结符集合VT非终结符集合非终结符集合VN(与与VT不相交不相交)产生式或文法规则

9、产生式或文法规则A形成的形成的集合集合P,其中其中AVN,(VTVN)*4)4)开始符号开始符号S，其中，其中SVN令令G G是一个如上所定义的文法，则是一个如上所定义的文法，则G=(VT,VN,P,S)产生式产生式的左部的左部产生式产生式的右部的右部1.1.上下文无关文法上下文无关文法(即即2 2型文法型文法)的形式定义的形式定义：上下文无关上下文无关文法是一个四元组文法是一个四元组(VT,VN,P,S)：mcy15例例 G1=(N,0，1,其中其中:非终结符集合：非终结符集合：VN=N终结符集合：终结符集合：VT=0，1产生式的集合：产生式的集合：P=N0N，N1N，N0，N1开始符号为：

10、开始符号为：N文法举例文法举例N0N,N1N,N0,N1,N）mcy16通常情况下，通常情况下，文法只用产生式的集合文法只用产生式的集合表示：表示：G1N:N0NN1NN0N1G1N:N0N|1N|0|1也可写成：也可写成：mcy17文法文法Gexpexp exp op expexp(exp)exp numberop+|-|*的终结符、非终结符、开始符号分别为？的终结符、非终结符、开始符号分别为？mcy183.2 3.2 上下文无关文法的形式定义上下文无关文法的形式定义1.1.上下文无关文法上下文无关文法(即即2 2型文法型文法)的形式定义的形式定义2.2.chomskychomsky文法的分

11、类文法的分类3.3.推导和规约的定义推导和规约的定义4.4.句型和句子的定义句型和句子的定义5.5.最左和最右推导最左和最右推导6.6.文法定义的语言文法定义的语言7.7.递归产生式和递归文法递归产生式和递归文法8.8.文法和语言文法和语言mcy192.chomsky文法的分类文法的分类通过对产生式施加不同的限制，通过对产生式施加不同的限制，chomsky将文法分为四种类型：将文法分为四种类型：0 0型文法：若文法型文法：若文法G中任一产生式中任一产生式，都有都有(V(VN NVVT T)+，(V(VN NVVT T)*，则称则称G G为为0 0型文法型文法1 1型文法型文法：若文法若文法G中

12、任一产生式中任一产生式，都有都有(V(VN NVVT T)+，(V(VN NVVT T)*|，仅仅仅仅 SS除外，则称除外，则称G G为为1 1型文法型文法2 2型文法型文法：若文法若文法G中任一产生式中任一产生式，都有都有VVN N，(V(VN NVVT T)*，则称则称G G为为2 2型文法，也称为型文法，也称为上下文无关文法上下文无关文法mcy20w3型文法：型文法：通常，我们把右线性文法及左线性文法通常，我们把右线性文法及左线性文法统称为统称为3型文法型文法或或正规文法正规文法。若文法若文法G中任一产生式中任一产生式的形式都为的形式都为AaB 或或 Aa，其中其中 A VN，B VN，

13、a VT，则称，则称G为右线性文法为右线性文法；类似地，如果类似地，如果G中仅含有形如中仅含有形如ABa 或或 Aa的的产生式，则称产生式，则称G为左线性文法为左线性文法；mcy21例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS：SCD SCD AbbA AbbA CaCA CaCA BaaB BaaB CbCB CbCB BbbB BbbB ADaD ADaD C C BDbD BDbD D D AabD AabDmcy22例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GSGS：SABSAB ABS|0 ABS|0 BSA|1 BSA|1mcy23

14、GSGS：S0A|1B|0S0A|1B|0 A0A|1B|0SA0A|1B|0S B1B|1|0B1B|1|0例：例：3 3型（上下文无关）文法型（上下文无关）文法mcy24文法文法Gexp：exp exp op expexp(exp)exp numberop+|-|*下面的下面的2 2型文法描述了包含加法、减法和乘法的简型文法描述了包含加法、减法和乘法的简单整型算术表达式的语法结构。单整型算术表达式的语法结构。34-3 34-3 是符合该是符合该语法结构的简单语法结构的简单整型算术表达式整型算术表达式(句子句子)吗？吗？mcy253.2 3.2 上下文无关文法的形式定义上下文无关文法的形式定

15、义1.1.上下文无关文法上下文无关文法(即即2 2型文法型文法)的形式定义的形式定义2.2.chomskychomsky文法的分类文法的分类3.3.推导和规约的定义推导和规约的定义4.4.句型和句子的定义句型和句子的定义5.5.最左和最右推导最左和最右推导6.6.文法定义的语言文法定义的语言7.7.递归产生式和递归文法递归产生式和递归文法8.8.文法和语言文法和语言mcy263.3.推导和规约的定义推导和规约的定义用产生式用产生式(规则规则)按一定方式产生句子的过程：按一定方式产生句子的过程：exp exp op exp numberop exp number-exp number-numbe

16、r expnumber-numbermcy27直接推导直接推导“”或或一步推导一步推导w若有若有v,w满足：满足：v=,w=其中：其中：是文法是文法G的产生式，的产生式，(VT VN)*,(VT VN)*则称则称v直接推导到直接推导到w,记作记作 v w，称称w直接归直接归约到约到v。w注：直接推导就是产生式规则的一次运用，注：直接推导就是产生式规则的一次运用，即用产生式的右部替换左部。即用产生式的右部替换左部。mcy28例：例：GSGS：S0S1S0S1，S01S01 直接推导：直接推导：S S 0S10S10 0S S1 1 0 00S10S11 10000S S11 11 00 000S

17、10S11111000000S S111 111 000 0000101111111mcy29推导的定义推导的定义w若存在若存在v=w0w1.wn=w(n0),我们用我们用v=+w表示表示一步或多步推导一步或多步推导，称，称v v推导出推导出w w，或或w归约到归约到v；w若有若有v=+w，或或v=w，则记为则记为v=*w，表示表示零步或多步推导零步或多步推导。mcy30例：例：GSGS：S0S1 S0S1，S01 S01 S S 0S10S100S1100S11000S111000S11100001111 00001111 S S +00001111+00001111给出字符串给出字符串00

18、001111的一个推导：的一个推导：mcy313.2 3.2 上下文无关文法的形式定义上下文无关文法的形式定义1.1.上下文无关文法上下文无关文法(即即2 2型文法型文法)的形式定义的形式定义2.2.chomskychomsky文法的分类文法的分类3.3.推导和规约的定义推导和规约的定义4.4.句型和句子的定义句型和句子的定义5.5.最左和最右推导最左和最右推导6.6.文法定义的语言文法定义的语言7.7.递归产生式和递归文法递归产生式和递归文法8.8.文法和语言文法和语言mcy32定义定义4 4 句型和句子句型和句子:设设G=(VN,VT,P,S)是一文是一文法法,且且 V=VNVT若若S=*

19、,V*,则称则称为文法为文法G的句型；的句型；若若S=+,VT*,则称则称为文法为文法G的句子；的句子；4.4.句型和句子的定义句型和句子的定义mcy33w简单整型算术表达式文法：简单整型算术表达式文法：exp exp op exp|(exp)|numberop +|-|*w给出算术表达式（给出算术表达式（34-3）*42的一个推导，请的一个推导，请列出推导过程中出现的句型和句子。列出推导过程中出现的句型和句子。mcy34 算术表达式（算术表达式（34-334-3）*42*42的推导：的推导：exp exp exp op expexp op exp exp op exp op numbernu

20、mber exp*exp*number number (expexp)*numbernumber (exp op expexp op exp)*numbernumber (exp op exp op number)number)*numbernumber (exp-exp-number)number)*numbernumber (number(number-number)*number)*numbernumbermcy353.2 3.2 上下文无关文法的形式定义上下文无关文法的形式定义1.1.上下文无关文法上下文无关文法(即即2 2型文法型文法)的形式定义的形式定义2.2.chomskycho

21、msky文法的分类文法的分类3.3.推导和规约的定义推导和规约的定义4.4.句型和句子的定义句型和句子的定义5.5.最左和最右推导最左和最右推导6.6.文法定义的语言文法定义的语言7.7.递归产生式和递归文法递归产生式和递归文法8.8.文法和语言文法和语言mcy365.5.最左和最右推导最左和最右推导最左推导最左推导对于文法对于文法GS:S S 是一个最左推导是一个最左推导是指：是指：在推导过程中的任何一步直接推导在推导过程中的任何一步直接推导，都是对字符串都是对字符串中的最左非终结符进行替换，中的最左非终结符进行替换，其中其中、是句型。是句型。简单整型算术表达式文法：简单整型算术表达式文法：

22、exp exp exp op exp exp op exp|(|(expexp)|)|numbernumber op op +|-|*mcy37 exp exp exp exp op expop exp (expexp)op exp)op exp (expexp op exp op exp)op exp op exp (number(number op op expexp)op exp op exp (number(number-expexp)op exp op exp (number(number-number)number)opop exp exp (number(number-numbe

23、r)*number)*expexp (number(number-number)*number)*numbernumber算术表达式（算术表达式（34-3）*42的的最左推导最左推导：mcy38最右推导最右推导：S S 是一个最右推导是指：是一个最右推导是指：在在推导过程中的任何一步直接推导推导过程中的任何一步直接推导，都是对都是对字符串字符串中的最右非终结符进行替换中的最右非终结符进行替换，其中，其中、是句型是句型。最右推导也被称为最右推导也被称为规范推导规范推导。由规范推导所得。由规范推导所得的句型称为的句型称为规范句型。规范句型。mcy39 算术表达式（算术表达式（34-334-3）*4

24、2*42的的最右推导最右推导：exp exp exp op exp op expexp exp exp opop numbernumber expexp*number number (expexp)*numbernumber (exp op exp op expexp)*numbernumber (exp exp opop number)number)*numbernumber (expexp-number)number)*numbernumber (number(number-number)*number)*numbernumbermcy40expexpexp op expexp op ex

25、p numbernumber op exp op exp numbernumber+exp+exp numbernumber +numbernumber简单整型算术表达式文法：简单整型算术表达式文法：exp exp exp op exp exp op exp|(|(expexp)|)|numbernumberop op +|-|*给出符号串给出符号串3+43+4的最左推导的最左推导:？mcy41expexpexp op expexp op exp exp op exp op numbernumber exp+exp+numbernumber number number+numbernumber

26、给出符号串给出符号串3+43+4的最右推导？的最右推导？mcy423.2 3.2 上下文无关文法的形式定义上下文无关文法的形式定义1.1.上下文无关文法上下文无关文法(即即2 2型文法型文法)的形式定义的形式定义2.2.chomskychomsky文法的分类文法的分类3.3.推导和规约的定义推导和规约的定义4.4.句型和句子的定义句型和句子的定义5.5.最左和最右推导最左和最右推导6.6.文法定义的语言文法定义的语言7.7.递归产生式和递归文法递归产生式和递归文法8.8.文法和语言文法和语言mcy436.6.文法定义的语言文法定义的语言w文法定义的语言文法定义的语言：根据文法可以推导出任一句型

27、和句子，而根据文法可以推导出任一句型和句子，而所有所有句子的集合句子的集合则为则为该文法所对应的语言该文法所对应的语言；即语言是所有句子构成的集合，它是所有终结即语言是所有句子构成的集合，它是所有终结符号串所组成的集合符号串所组成的集合VT*的子集。的子集。mcy44文法文法GS定义的语言定义的语言L(G)L(G)表示为表示为：L(G)=x|S=+x,其中其中S为开始符号为开始符号,xVT*L(G)VT*即即L(G)是由开始符号是由开始符号S S推导出的句子的集合。上下文推导出的句子的集合。上下文无关文法定义的语言称作无关文法定义的语言称作上下文无关语言上下文无关语言。mcy45文法定义的语言

28、举例文法定义的语言举例例例1 1：有文法：有文法GZ:GZ:(1)Z aZb (1)Z aZb (2)Z ab (2)Z ab它定义的它定义的语言语言是什么？是什么？由由(2)(2)知知:Zab ab 故故abab是文法的一个句子是文法的一个句子mcy46由由(1)(2)(1)(2)知知:ZaZba2b2 故故a2b2是文法的一个句子是文法的一个句子反复使用产生式反复使用产生式(1)(1)：ZaZba2Zb2an-1Zbn-1anbn所以上述文法所定义的语言为：所以上述文法所定义的语言为：L(GZ)=anbn|n 1mcy47例例2 2：已知语言：已知语言为为L(G)=abna|n 1 试给试

29、给出其文法。出其文法。G G1 1Z:Z aBaZ:Z aBa B bB|b B bB|bG G2 2Z:Z aBaZ:Z aBa B Bb|b B Bb|b结论结论：给定一种语言：给定一种语言L L，能确定其文法，但这种文法能确定其文法，但这种文法可能不是唯一的：可能不是唯一的：L LG G1 1或或G G2 2等价文法等价文法：如果：如果L(GL(G1 1)=L(GL(G2 2)，那么称那么称G G1 1和和G G2 2为等价为等价文法。文法。mcy483.2 3.2 上下文无关文法的形式定义上下文无关文法的形式定义1.1.上下文无关文法上下文无关文法(即即2 2型文法型文法)的形式定义的

30、形式定义2.2.chomskychomsky文法的分类文法的分类3.3.推导和规约的定义推导和规约的定义4.4.句型和句子的定义句型和句子的定义5.5.最左和最右推导最左和最右推导6.6.文法定义的语言文法定义的语言7.7.递归产生式和递归文法递归产生式和递归文法8.8.文法和语言文法和语言mcy49设给定文法设给定文法G=(VN,VT,P,S),若存在产生式若存在产生式AxAyP ，则称产生式，则称产生式AxAy是是递归产生式递归产生式；x，y(VNVT)*若若x=x=且且y y,则称产生式则称产生式A AAyAy是是左递归左递归产生式；产生式；若若xx且且y=,y=,则称产生式则称产生式A

31、 Ax xA A是是右递归右递归产生式。产生式。7.7.递归产生式和递归文法递归产生式和递归文法mcy50递归文法递归文法：w若文法中至少存在一条递归产生式则称该文法是若文法中至少存在一条递归产生式则称该文法是直直接递归的文法接递归的文法；w若有若有A+xAy,x,y(VN VT)*则称文法为则称文法为间接递归的间接递归的文法。文法。即对于文法中任一非终结符号，若能建立一个推导过程，即对于文法中任一非终结符号，若能建立一个推导过程，在推导所得的符号串中又出现了该非终结符号本身，则在推导所得的符号串中又出现了该非终结符号本身，则文法是递归的。文法是递归的。一般的文法都是递归的，文法一般的文法都是

32、递归的，文法G只有递归定义，只有递归定义，L(G)中的中的句子才是无穷的句子才是无穷的。mcy51例：有文法例：有文法GS:GS:S aB|bBS aB|bBB a|bB a|b是否是递归文法，定义的语言为？是否是递归文法，定义的语言为？非递归文法，非递归文法，L(GS)=aa,ab,ba,bbL(GS)=aa,ab,ba,bbmcy523.2 3.2 上下文无关文法的形式定义上下文无关文法的形式定义1.1.上下文无关文法上下文无关文法(即即2 2型文法型文法)的形式定义的形式定义2.2.chomskychomsky文法的分类文法的分类3.3.推导和规约的定义推导和规约的定义4.4.句型和句子

33、的定义句型和句子的定义5.5.最左和最右推导最左和最右推导6.6.文法定义的语言文法定义的语言7.7.递归产生式和递归文法递归产生式和递归文法8.8.文法和语言文法和语言mcy538.8.文法和语言文法和语言0型文法产生的语言称为型文法产生的语言称为0型语言型语言，它可由，它可由图灵机图灵机识别识别。1型文法或上下文有关文法型文法或上下文有关文法(CSG）产生的语言称产生的语言称为为1型语言或上下文有关语言型语言或上下文有关语言(CSL)，它可由它可由线性线性线界自动机识别线界自动机识别。2型文法或型文法或上下文无关文法上下文无关文法（CFG）产生的语言产生的语言称为称为2型语言或型语言或上下

34、文无关语言上下文无关语言（CFL），），它可它可由下推自动机识别由下推自动机识别。mcy54w3型型文法或正则文法或正则(正规正规)文法文法(RG)产生的语言称产生的语言称为为3型语言型语言正则正则(正规正规)语言语言(RL)，它可由它可由有限有限自动机识别自动机识别。w语言之间的关系依次：有不是语言之间的关系依次：有不是1型语言的型语言的0型型语言，有不是语言，有不是2型语言的型语言的1型语言，有不是型语言，有不是3型型语言的语言的2型语言。型语言。mcy55Number=digitdigit*Digit=0|1|2|3|4|5|6|7|8|9正规式正规式Number定义的正规集？定义的正规

35、集？Number Number (0|1|2|3|4|5|6|7|8|9)NumberNumberNumber Number 0|1|2|3|4|5|6|7|8|9例如，例如，3 3型文法型文法(正规文法正规文法)产生的语言？产生的语言？mcy561.1.对对 上的上的正规式正规式r,存在一个存在一个3 3型文法型文法G=(VN，VT，P，S)：L(G)=L(r)2.2.对对3 3型文法型文法G=(VN，VT，P，S),存在一个存在一个=VT上的上的正规式正规式r:L(r)=L(G)3.3.设设G=G=（V VN N,V,VT T,P,S,P,S）是是3 3型文法型文法，则存在，则存在一个有穷

36、一个有穷自动机自动机 M=(S,T,sM=(S,T,s0 0,A),A)，使得使得L(M)=L(G)L(M)=L(G)4.4.已知一有已知一有穷自动机穷自动机M=(S,T,s0,A),存在有存在有一个一个3 3型文法型文法G=(VN,VT,P,S),使得使得L(G)=L(M)。与与3 3型文法有关的定理型文法有关的定理mcy571.1.对对 上的上的正规式正规式r,存在一个存在一个3 3型文法型文法G=(VN，VT，P，S)：L(G)=L(r)1)1)初始初始令令VT=，引入开始符号，引入开始符号S S，生成正规产生成正规产生式生式 S Sr r 2)2)对形如对形如A Ar r1 1r r2

37、 2的的正规产生式：正规产生式：A Ar r1 1B B B Br r2 2 B B V VN Nmcy583)3)对形如对形如A Ar r r r1 1的的正规产生式：正规产生式：A ArBrB A Ar r1 1 B BrBrB B Br r1 1 B B V VN N mcy594)4)对形如对形如A Ar r1 1 r r2 2的的正规产生式正规产生式:A Ar r1 1 A Ar r2 2 5)5)不断应用不断应用2)2)、3)3)、4)4)做变换，直到每个产做变换，直到每个产生式都符合生式都符合3 3型文法的要求；型文法的要求；mcy60例例 r=a(a d)Sa(a d)SaAA

38、(a d)A(a d)BAB(a d)BBA(a d)SaAAaB dBABaB dBBmcy611.1.对对 上的上的正规式正规式r,存在一个存在一个3 3型文法型文法G=(VN，VT，P，S)：L(G)=L(r)2.2.对对3 3型文法型文法G=(VN，VT，P，S),存在一个存在一个=VT上的上的正规式正规式r:L(r)=L(G)3.3.设设G=G=（V VN N,V,VT T,P,S,P,S）是是3 3型文法型文法，则存在，则存在一个有穷一个有穷自动机自动机 M=(S,T,sM=(S,T,s0 0,A),A)，使得使得L(M)=L(G)L(M)=L(G)4.4.已知一有已知一有穷自动机

39、穷自动机M=(S,T,s0,A),存在有存在有一个一个3 3型文法型文法G=(VN,VT,P,S),使得使得L(G)=L(M)。与与3 3型文法有关的定理型文法有关的定理mcy62AxB,By A=xy AxA y A=x y Ax y A=x y其中，其中，A,B VN x,y VT 2.2.对对3 3型文法型文法G=(VN，VT，P，S),存在一个存在一个=VT上上的的正规式正规式r:L(r)=L(G)mcy63例：例：Gs:SaA|aAaA a dA dA(a d)A(a d)A=(a d)(a d)S=a(a d)(a d)a=a(a d)(a d)=a(a d)R=a(a d)mcy

40、641.1.对对 上的上的正规式正规式r,存在一个存在一个3 3型文法型文法G=(VN，VT，P，S)：L(G)=L(r)2.2.对对3 3型文法型文法G=(VN，VT，P，S),存在一个存在一个=VT上的上的正规式正规式r:L(r)=L(G)3.3.设设G=G=（V VN N,V,VT T,P,S,P,S）是是3 3型文法型文法，则存在，则存在一个有穷一个有穷自动机自动机 M=(S,T,sM=(S,T,s0 0,A),A)，使得使得L(M)=L(G)L(M)=L(G)4.4.已知一有已知一有穷自动机穷自动机M=(S,T,s0,A),存在有存在有一个一个3 3型文法型文法G=(VN,VT,P,

41、S),使得使得L(G)=L(M)与与3 3型文法有关的定理型文法有关的定理mcy653.3.设设G=G=（V VN N,V,VT T,P,S,P,S）是是3 3型文法型文法，则存在，则存在一个有穷一个有穷自动机自动机 M=(S,T,sM=(S,T,s0 0,A),A)，使得使得L(M)=L(G)L(M)=L(G)有穷自动机有穷自动机NFA M NFA M 构造方法：构造方法：1)1)=V VT T2)2)S S=V VN N N,NN,N为一个新状态为一个新状态,它不在它不在V VN N中中3)3)s s0 0=S S 4)4)A=NA=Nmcy664)4)对对G G中的形如中的形如DtB的产

42、生式的产生式,t t为终结符为终结符,有有T(D,t)=B5)5)对对G G中形如中形如Dt的产生式的产生式,t为终结符或为终结符或,有有 T(D,t)=N6)6)对对V VT T中的每一个中的每一个a,有有T(N,a)=mcy67G G：SaA|bBSaA|bB AbB|aD|a AbB|aD|a BaA|bD|b BaA|bD|b DaD|bD|a|b DaD|bD|a|baabbba,baBASDNababmcy681.1.对对 上的上的正规式正规式r,存在一个存在一个3 3型文法型文法G=(VN，VT，P，S)：L(G)=L(r)2.2.对对3 3型文法型文法G=(VN，VT，P，S)

43、,存在一个存在一个=VT上的上的正规式正规式r:L(r)=L(G)3.3.设设G=G=（V VN N,V,VT T,P,S,P,S）是是3 3型文法型文法，则存在，则存在一个有穷一个有穷自动机自动机 M=(S,T,sM=(S,T,s0 0,A),A)，使得使得L(M)=L(G)L(M)=L(G)4.4.已知一有已知一有穷自动机穷自动机M=(S,T,s0,A),存在有存在有一个一个3 3型文法型文法G=(VN,VT,P,S),使得使得L(G)=L(M)与与3 3型文法有关的定理型文法有关的定理mcy69所求文法所求文法G G的构造方法：的构造方法：1)VT=2)VN=S3)S=s04)4)若若T

44、(D,t)=B ，则产生式则产生式DtB加入加入P中中,如果如果B A，则将产生式，则将产生式Dt也加入也加入P中中4.4.已知一有已知一有穷自动机穷自动机M=(S,T,s0,A),存在有存在有一个一个3 3型文型文法法G=(VN,VT,P,S),使得使得L(G)=L(M)mcy70G：SaA|bBSaA|bB AbB|aD AbB|aD BaA|bD BaA|bD DaD|bD DaD|bDDBASaaabba,bb|b|b|a|a|a|a|b|bmcy713.1 3.1 语法分析过程语法分析过程3.2 3.2 上下文无关文法的形式定义上下文无关文法的形式定义3.3.3 3 二义性文法二义性

45、文法作业作业第三章第三章 上下文无关文法及分析上下文无关文法及分析mcy723.3.3 3二义性文法二义性文法w对于文法对于文法G，若存在某个句子若存在某个句子w L(G),w对应对应多个不同的最左（或最右）推导多个不同的最左（或最右）推导(即即w对应两个结构不同的对应两个结构不同的分析树分析树,详见详见4.1节节)，这类文法称为，这类文法称为二义性文法二义性文法。mcy73例例1 1，GEGE：E EE+E|E*E|(E)|i E+E|E*E|(E)|i 的句子的句子i+i*ii+i*i对应两个最右推导对应两个最右推导(即两个结构不同的即两个结构不同的分析树分析树)，故该文法是二义性文法，故

46、该文法是二义性文法。EEE+iEE*ii*EEEiEE+iimcy74例例2，文法，文法GC CifBthenC|ifBthenCelseCC S句子句子 ifB1thenifB2thenS1elseS2对应两个最右推导对应两个最右推导(有两个结构不同的分析树有两个结构不同的分析树)，所以，所以，它也是二义性文法。它也是二义性文法。mcy75CCifB1thenifB2thenC elseCS1S2ifB2then CCCifB1thenelseCS1S2mcy76由于二义性文法不能准确地指出程序设计语由于二义性文法不能准确地指出程序设计语言的语法结构，所以它是分析程序表示的一言的语法结构，所

47、以它是分析程序表示的一个严重问题。个严重问题。为解决二义性文法的不确定性，通常有两种为解决二义性文法的不确定性，通常有两种方法：方法：修改文法修改文法常用常用设置消除二义性规则设置消除二义性规则(优先权优先权和和结合性结合性)关于二义性文法的几点声明关于二义性文法的几点声明mcy77w任一前后文无关文法任一前后文无关文法是否是否是是二义性二义性的是的是不可不可判定判定的。但的。但存在一些判定文法是否二义性的存在一些判定文法是否二义性的充分条件：充分条件：若一文法含有若一文法含有既是左递归又是右递归的文法符号既是左递归又是右递归的文法符号，即有即有wA+AvA v(VN VT)*或或wA+A 或

48、或wA+A 及及 A+A 则则G必定是二义性的必定是二义性的。mcy78本章小结本章小结w本章给出了本章给出了chomsky文法的形式定义文法的形式定义,其中其中2 2型文法型文法(即上下文无关文法即上下文无关文法)是描述程序设计语言是描述程序设计语言语法的形式化工具；语法的形式化工具；3 3型文法是是描述程序设计语言词法的形式化工具；型文法是是描述程序设计语言词法的形式化工具；w举例：举例：一个简化的一个简化的C+C+类声明的语法的形式化定义类声明的语法的形式化定义 mcy79作业作业1.1._是描述程序设计语言语法结构的形式工具。是描述程序设计语言语法结构的形式工具。2.设设G=(VG=(

49、VN N，V VT T，P P，S)S)是一文法，且是一文法，且 V=VV=VN NV VT T，若若S S =*=*，V V*，则称则称为文法为文法G G的的 ，若，若S=*S=*，V VT T*，则称则称为文法为文法G G的的 。3.3.3.3.两个文法两个文法G G1 1SS和和G G2 2SS等价，当且仅当等价，当且仅当 _ _。4.4.给出语言给出语言L=L=a ai ib bj j|j|ji=1i=1的上下文无关文法的上下文无关文法;mcy805.文法文法GSGS的产生式如下：的产生式如下：S-S+S S-S*S S-i S-(S)S-S+S S-S*S S-i S-(S)对于输入串对于输入串 i+i*i:i+i*i:(1)给出一个推导；给出一个推导；(2)画出一棵分析树；画出一棵分析树；(3)文法文法G G是否是二义性的，请证明你的结论。是否是二义性的，请证明你的结论。mcy81