编译原理第4章语法分析课件.ppt

1、编译原理第四章 语法分析2022-6-11编译原理第四章 语法分析2022-6-12编译原理第四章 语法分析2022-6-13在词法分析的基础上，根据语法规则，从单词符号串中识别出识别出各种语法成分，同时进行语法检查，检查各种语法成分在语法结构上的正确性。编译原理第四章 语法分析2022-6-14从文法的开始符号出发，以从文法的开始符号出发，以给定的符号串为目标，根据文法规则，正向推给定的符号串为目标，根据文法规则，正向推导出给定符号串的一种方法。导出给定符号串的一种方法。从给定的符号串出发，反复使从给定的符号串出发，反复使用文法中有关产生式的左部去替换当前符号串用文法中有关产生式的左部去替换

2、当前符号串中的相应子串，逐步归约成文法开始符号的一中的相应子串，逐步归约成文法开始符号的一种方法。种方法。编译原理第四章 语法分析2022-6-15对任何输入串，试图用一切可能的方法，从文法的开始符号出发，采用最左推导，自上而下为输入串建立一棵语法树。设有文法：SxAyA* | *输入串：x*y看匹配过程编译原理第四章 语法分析2022-6-16当文法为左递归时，会使分析程序进入无限循环之中。若文法中有非终结符P=P(文法左递归)输入某输入串w=a1a2an 就有P= P= P 如此循环，不会终止编译原理第四章 语法分析2022-6-17引进新的非终结符，改写文法规则式。例如：算术表达式文法左

3、递归EE+T | TETETT*F | FE+TE| F(E) | iTFTT*FT | F(E) | i编译原理第四章 语法分析2022-6-18一般情况：有多个直接左递归：其中，每个 都不等于 ，而每个都不以P开头，则上式改写为 例如：AAc | Aad | bd | e改写为： A bd A | e A A c A | ad A | 编译原理第四章 语法分析2022-6-19采用扩充的BNF表示法改写文法规则式l用花括号表示符号串出现0次或多次。即*标识符：Il l | d 或Il l | d 7 l中括号表示是可供选择的符号串。if B then else l使用圆括号，可以在规则中提

4、因子。UXY|XW|XZUX(Y|W|Z)例如：算术表达式文法左递归EE+T | TET+TTT*F | FTF*FF(E) | i F(E) | i编译原理第四章 语法分析2022-6-110(1)把文法G的所有非终结符按任一顺序排列成P1 , P2 , Pn ; (2)执行循环语句：for i:=1 to n do将规则 PiPj 改写；改写方法：Pj1 | 2 | n 则 Pi1 | 2 | n 消除关于Pi的直接左递归end(3)化简由(2)得到的文法。编译原理第四章 语法分析2022-6-111例如：消除下面文法的左递归。文法：SQc | cQRb | bRSa | a(1)排列：R

5、 , Q , S(2)对对R ：没有直接左递归，不执行内循环 对对Q：将R代入Q变为 QSab | ab | b ，也没有直接左递归，不执行内循环。 对对S：将Q代入S变为 SSabc | abc | bc | c消除S的直接左递归，得下面文法： Sabc S| bc S | c S Sabc S| (3)Sabc S| bc S | c S QSab | ab | b Sabc S| RSa | a若排列方法不同，得到的文法也可能不同，但等价编译原理第四章 语法分析2022-6-112如果对同一个非终结符号，有若干个产生式右部 A 选择哪一个产生式匹配呢？ 匹配不好就产生回溯。回溯使语法分析

6、器的动作不确定。要消除回溯，必须使文法具有一定的特性。例如：ScAdAad | a 输入符号w=cad要求各规则式右部所推出的终结首符号的集合两两不相交。编译原理第四章 语法分析2022-6-113对文法中每一个非终结符A，如有规则： 则下面条件成立 上例中：FIRST(ab) FIRST(a)=a a=a 提取公共左因子提取公共左因子例如：if E then S1 else S2 | if E then S1 改写为： if E then S1 BB else S2 | 编译原理第四章 语法分析2022-6-114若满足条件 是否完全避免回溯呢？上例中： ScAdAad | a改写为： Sc

