上下文无关文法自顶向下分析课件.ppt

1、上下文无关文法自顶向下分析上下文无关文法自顶向下分析上下文无关文法的相关概念上下文无关文法的相关概念33.2 上下文无关文法上下文无关文法(CFG)FCFG的定义与表示的定义与表示上下文无关文法，Context Free Grammar，CFG定义定义3.1 CFG是一个四元组：G=（N，T，P，S），其中（1）N是非终结符非终结符（Nonterminals）的有限集合；（2）T是终结符终结符（Terminals）的有限集合，且NT=；（3）P是产生式产生式（Productions）的有限集合，形如：A，其中AN（左部），(NT)*（右部），若=，则称A为空产生式（也可以记为A）；（4）S是非

2、终结符，称为文法的开始符号开始符号（Start symbol）。43.2 上下文无关文法上下文无关文法(CFG)例3.2 简单算术表达式的上下文无关文法可表示如下：N=ET=+，*，(，)，-，idS=EP:E E+E（1）E E*E（2）E（E）（3）(G3.1)E -E（4）E id（5）1.产生式的一般读法记号 读作“定义为定义为”或者“可导出可导出”。“E E+E”表述为“算术表达式定义为两个算术表达式相加”；或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”。53.2 上下文无关文法上下文无关文法(CFG)2.由产生式集表示CFG前提前提：若文法正确结论结论：文法开始符

3、号S是第一个产生式的左部；N是可以出现在产生式左边符号的记号集合；T是绝不出现在产生式左边符号的记号集合；P:E E+E（1）E E*E（2）E（E）（3）E -E（4）E id（5）产生式表示也被称为巴克斯范式巴克斯范式（Backus-Naur Form，BNF），其中用:=表示S=EN=ET=+，*，(，)，-，id63.2 上下文无关文法上下文无关文法(CFG)FCFG产生语言的基本方法推导产生语言的基本方法推导CFG（产生式）通过推导推导的方法产生语言。通俗地讲，产生式产生语言的过程是从开始符号S开始，对产生式左部的非终结符反复地使用产生式：将产生式左部的非终结符替换为右部的文法符号序

4、列（展开产生式，用标记=表示），直到得到一个终结符序列终结符序列。例3.4 用(G3.2)产生终结符序列-(id+id)可如下：E E+E（1）|E*E（2）|（E）（3）(G3.2)|-E（4）|id（5）E=-E by(4)=-(E)by(3)=-(E+E)by(1)=-(id+E)by(5)=-(id+id)by(5)73.2 上下文无关文法上下文无关文法(CFG)定义定义3.2 利用产生式产生句子的过程中，将产生式A的右部代替文法符号序列A中的A得到的过程，称A直接推直接推导导出，记作：A=。若对于任意文法符号序列1，2，.n，均有1=2=.=n，则称此过程为零步零步或多步推导多步推导

5、，记为：1=*n，其中1=n的情况为零步推导零步推导。若1n，即推导过程中至少使用一次产生式，则称此过程为至少一步推导至少一步推导，记为：1=+n。两点注意：，有=*，即推导具有自反性；若=*，=*，则=*，即推导具有传递性。83.2 上下文无关文法上下文无关文法(CFG)定义定义3.3 由CFG G所产生的语言L(G)被定义为:L(G)=S=+and T*，L(G)称为上下文无关语言上下文无关语言(Context Free Language,CFL)，称为句子句子。若S=*，(NT)*，则称为G的一个句型句型。定义定义3.4 在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为最

6、左推导最左推导，由最左推导产生的句型被称为左句型左句型。类似可定义最右推导最右推导与右句型右句型，最右推导也被称为规范推导规范推导。E=-E=-(E)=-(E+E)=-(id+E)=-(id+id)12 3 4 5 66是句子，所有i(i=1.6)均是句型。语言与文法简介语言与文法简介103.3 语言与文法简介语言与文法简介F正规式与上下文无关文法正规式与上下文无关文法1.正规式到CFG的转换推论推论3.1 正规式描述的语言结构均可用CFG描述，反之不一定从正规式到CFG的对应关系：构造正规式的NFA；若0为初态，则A0为开始符号；对于move(i,a)=j，引入产生式AiaAj；对于move

