编译原理第四章语法分析自上而下分析ppt课件

1、第四章 语法分析-自上而下分析4.1 语法分析器的功能4.2 自上而下分析面临的问题4.3 LL(1)分析法4.4 递归下降分析程序构造4.5 预测分析程序4.6 LL(1)分析中的错误处置4.1 语法分析器的功能 功能定义： 按照文法产生式，识别输入符号串能否为一个句子。 技术道路： 能否能从文法的开场符号出发推导出这个输入串。或者，建立一颗与输入串相匹配的语法分析树。 战略： 自上而下分析法，自下而上分析法。词词法法分分析析器器分分析析器器符符号号表表取取下下一一个个记记号号源源程程序序记记号号分分析析树树前前端端的的其其余余部部分分中中间间表表示示图4.1 语法分析器在编译程序中的位置接

2、纳词法分析器输出的记号串，检查能否符合语法。报告语法错误，并恢复语法错误，从而可以继续分析。输出是分析树的某种方式。分析时其它义务：将各种记号的信息收入符号表、类型检查和其它语义检查、中间代码的生成，这些放在“前端的其它部分完成。4.2 自上而下分析面临的问题 例4.1 假定有文法 (1) SxAy (2)A*|* 对输入串x*y，构造语法树。 构造过程： (1)把S作为根 (2)用S的产生式构造子树 (3)让输入串指示器IP指向输入串的第一个符号。(4)调整输入串指示器IP与叶结点进展匹配。(5)假设为非终结符，用A的下一个产生式构建子树。(6)假设匹配胜利那么终了；否那么，回溯到步骤(4)

3、。SxAySxAy*SxAy* 自上而下分析法的缺陷： 是文法的左递归性问题。一个文法是含有左递归的自上而下的分析过程堕入无限循环。如PP。 由于有回溯，就会产生一大堆费事事情。 在上述的自上而下分析过程中，当一个非终结符用某一候选匹配胜利时，这种胜利能够仅是暂时的。这种虚伪景象，我们需求更复杂的回溯技术。普通说，要消除虚伪匹配是很困难的。 当最终报告分析不胜利时，我们不知道输入串中出错确实切位置。4.3 LL(1)分析法4.3.1 左递归的消除 4.3.2 消除回溯、提左因子 4.3.3 LL(1)分析条件4.3.1左递归的消除 一个简单例子： 知文法：PP|是一个左递归文法，它的等价的非左

4、递归文法为： P P P P| 例2.2 普通转换规那么有： PP1| P2| | Pm| 1 | 2 | n改写成 P1P|2P |nP P1P |2P| |mP | 其中： i都不以P开头, I不等于 一个反例： 文法：SQc|c；QRb|b；RSa|a虽然不是直接左递归，但S、Q、R都是左递归。 消除左递归算法： 算法的思想是： 首先构造直接左递归； 再利用普通转换规那么，消除直接左递归 化简文法。 下面算法在不含PP，也不含在右部产生式时可以消除左递归。 消除一个文法的左递归算法： (1)把文法G的一切非终结符按任一种顺利陈列成P1Pn；按此顺序执行； (2) FOR i:=1 TO

5、n DO BEGINFOR j:=1 TO i-1 DO把形如Pj+1Pj 的规那么改写成Pj+11|1|k|。其中Pj1|1|k是关于Pj的 一切规那么；消除关于Pi规那么的直接左递归性。 END 化简由所得的文法。即去除那些从开场符号出发永远无法到达的非终结符的产生规那么。 例子4.3： 对4.3文法，它的非终结符排序为R,Q,S。把R代入Q，Q代入S得到：SSabc|abc|bc|c 消除左递归后得到： SabcS|bcS|cS SabcS| QSab|ab|b(化简消去) RSa|a化简后消去 对不同的陈列，会有不同方式的无左递归文法，但它们等价。4.3.2 消除回溯、提左因子 消除回

6、溯的思绪： 对输入符号a，指派一个A的候选式1与a匹配，而再没有其他候选式i的字符与a匹配。 经过提取公共左因子，判别首字符集的差别。 首字符集定义： 对G的一切非终结符的每个候选，它的首字符集为 FIRST()=a| a，aVT，假设*，那么规定 FIRST()。 提取公共左因子算法： A1|2|n|1|2| |m(其中每个 不以开头) 那么可以把这些规那么改写成： AA|1|2| |m A1|2|n 例4.4 上述算法的缺乏： 当非终结符A面临输入符号a,且a不属于A的恣意候选首符集,但A的某个候选首符集包含时，就一定可以使A自动匹配。这是一种错误。4.3.3 LL(1)分析条件 定义FO

7、LLOW(A) 集合： 假定S是文法G的开场符号，对于G的任何非终结符A，我们定义 FOLLOW(A)=a|S*Aa,aVT 假设S*A，那么规定FOLLOW(A)。 LL(1)文法的充分必要条件： 文法不含左递归。 假 设 1 | 2 | | n ， 那 么FIRST(i)FIRST(j)= (ij) 对文法中的每个非终结符A，假设它存在某个候选首符集包含，那么FIRST(A)FOLLOW(A)= LL(1)匹配算法： 对输入符号a，A的一切产生式为： 1|2|n (1)假设aFIRST(i)，那么指派I去执行匹配义务。 (2)假设a不属于任何一个候选首符集，那么： FIRST(i)且aFO