7、AdA aA Ad | 输入符号w=cad 匹配d可能失败，差条件非终结符号A的后继符号的集合： 上例中：FIRST(d) FOLLOW(A)=d 产生回溯编译原理第四章 语法分析2022-6-115构造不带回溯的自上而下分析的条件是：1.文法不含左递归2.对文法中每一个非终结符A，如有规则： 则下面条件成立 3.对文法中每一个非终结符A，若它的某个产生式首符集包含 时 ，则：满足以上条件的文法称为文法。对于一个LL(1）文法，可以构造无回溯的自上而下分析。编译原理第四章 语法分析2022-6-116若 =a ，且a是终结符，则FIRST( )=a。若 =X ，且X是非终结符，且X=b，则把终

8、结符b加入到FIRST( )中。若 =X1X2Xk，且X1 , X2 , Xk 都是非终结符，而X1X2Xi=，则把 FIRST(Xi+1Xi+2Xk)加入到FIRST( )中。编译原理第四章 语法分析2022-6-117若有产生式B Aa ,且a是终结符，则把a加入到FOLLOW(A)中。若有产生式B AX ,且X是非终结符 , 则把FIRST(X)加入到FOLLOW(A)中。若有产生式B A，或B A，但=，则把FOLLOW(B)加入到FOLLOW(A)中。若A是文法的开始符号，则把结束符#加入到FOLLOW(A)中。编译原理第四章 语法分析2022-6-118例：已知文法例：已知文法GS

9、:SaSb | PPbPc | bQcQQa | a消除文法左递归后是不是消除文法左递归后是不是LL(1)文法？文法？解：消除文法左递归得到：解：消除文法左递归得到：SaSb | PPbPc | bQcQaQQaQ| 提取公共左因子后得文法：提取公共左因子后得文法：SaSb | PPbP P Pc | QcQaQQaQ| 计算计算FIRST和和FOLLOW集合：集合：FIRST(S)=a,bFIRST(P)=bFIRST(P)=a,bFIRST(Q)=aFIRST(Q)=a, Follow(S)=b,# Follow(P)=b,c,# Follow(P)=b,c,# Follow(Q)=c F

10、ollow(Q)=c 是是LL(1)文法文法编译原理第四章 语法分析2022-6-119例：将文法改写成例：将文法改写成LL(1)文法。文法。SS*aP | aP | *aPP+aP | +a解：消除文法左递归、提取公共左因子得到：解：消除文法左递归、提取公共左因子得到： SaPS | *aPS S *aPS | P+aP PP | 计算每个非终结符的计算每个非终结符的FIRST和和FOLLOW集合：集合：FIRST(S)=a,*Follow(S)=#FIRST(S)=*, Follow(S)=#FIRST(P)=+Follow(P)=*, #FIRST(P)=+, Follow(P)=*,#

11、以上文法是以上文法是LL(1)文法。文法。编译原理第四章 语法分析2022-6-120已知文法：GS：SAB | PQxAxy | mBbCCbC | PpP | Qq如果要保持文法为LL(1)文法，下列哪几个产生式不能加入到该文法中？为什么？（1）SbC（2）AbC（3）B （4）Q编译原理第四章 语法分析2022-6-121解：解：(1) 加入加入SbC后文法为：后文法为：SAB | PQx | bCAxy | mBbCCbC | PpP | Qq对对S: First(AB) First(PQx) First(bC)=x,m p,q b = 对对A: First(xy) First(m)

12、= x m=对对C: First(bC) Follow(C) = b #=对对P: First(pP) Follow(P) = p q=加入加入SbC后文法是后文法是LL(1)文法。文法。编译原理第四章 语法分析2022-6-122(2) 加入加入AbC后文法为：后文法为：SAB | PQxAxy | m | bCBbCCbC | PpP | Qq对对A: First(xy) First(m) First(bC)=x m b = 对对C:first(bC) follow(C)=b b,#=b不是不是LL(1)文法。文法。(3) 加入加入B 后文法为：后文法为：SAB | PQxAxy | mB

13、bC | CbC | PpP | Qq对对B: First(bC) Follow(B)=b # = 是是LL(1)文法。文法。编译原理第四章 语法分析2022-6-123(4) 加入加入Q 后文法为：后文法为：SAB | PQxAxy | mBbCCbC | PpP | Qq | First(S)=x,m,p,qFollow(S)=#First(A)=x,mFollow(A)=bFirst(B)=bFollow(B)=#First(C)=b, Follow(C)=#First(P)=p, Follow(P)=q,xFirst(Q)=q ,Follow(Q)=x对对S: First(AB) Fi

14、rst(PQx) = x,m p,q,x =x 加入加入Q 后文法不是后文法不是LL(1)文法。文法。编译原理第四章 语法分析2022-6-124定义规则的选择集合SELECT，设 A 是文法G的任一条规则，其中 AVN , (VNVT)* ，定义 SELECT(A ) =FIRST() FIRST()FOLLOW (A) */若 *若 编译原理第四章 语法分析2022-6-125例 设有文法GA: AaB | dBbBA | SELECT(AaB ) =FIRST(aB) = a SELECT(Ad ) =FIRST(d) = d 编译原理第四章 语法分析2022-6-126 b SELEC

15、T(BbBA ) =FIRST(bBA) = = , $, d, a FOLLOW(B)SELECT(B) =FIRST() FOLLOW(B) = $, d, a AaB | dBbBA | 编译原理第四章 语法分析2022-6-127LL(1)文法定义一个上下文无关文法 G是LL(1)文法, 当且仅当对 G 中每个非终结符A的任何两个不同的规则 A | ，满足 SELECT(A )SELECT(A) = 其中 、中至多只有一个能推出串。 编译原理第四章 语法分析2022-6-128例1 设有文法GS:S aAbA de | dSELECT(Ade)= FIRST(de)=dSELECT(A

16、d)= FIRST(d)=dSELECT(Ade)SELECT(Ad) 由LL(1)文法定义可知，该文法不是LL(1)文法，因此对输入串不能进行确定的自上而下分析。 编译原理第四章 语法分析2022-6-129例2 设有文法GA A aB | dB bBA | 则 SELECT(AaB)=FIRST(aB)=a SELECT(Ad)=FIRST(d)=d SELECT(BbBA)=FIRST(bBA)=b SELECT(B)=FIRST()FOLLOW(B)=a, d, $ = , a, d, $ 编译原理第四章 语法分析2022-6-130所以 SELECT(AaB)SELECT(Ad)=S

17、ELECT(BbBA)SELECT(B)=由定义可知，GA是LL(1)文法，对任何输入串W可进行确定的分析。 编译原理第四章 语法分析2022-6-131例3 设有文法GS:S aABA bB | dA | B a | e SELECT(AbB)=FIRST(bB)= b SELECT(AdA)=FIRST(dA)= d SELECT(A)=FIRST()FOLLOW(A) = a, e = , a, e 试判断该文法是否LL(1)文法。编译原理第四章 语法分析2022-6-132 SELECT(Ba)=FIRST(a)= a SELECT(Be)=FIRST(e)= e SELECT(AbB

18、)SELECT(AdA)=SELECT(AbB)SELECT(A)=SELECT(AdA)SELECT(A)=SELECT(Ba)SELECT(Be)=S aABA bB | dA | B a | e 该文法为LL(1)文法编译原理第四章 语法分析2022-6-133条件：要求文法为LL(1)文法1 基本思想：对每一个非终结符，构造相应的递归子程序，以完成该非终结符所对应语法成分的分析和识别任务。编译原理第四章 语法分析2022-6-1342 方法：方法：为每一个非终结符，构造相应的递归过程，过程的名为每一个非终结符，构造相应的递归过程，过程的名字表示规则左部的非终结符；过程体按规则右部符号字

19、表示规则左部的非终结符；过程体按规则右部符号串的顺序编写。串的顺序编写。对于产生式对于产生式：Ux1 | x2 | xn 则编写则编写if ch in FIRST(x1) then p(x1)else if ch in FIRST(x2) then p(x2) else error ;对于符号串对于符号串x=y1 y2yn ; p(x)的含义为：的含义为：begin p(y1) ; p(y2) ; p(yn) end 如果如果yiVT 则则if ch=yi then read(ch) else error 对于对于U;则则 if chFollow(U) then returnelse erro

20、r ;编译原理第四章 语法分析2022-6-135举例：设有文法G：EE+T | TTT*F | FF(E) | i试构造一个识别该文法句子的递归下降分析程序。消除文法左递归ETEE+TE| TFTT*FT | F(E) | i 改写后的文法是否为LL(1)文法：对E：First(+TE) Follow(E)=+ #, )=对T：First(*FT) Follow(T)=* +,#, )=对F： First(i) First( (E) )=i ( = 是LL(1)文法编译原理第四章 语法分析2022-6-136构造递归下降分析程序。定义：advance:读下一个单词并放入全程变量sym中 er

21、ror：错误诊断处理程序编程如下：主: advance;E ;procedure E; begin T; Eend;procedure E;beginif sym=+ thenbegin advance; T; Eend;else if symfollow(E) then return else errorEnd;编译原理第四章 语法分析2022-6-137 Procedure T ;BeginF ; TEnd;Procedure TBegin if sym=* thenbegin advance; F ; T;end else if sym not in +,),#then error el

