《compiler5_语法分析概要》由会员分享,可在线阅读,更多相关《compiler5_语法分析概要(163页珍藏版)》请在金锄头文库上搜索。
1、第五章 语法分析,5.1 语法分析概述 5.2 自顶向下分析法 5.2.1 自顶向下分析的一般过程 5.2.2 自顶向下分析方法特点 5.2.3 自顶向下分析存在的问题及解决方法 5.2.4 递归子程序法(递归下降分析法) 5.3 自底向上分析法 5.3.1 自底向上分析的一般过程(移进-归约分析) 5.3.2 算符优先分析法 5.3.3 LR分析法,2,2,功能:根据文法规则,从源程序单词符号串中识别出语法成分,并进行语法检查。,基本任务:识别符号串S是否为某语法成分,两大类分析方法:,自顶向下分析,自底向上分析,5.1 语法分析概述,3,存在主要问题: 左递归问题 回溯问题,主要方法: 递
2、归子程序法 LL分析法,自顶向下分析算法的基本思想为:,自底向上分析算法的基本思想为:,存在主要问题: 句柄的识别问题,主要方法: 算法优先分析法 LR分析法,5.2 自顶向下分析,4,4,5.2.1 自顶向下分析的一般过程 5.2.2 自顶向下分析方法特点 5.2.3 自顶向下分析存在的问题及解决方法 5.2.4 递归子程序法(递归下降分析法),5.2.1 自顶向下分析的一般过程,5,5,我们可以通过一例子来说明语法分析过程,给定符号串S,若预测是某一语法成分, 那么可根据该语法成分的文法,设法为S构造一棵语法树. 若成功,则S最终被识别为某一语法成分,即 SL(GZ)其中GZ为某语言成分的
3、文法. 若不成功,则 SL(GZ),6,6,例:已知符号串S=cad 文法GZ: ZcAd Aab|a 求解 SL(GZ),分析过程 是设法建立一棵语法树, 使语法树的末端结点与 给定符号串相匹配.,2.用Z的右部,符号串去匹配输入串,完成一步推导ZcAd 检查 c-c匹配 A是非终结符,将匹配任务交给A,7,7,3. 选用A的右部符号串匹配输入串 A有两个右部,选第一个,完成进一步推导Aab 检查,a-a匹配,b-d不匹配(失败) 但是还不能冒然宣布SL(GZ),4. 回溯 即砍掉A的子树 改选A的第二右部,Aa 检查 a-a匹配 d-d匹配,建立语法树,末端结点为cad与输入cad相匹配,
4、 建立了推导序列 EcAdcad cadL(G(E),S=cad GZ: ZcAd Aab|a,分析工作要部分地或全部地退回去重做叫回溯,5.2.2 自顶向下分析方法特点,1.分析过程是带有预测的,对输入符号串要预测属于什么 语法成分,然后根据该语法成分的文法建立语法树。,2.分析过程是一种试探过程,是尽一切办法(选用不同规则) 设法建立语法树的过程,由于是试探过程,故难免有失败, 所以分析过程需进行回溯,因此我们也称这种方法是带 回溯的自顶向下分析方法。,3.最左推导可以编出程序来实现,但在实际上价值不大, 效率低。,5.2.3 自顶向下分析存在的问题及解决方法,自顶向下分析方法的基本缺点:
5、 不能处理具有左递归性的文法,自顶向下分析为什么不能处理左递归文法?,1 左递归文法:,左递归文法 回溯问题,10,10,如果我们在匹配输入串过程中,假定正好轮到要用非终结符 U直接匹配输入串,即要用U的右部符号串U去匹配,为 了用U去匹配,又得用U去匹配,这样无限的循环下去 将无法终止。,如果文法具有间接左递归,则也将发生上述问题,只不过 环的圈子兜的更大。,要实行自顶向下分析,必须要消除文法的左递归,下面我们将介绍直接左递归的消除方法,在此基础上再介绍一般左递归的消除方法。,自顶向下分析为什么不能处理左递归文法?,11,11, 消除直接左递归:,11,11,规则一(提因子),i)已知 Ux
6、y | xw | | xz 解: Ux ( y | w | | z ) 得: Ux U Uy | w | | z iii)已知 Ux | xy 解: Ux ( y |),使用提因子法,不仅有助于消除直接左递归。而且有助于压缩文件的长度,使我们更加有效的分析句子。,ii)已知 Uxy | xw | | xz y y1y2 wy1w2 解:Ux ( y1 ( y2 | w2 ) | | z ) 得: Ux U U y1 y1 | | z y1 y2 | w2,12,12,规则二 将左递归规则改为右递归规则,若:PP| 则可改写为:P P P P| ,例2 已知GE: E:= T*F | T/F |
7、 F T:=F | T*F | T/F 解:左递归改为右递归得: E := T*F | T/F | F T := FT T := *FT | /FT | ,13,13,消除一般左递归,消 除 所 有 左 递 归 的 算 法,1.把G的非终结符整理成某种顺序A1,A2,An ,使得: A1 := 1|2|k A2 := A1 r A3 := A2u | A1v .,2. For i:=1 to n do begin for j :=1 to i-1 do 把每个形如AiAjr的规则替换成 Ai (1|2|k) r 其中Aj 1|2|k是当前全部Aj 的规则 消除Ai规则中的直接左递归 end,3
8、.化简由2得到的文法即可。,间接左递归,直接左递归,消除 直接左递归,一般左递归也可以通过改写法予以消除。,14,14,例:文法Gs为 S Qc|c Q Rb|b R Sa|a,非终结符顺序 重新排列,RSa|a QRb|b SQc|c,1.检查规则R是否存在直接左递归 RSa|a,2.把R代入Q的有关选择,改写规则Q QSab|ab|b,3.检查Q是否直接左递归,4.把Q代入S的右部选择 SSabc|abc|bc|c,5.消除S的直接左递归 S(abc|bc|c)S S abc S|,最后得到文法为:,S(abc|bc|c)S S abc S|,QSab|ab|b RSa|a,15,15,最
9、后得到的文法:,S(abc|bc|c)S S abc S| QSab|ab|b RSa|a,可以看出其中关于Q和R的规则是多余的规则 经过压缩后 S(abc|bc|c)S S abc S| 可以证明改写前后的文法是等价的,应该指出,由于对非终结符的排序不同,最后得到的文法在形 式上可能是不一样的,但是不难证明它们的等价.,2 回溯问题,16,16,什么是回溯?,分析工作要部分地或全部地退回去重做叫回溯,造成回溯的条件:,文法中,对于某个非终结符号的规则其右部 有多个选择,并根据所面临的输入符号不能准确 的确定所要选择时,就可能出现回溯。,回溯带来的问题:,严重的效率低,只有在理论上的意义而无实
10、际意义,17,17,效率低的原因,1)语法分析要重做,2)语法处理工作要推倒重来,为避免回溯,对文法的要求是,FIRST(i) FIRST(j)= (ij),定义 设文法G(不具左递归性) FIRST() = a | a, a Vt , , V* 若 ,则规定 FIRST(),*,*,18,18,消除回溯的途径:,(1) 改写文法,对具有多个右部的规则反复提取左因子,例1 UxV|xW U, V, WVn, xVt 改写为Ux(V|W) 更清楚表示 UxZ ZV|W,注意:问题到此并没有结束,还需要 进一步检查V和W的首符号是否相交 若Vab|cd FIRST(V)=a,c Wde|fg FI
11、RST(W)=d,f 只要不相交就可以根据输入符号确定 目标,若相交,则要代入,并再次提 取左因子。如:V:= ab w:= ac 则:Z:= a (b|c),19,19,例2:文法G | begin;end beginend 是否可用自顶向下方法进行语法分析。,FIRST() = begin FIRST() = begin ,改写文法: begin (; end | end ) 引入 begin ; end | end,20,20,例3:文法G : begin ; end | end real|integer|boolean|array|function|procedure 标识符|goto
12、| begin| if | for 是否可用自顶向下方法进行语法分析。,对于: FIRST( ; end) = real, integer, boolean, array, function, procedure FIRST( end ) = 标识符,goto, begin, if, for 不相交。 所以可用自顶向下方法进行语法分析,21,21,(2) 超前扫描,当文法不满足避免回溯的条件时,即各选择的首符号相交时,可以采用超前扫描的方法,即向前侦察各输入符号串的第二个、第三个符号来确定要选择的目标。,这种方法是通过向前多看几个符号来确定所选择的目标,从本质上来讲也有回溯的味道,因此比第一种
13、方法费时,但是读的仅仅是向前侦察情况,不作任何语义处理工作。,22,22,例, | begin; end begin end real | integer | boolean | array | function | procedure 标识符|goto| begin| if | for,这两个选择的首符号是相交,故,读到begin时并不能确定 该用哪个选择,这时可采用向前假读进行侦察,此例题只 需假读一次就可以确定目标。 因为的首符集为real,integer,procedure 而的首符集为标识符,if ,for,begin,只要超前假读得到的是“说明串”的首符,便是第一个选择。 若是“语
14、句串”的首符,就是第二个选择。,3文法的两个条件,23,23,为了在不采取超前扫描的前提下实现不带回溯的自顶向 下分析,对文法需要满足两个条件:,2、 对文法的任一终结符,若其规则右部有多个选择时,各选择所推出的终结符号串的首符号集合要两两不相交。,1、文法是非左递归的;,在上述条件下,就可以根据文法构造有效的、不带回溯的 自顶向下分析器。,5.2.4 递归子程序法(递归下降分析法),具体做法: 对语法的每一个非终结符都编一个分析程序,当根据 文法和当时的输入符号预测到要用某个非终结符去匹 配输入串时,就调用该非终结符的分析程序。,下面我们可以通过举例说明如何根据文法构造该文法的 语法分析程序
15、,25,25,如文法GZ: E := UV U := . V := . E的分析程序 U的分析程序 V的分析程序,注:消除左递归后,可有其它递归: U := U U := W W:= U,26,26,例:文法GZ Z(U)|ab UdZ|Ud|e,1.检查并改写文法,Z(U)|ab UdZU|eU U=dU|,改写后无左递归且首符集不相交: (a= de=,2.检查文法的递归性,因此,Z和U的分析程序要编成递归子程序,递归子程序法对应的是最左推导过程,27,27,3.算法框图,非终结符号的分析子程序功能是: 用规则右部符号串去匹配输入串。,以下是以框图形式给出的子程序:,28,Z(U)|ab UdZU|eU U=dU|