《上次课程内容回顾》由会员分享,可在线阅读,更多相关《上次课程内容回顾(38页珍藏版)》请在金锄头文库上搜索。
1、上次课程内容回顾Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望3.3.3 形式语言与自动机简介 对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型)正规集有限自动机定义3.
2、8 若文法G=(N,T,P,S)的每个产生式中,均有(NT)*,且至少含有一个非终结符,(NT)*,则称G为0型文法。23.3.3 形式语言与自动机简介(续)L3=anbncn|n1L3=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、 3) = akbBk-1Ck (by 4) =.= akbkCk (by 5) = akbkcCk-1 (by 6) =.= akbkck (by 7)结论:CSG、CFG、正规式能力递减但是:能力越强的文法,其文法的设计和自动机的构造越困难因此:语法分析仅用到CFG(除特别指出,文法即指CFG )再考察L3:33.4 自上而下语法分析3.4.1 自上而下分析的一般方法用推导的方法分析输入序列(记号流):对任何一个输入序列,从S开始进行最左推导,直到得到一个合法的句子或发现一个非法结构。在推导的过程中,从左到右扫描输入序列,并试图用一切可能的方法,自上而下建立它的分析树。自上而下分析是一种试
4、探的过程,是反复使用不同产生式谋求与输入序列匹配的过程。43.4.1 自上而下分析的一般方法(续1)例3.20 用下述文法分析输入序列=cad:S cAdA ab | a问题: 若有A1|2,(公共左因子),则会虚假匹配和大量回溯;造成分析效率低、语义动作难以恢复、以及出错位置的报告不确切等。 若有AA,(左递归),则死循环使分析无法进行下去。 重写文法:1.消除左递归,以避免陷入死循环;2.提取左因子,以避免回溯。53.4.2 消除左递归 定义3.9 若文法G中的非终结符A,对某个文法符号序列存在推导A=+A,则称G是左递归的。若G中有形如AA的产生式,则称该产生式对A直接左递归。 消除文法
5、的直接左递归 考虑: AA|产生的语言:*替换为:AA AA|消除了一个直接左递归6 消除文法的直接左递归(续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产生式为如下形式:7 消除文法的直接左递归(续1)例3.17 用算法3.1消除算术表达式文法的直接左递归:E TE (1)E+TE| (2) (G3.4)
6、T FT (3) T*FT| (4)F (E) |-F|id (5).(7)EE+T|TTT*F|F (G3.4)F(E)|-F|id替换: AA|为: A A AA|关键:将实际文法符号对应到A、和具体到E产生式: E +T|T A 8 消除文法的直接左递归(续2)输入序列:id+id*id改写的代价EE+T|TTT*F|FF(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(G3.2)What a mess!9 消除文法的左递归 文法:SAa|b A
7、Ac|Sd| S左递归(但不是直接左递归)因为:S=Aa=Sda 注意:若G产生句子的过程中出现A A的推导,则无法消除左递归 +=核心思想:将不是直接左递归的非终结符右部展开到其他产生式中for i in 2.n loop for j in 1.i-1loop end loop; end loop; 用Aj1|2|.|k的右部 替换每个形如AiAj产生式中的Aj, 得到新产生式:Ai1|2|.|k;消除Ai产生式中的直接左递归;算法3.2 消除左递归输入 无回路文法G输出 无左递归的等价文法G方法 将非终结符合理排序:A1,A2,.,An;10 消除文法的左递归(续1)例3.18 用算法3.
8、2消除文法SAa|b AAc|Sd|中的左递归。核心思想:将不是直接左递归的符号用其右部展开到其他产生式关键步骤:合理排序非终结符:A1,A2,.,An; 用Aj1|2|.|k右部替换AiAj中的Aj 得到Ai1|2|.|k; 消除Ai产生式中的直接左递归; 将S的右部展开在A中,得到:AAc|Aad|bd| 消除新产生式中的直接左递归,得到:S Aa | bA bdA | A(G3.8)A cA | adA | 113.4.3 提取左因子 当不确定用A产生式的哪个候选项替换A时,可以重写A产生式来推迟这种决定,直到看见足够的输入,能正确决定所需选择为止。这一过程被称为提取左因子,它类似于有限
9、自动机的确定化。 公共前缀:A 1|2将: A 1|2替换为:A AA1|2它等价于:A (1|2 )(对照算术表达式中的提取公因式)S cAdA ab | a123.4.3 提取左因子(续1)算法3.3 提取文法的左因子输入 文法G输出 等价的无左因子文法G方法 重复下述过程,直到所有A产生式候选项中不再有公共前缀例3.20 考察悬空else文法:SiCtS|iCtSeS|a Cb 用算法3.3提取左因子,得到如下文法:既有左递归又含左因子?先消除左递归。(为什么?) SiCtSS|aSeS|Cb 重排A产生式:A1|2| .|n|; 并用 AA| 和 A1|2| .|n取代原A产生式。 1
10、33.4.4 递归下降分析 1.直接以程序的方式模拟产生式产生语言的过程;2.每个产生式对应一个子程序,产生式右边的非终结符对应子程序调用,终结符则与输入序列匹配;3.它对文法的限制是不能有公共左因子和左递归;4.它是一种非形式化的方法,只要能写出子程序,用什么样的方法和步骤均可。14稳妥的笨方法:递归下降分析的文法: 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 T*FT|/FT| mod FT| F (E)|id|num 构造状态转换图且化简1.构造文法的状态转换
11、图并且化简;2.将转换图转化为EBNF表示;3.从EBNF构造子程序。 15文法的状态转换图 :每个非终结符对应一个状态转换图:1.为非终结符A建立一个初态和一个终态;2.为AX1X2.Xn构造从初态到终态的路径,边标记为X1,X2,.,Xn。3.根据识别同一集合的原则,化简转换图。 L E;L|E TEE+TE|-TE|T FTT*FT|/FT |mod FT|F (E)|id|num 文法状态转换图:16状态图的化简:1.标记为A的边可等价为标记的边转向A转换图的初态;2.边连接的两个状态可以合并;3.标记相同的路径可以合并;4.不可区分的状态可以合并。 化简E产生式:1. 合并路径:2.
12、 转向E的初态:3. 合并连接的节点:4. 将E的转换图代入E :5.合并连接的节点:6.合并相同路径:17状态图的化简(续1) 最终全部化简的转换图: 文法的扩展BNF(EBNF)表示 :重复0或若干次(while) :可选择(if或while) |: 括 弧 ( )之 内 的 或 关 系(case) ( ):改变运算的优先级和结合性EBNF表示:(F无需化简,为什么?)L E; E T (+|-) T T F (*|/|mod) F F ( E ) | id | num 18 递归下降子程序 L E; E T (+|-) T T F (*|/|mod) F F ( E ) | id | n
13、umprocedure L isbegin lookahead := lexan; while (lookahead/=eof)loop E; match(;); end loop;end L;procedure E isbegin T; while lookahead(+|-) loop match(lookahead); T; end loop;end E;procedure F isbegin case lookahead is ( : match(); E; match(); id : match(id); num : match(num); others : error(syntax
14、 error2); end case;end F;19 递归下降子程序(续)再看左递归问题:若存在产生式E E + id,则E的递归下降子程序如下:procedure E isbegin E; match(+); match(id);end E;此程序永不停机。#include const int id=0;void match(int x);void E()cout match E endl;E(); match(+); match(id);cout match + and id endl; / 永远不执行void main() E(); 同样,文法中的公共左因子也会给递归下降分析造成困难。
15、 结束(2007年4月3日)20上次课程内容回顾1.形式语言与自动机简介2.自上而下分析的一般方法:自上而下(用推导的方法建立分析树)、从左到右(扫描输入序列);3.自上而下分析对文法的限制:不能有左递归和左因子4.消除左递归:左递归与直接左递归(定义3.9)基本公式(替换AA|为A A AA|)消除直接左递归(算法3.1)和消除左递归(算法3.2)5.提取左因子:合并公共前缀(算法3.3)6.递归下降分析(一个非终结符是一个子程序)构造文法的状态转换图并且化简;将转换图转化为EBNF表示;从EBNF构造子程序。213.4.5 预测分析器 3.4.5.1 非递归预测分析器的工作模式预测分析器的
16、核心概念:1.分析方法:格局与格局变换2.分析表+驱动器(模拟算法)3.预测分析表的构造4.LL(文法、语言、分析器)22 预测分析表L E;L|E TE E+TE|-TE|T FT T*FT|/FT|mod FT|F (E)|id|num idnum+-*/mod();#LE;LE;LE;LETETETEE+TE-TETFTFTFTT*FT/FTmod FTFidnum(E)文法:LE;L|EE+T|E-T|TTT*F|T/F|T mod F|FF(E)|id|numMA, a的内容:若当前栈顶是非终结符A,下一输入终结符是a,则MA, a指示下一步动作。构造 分析表(MA, a):23 工
17、作方式放幻灯的方式:1.每张“幻灯片”称为一个格局。 2.分析从某个初始格局开始,经过一系列的格局变化,最终到达接收格局,表明分析成功;3.或者到达出错格局,表明发现一个语法错误。 格局:格局是一个三元组 (栈内容,当前剩余输入,改变格局的动作) top ip改变格局的动作: 匹配终结符:若top=ip(但#),则pop且next(ip); 展开非终结符: 若 top= X且 MX, a=(X), 则 pop且push(); 报告分析成功:若top=ip=#,则分析成功并结束; 报告出错:其它情况,调用错误恢复例程。 24 驱动器算法算法3.4非递归的预测分析输入 输入序列和文法G的预测分析表
18、M输出若L(G),得到的一个最左推导;否则指出一个错误方法初始格局为: (#S,#,分析器的第一个动作) 令ip指向#中的第一个终结符,top指向S; loop x := top; a := ip;exit when x=#; - 分析成功 end loop; if x Tthen if x=a then pop(x); next(ip); - 匹配终结符 else error(1); - 出错:栈顶终结符不是a end if;else if Mx, a = XY1Y2.Ykthen pop(X); push(YkYk-1.Y2Y1);-展开产生式 else error(2); - 出错:产生
19、式不匹配 end if;end if;25loop x := top; a := ip;if x Tthen if x=a then pop(x); next(ip); - 匹配终结符 else error(1); - 出错:栈顶终结符不是a end if;else if Mx, a = XY1Y2.Ykthen pop(X); push(YkYk-1.Y2Y1);-展开产生式 else error(2); - 出错:产生式不匹配 end if;end if;exit when x=#; - 分析成功end loop; idnum+-*/mod();#LE;LE;LE;LETETETEE+TE
20、-TETFTFTFTT*FT/FTmod FTFidnum(E) 用预测分析器分析句子 id+id*id;26 用预测分析器分析句子(续) 栈当前剩余输入 动作#Lid+id*id;# pop(L), push(E;L)(LE;L)#L;Eid+id*id;# pop(E), push(TE)(ETE)#L;ETid+id*id;# pop(T), push(FT)(TFT)#L;ETFid+id*id;# pop(F), push(id)(Fid)#L;ETidid+id*id;# pop(id), next(ip) id#L;ET +id*id;# pop(T)(T)#L;E +id*id
21、;# 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(id), next(ip) i
22、d#L;ET ;# pop(T)(T)#L;E ;# pop(E)(E)#L; ;# pop(;), next(ip) ;#L # pop(L)(L) # #正确结束273.4.5.2 构造预测分析表 1.首先构造FIRST集合与FOLLOW集合;2.然后根据两个集合构造预测分析表。 定义3.11 非终结符A的FOLLOW集合如下:FOLLOW(A) = a |S=*.Aa.,aT,若A是某句型的最右符号,则#FOLLOW(A)。 通俗地讲,的FIRST集合就是从开始可以导出的文法符号序列中的开头终结符。 而A的FOLLOW集合,就是从开始符号可以导出的所有含A的文法符号序列中紧跟A之后的终结
23、符。 例如:FIRST(E)= (,id, num FOLLOW(E)= ),; L E;L|E TE E+TE|-TE|T FT T*FT|/FT|mod FT|F (E)|id|num 定义3.10 文法符号序列的FIRST集合为: FIRST()=a|=*a.,aT,若=*,则FIRST()。283.4.5.2 构造预测分析表(续1)算法3.5 计算X的FIRST集合输入 文法符号X输出 X的FIRST集合方法 应用下述规则:1.若XT,则FIRST(X)=X;2.若X是非终结符且有X,则加入到FIRST(X);3.若 X是 非 终 结 符 且 有 XY1Y2.Yk, 并 设 Y0=,Y
24、k+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|/FT|mod FT|F (E)|id|num 293.
25、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)1.加入#到FOLLOW(S),其中S是开始符号,#是输入结束标记2.若有产生式AB,则除外,FIRST()的全体加入到FOLLOW(B)。3.若有产生式AB或AB而FIRST(),则FOLLOW(A)的全体加入到FOLLOW(B)。 303.4.5.2
26、 构造预测分析表(续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 numFIRST(T) = * / mod FIRST(T) = FIRST(F) =( id numFIRST(E) = + - FIRST(E) = FIRST(T) = FIRST(F) = ( id numFIRST(L) = FIRST(E) = ( id num FOLLOW(L) = #FOLL0W(
27、E) = ) ;FOLLOW(E) = ) ;FOLLOW(T) = + - ; )FOLLOW(T) = + - ; )FOLLOW(F) = + - * / mod ) ; 313.4.5.2 构造预测分析表(续4)算法3.7 构造预测分析表输入 文法G输出 分析表M方法 应用下述规则1.对文法的每个产生式A,执行2和3;2.对FIRST()的每个终结符a,加入到MA,a;3.若FIRST(),则FOLLOW(A)每个终结符b(包括#),加入到MA,b;4.M中其它没有定义的条目均是error。 MA,a如何指导下一步动作:1.若当前栈顶为A,当前输入为a,则规则2表示下一步动作是展开A,
28、因为aFIRST(),所以展开后下一次正好匹配a。 2.若当前栈顶为A,当前输入为b且bFOLLOW(A),则规则3表示下一步动作是展开A,即栈顶弹出A,继续分析A之后的部分,因为bFOLLOW(A),所以弹出A后下一次正好匹配A的后继b。 323.4.5.2 构造预测分析表(续5)FIRST(F/T/E)= ( id numFIRST(T) = * / mod FIRST(E) = + - FIRST(L) = ( id numFOLLOW(L) = #FOLL0W(E/E)= ) ;FOLLOW(T/T)= + - ; )FOLLOW(F) = + - * / mod ) ; 2. 对FI
29、RST()的每个终结符a,加入到MA,a;3. 若FIRST(),则FOLLOW(A)每个终结符b(包括#), 加入到MA,b; 从文法构造分析表 idnum+-*/mod();#LEETTFE;LE;LE;LTETETE+TE-TEFTFTFT*FT /FTmod FTidnum(E)333.4.5.3 LL(1)文法 MA,a的作用:指导产生式产生句子(指导推导)问题:是否为任意文法构造的分析表MA,a中都最多有一个条目? 例3.23 二义文法文法的预测分析表: 文法: SiCtSS|aSeS|Cba beit#SSC预测分析表:FIRST与FOLLOW集合:FIRST(C) = bFIR
30、ST(S) = , eFIRST(S) = i, a FOLLOW(S) = #, eFOLLOW(S)= #, eFOLLOW(C) = t aiCtSSbeS343.4.5.3 LL(1)文法(续1)定义3.12 文法G被称为是LL(1)文法,当且仅当为它构造的预测分析表中不含多重定义的条目。由此分析表所组成的分析器被称为LL(1)分析器,它所分析的语言被称为LL(1)语言。第一个L代表从左到右扫描输入序列,第二个L表示产生最左推导,1表示在确定分析器的每一步动作时向前看一个终结符。 判定LL(1)文法的方法:a.构造分析表; b.无需构造分析表。 推论3.2 G是LL(1)的,当且仅当G
31、的任何两个产生式A|满足:1.对任何终结符a,和不能同时推导出以a开始的串;2.和最多有一个可以推导出;若=*,则不能导出以FOLLOW(A)中终结符开始的任何串。353.4.5.3 LL(1)文法(续2)对所有A:2. 对FIRST()的每个终结符a,加入到MA,a;3. 若FIRST(),则FOLLOW(A)每个终结符b(包括#), 加入到MA,b;证明:1.若条件1不满足,即存在终结符a,和同时推导出以a开始的串,则根据算法3.7步骤2,MA,a中有多重定义A和A;2.若条件2不满足,即和均可推出串,则根据算法3.2步骤3,任何属于FOLLOW(A)的终结符b(包括#),MA,b中有多重
32、定义A和A ;3.若条件3不满足,即存在终结符b,它既在FOLLOW(A)中,又在FIRST()中,则算法3.2步骤2把条目A加入到MA,b中,而步骤3又把条目A加入到MA,b中,即MA,b 中有多重定义A和A。 363.4.5.3 LL(1)文法(续3)推论3.2 G是LL(1)的,当且仅当G的任何两个产生式A|满足:1.对任何终结符a,和不能同时推导出以a开始的串;2.和最多有一个可以推导出;若=*,则不能导出以FOLLOW(A)中终结符开始的任何串。 E TE (1)E+TE| (2) (G3.4)T FT (3) T*FT| (4)F (E) |-F|id (5).(7)EE+T|TT
33、T*F|F (G3.4)F(E)|-F|id文法(G3.4)不是LL(1)的,因为不满足条件1。事实上:任何直接左递归必有公共左因子。(为什么?)文法(G3.4)是LL(1)的,因为三个条件均满足。具体判断请同学们自己做。 根据推论3.2,有左递归和左因子的文法不是LL(1)文法。为什么?(考虑算术表达式文法), 二义文法呢?373.4.5.3 LL(1)文法(续4)LL(1)文法的弱点:1.文法难写、难懂; 2.适应范围有限,往往写不出有些语言的LL(1)文法。 因此,实际编译器中使用更多的是一类LL(1)文法的真超集,即LR(1)文法。结束(2007年4月5日)下周二交语法分析前4次课作业38