编译原理（王晓斌）编译第九章.ppt

第九章 自上而下的语法分析 第一节 引言 一. 语法分析的功能 符号串 （二元式流） 正确句子的语法树 报告语法错误 语法分析程序 二. 语法分析方法的分类 u语法分析: 自上而下(自顶而下) 自下而上(自底而上) u自上而下语法分析法:或从开始符号出发,找最 左推导;或从根开始,构造推导树。 u自下而上语法分析法:从输入串开始,归约,直 至文法开始符。 第二节 回溯分析法 一.一个实例 SxAy Aaba 输入串为xay,说明分析过程 S x A y S x A y a b S x A y a 二. 存在的问题 (1)回溯公共左因子的存在 A1| 2 (2)左递归 AA 或 AA (3)产生式也会引起回溯 SaAS Sb AbAS A + 第三节 递归下降分析法 一. 提取公共左因子 A1| 2| . |n| 改写为:AB| B 1| 2| . |n 例： SxAy Aaba 改写为： SxAy AaB Bb 二. 左递归的消除 (1)直接左递归的消除 PP 改写为:PP PP 一般地 AA1|A2|Am|1|2|n （i，j不以A开头） 改写为:A1P 2P. . . nP P 1P2P. . .mP (2)间接左递归的消除 PP (a)将文法G的所有非终结符按任一给定的 顺序排列,设为A1,A2,An; + (b)消除可能的左递归; for i:=1 to n do begin for j:=1 to i-1 do 把一个形如AiAj的产生式改写为 Ai1|2|k 其中Aj1|2|k是Aj的所有产生式; 消除Ai产生式的直接左递归 end (c)化简 以 SQcc QRbb RSaa 为例,按S,Q,R排列,或R,Q,S排列 u按S、Q、R排列, 代入后 SQcc QRbb R Rbcabcacaa SQcc QRbb RSaa u消除R中的直接左递归 R bcaRcaRaR R bcaR u文法产生的语言:(bca|ca|a)(bca)*bc|bc|c u按R、Q、S排列, 代入后 RSaa QSababb SSabcabc bcc SQcc QRbb RSaa u消除S中的直接左递归 SabcSbcScS SabcS u文法产生的语言:(abc|bc|c)(abc)* 三. 递归下降分析器的构造 当改造文法为无公共左因子,无左递归时, 让每个非终结符对应一个过程;该过程对 相应的非终结符产生式的右部短语进行 语法分析 例: G(E) EE+TT TT*FF F(E) i 消除左递归: ETE E+TE TFT T*FT F(E)i u过程match:匹配单词符号,并读入下一符号 u变量lookahead:即将处理但尚未处理的符号 procedure match(t:token); begin if lookahead=t then lookahead=nexttoken else error end; procedure E; begin T; E end; procedure T; begin F; T end; ETE TFT procedure E; if lookahead=+ then begin match(+); T; E end; procedure T; if lookahead=* then begin match(*); F; T end; E+TE T*FT procedure F; if lookahead=i then match(i) else if lookahead=( then begin match(); E; if lookahead=) then match() else error end else error; F(E)i E T F i i M(i) E T F i i M(i) i+i*i#的递归下降分析过程 + + M(+) * # * T M(*) i F # # T E M() # # # # M(i)M() ETE E+TE TFT T*FT F(E)i T + + M() 四. 扩充的BNF (1)表示形式: u用花括号表示闭包运算* ; u用 表示可任意重复0次至n次 =0=; u用方括号表示 ,即表示的出现可 有可无(等价于) n 0 0 0 1 0 例: 实数可定义为 decimal signinteger.digitexponent exponentEsigninteger integerdigitdigit sign+- (2)左递归的消除 pxy. zpv 改写成: p(xy. .z)v (3)文法的转换图表示 产生式右端可用转换图表示。 如: ET+T 表示成 012 T + (4)递归下降分析器的改进 procedure E; begin T; while lookahead=+ do begin match(+); T end end; procedure T; begin F; while lookahead=* do begin match(*); F end end; procedure F; if lookahead=i then match(i) else if lookahead=( then begin match(); E; if lookahead=) then match() else error end else error； i+i*i#的递归下降分析过程 E T F i i M(i) T F i M(i) + +i M(+) * F M(i) i # # M(*) ET+T TF*F F(E)i 第四节 预测分析法 一. 预测分析过程 1. 预测分析表 形式:MA,a矩阵, AVN,a VT# 内容:A或出错标志(空白) 预测分析表 E E T T F i+ * () # ETE ETE E+TE TFTTFT T*FT FiF(E) EE TTT 2. 分析方法 初始时,#和开始符入栈,输入指针指 向第一个符号,然后根据下推栈栈顶 符x和当前输入符a进行工作: x=a=#, 成功 x=a#, 匹配 xVN, 查表 例:i+i*i的分析过程 下推栈输入串查分析表 i+i*i#E #ET #ETF #ET #ETi #E #ET #ET+ i+i*i# +i*i# i+i*i# i+i*i# +i*i# +i*i# i*i# ETE TFT TFT Fi T E+TE #ETF i*i#ETi #ET #ETF* #ETi #ETF #ET # #E *i# i# *i# i# # # # T*FT 结束 Fi T i*i#Fi E 二. FIRST集和FOLLOW集 1FIRST集 (1)定义:对(VTVN)*,有 FIRST（）a|a. . . , aVT 若,则FIRST() (2)对文法符号XVTVN (3)当=X1X2Xn时 * * uXVT, 则FIRST(X)=X; uXVN, 分三种情形: Xa XY XY1Y2Yk 例子：X Y1Y2A Y1 y1 Y2 y2 A a FIRST(Y1)=y1, FIRST(Y2)=y2, FIRST(A)=a FIRST(X)=y1, y2, a 2. FOLLOW集 (1)定义:对AVN ,有 FOLLOW(A)=aS . . .Aa. . . ,aVT 若S .A, 则#FOLLOW(A),其中S为开始符号 * * (2)求法 u# FOLLOW(S) uAB: 将FIRST()-加入FOLLOW(B) uAB或者AB且: 将FOLLOW(A)加入 FOLLOW(B) 注意: 求FOLLOW(B)实际上是考察B在产生式右 端的每一次出现 * 例: G(E) ETE E+TE TFT T*FT F(E)i E E T T F FIRST FOLLOW ( i ( i ( i + * ) # ) # + ) # + ) # * + ) # ETE E+TE TFT T*FT F(E)i 三. 预测分析表的构造 1. 构造算法 对每个产生式A 对aFIRST(),将A记入MA,a中; 若FIRST(),对bFOLLOW(A), 将A记入MA,b中; 凡未被定义的MA,a项中标以出错标志。 如: G(E) ETE E+TE TFT T*FT F(E)i E E T T F FIRST FOLLOW ( i ( i ( i + * ) # ) # + ) # + ) # * + ) # 预测分析表 E E T T F i+ * () # ETE ETE E+TE TFTTFT T*FT FiF(E) EE TTT G(E) ETE E+TE TFT T*FT F(E)i 2. 预测分析表的改进 MA,a中只记产生式右部; 对=x1x2. . .xn, 在M,a中记xn xn-1. x1; 当xn xn-1. x1的x1VT时, x1必为a, x1无须入栈,只移动输入指针。 四. LL(1)文法 设上下文无关文法G的产生式形如 A1|2|n, 当G满足下述条件时则称为 LL(1)文法: FIRST(i) FIRST(j)=, ij,i,j=1,2,. . .,n 若i,则FIRST(j) FOLLOW(A)=, j=1,2,. . .,n且ji。 于是,在自顶向下分析时,可根据当前输入符号 a选择aFIRST(i)的Ai。 * 五. 非LL(1)文法的处理 （1）并非任何文法G都可以改写成LL(1)文 法； （2）对非LL(1)文法可以根据语义进行处 理。 例：下述文法具有二义性 S i C t Si C t S e Sa C b 提取公共左因子后： S i C t S Sa S e S C b FIRST(S)=i, a FIRST(S)=e, FIRST(C)=b