7、(i,)=j，引入产生式 AiAj；若i是终态，则引入产生式Ai。例3.11 从正规式r=(a|b)*abb的NFA构造CFG：A0 aA0|bA0|aA1A1 bA2A2 bA3A3 经验的方法：A HTH|Ha|HbT abb113.3 语言与文法简介语言与文法简介2.为什么用正规式而不用CFG描述词法？词法规则简单，用正规式描述已足够；正规式的表示比CFG更直观、简洁、易于理解；有限自动机的构造比下推自动机简单，且分析效率高；区分词法和语法，为编译器前端的模块划分提供方便。贯穿词法分析和语法分析始终的思想：语言的描述和语言的识别是表示一个语言的两个不同侧面，二者缺一不可；（语言、文法、自

8、动机）用正规式和CFG描述的语言，对应的识别方法（自动机）不同；正规式适合描述线性结构线性结构，如标识符、关键字、注释等；CFG适合描述具有嵌套（层次）性质的非线性结构非线性结构，如不同结构的句子if-then-else、while-do等。123.3 语言与文法简介语言与文法简介F上下文有关语言上下文有关语言Context Sensitive Language,CSL 程序设计语言中除了CFG可以描述的结构之外，还有一些是CFG无法描述的所谓上下文有关的结构。典型的这类语言结构包括：变量的声明与引用、过程调用时形参与实参的一致性检查等。描述它们的文法被称为上下文有关文法（Context Se

9、nsitive Grammar,CSG）。133.3 语言与文法简介语言与文法简介例3.12 不能用不能用CFG描述描述的语言：L1=c|(a|b)*(标识符声明与引用一致性的抽象)L2=anbmcndm|n1和m1(形参与实参一致性的抽象)L3=anbncn|n1(计数问题的抽象)相近的相近的CFL：L1=cr|(a|b)*L2=anbmcmdn|n1,m1L2=anbncmdm|n1,m1L3=ambmcn|m,n1SaSa|bSb|cSaSd|aAd AbAc|bcSAB AaAb|ab BcBd|cdAAC AaAb|ab CcC|c143.3 语言与文法简介语言与文法简介计数问题计数

10、问题L3=anbncn|n1CSLL3=ambmcn|m,n1CFLL3=akbmcn|k，m，n1正规集命题命题：L3不是正规集，因为构造不出可以识别L3的DFA。证明：证明：（反证）假设L3是正规集，则可构造n个状态的DFA D，它接受L3；考察D读完，a，aa，.，an，分别到达S0，S1，.，Sn，共有n+1个状态。根据鸽巢原理鸽巢原理，序列中至少有两个状态相同，设Si=Sj（ji），因为aibickL3，所以存在路径aibick。但是D中也有路径ajbick，矛盾。故L3不是正规集。AAC AaAb|ab CcC|c?a+b+c+S0SiSkfaibickaj-i153.3 语言与文

11、法简介语言与文法简介F形式语言与自动机简介形式语言与自动机简介 定义定义3.8 若文法G=(N，T，P，S)的每个产生式中，均有(NT)*，且至少含有一个非终结符，(NT)*，则称G为0型文法。对0型文法施加以下第i条限制，即得到i型文法。1.G的任何产生式（S除外）满足|；2.G的任何产生式形如A，其中AN，(NT)*；3.G的任何产生式形如Aa或者AaB(或者ABa)，其中A和BN，aT。文文 法法语语 言言自自 动动 机机短语文法(0型)短语结构语言图灵机CSG(1型)CSL线性界线自动机CFG(2型)CFL下推自动机正规文法(3型)正规集有限自动机163.3 语言与文法简介语言与文法简

12、介再考察L3：L3=anbncn|n1例3.15 L3可用下述CSG描述：SaSBC(1)SaBC(2)CBBC(3)aBab(4)bBbb(5)bCbc(6)cCcc(7)CSG、CFG、正规式能力递减，但是能力越强的文法，其文法设计和自动机的构造越困难，因此语法分析仅用到CFG（除特别指出，文法即指CFG）句子句子akbkck 的推导：的推导：S=.=ak-1S(BC)k-1(by 1)=ak(BC)k(by 2)=.=akBkCk(by 3)=akbBk-1Ck(by 4)=.=akbkCk(by 5)=akbkcCk-1(by 6)=.=akbkck(by 7)二义性与二义性的消除二义

