《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|
