《程序设计语言编译原理第三版第4章资料讲解》由会员分享，可在线阅读，更多相关《程序设计语言编译原理第三版第4章资料讲解（53页珍藏版）》请在金锄头文库上搜索。
1、第四章语法分析自上而下分析,4.1 语法分析器的功能 4.2 自上而下分析面临的问题 4.3 LL（1）分析法 4.4 递归下降分析程序构造 4.5 预测分析程序 4.6 LL（1）分析中的错误处理(略),4.1 语法分析器的功能,1.任务：在词法分析识别出单词符号串的 基础上，分析并判定程序的语法 结构是否符合语法规则。,2.语法分析器的地位：,4.1 语法分析器的功能,3.本质：按文法的产生式，识别输入符号串 是否为一个句子。,4.语法分析方法分类： 自上而下分析法 自下而上分析法,4.2 自上而下面临的问题,二、举例： 自上而下方法的分析过程本质上 是一种试探过程，是反复使用不同产生 式
2、谋求匹配输入串的过程。,4.2 自上而下面临的问题,S,x A y,4.2 自上而下面临的问题,实现上述带回溯试探法的简单途径： 让每个非终结符对应一个递归子程序。每 个这种子程序可作为一个布尔过程。一旦发现 它的某个候选与输入串相匹配，就用这个候选 去扩展语法树，并返回“真”值；否则，保持原 来的语法树和IP值不变，并返回“假”值。,4.2 自上而下面临的问题,三、困难和缺点,1.文法的左递归性问题 使自上而下的分析过程陷入无限循环,2.回溯问题; 3.虚假匹配难以消除;,4.当最终报告分析不成功时,难于知道输入串中 出错的确切位置;,5.采用了一种穷尽一切可能的试探法,效率很低, 代价极高
3、.,4.3 LL(1)分析法,一、左递归的消除：,1. 规则:（直接左递归消除）,PP,PP|P|P|,4.3 LL(1)分析法,4.3 LL(1)分析法,. 消除间接左递归：,（）把文法的所有按任一种顺序排列成 P1,P2,Pn; 按此顺序执行:,（）FOR i = 1 To n Do Begin For j :=1 To i-1 Do 把形如Pi Pj 的规则改写成 Pi1|2|k 其中Pj1|2|k是关于Pj的所有规则； 消除关于Pi规则的直接左递归性 End,4.3 LL(1)分析法,解答,（）化简由（）所得的文法,即去除那些从开始符号 出发永远无法到达的非终结符的产生规则.,解答:
4、令非终结符排序为 R、Q、S i=1，无法执行for i=2，j=1Q Rb|b R Sa|a Q Sab|ab|b,4.3 LL(1)分析法,i=3，j=1无关系 i=3，j=2S Qc|c Q Sab|ab|b S Sabc|abc|bc|c,消除S的直接左递归 S abcS|bcS|cS S abcS|,返回,4.3 LL(1)分析法,二、消除回溯,提取公共左因子,4.3 LL(1)分析法,.消除回溯必须保证: 对文法的任何非终结符,当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。,即： 若此候选获得成功匹配，那么，这
5、种匹配决不会是虚假的； 若此候选无法完成匹配任务，则任何其它候选也肯定无法完成。,例： 设所面临的第一个输入符号为，若能根据不同的输入符号指派相应的候选 作为全权代表去执行任务，那就肯定无需回溯。在这里已不再是让某个候选去试探性地执行任务，而是根据所面临的输入符号准确地指派唯一的一个候选。,4.3 LL(1)分析法,.当不得回溯时，对文法有什么要求？ 非终结符的各个候选的首符集的交集均为空。,4.3 LL(1)分析法,此时，当要求A匹配输入串时，A根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务；这个候选就是那个终结首符集含a的.,即: first()是的所有可能推导的开头终结
6、符或可能的。,3.提取公共左因子 A.事实上，许多文法均存在这样的非终结符， 其所有候选的终结首符集并非两两不相交。 例如：语句if条件then语句else语句 if条件then语句,4.3 LL(1)分析法,B.如何把一个文法改造成任何非终结符的所有 候选首符集两两不相交呢？,代价: 大量引进新的非终结符和_产生式.,4.3 LL(1)分析法,经过反复提取左因子,就能把每个非终结符(包括新引进者)的所有候选首符集变成两两不相交.,三、分析条件,1.当一个文法不含左递归,并且满足每个非终结符的所有候选首符集两两不相交的条件,是不是就一定能进行有效的自上而下分析了呢?,4.3 LL(1)分析法,
7、例：文法 EE+T|T TT*F|F F（E）|i,输入串：,4.3 LL(1)分析法,经消去直接左递归后变成 ETE E+TE| TFT T*FT| F（E） i,.由上分析是不是就意味着：当非终结符面临输入符号，且不属于的任意候选首符集，但的某个候选首符集包含时，就一定可以使自动匹配？,分析：只有当是在文法的某个句型中允许跟在后的终结符时，才可能允许自动匹配，否则，在这里的出现是一种语法错误。,4.3 LL(1)分析法,4.3 LL(1)分析法,即: follow(A)是所有句型中出现在紧接A之后的终结符或“”。,当面临输入符号，且 first（A），但first（A），只有当afollo
8、w（A）时，才可能允许A自动匹配。,3.LL(1)文法,4.3 LL(1)分析法,构造不带回溯的自上而下分析的文法的条件： （1）文法不含左递归;,（2）文法中每一个非终结符A的各个产生式的候选首符集 两两不相交 即：若A1|2|n 则first(i)first(j)=（）,(3) 对文法中的每个非终结符，若它存在某个候选首符 集包含 ，则first(A)follow(A)= ,若一个文法G满足以上条件,则称该文法G为LL(1)文法.,4.LL(1)文法的自上而下分析 (有效的无回溯的),分析：A1|2|n,4.3 LL(1)分析法,对非终结符A进行匹配,此时面临的输入符号为a: (1)若af
9、irst( i ),则指派i去执行匹配任务;,(2)若a不属于任何一个候选首符集,则 若first( i ),且afollow(A),则让A与自动匹配; 否则,a的出现是一种语法错误.,一.实现思想 对应文法中每个非终结符编写一个递归过程,每个过程 的功能是识别由该非终结符推出的串,当某非终结符的产生 式有多个侯选时能够按LL(1)形式可唯一地确定选择某个侯 选进行推导.,4.4 递归下降分析程序构造,二.基本构造方法 1.基本构造方法:对文法的每个非终结符号,都根据其产生式 的各个候选式的结构,为其编写一个对应的子程序(或函数), 该子程序完成相应的非终结符对应的语法成分的识别和分 析任务.
10、,2.子程序的功能 对某个非终结符,用规则的右部符号串去匹配输入串.分析 过程是按文法规则自上而下一级一级地调用有关子程序来完成.,4.4 递归下降分析程序构造,3.举例 (1)Advance/Sym/IP (2)图4.2,4.符号的含义 (1) - * (2) n0- 可重复0次或任意次. (3) - ,4.4 递归下降分析程序构造,三.优缺点分析 1.优点:简单直观,易于构造. 2.缺点:(1)对文法要求高,必须满足LL(1)文法; (2)由于递归调用多,所以速度慢占用空间多. 应用举例: Pascal, C语言,预测分析器模型,4.5 预测分析程序,4.5 预测分析程序,1.分析表MA,
11、a形式的矩阵表示 矩阵元素MA,a存放内容：一条A的产生式或出错标志； 矩阵元素实际是相应的分析动作（即所选用的推导的产生式）。,2.分析栈用于存放分析过程中的文法符号。,3.总控程序 功能：依据分析表和分析栈联合控制输入字符串的识别和分析， 它在任何时候都是根据当前分析栈的栈顶符号X和当前的 输入字符a来执行控制功能。,4.5 预测分析程序,二. 预测分析表的构造,一. 预测分析程序工作过程,一、预测分析程序工作过程,1.总控程序算法描述 2.分析过程举例,4.5 预测分析程序,(1)初始化:依次把#和文法开始符号压入分析栈, 将输入串第一个符号读入a;,4.5 预测分析程序,1.总控程序算
12、法描述,(2)若XVT Xa”#”, 则将X从分析栈顶退掉, a指向下一个输入字符;,(3)若XVN , 则查分析表. 此时对MX,a:,Xa”#”, 表示分析成功,停止分析过程;,Xa ,表示不匹配的出错情况.,若MA, a= XX1X2X k ,则 将X从栈中弹出并将Xk,Xk-1,X1一一推进栈;,若MA, a中为空白,则表示出错,可调用语法出错处理子程序.,下面用预测分析方法对输入串i+i*i# 进行分析，给出栈的变化过程如下：,2 #ET i+i*i#,ETE,TFT ,1#E i+i*i#,2.分析过程举例,4.5 预测分析程序,Fi,i匹配,T,E+TE,预测分析器模型,4.5
13、预测分析程序,4.5 预测分析程序,二. 预测分析表的构造,1. FIRST集合构造 2. FOLLOW集合构造 3. LL(1)分析表的构造,4.5 预测分析程序,二. 预测分析表的构造,1.First(X)集合构造，XVTVN,即: first()是的所有可能推导的开头终结符或可能的。,1.Aa .,A1| 2|.| n FIRST(A),2.A,3.AX1 X2.XK,a.X2.,FIRST(X1)/, X2.,FIRST(X2)/,.,(1),(2),(3),4.5 预测分析程序,1.First(X)集合构造，XVTVN,例：求下题的FIRST集 ETEE+TE|T FTT*FT|F
14、(E)|i,FIRST(E)= FIRST(E)=FIRST(T)=FIRST(T)=FIRST(F)=,（，i ,+, ,*, ,（, i ,（, i ,4.5 预测分析程序,1.First(X)集合构造，XVTVN,2.Follow(A)集合构造，AVN,4.5 预测分析程序,即: follow(A)是所有句型中出现在紧接A之后的终结符或“”。,(2)BA,FOLLOW(A),(3)BA,(1)若A是开始符号,#,FIRST()/ ,FOLLOW(B),FIRST()/FOLLOW(B),4.5 预测分析程序,2.Follow(A)集合构造，AVN,ETEE+TE|TFTT*FT|F(E)
15、|i,FIRST(E)= ( ,i FIRST(E)=+, FIRST(T)=( ,i FIRST(T)=*, FIRST(F)= (,i ,FOLLOW(E)= FOLLOW (E)=FOLLOW (T)=FOLLOW (T)=FOLLOW (F)=, #, ) , #, ) , +,#, ) , +,#, ) , *,+,#, ) ,例：求下题的FOLLOW集,4.5 预测分析程序,练习：求下题的FIRST和FOLLOW集合。 Sa | (T) TST T ,ST | ,3.LL(1)分析表的构造,构造分析表M的算法是:,4.5 预测分析程序,(1)对每个终结符aFIRST(),把A加至M
16、A, a中;,(2)若FIRST(),则对任何bfollow(A)把 A加 至MA, b中;,(3)把所有无定义的MA, a标上“出错标志”。,对文法G的每个产生式A执行第1步和第2步;,例： E TEE +TE |T FTT *FT |F (E) |i,ETE,ETE,E+TE,E,E,TFT,T FT,T ,T ,T ,Fi,F(E),T*FT,4.5 预测分析程序,4.6 LL（1）中的错误处理,1.栈顶为非终结符A，面临输入符号a, 但分析表M中的MA,a为空. 2.栈顶终结符和当前输入符号不相同。,第4章 总结,LL（1）文法的判定,1.语法分析器的功能,2.自上而下分析面临的问题,将#和文法开始符号依次进栈STACK；,(2) 把第一个输入符号读进a；,(3) FLAG：=TRUE；,WHILE FLAG DO,begin 栈顶