13、性与二义性的消除183.2 上下文无关文法上下文无关文法(CFG)F二义性与二义性的消除二义性与二义性的消除二义性问题：一个句子可能对应多于一棵分析树例3.7 文法G3.2为EE+E|E*E|（E）|-E|id句子id+id*id和id+id+id可能的分析树有：193.2 上下文无关文法上下文无关文法(CFG)定义定义3.7 若文法G对同一句子产生不止一棵分析树，则称G是二二义义的。原因原因：在产生句子的过程中某些直接推导有多于一种选择注意注意：1.一个句子有多于一棵分析树，仅与文法和句子有关，与采用的推导方法无关；2.文法中缺少对文法符号优先级和结合性的规定。“悬空（悬空（dangling

14、）else”问题S if C then S(1)|if C then S else S(2)|id:=E(3)(G3.3)C E=E|E E(4).(6)E E+E|-E|id|n(7).(10)203.2 上下文无关文法上下文无关文法(CFG)例3.8 条件语句 if x0 then x:=5 else x:=-5if x0 then x:=5 else x:=-5else与离它远的与离它远的then匹配匹配if x0 then x:=5 else x:=-5else与离它近的与离它近的then匹配匹配213.2 上下文无关文法上下文无关文法(CFG)文法二义不能说明它所产生的语言一定是二义

15、的。消除语言二义有两种方法：改写二义文法为非二义文法；规定二义文法中符号的优先级和结合性。改写改写例3.9 与G3.2等价的非二义文法：E E+T|TT T*F|F(G3.4)F（E）|-F|id问题问题：如何改写？EE+E|E*E|（E）(G3.2)|-E|id223.2 上下文无关文法上下文无关文法(CFG)观察结论观察结论：F新引入的非终结符限制每一步直接推导均有唯一选择；F最终分析树的形状，仅与文法有关，而与推导方法无关；F非终结符的引入，增加了推导步骤(分析树增高)；F越接近S的文法符号的优先级越低。(如EE+T)F对于AA，若A在终结符左边出现(即终结符在中)，则A产生式具有左结合

16、性质。改写二义文法的关键步骤关键步骤：1.引入新的非终结符，增加一个子结构并提高一级优先级；2.递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。233.2 上下文无关文法上下文无关文法(CFG)例3.10 改写二义文法G3.2为G3.4：引入新的非终结符，增加一个子结构并提高一级优先级；递归非终结符在终结符左边，运算具有左结合性，否则具有右结合性。1.优先级：+*(),-,id2.结合性：左结合+,*右结合-无结合id3.非终结符与运算：E:+（E产生式，左递归）T:*（T产生式，左递归）F:-,(),id（F产生式，右递归）E E+E(1)|E*E(2)|（E）(3)|-E(4

17、)|id(5)E E+T|TT T*F|FF (E)|-F|id243.2 上下文无关文法上下文无关文法(CFG)“悬空悬空else”问题：在复合if语句中，可能then多于else，使得else不知与哪个then结合。一般原则是右结合，即else与左边最靠近的then结合。改写文法的根据是将S分为完全匹配完全匹配(MS)和不完全匹配不完全匹配(UMS)两类，并且在UMS中规定else右结合。S MS(1)|UMS(2)MS if C then MS else MS(3)|id:=E(4)UMS if C then S(5)|if C then MS else UMS(6)C E=E|E E(

18、7).(9)E E+T|T(10).(11)T (E)|-T|id|n(12).(15)S if C then S|if C then S else S|id:=EC E=E|EEE E+E|-E|id|n253.2 上下文无关文法上下文无关文法(CFG)S MS|UMS(1).(2)MS if C then MS else MS|id:=E(3).(4)UMS if C then S|if C then MS else UMS(5).(6)(G3.5)C E=E|E E(7).(9)E E+T|T(10).(11)T （E）|-T|id|n(12).(15)if x0 then x:=5 e

19、lse x:=-5263.2 上下文无关文法上下文无关文法(CFG)S MS|UMS(1).(2)MS if C then MS else MS|id:=E(3).(4)UMS if C then S|if C then MS else UMS(5).(6)(G3.5)C E=E|E E(7).(9)E E+T|T(10).(11)T （E）|-T|id|n(12).(15)if x0 then x:=5 else x:=-5273.2 上下文无关文法上下文无关文法(CFG)规定优先级和结合性规定优先级和结合性二义文法的优点：1.比非二义文法容易理解；2.分析效率高(分析树低，直接推导步骤少)

