《上次课程内容回顾》由会员分享，可在线阅读，更多相关《上次课程内容回顾（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
