上次课程内容回顾.ppt_三一文库31doc.com

资源描述

《上次课程内容回顾.ppt》由会员分享，可在线阅读，更多相关《上次课程内容回顾.ppt（38页珍藏版）》请在三一文库上搜索。

1、1,上次课程内容回顾,一、二义性与二义性的消除造成二义性的原因文法符号缺乏明确的优先级和结合性消除二义性的方法：改写二义文法为无二义文法为文法符号规定优先级和结合性改变语言的结构或书写方式,二、语言与文法的分类正规式、CFG、CSG 从计数问题看三者之间的关系,2,3.3.3 形式语言与自动机简介,对0型文法施加以下第i条限制，即得到i型文法。 G的任何产生式（S除外）满足|； G的任何产生式形如A，其中AN，(NT)*； G的任何产生式形如Aa或者AaB(或者ABa)，其中A和BN，aT。 ,文法、语言与自动机,定义3.8 若文法G=(N，T，P，S)的每个产生式中，均有(NT)

2、*，且至少含有一个非终结符，(NT)*，则称G为0型文法。,3,3.3.3 形式语言与自动机简介（续）,L3=anbncn|n1 L3=ambmcn|m,n1 （AAC AaAb|ab CcC|c） L3=akbmcn|k，m，n1 （a+b+c+ ）,例3.15 L3可用下述CSG描述： SaSBC (1) SaBC (2) CBBC (3) aBab (4) bBbb (5) bCbc (6) cCcc (7),句子akbkck 的推导： S =.= ak-1S(BC)k-1 (by 1) = ak(BC)k (by 2) =.= akBkCk (by 3) = akbBk-1Ck (by

3、 4) =.= akbkCk (by 5) = akbkcCk-1 (by 6) =.= akbkck (by 7),结论：CSG、CFG、正规式能力递减但是：能力越强的文法，其文法的设计和自动机的构造越困难因此：语法分析仅用到CFG（除特别指出，文法即指CFG ）,再考察L3：,4,3.4 自上而下语法分析 3.4.1 自上而下分析的一般方法,用推导的方法分析输入序列（记号流）：对任何一个输入序列，从S开始进行最左推导，直到得到一个合法的句子或发现一个非法结构。在推导的过程中，从左到右扫描输入序列，并试图用一切可能的方法，自上而下建立它的分析树。自上而下分析是一种试探的过程，是反复

4、使用不同产生式谋求与输入序列匹配的过程。,5,3.4.1 自上而下分析的一般方法（续1）,例3.20 用下述文法分析输入序列=cad：,S cAd A ab | a,问题：若有A1|2，(公共左因子)，则会虚假匹配和大量回溯；造成分析效率低、语义动作难以恢复、以及出错位置的报告不确切等。若有AA，(左递归)，则死循环使分析无法进行下去。,重写文法：消除左递归，以避免陷入死循环；提取左因子，以避免回溯。,6,3.4.2 消除左递归,定义3.9 若文法G中的非终结符A，对某个文法符号序列存在推导A=+A，则称G是左递归的。若G中有形如AA的产生式，则称该产生式对A直接左递归。 , 消除文法

5、的直接左递归考虑： AA| 产生的语言：*,替换为：AA AA| 消除了一个直接左递归,7, 消除文法的直接左递归(续1),A A1|A2|.|Am|1|2|.|n 其中i非空，j均不以A开始。然后用下述产生式代替A产生式：,若i为空，则形成一个有环的A产生式,算法3.1 消除直接左递归,A 1 A |2 A | .|n A A 1 A | 2 A | . | m A | ,输入 G中所有的A产生式(含直接左递归) 输出等价的不含直接左递归的G 方法首先，整理A产生式为如下形式：,8, 消除文法的直接左递归(续1),例3.17 用算法3.1消除算术表达式文法的直接左递归：,E TE (1

6、) E+TE| (2) (G3.4) T FT (3) T*FT| (4) F (E) |-F|id (5)(7),EE+T|T TT*F|F (G3.4) F(E)|-F|id,替换： AA| 为： A A AA|,关键：将实际文法符号对应到A、和具体到E产生式： E +T|T A ,9, 消除文法的直接左递归(续2),输入序列：id+id*id,改写的代价,EE+T|T TT*F|F F(E)|-F|id (G3.4),E TE (1) E+TE| (2) T FT (3) T*FT| (4) F (E) |-F|id (5)(7) (G3.4),EE+E|E*E |(E)|-E|id