20、。YACC为二义文法规定优先级和结合性：%left+%left*%right-E E+E|E*E|（E）|-E|idE E+T|TT T*F|FF (E)|-F|id自上而下分析自上而下分析4.3 自上而下分析自上而下分析 4.3.1 自上而下分析的一般方法自上而下分析的一般方法F例例 文法文法 S aCbC cd|c为输入串为输入串w=acb建立分析树建立分析树SaCbSaCbcdSaCbc不能处理不能处理左递归左递归4.3 自上而下分析自上而下分析F不能处理左递归的例子不能处理左递归的例子 算术表达文法算术表达文法E E+T|TT T F|FF (E)|idEE+TE+TE+T 4.3 自

21、上而下分析自上而下分析 4.3.1 自上而下分析的一般方法自上而下分析的一般方法F例例 文法文法 S aCbC cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术4.3 自上而下分析自上而下分析 4.3.1 自上而下分析的一般方法自上而下分析的一般方法F例例 文法文法 S aCbC cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术、回溯导致语义工作推倒重来回溯导致语义工作推倒重来4.3 自上而下分析自上而下分析

22、 4.3.1 自上而下分析的一般方法自上而下分析的一般方法F例例 文法文法 S aCbC cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术、回溯导致语义工作推倒重来回溯导致语义工作推倒重来、难以报告出难以报告出错的确切位置错的确切位置4.3 自上而下分析自上而下分析 4.3.1 自上而下分析的一般方法自上而下分析的一般方法F例例 文法文法 S aCbC cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂的回溯技术复杂的回溯技术、回溯导

23、致语义工作推倒重来回溯导致语义工作推倒重来、难以报告出难以报告出错的确切位置错的确切位置、效率低效率低4.3 自上而下分析自上而下分析 4.3.2 LL(1)文法文法 F对文法加什么样的限制可以保证没有对文法加什么样的限制可以保证没有回溯回溯？F先定义两个和文法有关的函数先定义两个和文法有关的函数FIRST()=a|*a,a VT 特别是，特别是，*时，规定时，规定 FIRST()对对A的任何两个不同选择的任何两个不同选择 i 和和 j，希望有希望有FIRST(i)FIRST(j)=若若FIRST(i)或或 FIRST(j)含含，还需增加条件，还需增加条件4.3 自上而下分析自上而下分析 4.

24、3.2 LL(1)文法文法 F对文法加什么样的限制可以保证没有对文法加什么样的限制可以保证没有回溯回溯？F先定义两个和文法有关的函数先定义两个和文法有关的函数FIRST()=a|*a,a VT 特别是，特别是，*时，规定时，规定 FIRST()FOLLOW(A)=a|S*Aa，a VT如果如果A是某个句型的最右符号，那么是某个句型的最右符号，那么$属于属于FOLLOW(A)4.3 自上而下分析自上而下分析 FLL(1)文法文法任何两个产生式任何两个产生式A|都满足下列条件：都满足下列条件：FIRST()FIRST()=若若 *，那么，那么FIRST()FOLLOW(A)=例如例如,对于下面文法

25、，面临对于下面文法，面临a时，第时，第2步推导不步推导不知用哪个产生式知用哪个产生式S A BA a b|a FIRST(ab)FOLLOW(A)B a CC 4.3 自上而下分析自上而下分析 FLL(1)文法文法任何两个产生式任何两个产生式A|都满足下列条件：都满足下列条件：FIRST()FIRST()=若若 *，那么，那么FIRST()FOLLOW(A)=FLL(1)文法有一些明显的性质文法有一些明显的性质没有公共左因子没有公共左因子不是二义的不是二义的不含左递归不含左递归4.3 自上而下分析自上而下分析 F计算计算X的的FIRST(X)时，不断运用以下规则，直到没时，不断运用以下规则，直

