【人工智能_编译new】第四章自上而下语法分析

第四章 语法分析 自上而下分析 本章内容 l语法分析的任务与分类 l自上而下分析面临的问题 l递归下降分析程序构造 l预测分析程序 lLL(1)文法 一、 语法分析的任务与分类 l 语法分析的任务： 对任一给定 w V T*，判断 w L （ G） l 语法分析器：是一个程序，它按照 P，做识别 w的工作 词法分析器 语法分析器 编译程序后续部分 符号表 源程序 单词符号 取下一个 单词符号 语法分析 图 4.1 语法分析器在编译程序中的地位 二、自上而下分析面临的问题 1、 主旨： 从文法开始符号出发， 自上而下 的为输入 串建立一棵语法树 l 语法分析的分类： 自下而上 自上而下 l 例 4.1 文法 G1： S cAd A ab|a 输入串： w=cad，为它建立语法树 S c A d a ba S cAd A ab A a 输入串 w : 文法 G: IP 分析过程： 1） w 输入串； IP c S 扩充； c 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还有替换式未试过，而又 可能匹配； 语法树的形成 l上述分析方法的实现： 每一非终结符对应一个递归子程序，在只生成 两个串的文法，过程无须递归，而对生成无数个串的文 法，递归是不可避免的； 递归子程序：是一个布尔过程，一旦发现它的 某个候选式与输入串匹配，它就按此式扩充语法树， 并返回 true，指针移过已匹配子串。否则， 返回 false ，保持原来的语法树和指针不变。 l程序实现： l使用记号： input_symbol：当前符号内容 input_pointer：输入字符指针 l使用过程： 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; return 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、困难和问题 l文法的左递归 l回溯 l用替换符的顺序会影响所接受的语言 如： A ab|a 改为 A a|ab l难以报告出错的确切位置 l穷举试探法 低效的分析方法 三、自上而下分析的问题解决 消除文法的左递归 克服回溯问题 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+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、消除一个文法的一切左递归算法 l对文法 G的所有非终结符进行排序 l按上述顺序对每一个非终结符 Pi依次执行 : for( j=1； j 1| 2| m ， 那么，要知道哪一个 i是获得以 a开头的串的唯一替换式。 即：选择哪一个 i，亦即通过查看第一个（当前）符号来发 现合适的替换式 i。 怎样选择 i？ 以 a为头的 i 如有多个 i以 a为头的，这是文法的问题 例如，有产生式： 语句 -if 条件 then 语句 else 语句 | while 条件 do 语句 |begin 语句表 end 若要寻找一个 语句 ，那么关键字 if， while， begin就 提示我们哪一个替换式是仅有可能成功的替换式。 抽象地看问题： 若要求不得回溯，文法 G（当然 G不含左递归） 的必要条件是什么，也即对文法有什么要求？ 若由 i a ，选该 必中，但若 j a ， 就会导致无法百发百中，解决办法是对文法本身提 出要求： “ 不会出现以上情况 ” ，把这些阐明清楚 是用一个 FIRST( )。 l定义 FIRST( )： FIRST( )= a | a, aV T 若 ，规定 F IRST( ) l定理 若一个 A VN，就有许多 FIRST( i )，如果 A的 任何两个候选式 i和 j，均有 FIRST( i ) FIRST( j ) = 意味着， A的每一候选式 推导后所得的字符串 第一个 VT均不同。 于是，对输入符号 a，如果 a FIRST( i )，则 a not FIRST( j )， ( ji )，因此，对 A的展开无疑应 选候选式 i ， 才有可能命中。 l消除回溯目的： 非终结符 A的所有侯选式的首符集两两不相交 l方法：提取公共左因子 若 ： A 1| 2| n| 1| 2| m (其中 ,每个 不以 开头 ) 那么 ,可以把这些规则改写成 A A | 1| 2| m A 1| 2| n 四、递归下降分析程序构造 在 不含左递归 和 每个非终结符的所有候选 式的终结首符集都两两不相交 条件下，构造一 个不带回溯的自上而下分析程序，该分析程序 由一组递归过程组成，每个过程对应文法的一 个非终结符。 这样的一个分析程序称为 递归下降分析器。 E TE E +TE| T FT T *FT| F （ E） | i 每个非终结符所对应的递归子程序如下所示： 1 例 4.4 文法 G ： PROCEDURE E; BEGIN T;E END; PROCEDURE 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 i1 + i2 * i3 分析过程： E T E F T i1 PROCEDURE E; BEGIN T;E END; T; F;T 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 i1 i2 i3 PROCEDURE E ; IF SYM=+THEN BEGIN ADVANCE; T;E END; PROCEDURE T ; IF SYM=*THEN BEGIN ADVANCE; F;T END; 2、注意： 有 ，自动匹配，不会失败 无成功 /失败消息返回 出错位置不确切 五、预测分析程序 问题： 用递归子程序描写递归下降分析 器，要求实现该编译系统的语言允 许递归。 改进： 使用一张分析表和一个栈同样可实现递 归下降分析，用这种方法实现的语法分析程序 叫 预测分析程序 。 a 总控程序 预测分析表 M x # 输 出 栈 输入串 1、预测分析程序的工作过程 l预测分析程序有 四 部分 求值 X:=A Ba ， 则 a FIRST(X) X- ， 则 FIRST(X) 若 XV N ,X-Y, YV N ,则 FIRST(Y) FIRST(X) 进而： X-Y1Y2Y i-1Yi Yk ,YjV N ,1ji-1 FIRST(Yj )，即 Y1Y2Y i-1 ，则 当 则 FIRST(X) l再进而构造 FIRST(X1X2 Xn) FIRST(X1)的 非 终结符 加入 FIRST( ) 若 FIRST(X 1)， 则 FIRST(X2)的所有非 终结符加入 FIRST( ) 若 FIRST(X 1), FIRST(X 2)， 则 FIRST(X3)的所有非 终结符加入 FIRST( ) 最后，若 FIRST(Xi), i=1n，则 加入 FIRST( ) 3）构造 FOLLOW(A) 应用下列规则，直到再没有什么加进任一 FOLLOW为止 #属于 FOLLOW(S) 若存在 A- B ， 则 FIRST( ) FOLLOW(B)， 除 外 若有 A- B，或 A- B 且 FIRST( )， 则 FOLLOW(B) FOLLOW(A) 4）例 4.6 已知文法 G： E TE T *FT| E +TE| F （ E） | i T FT 求它的 FIRST( ),FOLLOW(A) FIRST集的构造： FIRST(E) = FIRST(T) = FIRST(F) = ( , i FIRST(E) = + , FIRST(T) = * , #属于 FOLLOW(S) 若存在 A- B ，则 FIRST( ) FOLLOW(B),除 外 由 得： FOLLOW(E) = # 由 得： E TE 则 FIRST(E) FOLLOW(T)， 即 FOLLOW(T) = + T FT 则 FIRST(T) FOLLOW(F) , 即 FOLLOW(F) = * F （ E） 则 FIRST( ) ) FOLLOW(E) , 即 FOLLOW(E) = # , ) FOLLOW集的构造： FIRST(T) = * , FIRST(E) = + , 即 FOLLOW( F ) = * , , , 若有 A- B，或 A- B 且 FIRST( ),则 FOLLOW(B) FOLLOW(A) FOLLOW( E ) = ) , # FOLLOW( T ) = + FOLLOW( F ) = * 由 得 ： E TE 得 FOLLOW(E) FOLLOW(E)， 即 FOLLOW( E ) = , ) # E TE 且 E 得 FOLLOW(E) FOLLOW(T)， 即 FOLLOW( T ) = + , , ) T FT 得 FOLLOW(T) FOLLOW(T), 即 FOLLOW( T ) = , , T FT 且 T 得 FOLLOW(T) FOLLOW(F), ) # + ) + FIRST(E) = FIRST(T) = FIRST(F) = ( , i FIRST(E) = + , FIRST(T) = * , FOLLOW(E) = FOLLOW(E) = ) , # FOLLOW(T) = FOLLOW(T) = + ， ) ， # FOLLOW(F) = * , + , ) , # 最终构造结果： 5）构造分析表 算法：输入 G1 文法，输出 分析表 M 对文法的每一个 A- ,做 和 ； 对于任 aFIRST ( ),把 A- 加进 MA， a 若 FIRST( )，则把 A- 加进 MA ,b ,b FOLLOW(A)； 若 FIRST( )， $ FOLLOW(A), 则把 A- 加进 MA ,$ 6)例 4.7 算法应用于文法 G E TE 填法： FIRST(TE)=FIRST(T)= ( , id M E , ( = E TE M E ,id = E TE E +TE 填法： M E, + = E +TE E 填法： FOLLOW(E)= ), # M E, ) = E M E , # = E 六、 LL（ 1）分析法 lLL：第一个 L表示从左到右扫描输入串， 第二个 L表示最左推导 l（ 1）：表示分析时每一步只需向前查看一个符号 2、 LL（ 1）文法的条件 1、 LL（ 1）文法 一个文法 G，若它的分析表 M不含多重定义入口，则称它是 一个 LL（ 1）文法 。 （ 1） FIRST( ） FIRST( ) = （ 2）若 ，则 FIRST（ ） FOLLOW（ A） = 文法 G是 LL(1)的，则对于 G的每一个非终结符 A 的任何两个不同产生式 A - | ,有： 使用 LL(1)文法，一定可以实现 不带回溯 的 自上而下分析 ； 对 A- | ， 若条件（ 1）不成立， 则 FIRST( ） FIRST( ) ， 假 设， FIRST( ） FIRST( ) = a 那么 ，当 A面临输入符号 a，而 a同时属于 FIRST( ）和 FIRST( ) ，则分析无法继续进行下 去，因为不能确定用哪一个候选式可以保证一定 能够得到匹配而不进行回溯。 实质 就是分析表的 MA, a中包含两条候选式 A - A - 反之， 分析表的 MA, a中只包含一条候选式 则意味着可以进行确定性的无回溯的分析。 对 A- | ， 若 ，且 条件（ 2）不成立， 则 FIRST（ ） FOLLOW（ A） 假 设， FIRST( ） FOLLOW(A) = a 那么，当 A面临输入符号 a时 ， 若选候选式 A - ，则由于 a FIRST( ）可以 使 a一定得到匹配； 同时，若选候选式 A - 也可以满足要求， 这是 由 ，而 a FOLLOW(A) 。 实质 同样是由于分析表的 MA, a中包含两条候选式： A - A - 而这与 LL(1)文法的定义互相矛盾。 综上所述， 若某文法为 LL(1)文法，则该文 法一定满足这两个条件，它意味着进行自上而下分 析时可以对候选式进行不带回溯的确定性的选择。 因此，不能确定用哪一个候选式可以保 证一定能够得到 a的后续匹配而不进行回溯。 但是，条件语句文法不能改造成 LL(1