7、(G3.2),What a mess!,10, 消除文法的左递归,文法：SAa|b AAc|Sd| S左递归(但不是直接左递归) 因为：S=Aa=Sda,核心思想：将不是直接左递归的非终结符右部展开到其他产生式中,for i in 2n loop for j in 1i-1 loop end loop; end loop; ,用Aj1|2|.|k的右部替换每个形如AiAj产生式中的Aj, 得到新产生式：Ai1|2|.|k; 消除Ai产生式中的直接左递归;,算法3.2 消除左递归输入无回路文法G 输出无左递归的等价文法G 方法将非终结符合理排序：A1，A2，.，An;,11, 消除文法

8、的左递归（续1）,例3.18 用算法3.2消除文法SAa|b AAc|Sd|中的左递归。,核心思想：将不是直接左递归的符号用其右部展开到其他产生式关键步骤：合理排序非终结符：A1，A2，.，An; 用Aj1|2|.|k右部替换AiAj中的Aj 得到Ai1|2|.|k; 消除Ai产生式中的直接左递归;, 将S的右部展开在A中，得到： AAc|Aad|bd| 消除新产生式中的直接左递归，得到：,S Aa | b A bdA | A (G3.8) A cA | adA | ,12,3.4.3 提取左因子,当不确定用A产生式的哪个候选项替换A时，可以重写A产生式来推迟这种决定，直到看见足够的输入，能

10、| Cb,重排A产生式：A1|2| .|n|；并用 AA| 和 A1|2| .|n取代原A产生式。 ,14,3.4.4 递归下降分析,直接以程序的方式模拟产生式产生语言的过程；每个产生式对应一个子程序，产生式右边的非终结符对应子程序调用，终结符则与输入序列匹配；它对文法的限制是不能有公共左因子和左递归；它是一种非形式化的方法，只要能写出子程序，用什么样的方法和步骤均可。,15,稳妥的笨方法：,递归下降分析的文法： LE;L| EE+T|E-T|T TT*F|T/F|T mod F|F F(E)|id|num,消除左递归后的等价文法: L E;L| E TE E+TE|-TE| T FT

11、 T*FT|/FT| mod FT| F (E)|id|num, 构造状态转换图且化简,构造文法的状态转换图并且化简；将转换图转化为EBNF表示；从EBNF构造子程序。,16,文法的状态转换图：,每个非终结符对应一个状态转换图：,为非终结符A建立一个初态和一个终态；为AX1X2.Xn构造从初态到终态的路径，边标记为X1，X2，.，Xn。根据识别同一集合的原则，化简转换图。,L E;L| E TE E+TE|-TE| T FT T*FT|/FT |mod FT| F (E)|id|num,文法状态转换图：,17,状态图的化简：,标记为A的边可等价为标记的边转向A转换图的初态；边连接的

12、两个状态可以合并；标记相同的路径可以合并；不可区分的状态可以合并。,化简E产生式：,1. 合并路径：,2. 转向E的初态：,3. 合并连接的节点：,4. 将E的转换图代入E ：,5.合并连接的节点：,6.合并相同路径：,18,状态图的化简（续1）,最终全部化简的转换图：, 文法的扩展BNF（EBNF）表示, ：重复0或若干次（while）：可选择（if或while） |：括弧( )之内的或关系（case） ( )：改变运算的优先级和结合性 EBNF表示：,（F无需化简，为什么？）,L E; E T (+|-) T T F (*|/|mod) F F ( E ) | id | num,19

