04自上而下语法剖析.pptVIP

自上而下语法分析;高级语言的语法结构适合用上下无关文法描述，因此，我们将上下文无关文法作为语法分析的基础 本章和下一章，我们将介绍编译程序构造中的一些典型的语法分析方法;1 语法分析器功能;例：自顶向下构造最左推导（aabbaa) S?aAS?a A ?SbA ?SS ?ba;2 自上而下分析面临的问题;;;3 LL(1) 分析法;3.1 左递归的消除;;;例4.3：考虑文法：S?Qc|c Q ?Rb|b R ?Sa|a 消除左递归。 解：将终结符排序为R、Q、S。对于R不存在直接左递归。把R带入到Q中有关的候选式： Q ? Sab|ab|b 现在Q同样不含直接左递归，把它带入S的有关候选式： S ?Sabc|abc|bc|c 经消除S的直接左递归后我们们得到整个文法 S ?abcS’|bcS’|cS’ S’ ?abcS’|? Q ? Sab|ab|b R ?Sa|a 由于关于Q,R的规则式多余的则可化简得到： S ?abcS’|bcS’|cS’ S’?abcS’|?;3.2 消除回溯、提左因子;;;; 3.3 LL（1）分析条件;;;;4.4 递归下降分析程序构造;;;;;5 预测分析程序;5.1预测分析程序工作过程;预测分析器的总控程序： 置 ip指向 w#的第一个符号；令X为栈顶符号，a是 ip所指向的符号 BEGIN push(st,#); push(st,S); FLAG:=TRUE; WHILE FLAG DO BEGIN IF X?VT THEN IF X=a THEN { pop(st); ip:=ip+1} ELSE ERROR ELSE IF X=‘#’ THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELSE IF M[x,a]={X?X1X2…Xk} THEN {pop(st);push(st,Xk);…push(st,X1)} ELSE ERROR、 END OF WHILE; STOP END;;例：输入串为i1+i2，利用分析表进行预测分析。;计算FIRST集 若X?V?,则FIRST(X)={X} 若X?VN,且有产生式X?a…，则把a加入到FIRST(X)中;若X??也是一条产生式,则把?也加到FIRST(X)中 若X?Y…是一个产生式且Y?VN,则把FIRST(Y)中的所有非?元素都加到FIRST(X)中;若X ? Y1Y2…YK 是一个产生式,Y1,Y2,…,Y(i-1)都是非终结符,而且,对于任何j,1≤j ≤i-1, FIRST(Yj)都含有? (即Y1..Y(i-1) =* ? ),则把FIRST(Yi)中的所有非?元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj , j=1,2,…,K)均含有?,则把?加到FRIST(X)中;;计算FOLLOW集 对于文法的开始符号S,置#于FOLLOW(S)中 若Ａ? αBβ是一个产生式,则把FIRST(β)\{?}加至FOLLOW(B)中 若Ａ?αB是一个产生式,或Ａ?αBβ是一个产生式而β=* ?(即??FIRST(β)），则把FOLLOW（A）加至FOLLOW（B）中; 例4.7 对于文法 E?TE’ E’ ?+TE’|? T ?FT’ T’ ?*FT’| ? F ?(E)| i 我们构造每个非终结符的FIRST和FOLLOW集合 解：FIRST(E) = { (, i } FOLLOW(E) ={ ), # } FIRST(E’) = {+, ? } FOLLOW(E’) = { ), #} FIRST(T) = {(, i }