22、se returnEnd;Procedure FBegin if sym=i then advance; else if sym=( then beginadvance;E; if sym=) thenadvance;else error; end else error;End; 编译原理第四章 语法分析2022-6-138若改写文法用BNF范式表示：ET+TTF*FF(E) | i则编程如下：Procedure E;BeginT;while sym=+ do beginadvance;T;endendProcedure T;BeginF;while sym=* do beginadvance

23、;F;endend编译原理第四章 语法分析2022-6-139 例如：编译原理第四章 语法分析2022-6-140 编译原理第四章 语法分析2022-6-141 编译原理第四章 语法分析2022-6-142 PROCEDURE BEGIN IF SYM=iTHEN READWORD ELSE ERROREND;编译原理第四章 语法分析2022-6-143 PROCEDURE BEGIN编译原理第四章 语法分析2022-6-144 编译原理第四章 语法分析2022-6-145条件：要求文法为LL(1)文法L从左到右进行分析L每次进行最左推导(1)向前查看一个符号编译原理第四章 语法分析2022-

24、6-146a1a2aian#总控程序LL(1)分析表x Z1#TjSkj编译原理第四章 语法分析2022-6-147文法G分析表M对文法中每一个产生式A，按照下述规 则确定M中各个元素。对于FIRST()中的每一个终结符a置为 MA , a=A 若空串 FIRST()，则对Follow(A)中的每一个终结符b置为 MA , b=A 把M中未定义的元素置为error。编译原理第四章 语法分析2022-6-148例如：已知文法GE: 试构造分析表。ETEE+TE| TFTT*FT | F(E) | i对ETE产生式：First(TE)=( , i 置 ME , ( = ETEME , i = ET