13、, 递归下降子程序,L E; E T (+|-) T T F (*|/|mod) F F ( E ) | id | num,procedure L is begin lookahead := lexan； while (lookahead/=eof)loop E; match(;); end loop; end L;,procedure E is begin T; while lookahead(+|-) loop match(lookahead); T; end loop; end E;,procedure F is begin case lookahead is ( : match();

14、E; match(); id : match(id); num : match(num); others : error(“syntax error2“); end case; end F;,20, 递归下降子程序（续）,再看左递归问题：,若存在产生式E E + id，则E的递归下降子程序如下： procedure E is begin E; match(+); match(id); end E; 此程序永不停机。,#include const int id=0; void match(int x); void E() cout “match E“ endl; E(); match(+); m

15、atch(id); cout “match + and id“ endl; / 永远不执行 void main() E();,同样，文法中的公共左因子也会给递归下降分析造成困难。,结束（2007年4月3日）,21,上次课程内容回顾,形式语言与自动机简介自上而下分析的一般方法：自上而下(用推导的方法建立分析树)、从左到右(扫描输入序列)；自上而下分析对文法的限制：不能有左递归和左因子消除左递归：左递归与直接左递归（定义3.9）基本公式（替换AA|为A A AA|）消除直接左递归（算法3.1）和消除左递归（算法3.2）提取左因子：合并公共前缀（算法3.3）递归下降分析（一个非终结符

16、是一个子程序）构造文法的状态转换图并且化简；将转换图转化为EBNF表示；从EBNF构造子程序。,22,3.4.5 预测分析器 3.4.5.1 非递归预测分析器的工作模式,预测分析器的核心概念：分析方法：格局与格局变换分析表+驱动器（模拟算法）预测分析表的构造 LL（文法、语言、分析器）,23, 预测分析表,L E;L| E TE E+TE|-TE| T FT T*FT|/FT|mod FT| F (E)|id|num,文法：,LE;L| EE+T|E-T|T TT*F|T/F|T mod F|F F(E)|id|num,MA, a的内容：若当前栈顶是非终结符A，下一输入终结符是a，

17、则MA, a指示下一步动作。构造,分析表(MA, a)：,24, 工作方式,放幻灯的方式：每张“幻灯片”称为一个格局。分析从某个初始格局开始，经过一系列的格局变化，最终到达接收格局，表明分析成功；或者到达出错格局，表明发现一个语法错误。,格局：格局是一个三元组（栈内容，当前剩余输入，改变格局的动作） top ip,改变格局的动作：匹配终结符：若top=ip(但#)，则pop且next(ip)；展开非终结符：若top= X且MX, a=(X)，则pop且push()；报告分析成功：若top=ip=#，则分析成功并结束；报告出错：其它情况，调用错误恢复例程。,25, 驱动器算法

18、,算法3.4 非递归的预测分析输入输入序列和文法G的预测分析表M 输出若L(G)，得到的一个最左推导；否则指出一个错误方法初始格局为: （#S，#，分析器的第一个动作）,令ip指向#中的第一个终结符，top指向S; loop x := top; a := ip; exit when x=#; - 分析成功 end loop; ,if x T then if x=a then pop(x); next(ip); - 匹配终结符 else error(1); - 出错：栈顶终结符不是a end if;,else if Mx, a = XY1Y2.Yk then pop(X); push(

19、YkYk-1.Y2Y1);-展开产生式 else error(2); - 出错：产生式不匹配 end if; end if;,26,loop x := top; a := ip; if x T then if x=a then pop(x); next(ip); - 匹配终结符 else error(1); - 出错：栈顶终结符不是a end if; else if Mx, a = XY1Y2.Yk then pop(X); push(YkYk-1.Y2Y1);-展开产生式 else error(2); - 出错：产生式不匹配 end if; end if; exit when x=#; -

20、分析成功 end loop;, 用预测分析器分析句子,id+id*id;,27, 用预测分析器分析句子（续）,栈当前剩余输入动作 #L id+id*id;# pop(L), push(E;L) (LE;L) #L;E id+id*id;# pop(E), push(TE) (ETE) #L;ET id+id*id;# pop(T), push(FT) (TFT) #L;ETF id+id*id;# pop(F), push(id) (Fid) #L;ETid id+id*id;# pop(id), next(ip) id #L;ET +id*id;# pop(T) (T) #L;E +id

21、*id;# pop(E), push(+TE) (E+TE) #L;ET+ +id*id;# pop(+), next(ip) + #L;ET id*id;# pop(T), push(FT) (TFT) #L;ETF id*id;# pop(F), push(id) (Fid) #L;ETid id*id;# pop(id), next(ip) id #L;ET *id;# pop(T), push(*FT) (T*FT) #L;ETF* *id;# pop(*), next(ip) * #L;ETF id;# pop(F), push(id) (Fid) #L;ETid id;# pop(

22、id), next(ip) id #L;ET ;# pop(T) (T) #L;E ;# pop(E) (E) #L; ;# pop(;), next(ip) ; #L # pop(L) (L) # # 正确结束,28,3.4.5.2 构造预测分析表,首先构造FIRST集合与FOLLOW集合；然后根据两个集合构造预测分析表。,定义3.11 非终结符A的FOLLOW集合如下: FOLLOW（A） = a |S=*.Aa.，aT，若A是某句型的最右符号，则#FOLLOW（A）。 ,通俗地讲，的FIRST集合就是从开始可以导出的文法符号序列中的开头终结符。而A的FOLLOW集合，就是从开始符号

