《语法和语义分析.ppt》由会员分享，可在线阅读，更多相关《语法和语义分析.ppt（116页珍藏版）》请在三一办公上搜索。
1、第五六章 语法和语义分析,2,语法分析是编译程序的核心部分,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠错工作.,语义分析的主要任务是分析语法结构含义,表示成中间语言或生成目标指令.,语法分析的方法有多种多样，常用的方法有递归子程序方法、运算符优先数法、状态矩阵法、LL（K）方法和LR（K）方法。归纳起来，大体上可分为两大类，即自顶向下分析方法和自底向上分析方法.,3,6.1 常用的终结符号集,1 首符号集First,2 向前看集Follow,3 可选集Select,4,设文法GS,字汇表为V,则符号串的首符号集为,定义,1 首符号集First,即First()
2、是的所有可能推导的开头终结符或可能的。,若为空符号串，则有First()=,（空集）,若，则First（）,5,例：,文法GE：ETE E+TE TFT T*FT F(E)i,则有,First(E)=First(T)=First(F)=(,i,First(E)=+,First(T)=*,First(i+i)=i,6,2 向前看集 Follow,定义,设文法GS,非终结符号U的向前看集为,即Follow(U)为所有含有U的句型中紧跟在U之后的终结符号或组成的集合。（若紧跟在非终结符号U后面的符号串为空时，则视U后面的符号为特殊符号）,7,文法GE：EE+TT TT*FF F(E)i,例：,Fol
3、low（F）=，*，+，）,8,3 可选集 Select,定义,设文法GS,并有规则A（为符号串）则该规则的可选集为,Select（A）=,First（），当不为空符号串,Follow（A），当为空符号串,非规则，求的First，规则求A的Follow,9,例：,文法GE：EE+TT TT*FF F（E）i,Sellect（ET）=First（T）=（，I,Sellect（F（E）=First（E）=（,Sellect（EE+T）=First（E+T）=（，i,Sellect（TT*F）=First（T*F）=（，i,Sellect（TF）=First（F）=（，i,Sellect（Fi）=F
4、irst（i）=i,10,例：,文法GE：SaBcbB BbBd,Sellect（SbB）=First（bB）=b,Sellect（B）=Follow（B）=,c,Sellect（SaBc）=First（aBc）=a,Sellect（BbB）=First（bB）=b,Sellect（Bd）=First（d）=d,11,例：,文法GE ETE E+E TFT TT FPF F*F P(E)ab,First(E)=First(T)=First(F)=First(P)=(,a,b,First(E)=+,First(T)=(,a,b,First(F)=*,Follow(E)=Follow(E)=),1
5、2,对每一文法符号X VN，计算FOLLOW(X),S为文法的开始符号，则把#加入FOLLOW(S),若XB，则把FIRST()-加入FOLLOW(B),13,例：,文法GE ETE E+E TFT TT FPF F*F P(E)ab,First(E)=First(T)=First(F)=First(P)=(,a,b,First(E)=+,First(T)=(,a,b,First(F)=*,Follow(E)=Follow(E)=),Follow(T)=Follow(T)=),+,Follow(F)=Follow(F)=),+,，(,a,b,Follow(P)=*，),+,，(,a,b,ETE
6、 把FIRST（E）-加入FOLLOW（T）E FOLLOW（E）加入FOLLOW（T）中。,TFT 把FIRST（T）-加入FOLLOW（F）T FOLLOW（T）加入FOLLOW（F）中。,14,6.2 句子的分析,一 自顶向下分析,1 自顶向下分析思想,从推导的角度来看，它是从文法的开始符号出发，根据文法试着建立一个推导序列，若得到所给的句子，则句子得到识别，表明其结构符合文法，否则不符合文法,从语法树建立的角度来看，它是根据文法从树根结点开始，试着自上而下建立一棵语法树，其末端结点 按从左到右的顺序若是给定的句子，则句子得到识别，表明其结构符合文法，否则不符合文法。,推导,15,文法G
7、N：NDND D0129,分析25是否符合该文法,16,2 自顶向下分析的难点及解决办法,难点1：,若文法中有如Ux1x2xn此时很难确定应用哪一条规则进行替换,解决办法：,把文法中每个非终结符号A的右部称为A的候选式,对文法的每个规则A求可选集,当不为空符号串，若当前输入符号a，有aFirst（），则可选用规则A进行推导,17,对于某个非终结符号有n个规则(n个候选式)，此时要分两种情况,I 首符号不相同,AX1 X2 XnFirst(Xi)First(Xj)=(空集)(ij),对于当前输入符号a，有a First(Xk)，则选择规则AXk进行推导,18,例：,文法GZ：ZaVbZ VbaZ
8、x 分析符号串bbabaax是否符合此文法,Select(ZaV)=a,Select(ZbZ)=b,Z,b,b,a,b,a,x,所以符号串bbabaax符合此文法,Select(VbaZ)=b,Select(Vx)=x,19,II 首符号相同,AX1X2Xn First(Xi)First(Xj)(空集)(ij),即非终结符A的n个候选式的首符号相同，此时无法根据当前输入符号准确地决定用哪个候选式，而只能采取试探的方法，先选用一个候选式去试探，若不行，则另换一个候选式去试探，这样就造成了回溯现象。,回溯既麻烦又浪费时间，且效率低，代价高，只有理论意义而无实践意义。因此需要消除回溯。,20,采取左
9、提“左因子”的方法修改文法，使首符号不相同。,例：,UaX1aX2X3Xn First(Xi)First(Xj)=(空集)(i,j3,ij),First(Xi)a(i3),但X1和X2的首符号相同,可将 UaX1aX2Xn 改为等价的规则 UaVX3Xn VX1X2,21,文法GA AxBy B*,对于非终结符号B的两个候选式的首符号相同可以用 B*V V*替换 B*,一般地，UaX1aX2aXn,可用 UAV VX1X2Xn 替换,22,难点2：,文法的左递归性问题,含有左递归的文法使用自上而下的分析过程会陷入无限循环。,解决办法：,消除文法的左递归性,23,二 自底向上分析,1 自底向上分
10、析思想,从所给符号串开始，从左到右扫描，自底向上分析，试图归约成开始符号。若能归约到开始符号，则所给符号串符合此文法，否则不符合。,每次直接归约当前句型的句柄。,归约,24,文法GS SaAcBe AAbb Bd 分析符号串abbcde是否为此文法的句子,例：,abbcde,符号串abbcde为此文法的句子,根据语法树进行分析,25,用矩阵的形式描述分析过程,先建立一个符号栈,1 从左到右扫描输入串，将输入串中的符号逐个进栈,2 当栈顶形成某规则的右部，则将其归约成相应的左部符号，并将归约后的符号进栈，继续扫描输入串，符号逐个进栈。反复进行本步，直到输入串全部移进,3 符号栈是否只为文法的开始
11、符号，若是，则输入串符合文法，否则，输入串不为文法的句子,用特殊符号#将句子括起来,26,#,abbcde#,#a,bbcde#,#ab,bcde#,b,Ab,#aA,bcde#,#aAb,cde#,Ab,AAb,#aA,cde#,#aAc,de#,#aAcd,e#,d,Bd,#aAcB,e#,#aAcBe,#,aAcBe,SaAcBe,#S,#,27,2 自底向上分析的难点,若一个文法有两条以上的规则，其右部符号相同，如果符号串又构成句型的句柄时，选用哪一条规则进行归约是个难题。如文法中有规则：Ad Bd 若当前句型的句柄为d，则很难选择哪条规则规约,28,6.5 LL(K)分析方法,LL(
12、K)分析方法是一种自顶向下的分析技术这种分析方法是从左到右扫描源程序(输入串)，同时从识别符号开始生成句子的最左推导，向前看K个符号，便能确定当前应选用怎样的规则。当K=1时，即是LL(1)分析法,29,一 LL(1)方法思想,根据句子的当前输入符号，确定用某规则进行推导，即：当推导的第一个符号与句子中的第一个符号匹配时，则取出句子的第二个符号，以确定下一个推导，这样逐步推导，直到推导出句子,文法GS SaBcbB BbBd 分析符号串abbbdc是否为此文法的句子,S,a,aBc,_,b,abBc,_,b,abbBc,_,b,abbbBc,_,d,abbbdc,30,二 LL(1)文法,定义
13、:,对于文法GS,其每个非终结符号的不同规则具有不相交的可选集Select，则称该文法为LL(1)文法,AX1 X2 Xn Select(AXi)Select(AXj)=(空集)(ij)即若Xi都，则First(Xi)First(Xj)=(空集)(ij),31,例：,文法GE：SaBcbB BbBd,Sellect（SbB）=First（bB）=b,Sellect（SaBc）=First（aBc）=a,Sellect（BbB）=First（bB）=b,Sellect（Bd）=First（d）=d,因为 Sellect（SaBc）Sellect（SbB）=,Sellect（BbB）Sellect
14、（Bd）=,从而该文法为LL(1)文法,32,三 LL(1)分析方法的逻辑结构,根据当前输入符号ai和栈顶符号xi，决定选择规则进行推导，按分析表进行某种相应的操作,利用下推自动机识别输入符号串,33,四 LL（1）分析表,假设,1 LL（1）分析过程,当前句型的右端部分为：x1x2xn(xiV)输入流(待分析串)右端部分为：y1y2yn(yiVt),有几种情况,I 当xiVn(xi为非终结符号)，则根据当前输入符号yi选择相应的规则替换xi,II 当xiVt(xi为终结符号),若xi与yi相同，则分别删除xi，yi，认为xi与yi相匹配，继续向前分析，否则xi与yi不匹配，为出错。,III
15、若上述两个字符串均为空，即全部相匹配，则全部删除，分析成功。,34,1,A,abbdc,_,_,2,cBa,AaBc,abbdc,_,_,3,cB,bbdc,a,4,_,_,cBb,BbB,bbdc,5,_,_,cB,bdc,b,6,_,_,cBb,BbB,bdc,7,_,_,cB,dc,b,8,_,_,cd,Bd,dc,9,_,_,c,c,d,10,_,_,c,空,空,句型的逆串,35,2 LL(1)分析表的构造,分析矩阵,分析栈中的元素为A，输入元素为a，则其匹配关系记为LL(A，a),几个约定：,1 N表示继续读下一个符号,2 P表示重读当前符号，即不读下一个符号,3 R()表示用的逆串
16、替换栈顶符号,为分析方便，将输入串用#括起来，分析栈中的元素可以是终结符、非终结符和#,36,分析矩阵构造方法,1 对于Aa(aVt)，则令LL(A,a)=R()N,2 对于AD(DVn)，且Select(AD)=b1,b2,bn 则令LL(A,bi)=R(D)P(i=1,2,n),3 对于A，且Select(A)=b1,b2,bn 则令LL(A,bi)=R()P(i=1,2,n),4 若aVt，而a从未出现在规则右部的首部，则令LL(a,a)=R()N,5 对于，则令LL(,)=acc,6 其它情况出错，在分析矩阵中可用空白表示,37,例：,文法GE：EE+TT TT*FF F（E）i,消除
17、左递归,ETE1 E1+TE1TFT1 T1*FT1F(E)i,对每一个规则求出其Select集,Select(ETE1)=First(TE1)=(,i,Select(E1+TE1)=First(+TE1)=+,Select(E1)=Follow(E1)=#,),Select(TFT1)=First(FT1)=(,i,Select(T1*FT1)=First(*FT1)=*,Select(T1)=Follow(T1)=#,),+,Select(F(E)=First(E)=(,Select(Fi)=First(i)=i,38,终结符）不出现在规则右部的首部,分析矩阵：第一列为非终结符和未出现在规
18、则右部的首部的终结符,Select(ETE1)=(,i,E1T/P,E1T/P,Select(E1+TE1)=+,E1T/N,/P,/P,Select(TFT1)=(,i,T1F/P,T1F/P,Select(T1*FT1)=*,T1F/N,/P,/P,/P,Select(F(E)=(,/N,)E/N,/N,acc,Select(E1)=#,),Select(T1)=#,),+,Select(Fi)=i,39,对于输入串i+i*i的分析过程,1,#E,i+i*i#,E1T/P,2,#E1T,i+i*i#,T1F/P,3,#E1T1F,i+i*i#,/N,4,#E1T1,/P,+i*i#,5,#
19、E1,+i*i#,E1T/N,6,#E1T,i*i#,T1F/P,7,#E1T1F,i*i#,/N,8,#E1T1,*i#,T1F/N,9,#E1T1F,i#,/N,10,#E1T1,#,/P,11,#E1,#,/P,12,#,#,acc,作业P159 6.6,40,例：,文法GS SBA ABSd BaAbS c,证明文法G是LL（1）文法；构造LL（1）分析表；写出句子adccd的分析过程。,对每一个规则求出其Select集,Select(SBA)=First(BA)=a,b,cSelect(ABS)=First(BS)=a,b,cSelect(Ad)=First(d)=d Select(
20、BaA)=First(aA)=a Select(BbS)=First(bS)=b Select(Bc)=First(c)=c,41,a 该文法不含左递归规则 b 文法中每一个非终结符号S，A，B的各个规则的可选集两两不相交,该文法是LL（1）文法,42,1,#S,adccd#,AB/P,2,#AB,adccd#,A/N,3,#AA,dccd#,/N,4,#A,SB/P,ccd#,5,#SB,ccd#,/N,6,#S,cd#,AB/P,7,#AB,cd#,/N,8,#A,d#,/N,9,#,#,acc,43,实验二 LL（1）分析法（选做）,实验目的：根据某一文法编制调试LL(1)分析程序，以便
21、对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL(1)分析法的理解。估计实验时间：1.课余准备20小时；2.上机二次4小时；3.完成实验报告5小时。,44,实验规定对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E:=TG（2）G:=+TG（3）G:=（4）T:=FS（5）S:=*FS（6）S:=（7）F:=(E)（8）F:=i,45,若输入串为i+i*i#则输出为：,1,#E,i+i*i#,2,#GT,i+i*i#,3,#GSF,i+i*i#,4,#GSi,i+i*i#,5,#GS,+i*i#,6,#G,+i*i#,7,#GT+,+i*i#,46,do/*读
22、入分析串*/scanf(%c,47,for(j=0;j=5;j+)/*判断是否为终结符*/if(x=v1j)flag=1;break;if(flag=1)/*如果是终结符*/if(x=#)finish=1;/*结束标记*/printf(acc!n);/*接受*/getchar();getchar();exit(1);if(x=ch)print();print1();printf(%c匹配n,ch);ch=B+b;/*下一个输入字符*/flag=0;/*恢复标记*/else/*出错处理*/print();print1();printf(%c出错n,ch);/*输出出错终结符*/exit(1);,
23、48,else/*非终结符处理*/for(j=0;j,cha.origin);/*输出产生式*/for(j=0;j=0;j-)/*产生式逆序入栈*/A+top=cha.arrayj;if(Atop=)/*为空则不进栈*/top-;,49,void print()/*输出分析栈*/int a;/*指针*/for(a=0;a=top+1;a+)printf(%c,Aa);printf(tt);void print1()/*输出剩余串*/int j;for(j=0;jb;j+)/*输出对齐符*/printf();for(j=b;j=l;j+)printf(%c,Bj);printf(ttt);,50
24、,char A20;/*分析栈*/char B20;/*剩余串*/char v120=i,+,*,(,),#;/*终结符*/char v220=E,G,T,S,F;/*非终结符*/int j=0,b=0,top=0,l;/*L为输入串长度*/typedef struct type/*产生式类型定义*/char origin;/*大写字符*/char array5;/*产生式右边字符*/int length;/*字符个数*/type;type e,t,g,g1,s,s1,f,f1;/*结构体变量*/type C1010;/*预测分析表*/,51,/*把文法产生式赋值结构体*/e.origin=E
25、;strcpy(e.array,TG);t.origin=T;strcpy(t.array,FS);g.origin=G;strcpy(g.array,+TG);g1.origin=G;g1.array0=;s.origin=S;strcpy(s.array,*FS);s1.origin=S;s1.array0=;f.origin=F;strcpy(f.array,(E);f1.origin=F;f1.array0=i;,52,for(m=0;m=4;m+)/*初始化分析表*/for(n=0;n=5;n+)Cmn.origin=N;/*全部赋为空*/*填充分析表*/C00=e;C03=e;C1
26、1=g;C14=g1;C15=g1;C20=t;C23=t;C31=s1;C32=s;C34=C35=s1;C40=f1;C43=f;,53,填充分析表,ETG TFS G+TGS*FSF(E)i,54,自下而上的语法分析,实现思想从输入符号串开始，从左到右进行扫描，将输入符号逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个产生式的右部时，就用该产生式的左部非终结符代替，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功，称为“移进-归约”方法。从语法树的角度看：从语法树的树叶开始，逐步向上归约构造分析树，直到形成根结。是推导的逆过程。,55,步骤动作,(1)S a
27、AcBe(2)A b(3)A Ab(4)B d,最左规约过程是最右推导的逆过程，对输入串abbcde的规约过程如下：,该分析过程反复执行“移进”和“归约”两个动作，直到栈中只有开始符号为止。,a,b a,A a,b A a,A a,c A a,dc A a,Bc A a,eBc A a,S,56,语法分析树的生成演示,a b b c d e,A,A,B,S,Ab,AAb,Bd,SaAcBe,(1)S aAcBe(2)A b(3)A Ab(4)B d,57,问题的提出：在构造语法树的过程中，何时归约？如何知道在栈顶符号串中已经形成可归约串？,当可归约串出现在栈顶时就进行归约,通过不同的自底向上的
28、分析算法来解释，不同的算法对可归约串的定义是不同的，但分析过程都有一个共同的特点：边移进边归约。,58,使用修剪语法树的方法来进行归约：,59,例2：有文法：E-E+T|TT-T*F|FF-(E)|id对输入串 id+id*id 的规范规约过程：,60,动作 栈 输入缓冲区1)准备#id+id*id#2)移进#id+id*id#3)归约 Fid#F+id*id#4)归约 TF#T+id*id#5)归约 ET#E+id*id#6)移进#E+id*id#7)移进#E+id*id#8)归约 Fid#E+F*id#9)归约 TF#E+T*id#10)移进#E+T*id#11)移进#E+T*id#12)
29、归约 Fid#E+T*F#13)归约 TT*F#E+T#14)归约 EE+T#E#15)接受,E-E+T|TT-T*F|FF-(E)|id,id+id*id,F,T,E,F,T,F,T,E,61,移进归约分析中的问题,移进-归约冲突 在分析到某一步时，既可以移进，又可以归约上例第10)步可以移进*，也可以按产生式EE+T进行归约。归约-归约冲突存在两个可选的句柄，可对栈顶符号进行归约例如上述第13)步，可以用TF进行归约，又可以按TT*F进行归约。各种分析方法中处理冲突的技术不同,62,优先分析法有两种：简单优先分析法对一个文法按一定原则求出该文法所有符号（终结符和非终结符）之间的优先关系，按
30、照这种关系确定归约过程中的句柄，它的归约实际上是一种规范归约。算符优先分析法只规定算符（终结符）之间的优先关系。找到句柄就归约，不是规范归约。,自底向上优先分析法概述,63,1.算符优先分析法是一种特别有利于表达式分析，宜于手工实现的语法分析方法。2.算符优先分析过程是自下而上的归约过程，但未必是严格的最左归约，因此，它不是一种规范归约法。3.所谓算符优先分析法就是仿效算术表达式的运算过程而设计的一种语法分析方法；这种方法的关键在于规定算符（终结符）的优先顺序和结合性质。,算符优先分析法概述,64,二义性文法存在规范归约不唯一的句子。例如，文法GE:EEE|E*E|(E)|id 句子idid*
31、id有二个不同的最右推导:E=E+E E=E*E=EE*E=E*id=EE*id=E+E*id=E+id*id=E+id*id=id+id*id=id+id*id 句型EE*id中，句柄不唯一。但若按算符优先顺序和结合规则的规定进行归约，句子的归约过程就是唯一的，运算结果也唯一。,65,按传统的习惯规定优先级从高到低为：乘幂运算符，右结合 乘、除运算符，左结合 加、减运算符；左结合 有括号时，先括号内后括号外;运算对象的终结符优先级最高;“#”优先级比它相邻的任何运算符都低。文法EEE|E*E|id 文法的句子idid*id的归约过程为：右句型 归约中用到的产生式(1)id+id*id Eid
32、(2)E+id*id Eid(3)EE*id Eid(4)EE*E EE*E(5)EE EEE(6)E 在上述的整个归约过程中，起决定作用的是相邻两个终结符的优先关系,66,6.6 运算符优先数法自底向上的语法分析方法,一 简单表达式的逆波兰表示,1 简单表达式的表示法,（1）中缀表示法,把双目运算符放在两个运算分量中间的表示法,a+b,a+b*c,（2）前缀表示法,把运算符放在运算分量前面的表示法,波兰表示法,+ab,+a*bc,（a+b）*c,*+abc,（3）后缀表示法,把运算符放在运算分量后面的表示法,逆波兰表示法,ab+,abc*+,ab+c*,67,2 逆波兰表达式的生成,运算符的
33、优先数关系,+，-,*，/,单目减,（,其右边的运算符,）最低，不进运算符栈，也不进输出区,运算符栈（栈），存放暂时不能处理的运算符,68,例：,表达式(a+b*c)*d，其逆波兰表达式的生成过程,栈,*,（,a,+,b,*,c,_,(,a,+,b,*,c,),(,a,+,b,*,c,),*,*,+,+,（,*,d,*,d,d,*,*,或者用矩阵描述,69,(a+b*c)*d,(,(,a+b*c)*d,a,(,a,+b*c)*d,+,(+,a,b*c)*d,b,(+,ab,*c)*d,*,(+*,ab,c)*d,c,(+*,abc,)*d,(+,abc*,)*d,(,abc*+,),*d,ab
34、c*+,*d,*,*,abc*+,d,d,*,abc*+d,abc*+d*,作业P159 6.7(4),70,三 逆波兰表达式的处理,将逆波兰表达式进行分析处理生成目标代码的形式,1 算法,建立一个运算分量栈（栈）,步骤：,从左到右扫描逆波兰表达式,（1）遇到运算分量，则进入栈,（2）遇到运算符，则取出栈中栈顶的两个或一个分量，生成相应的目标代码，运算结果存放在累加器“AC”中，把AC标志放入栈,（3）反复执行（1）和（2），直到表达式处理完为止,71,2 具体过程,例：,abc*+d*,a,a,a入栈,a,“AC”,“AC”,SGN a,b,“AC”b,b入栈,c,“AC”bc,c入栈,*,
35、(AC),M,STO M,b*c,“AC”,CLA b,MPY c,M“AC”,+,(AC)+(M),“AC”,“AC”,d,d入栈,“AC”d,*,(AC)*d,“AC”,MPY d,ADD M,72,四 运算符优先数法,两个栈，运算符栈（栈）和运算分量栈（栈）,运算分量栈,算法步骤：,运算符号栈,从左到右扫描表达式,运算分量,运算符号,考虑运算符号的优先关系,73,例：,#a+(b-c)*d#,栈,#,#,栈,a,+,(,b,-,c,当遇到）时,）,从栈中取出两个分量,从栈中取出进行运算，且（也退栈，这时，生成目标代码 CLA b SUB c,c,b,-,(,*,d,当遇到#时,#*，+，
36、从栈中取出两个分量,从栈中取出*，+进行运算，这时，生成目标代码 MPY d ADD a 最后栈和栈的#均退栈,74,算符优先分析,算符优先分析法的思想源于表达式的分析，即利用相邻终结符号之间的关系来寻找可归约串。显然，在一个符号串中，任意两个相邻终结符号a和b之间，只可能存在以下四种优先关系：(1)a,b优先性相同，记作a b。(2)a优先性高于b，记作a b。(3)a优先性低于b，记作a b。(4)a与b不可能相邻，即此符号串不是句型(出错)如果以上四种关系中的任意两种都不会同时成立,则可以根据终结符号之间的归约关系进行语法分析。,75,算符文法：一个上下无关文法G，如果没有P，且没有P.
37、QR.(P,Q,R属于非终结符)，则G是一个算符文法(Operater Grammer)算符优先关系的定义(自底向上，可通过树形结构观察)a b,G中有P-.ab.或P-.aQb.(在同一产生式中)a b,G中有P-.aR.的产生式,且R=b.或R=Qb.(注意ab相邻)b先规约到R,再同a一起规约a b,G中有P-.Rb.的产生式,且R=.a或R=.aQ(注意ab相邻)a先规约到R,再同b一起规约,算符优先文法的定义,谁先规约谁优先,76,例：EE+E|E*E|(E)|i 证明不是OPG文法。因为：EE+E，EE*E 则有+*又因为：EE*E,EE+E 则有+*所以不是算符优先文法。,算符优
38、先文法算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系，至多有,中的一种成立，则G为一算符优先文法。,77,算符优先矩阵的构造,用矩阵形式来表示各终结符号的优先关系，这种运算符优先关系的矩阵表示称为优先矩阵。构造优先矩阵的方法：按照定义手工计算使用算法 例:P:E:=E+T|T T:=T*F|F F:=(E)|i 求算符优先矩阵。,78,由F:=(E)得(),例:P:E:=E+T|T T:=T*F|F F:=(E)|i 求算符优先矩阵,相同的终结符之间的优先关系一定是？如果有a b,是否一定有b a(即具有传递性)？,79,算符优先矩阵的构造,FIRSTVT集定义：对每个非终结符
39、P,FIRSTVT(P)=a|P=a.或P=Qa.，a为终结符，P，Q为非终结符 即第一个终结符。,+,+,80,按照下面两条规则来构造FIRSTVT集：若有产生式Pa.或PQa.,则aFIRSTVT(P)若有产生式PR.,则FIRSTVT(R)包含在FIRSTVT(P)中按照下面两条规则来构造LASTVT集 若有产生式Pa或PaQ，则aLASTVT(P)若有产生式PR，则LASTVT(R)包含在LASTVT(P)中,求文法各非终结符的FirstVT集：,EE+T|TTT*F|FF(E)|i,从而得到：FirstVT(E)=+,*,(,iFirstVT(T)=*,(,iFirstVT(F)=(
40、,i,81,如果每个非终结符的FIRSTVT和LASTVT集均已知，则可构造优先关系表。若产生式右部有.aP.的形式,则对于每个bFIRSTVT(P)都有a b(优先集)若产生式右部有.Pb的形式,则对于每个aLASTVT(P)集，都有a b 若产生式形如：Aab 或 AaBb形式，则有a b,构造优先关系表,82,若产生式右部有.aP.的形式，则对于每个bFIRSTVT(P)都有a b(优先集)若产生式右部有.Pb的形式，则对于每个aLASTVT(P)集,都有a b,83,84,85,两个概念：素短语：至少含有一个终结符,且除自身外,不再包含任何其它更小的素短语。最左素短语(leftmost
41、 prime phrase)：是指位于句型最左边的那个素短语。,算符优先分析算法,86,例：下述文法的一个句型：T*F+i 其短语、素短语、最左素短语分别是？,ET|E+TTF|T*FFi|(E),短语有：i,T*F,T*F+i素短语有：i,T*F最左素短语是：T*F,87,例:文法GE E-E+T|T T-T*F|F F-(E)|i句型T+T*F+i的语法树如图：,根据语法树可知：句型#T+T*F+i#的短语有：T 相对非终结符E的短语T*F 相对非终结符T的短语T+T*F 相对非终结符E的短语i 相对非终结符P、F、T的短语T+T*F+i 相对非终结符E的短语,根据素短语的定义可知：i和T
42、*F为素短语。其中：T+T*F(含T*F素短语)、T+T*F+i(含T*F素短语)和 T(不含终结符)也不是素短语T*F为最左素短语。,88,该定理说明了最左素短语与周围符号之间的关系,一个算符文法G的某个句型的最左素短语可描述：设句型的一般形式为(NiVN,ai VT#N1a1 N2a2 Nnan#它的最左素短语是满足下列条件的最左子串：Niai Ni+1ai+1 Njaj Nj+1其中：ai-1 ai,ai ai+1.aj-1 aj，aj aj+1,89,查找最左素短语的方法 在句型中加入优先关系，例如：i+i*i#+*#1、找最左素短语的右端；从左至右扫描符号串直至遇到第一个为止。2、找
43、最左素短语的左端；然后向回扫描(向左)越过任何=，直至一个被发现。3、归约 可归约串包括在第1步所遇到的的左边和第2步所遇到的的右边的所有终结符号，包括插入在中间的或环绕在两旁的非终结符号。归约时把最左素短语归约为某一非终结符号,90,算符优先分析过程见下图：,91,算符优先分析过程,根据最左素短语的定义句型的一般形式:#N1a1N2a2.NnanNn+1#(ai为终结符，Ni为可有可无的非终结符)从左向右扫描各符号,依次查看算符优先矩阵,直至找到满足ai ai+1的终结符为止,一直移进.再从ai开始往左扫描，直至找到满足关系aj-1 aj的终结符为止，进行归约。此时，形如:Nj aj Nj+
44、1 aj+1.Ni ai Ni+1的子串即为最左素短语，应被归约。分析过程的结束：分析栈中为#S，输入串为#,92,例如：根据下面文法及其算符优先表，按通用算符优先分析的算法分析语句if b then i else i#。S if Eb then E else E E E+T|T T T*F|F F i Eb b,93,94,95,算符优先分析一般并不等价于规范规约并不对文法的非终结符定义优先关系，无法发现由单个非终结符组成的“可归约串”。即无法使用单非产生式(如：TF)进行归约。算符优先分析比规范归约过程要快，跳过了所有的单非产生式。由于忽略了非终结符在归约中的作用，它可能会把错误的输入串误
45、认为是句子。,算符优先分析法小结,96,优缺点,优点简单、效率高。算符优先文法适用范围比简单优先文法大得多，许多程序设计语言都可以用它来分析。算符优先分析优先表构造简单，甚至可以用手工构造。能够处理部分二义性文法缺点文法书写限制大。在于有些文法不满足算符优先文法，必须先改写，有些甚至无法改写。占用内存空间大。若终结符数目多，优先表可能会占有太多空间。不规范、存在查不到的语法错误,97,七 合适优先函数,对于一种有多种广义运算符的语言来说，优先矩阵占用的内存容量太大。,解决办法：,将简单变量作为运算分量处理,将矩阵分块，减少空元素,这两种方法不能从根本上解决问题，最切实可靠的办法是,根据优先矩阵
46、构造合适优先函数,98,1 合适优先函数,内优先数,外优先数,处于栈内运算符的优先函数用f内（x）表示,处于栈外运算符的优先函数用f外（x）表示,99,合适优先函数,根据优先矩阵，对于所有的运算符x，y，若,xy，则f内（x）f外（y）,xy，则f内（x）f外（y）,xy，则f内（x）f外（y）,合适优先函数与优先矩阵一样，刻划了运算符之间的优先关系，且它由优先矩阵而建立。,100,并不是所有的优先矩阵均有优先函数，若存在也不唯一,f内(a)f外(b)=f内(b)=f外(a)=f内(a),矛盾,101,2 合适优先函数的构造,Floyd费路伊德,对于所有的运算符，令f内(x)=f外(x)=1,
47、若xy，且f内(x)f外(y)，则f内(x)=f外(y)+1,若xy，且f内(x)f外(y)，则f外(y)=f内(x)+1,若x=y，且f内(x)f外(y)，则f内(x)=f外(y)=max（f内(x)，f外(y)）,重复，直到各优先数不再改变为止,102,1,1,1,1,1,1,1,1,1,1,1,1,左,右,+-+-,F内（+-）F外（+-）,F内（+-）=F外（+-）+1,1,2,+-*/,F内（+-）F外（*/）,F外（*/）=F内（+-）+1,1,3,1,3,1,3,*/+-,F内（*/）F外（+-）,F内（*/）=F外（+-）+1,1,2,*/*/,F内（*/）F外（*/）,F内（
48、*/）=F外（*/）+1,2,4,3,5,3,5,F内（）F外（）,F内（）=F外（）+1,1,6,(,F内（）F外（(）,F外（(）=F内（）+1,5,7,1,6,1,2,#+-,F内（#）F外（+-）,F外（+-）=F内（#）+1,2,3,3,4,4,5,5,6,6,7,7,8,6,7,103,什么是自下而上语法分析的策略？什么是移进-归约分析？移进-归约过程和自顶向下最右推导有何关系？自下而上语法分析成功的标志是什么？什么是可归约串？移进-归约过程的关键问题是什么？如何确定可归约串？如何决定什么时候移进，什么时候归约？什么是算符文法？什么是算符优先文法？算符优先分析是如何识别可归约串的？
49、算符优先分析法的优缺点和局限性有哪些？,104,实验三 逆波兰式的产生及计算,实验目的：将用中缀式表示的算术表达式转换为用逆波兰式表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。估计实验时间：1.课余准备15小时；2.上机一次2小时；3.完成实验报告5小时。,105,输入如下：21+（42-2）*15+6）-18#,实验三 逆波兰式的产生及计算,输出如下：原来表达式：21+（42-2）*15+6）-18#后缀表达式：21&42&2&-15&*6&+18&-计算结果：609,106,例：,表达式(a+b*c)*d，其逆波兰表达式的生成过程,栈,*,（,a,+,b,*,c,_,(,a,+
50、,b,*,c,),(,a,+,b,*,c,),*,*,+,+,（,*,d,*,d,d,*,*,107,开始,从左到右扫描中缀表达式,结束,运算分量,error,退栈输出,当前运算符与栈顶运算符比较优先级,运算符,左括号(,右括号）,栈为空,栈为空,入栈,error,入栈,栈顶为（,退栈,栈为空,栈顶为（,退栈输出,入栈,输出,108,/*判定为数字*/,default:while(ch=0,实验三 逆波兰式的产生及计算,109,case+:case-:while(top!=0,实验三 逆波兰式的产生及计算,/*判定为加减号*/,/*stack为运算符栈*/,110,/*判定为乘除号*/,cas