8、LLOW(A)，那么让A(i)与(a)自动匹配； 否那么，a的出现是一种语法错误。 例 4.44.4 递归下降分析程序构造 递归下降分析器： 这个分析程序由一组递归过程组成的，每个过程对应文法的一个非终结符。 ETE E+TE| TFT T*FT| F(E)|iPROCEDURE E PROCEDURE TBEGIN BEGIN T ; E F ; TEND ENDPROCEDURE E PROCEDURE TIF SYM=THEN IF SYM=THENBEGIN BEGIN ADVANCE ; ADVANCE; T ; E F ; TEND END PROCEDURE F IF SYM=i

9、THEN ADVANCE ELSE IF SYM=(THEN BEGIN ADVANCE; E; IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR; 扩展巴科斯范式(Backus Naur Form)： 用花括号表示闭包运算*。 用n0表示可恣意反复次至n次， 000 =。 用方括号表示0，即表示的出现可 有可无,等价于|。 例4.5： 文法 ET|E+T T F|T*F F i|(E) 可表示成 E T+T F F*F F (E)|I4.5 预测分析程序 4.5.1 预测分析程序任务过程 4.5.2 预测分析表的构造 预测分析器思想 ：.a总控程

10、序预测分析表MX.#输出输入串栈表4.1 文法4.2的LL(1)分析表 i+*()#EETE ETE E E +TE E E TTFT TFT T T T *FT T T FFi F(E) 预测分析程序的总控程序： 其详细任务过程是首先把文法开场符号和 # 压入栈，然后总控程序在任何时候都是按STACK栈顶符号X和当前输入符号a行事的，如下图。对于任何X,a,总控程序每次都执行下述三种能够的动作之一： 假设X=a,那么宣布分析胜利，停顿分析过程。 假设X=a,那么把X从STACK栈顶逐出，让a指示器指向下一个输入符号。 假设X是一个非终结符，那么查看分析表M。假设MA,a中存放着关于X的一个产

11、生式，那么X出栈，把X产生式右部符号串按反序压栈，假设MA,a中存放出错标志，那么调用诊断程序。 预测分析程序的总控程序描画是： BEGIN 首先把然后把文法开场符号推进STACK栈； 把第一个输入符号读进a； FLAG:=TRUE; WHILE FLAG DO BEGIN 把STACK栈顶符号上托出并放在X中； IF XVT THEN IF X= a THEN 把下一输入符号读进a ELSE ERROR ELSE IF X=# THEN IF X= a THEN FLAG:=FALSE ELSE ERROR ELSE IF MA,a=XX1X2XkTHEN 把Xk ,Xk-1, ,X1一一推

12、进STACK栈 /*假设X1X2Xk=，不推任何字进栈*/ ELSE ERROREND OF WHILE;STOP /*分析胜利，过程终了*/END 例例4.6：输入串为：输入串为i1*i2+i3,利用分析表进展预测分析的步利用分析表进展预测分析的步骤骤步骤步骤 符号栈符号栈 输入串输入串 所用产生式所用产生式0 #E i1*i2+i3#1 #ET i1*i2+i3# ETE2 #ETF i1*i2+i3# TFT3 #ETi i1*i2+i3# Fi4 #ET *i2+i3#5 #ETF* *i2+i3# T*FT 15 #E # T 16 # # E 4.5.2 预测分析表的构造 FIRS

13、T(X)集的构造算法： 假设XVT，那么FIRST(X)X。 假设XVn，且有产生式Xa,那么把a参与到FIRST(X)中；假设X 也是一条产生式，那么把也加到FIRST(X)中。 假设XY是一个产生式，且YVn，那么把FIRST(Y)中一切非-元素都加到FIRST(X)中；假设XY1Yi-1是一个产生式且YVn，且对任何的j(1ji-1),FIRST(Yj)都含有即Y1Yi-1* 那么把FIRST(Yj)中的一切非-元素都加到FIRST(X)中；特别地,假设FIRST(Yj)都含有,把 参与FIRST(X) 中 反复以上操作，直到FIRST (X)不再增大为止。 上述算法可以推行到FIRST

14、()，= X1Xk 非终结符B的FOLLOW(B)构造算法： 对 于 文 法 的 开 场 符 号 S , 置 于FOLLOW(B)中; 假设AB是一个产生式,那么把FIRST()-加至FOLLOW(B)中； 假设AB是一个产生式,或AB是 一 个 产 生 式 而 即FIRST(),那么把FOLLOW(A)加至FOLLOW(B)中。 构造分析表M的算法： (1)对文法G的每个产生式A执行第步和第步； (2)对每个终结符aFIRST(),把A加至MA,a中； (3)假设FIRST()，那么对任何bfollow(A)把()加至MA,b中； (4)把一切无定义的MA,a标上“出错标志 例4.7、4.84.6 LL(1)分析中的错误处置 错误类型： 栈顶的终结符与当前的输入符号不匹配。 非终结符A处于栈顶,面临的输入符号为a，但分析表M中的MA,a为空。 错误处置方法： 跳过输入串中的一些符号直至遇到“同步符号为止。 同步符号集合的选择方法： 把FLLOWO(A)参与A的同步活动集。 把FIRST(A)参与到A的同步活动集。