26、到没有新的终结符或有新的终结符或可以被加入到可以被加入到FIRST(X)如果如果X是终结符，是终结符，FIRST(X)=X4.3 自上而下分析自上而下分析 F计算计算X的的FIRST(X)时，不断运用以下规则，直到没时，不断运用以下规则，直到没有新的终结符或有新的终结符或可以被加入到可以被加入到FIRST(X)如果如果X是终结符，是终结符，FIRST(X)=X如果如果XY1Y2Yk,且且a在在FIRST(Yi)集合中，并且集合中，并且Y1*,Y2*,Yi-1*，则将，则将a插入到插入到FIRST(X)中。中。4.3 自上而下分析自上而下分析 F计算计算X的的FIRST(X)时，不断运用以下规则

27、，直到没时，不断运用以下规则，直到没有新的终结符或有新的终结符或可以被加入到可以被加入到FIRST(X)如果如果X是终结符，是终结符，FIRST(X)=X如果如果XY1Y2Yk,且且a在在FIRST(Yi)集合中，并且集合中，并且Y1*,Y2*,Yi-1*，则将，则将a插入到插入到FIRST(X)中。中。如果如果X 是一个产生式，则将是一个产生式，则将插入到插入到FIRST(X)中。中。4.3 自上而下分析自上而下分析 F计算非终结符计算非终结符A的的FOLLOW(A)时，不断运用以下规时，不断运用以下规则，直到没有新的终结符可以被加入到则，直到没有新的终结符可以被加入到FOLLOW(A)将将

28、$放到放到FOLLOW(S)中，中，S是开始符，是开始符，$是输入右端的结是输入右端的结束标记束标记4.3 自上而下分析自上而下分析 F计算非终结符计算非终结符A的的FOLLOW(A)时，不断运用以下规时，不断运用以下规则，直到没有新的终结符可以被加入到则，直到没有新的终结符可以被加入到FOLLOW(A)将将$放到放到FOLLOW(S)中，中，S是开始符，是开始符，$是输入右端的结是输入右端的结束标记束标记如果存在如果存在AB，那么，那么FIRST()中非中非的所有符号都在的所有符号都在FOLLOW(B)中中4.3 自上而下分析自上而下分析 F计算非终结符计算非终结符A的的FOLLOW(A)时

29、，不断运用以下规时，不断运用以下规则，直到没有新的终结符可以被加入到则，直到没有新的终结符可以被加入到FOLLOW(A)将将$放到放到FOLLOW(S)中，中，S是开始符，是开始符，$是输入右端的结是输入右端的结束标记束标记如果存在如果存在AB，那么，那么FIRST()中非中非的所有符号都在的所有符号都在FOLLOW(B)中中如果存在如果存在AB或或AB，且，且FIRST()包含包含，则，则FOLLOW(A)中的所有符号都在中的所有符号都在FOLLOW(B)中。中。4.3 自上而下分析自上而下分析 F例例 E TE E +TE|T FT T FT|F (E)|idFIRST(E)=FIRST(

30、T)=FIRST(F)=(,id FIRST(E )=+,FRIST(T )=,FOLLOW(E)=FOLLOW(E )=),$FOLLOW(T)=FOLLOW(T )=+,),$FOLLOW(F)=+,),$练习练习F文法文法S-aSbS|bSaS|产生的语言是什么？该文法是否有二义性？F下面的二义文法描述命题验算公式的语法，为他写下面的二义文法描述命题验算公式的语法，为他写一个等价的非二义文法一个等价的非二义文法FS-S and S|S or S|not S|p|q|(S)练习练习F文法文法R-R|R|RR|R*|(R)|a|b产生字母表a,b上所有不含的正则式。为该文法写一个等价的非二义

31、文法。练习练习F考虑文法考虑文法S-(L)|aL-L,S|SF建立句子建立句子(a,(a,a)和和(a,(a,a),(a,a)的分析树的分析树F为（为（a）的两个句子构造最左推导）的两个句子构造最左推导F为（为（a）的两个句子构造最右推导）的两个句子构造最右推导F这个文法产生的语言是什么？这个文法产生的语言是什么？练习练习F为下面的语言写一个无二义性的文法为下面的语言写一个无二义性的文法(s;s);(s;s;s);s);(s;s)F下面是用正则表达式表示的变量声明下面是用正则表达式表示的变量声明(int|float)id(,id)*;请改用CFG表示练习练习F构造下面构造下面LL(1)文法的分析表文法的分析表D-TLT-int|realL-id RR-,id R|练习练习F构造下面文法的构造下面文法的LL(1)分析表分析表S-aBS|bAS|A-bAA|aB-aBB|b