《自上而下语法分析 课件》由会员分享，可在线阅读，更多相关《自上而下语法分析 课件（60页珍藏版）》请在金锄头文库上搜索。
1、第四章 语法分析自上而下分析,本章内容 语法分析的任务与分类 自上而下分析面临的问题 递归下降分析程序构造 预测分析程序 LL(1)文法,一、 语法分析的任务与分类 语法分析的任务： 对任一给定 w VT*，判断 w L（G） 语法分析器：是一个程序，它按照P，做识别w的工作,词法分析器,语法分析器,编译程序后续部分,符号表,图4.1 语法分析器在编译程序中的地位,二、自上而下分析面临的问题,1、主旨：从文法开始符号出发，自上而下的为输入串建立一棵语法树,S,c,A,d,a,b,a,S cAd,A ab,A a,输入串w :,文法G:,IP,分析过程：,1）w输入串； IP c S扩充；,c
2、a d,2）=c A d； 与 IP c 匹配；,3）IP a A扩展，第一式ab, IP a与ab匹配； IP d,但d与b不匹配;,4）报告失败，撤销A的子树，回到A; 指针回退到IP a; A还有替换式未试过，而又可能匹配；,语法树的形成,上述分析方法的实现：,每一非终结符对应一个递归子程序，在只生成两个串的文法，过程无须递归，而对生成无数个串的文法，递归是不可避免的；,递归子程序：是一个布尔过程，一旦发现它的某个候选式与输入串匹配，它就按此式扩充语法树，并返回true，指针移过已匹配子串。否则， 返回false，保持原来的语法树和指针不变。,程序实现：,使用记号： input_symb
3、ol：当前符号内容 input_pointer：输入字符指针 使用过程： ADVANCE( )：把input_pointer移到下一输入符号位置，置input_symbol是当前符号内容；,使用两个过程：S( )和A( )，它们送回true or false，决定于它们是否在输入串中找到相应的非终结符所构成的串。,procedure S( ); begin if input_symbol =cthen begin ADVANCE( ); if A( ) then if inputSymbol=d then begin ADVANCE( ); return true end end; retur
4、n false; end;,procedure A( ); begin isave:= input_pointer; if input_symbol= a then begin ADVANCE( ); if inputSymbol = b then begin ADVANCE( ); return true; end end /*failure to find ab*/ input_pointer:=isave; if inputSymbol = a then begin ADVANCE( ); return true; end else return false; end;,2、困难和问题,
5、文法的左递归 回溯 用替换符的顺序会影响所接受的语言 如：A ab|a 改为 A a|ab 难以报告出错的确切位置 穷举试探法低效的分析方法,三、自上而下分析的问题解决,消除文法的左递归 克服回溯问题,1、区分三种类型的左递归,-直接左递归 即形如：N-N -间接左递归 即形如：N-A A-B B-N,-潜在左递归 即形如：N-N 而 ,2、直接左递归的消除,候选式： A-A|, ,A - A A- A | ,消除方法： 若：A A| ，其中不以A开头 则修改规则为：A A A A|,消去直接左递归后： E TE E +TE| T FT T *FT| F （E）| i,例4.2 文法： E E
6、+T | T T T*F | F F （E）| i,消除方法： 若：A A| ，(不以P开头) 则修改规则为：A A A A|,3、间接和潜在左递归的消除,代入法 将一个产生式规则右部的中的非终结符N替换为N的候选式。如果N有 n个候选式，右边的重复n次，而且每一次重复都有N的不同候选式来代替N。,例4.3 N-a|Bc|在S-pNq中的代入结果为 S-paq|pBcq|pq,间接和潜在左递归通常通过代入能转换为 直接左递归,4、消除一个文法的一切左递归算法,对文法G的所有非终结符进行排序 按上述顺序对每一个非终结符Pi依次执行: for( j=1； j i-1；j+) 将Pj代入Pi的产生式
7、（若可代入的话）； 消除关于Pi的直接左递归； 化简上述所得文法。,5、消除回溯、提左因子,回溯原因,若当前符号 = a，对 A 展开，而 A -1|2|m ， 那么，要知道哪一个i是获得以a开头的串的唯一替换式。 即：选择哪一个i，亦即通过查看第一个（当前）符号来发 现合适的替换式i。,怎样选择i？ 以a为头的i 如有多个i以a为头的，这是文法的问题,例如，有产生式： 语句-if 条件 then 语句 else 语句 | while 条件 do 语句 |begin 语句表 end,若要寻找一个语句，那么关键字 if，while，begin就 提示我们哪一个替换式是仅有可能成功的替换式。,抽象
8、地看问题： 若要求不得回溯，文法G（当然G不含左递归） 的必要条件是什么，也即对文法有什么要求？,若由i a，选该必中，但若j a， 就会导致无法百发百中，解决办法是对文法本身提 出要求：“不会出现以上情况”，把这些阐明清楚 是用一个FIRST()。,定义FIRST()： FIRST()= a | a,aVT 若 ，规定FIRST(),定理,若一个 AVN，就有许多FIRST(i )，如果A的任何两个候选式i和j，均有 FIRST(i ) FIRST(j ) = 意味着，A的每一候选式推导后所得的字符串第一个VT均不同。 于是，对输入符号a，如果aFIRST(i )，则a notFIRST(j
9、 )，( ji )，因此，对A的展开无疑应选候选式i ，才有可能命中。,消除回溯目的： 非终结符A的所有侯选式的首符集两两不相交 方法：提取公共左因子,若：A 1|2|n|1|2|m (其中,每个不以开头) 那么,可以把这些规则改写成 A A|1| 2|m A1|2|n,四、递归下降分析程序构造,在不含左递归和每个非终结符的所有候选式的终结首符集都两两不相交条件下，构造一个不带回溯的自上而下分析程序，该分析程序由一组递归过程组成，每个过程对应文法的一个非终结符。 这样的一个分析程序称为递归下降分析器。,1 例4.4 文法 G ：,PROCEDURE E; BEGIN T;E END;,PROC
10、EDURE T; BEGIN F;T END;,PROCEDURE E; IF SYM=+THEN BEGIN ADVANCE; T;E END;,E TE,E +TE|,T FT,PROCEDURE T; IF SYM=*THEN BEGIN ADVANCE; F;T END;,PROCEDURE F; IF SYM=iTHEN ADVANCE ELSE IF SYM=(THEN BEGIN ADVANCE; E; IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;,面临输入：i1+i2*i3时的分析步骤如下：,T *FT| F （E）| i,i
11、1 + i2 * i3 分析过程：,E,T,E,F,T,i1,PROCEDURE E; BEGIN T;E END;,PROCEDURE T; BEGIN F;T END;,PROCEDURE F; IF SYM=iTHEN ADVANCE ELSE IF SYM=(THEN BEGIN ADVANCE; E; IF SYM=) THEN ADVANCE ELSE ERROR END ELSE ERROR;,PROCEDURE T; IF SYM=*THEN BEGIN ADVANCE; F;T END;,i1 + i2 * i3 分析过程：,E,T,E,F,T,+,E,T,F,T,*,F,T
12、,i1,i2,i3,PROCEDURE E; IF SYM=+THEN BEGIN ADVANCE; T;E END;,PROCEDURE T; IF SYM=*THEN BEGIN ADVANCE; F;T END;,2、注意：,有，自动匹配，不会失败 无成功/失败消息返回 出错位置不确切,五、预测分析程序,问题：用递归子程序描写递归下降分析器，要求实现该编译系统的语言允许递归。,改进：使用一张分析表和一个栈同样可实现递归下降分析，用这种方法实现的语法分析程序叫预测分析程序。,1、预测分析程序的工作过程,预测分析程序有四部分,分析程序的动作,程序测定栈顶有X和当前输入符a，由（X，a） 决定
13、程序动作，三种可能: 1）若X=a=#，分析停止，宣告成功地完成 分析； 2）若X=a#，则X弹出栈，下移输入指针； 3）若XVN，则去查分析表M的元素MX，a，该元素或为X的产生式，或为一个出错元素。,如：MX，a=XUVW,就用WVU（U在顶）替换栈顶的X作为输出； 如：MX，a=error，则调用error程序。,对第3）条， XVN，查分析表M的元素MX，a,分析表格式,E TE E +TE| T FT T *FT | F （E）|i,例4.5 按预测分析程序，对于输入 id+id*id 所作动作如下所示：,1 #E id+id*id# 2 #ET id+id*id# ETE 3 #E
14、TF id+id*id# TFT 4 #ETid id+id*id# Fid 5 #ET +id*id# 6 #E +id*id# T 7 #ET+ +id*id# E +TE #ET id*id# #ETF id*id# T FT,M E, id = E TE,M T, id = T FT,MF, id = F id,匹配，id出栈 输入串指针后移,E,id,T,id,F,id,id,id,10 #ETid id*id# Fid 11 #ET *id# 12 #ETF* *id# T*FT 13 #ETF id# 14 #ETid id# F id 15 #ET # 16 #E # T #
15、# E 有: X=a=#，分析成功。,id,id,T ,id,*,*,F,id,id,id,T,#,E,#,#,#,结论： 输出的产生式就是最左推导的产生式。栈中放右部，等待与匹配； 表指出（栈顶，a）时，如何扩充树，出错马上发现。 实质： 栈：残缺规范句型 表：指出VN按哪一条扩充，依赖于VT,上述分析过程生成的语法树：,F (E),F id,F,T ,T ,T *FT,T ,T,T FT,T FT,T,E ,E ,E +TE,E,E TE,E TE,E,#,),(,*,+,id,id + id * id # ：,+,E,T,F,T,*,F,T,id,id,E,T,E,F,T,id,2、分析表的构造,分析表格式：,思路： 1）把产生式填到何处？ 2）按 ? 将产生式分为两种： 一种是： a 另种是： ,先要构造两个与G有关的集合：FIRST()和FOLLOW(A)； 1）定义：若G，V*，S，AVN,2）构造FIRST() 先构造FIRST(X),XV。,连续使用以下规则，直至再无终结符， 或加入任一FIRST集为止, 若XVT，则 FIRST(X)是X 若XVN ,且X-a，则 a