24、是非终结符且有XY1Y2.Yk，并设Y0=，Yk+1=。那么对所有j(0jk)，若aFIRST(Yj+1)且FIRST(Yj),则加入a到FIRST(X)。 ,对任意文法符号序列X1X2.Xn，FIRST(X1X2.Xn)的计算方法与算法3.5中步骤3类似即：FIRST(X1X2.Xn)是所有FIRST(Xi)(i=1,2,k)的并集其中k为第一个具有性质不属于FIRST(Yj)或kn的文法符号若kn，则FIRST(X1X2.Xn）,再考虑：FIRST(E)=FIRST(TE)=FIRST(FTE)= (，id, num ,L E;L| E TE E+TE|-TE| T FT T*FT|

25、/FT|mod FT| F (E)|id|num,30,3.4.5.2 构造预测分析表（续2）,算法3.6 计算所有非终结符的FOLLOW集合输入文法G 输出 G中所有非终结符的FOLLOW集合方法应用下述规则:,步骤3的理解：若 S =*Aa a紧跟A之后则 =*Ba a也紧跟B之后因为 FIRST() 使得B成为A产生式右部最右的文法符号即对任何aFOLLOW(A)，均有aFOLLOW(B),加入#到FOLLOW(S)，其中S是开始符号，#是输入结束标记若有产生式AB，则除外，FIRST()的全体加入到FOLLOW(B)。若有产生式AB或AB而FIRST()，则FOL

26、LOW(A)的全体加入到FOLLOW(B)。 ,31,3.4.5.2 构造预测分析表（续3）,例3.22 计算非终结符的FIRST 与FOLLOW。提示：自下而上计算FIRST 自上而下计算FOLLOW(为什么?),L E;L| E TE E+TE|-TE| T FT T*FT|/FT|mod FT| F (E)|id|num,FIRST(F) = ( id num FIRST(T) = * / mod FIRST(T) = FIRST(F) = ( id num FIRST(E) = + - FIRST(E) = FIRST(T) = FIRST(F) = ( id num FIRST(L

27、) = FIRST(E) = ( id num,FOLLOW(L) = # FOLL0W(E) = ) ; FOLLOW(E) = ) ; FOLLOW(T) = + - ; ) FOLLOW(T) = + - ; ) FOLLOW(F) = + - * / mod ) ;,32,3.4.5.2 构造预测分析表（续4）,算法3.7 构造预测分析表输入文法G 输出分析表M 方法应用下述规则,对文法的每个产生式A，执行2和3；对FIRST()的每个终结符a，加入到MA，a；若FIRST()，则FOLLOW(A)每个终结符b（包括#），加入到MA，b； M中其它没有定义的条目均是erro

28、r。 ,MA，a如何指导下一步动作：若当前栈顶为A，当前输入为a，则规则2表示下一步动作是展开A，因为aFIRST()，所以展开后下一次正好匹配a。若当前栈顶为A，当前输入为b且bFOLLOW(A)，则规则3表示下一步动作是展开A，即栈顶弹出A，继续分析A之后的部分，因为bFOLLOW(A)，所以弹出A后下一次正好匹配A的后继b。,33,3.4.5.2 构造预测分析表（续5）,FIRST(F/T/E)= ( id num FIRST(T) = * / mod FIRST(E) = + - FIRST(L) = ( id num FOLLOW(L) = # FOLL0W(E/E)= ) ;

29、FOLLOW(T/T)= + - ; ) FOLLOW(F) = + - * / mod ) ;,2. 对FIRST()的每个终结符a，加入到MA，a； 3. 若FIRST()，则FOLLOW(A)每个终结符b(包括#)，加入到MA，b；,从文法构造分析表,E;L,E;L,E;L,TE,TE,TE,+TE,-TE,FT,FT,FT,*FT,/FT,mod FT,id,num,(E),34,3.4.5.3 LL(1)文法,MA,a的作用：指导产生式产生句子（指导推导）问题：是否为任意文法构造的分析表MA,a中都最多有一个条目？,例3.23 二义文法文法的预测分析表：文法： SiCtSS|a

30、 SeS| Cb,预测分析表：,FIRST与FOLLOW集合： FIRST(C) = b FIRST(S) = , e FIRST(S) = i, a,FOLLOW(S) = #, e FOLLOW(S)= #, e FOLLOW(C) = t,a,iCtSS,b,eS,35,3.4.5.3 LL(1)文法（续1）,定义3.12 文法G被称为是LL(1)文法，当且仅当为它构造的预测分析表中不含多重定义的条目。由此分析表所组成的分析器被称为LL(1)分析器，它所分析的语言被称为LL(1)语言。第一个L代表从左到右扫描输入序列，第二个L表示产生最左推导，1表示在确定分析器的每一步动作时向前看一个终

31、结符。 ,判定LL(1)文法的方法：a.构造分析表； b.无需构造分析表。,推论3.2 G是LL(1)的，当且仅当G的任何两个产生式A|满足: 对任何终结符a，和不能同时推导出以a开始的串；和最多有一个可以推导出；若=*,则不能导出以FOLLOW(A)中终结符开始的任何串。 ,36,3.4.5.3 LL(1)文法（续2）,对所有A： 2. 对FIRST()的每个终结符a，加入到MA，a； 3. 若FIRST()，则FOLLOW(A)每个终结符b(包括#)，加入到MA，b；,证明：,若条件1不满足，即存在终结符a，和同时推导出以a开始的串，则根据算法3.7步骤2，MA，a中有多重定义A和A

32、；若条件2不满足，即和均可推出串，则根据算法3.2步骤3，任何属于FOLLOW（A）的终结符b(包括#)，MA，b中有多重定义A和A ；若条件3不满足，即存在终结符b，它既在FOLLOW(A)中，又在FIRST()中，则算法3.2步骤2把条目A加入到MA，b中，而步骤3又把条目A加入到MA，b中，即MA，b 中有多重定义A和A。 ,37,3.4.5.3 LL(1)文法（续3）,推论3.2 G是LL(1)的，当且仅当G的任何两个产生式A|满足: 对任何终结符a，和不能同时推导出以a开始的串；和最多有一个可以推导出；若=*,则不能导出以FOLLOW(A)中终结符开始的任何串。 ,E TE

33、(1) E+TE| (2) (G3.4) T FT (3) T*FT| (4) F (E) |-F|id (5)(7),EE+T|T TT*F|F (G3.4) F(E)|-F|id,文法(G3.4)不是LL(1)的，因为不满足条件1。事实上：任何直接左递归必有公共左因子。（为什么？）,文法(G3.4)是LL(1)的，因为三个条件均满足。具体判断请同学们自己做。,根据推论3.2，有左递归和左因子的文法不是LL(1)文法。为什么？（考虑算术表达式文法），二义文法呢？,38,3.4.5.3 LL(1)文法（续4）,LL(1)文法的弱点：文法难写、难懂；适应范围有限，往往写不出有些语言的LL(1)文法。,因此，实际编译器中使用更多的是一类LL(1)文法的真超集，即LR(1)文法。,结束（2007年4月5日）下周二交语法分析前4次课作业,

展开阅读全文