25、E编译原理第四章 语法分析2022-6-149编译原理第四章 语法分析2022-6-150编译原理第四章 语法分析2022-6-151例如：已知文法G，请利用LL(1)分析表给出输入串i1*i2+i3的分析过程。GE:ETEE+TE| TFTT*FT | F(E) | i编译原理第四章 语法分析2022-6-152 编译原理第四章 语法分析2022-6-153例2：已知文法GA：AaAa | 该文法是LL(1)文法吗？为什么？若采用LL(1)方法进行语法分析，请构造该文法的LL(1)分析表？若输入符号串为“aaaa”，请给出语法分析 过程。请给出该文法的递归下降分析子程序。编译原理第四章 语法

26、分析2022-6-154解：Follow(A)=# First(a)=a , # 有: First(A) Follow(A)=a , a , # 该文法不是LL(1)文法。修改文法 GA : AaaA | 由于：First(A) Follow(A)= a , # = GA 是LL(1)文法该文法的分析表为：编译原理第四章 语法分析2022-6-155若输入符号串为“aaaa”，则分析过程如下。编译原理第四章 语法分析2022-6-156编译原理第四章 语法分析2022-6-157例3：已知文法GP:Pbegin d ; X endXd ; X | sYY ; sY | 作出该文法的LL(1)分

27、析表。解：Follow(Y)=Follow(X) Follow(Y)=end该文法的LL(1)分析表为：编译原理第四章 语法分析2022-6-1581.设字母表=a,b，给出上的正规式R=(a|ba)*求最小化的DFA M ，使得L(M)=L( R)。求右线性文法G，使得L(G)=L( M)。2.已知文法GM为：MTBTBa | BDb |eT | Dd | 首先计算每个非终结符的First集和Follow集，然后判断该文法是不是LL(1)文法。编译原理第四章 语法分析2022-6-1593.已知文法GS:SBAABS | dBaA | bS | c求：每一个非终结符的First集和Follow集。证明文法G是LL(1)的。构造LL(1)分析表。写出句子adccd的分析过程