自下而上语法分析.ppt

1、,若文法G的任何产生式的右部都不含两个相继的非终结符， 称文法为算符文法。 即：不含形如：UVW 的产生式，U、V、WVN,G1S： S E E ET | T T T*F | F F PF | P P (E)| i,G2E： E TE E +TE |,5.3 算符优先分析法5.3.1 算符优先文法及优先表构造,1. 算符文法,2. 优先关系：设G是算符文法，不含 P产生式, 对于任何一对终结符 a，b a b G中存在形如：Pab 或 PaRb 的产生式； a. b G中存在形如：P aR 的产生式， 且R b 或 R Q b ； a .b G中存在形如：P 的产生式， 且R a 或 R a

2、Q ；,G1S： SE EET | T TT*F | F FPF | P P(E)| i,S#E# # # P (E) ( ) 2) S#E# E=ET # T * F ET # EET E=ET ,设有算符文法G，如果其任意两个终结符号之间，最 多只有一种算符优先关系成立，称G为算符优先文法。 算符优先文法是无二义的。,3. 算符优先文法,4. 优先表,二维表，行标、列标VT ，表项：存放优先关系 Aa,b= a b Aa,b= a b Aa,b= a b,G1S： S E E ET | T T T*F | F F PF | P P (E)| i,优先表,对优先关系： # # ( ) # #

3、 ,没有优先关系,FirstVT(P)= a | P a 或 P Q a a VT , P、Q VN ( P推导出的符号串的第一个终结符构成的集合) LastVT(P) = a | P a 或 P a Q a VT , P、Q VN ( P推导出的符号串的最后一个终结符构成的集合),6.计算FirstVT集合,若有 P a 或 PQ a ，则 aFirstVT(P) 若 aFirstVT(Q)，且 PQ ，则 aFirstVT(P),5. 定义集合,若有 P a 或 PQ a ，则 aFirstVT(P) 若 aFirstVT(Q)，且 PQ ，则 aFirstVT(P),For (PVN ,

4、 a VT) do FP,a=.F. ; For (P a 或PQa ) do insert(P,a); While stack非空 do 弹出stack栈顶组对(P,a); RP do insert(R,a); ,Proc insert(P,a) if FP,a=.F. then FP,a=.T.； (P,a)入stack； ,引入： 栈stack，存放二元组对 (P,a) 布尔数组F, FP,a=.T.aFirstVT(P),算法：,GS：S#E# EE+T|T TT*F|F FPF|P P(E)|i,For (PVN , a VT) do FP,a=.F. ; For (P a 或PQa

5、 ) do insert(P,a); While stack非空 do 弹出stack栈顶组对(P,a); RP do insert(R,a); ,Proc insert(P,a) if FP,a=.F. then FP,a=.T.； (P,a)入stack； ,For (PVN , a VT) do FP,a=.F. ; For (P a 或PQa ) do insert(P,a); While stack非空 do 弹出stack栈顶组对(P,a); RP do insert(R,a); ,Proc insert(P,a) if FP,a=.F. then FP,a=.T.； (P,a)入

6、stack； ,GS：S#E# EE+T|T TT*F|F FPF|P P(E)|i,GS： S#E# EE+T|T TT*F|F FPF|P P(E)|i,FirstVT(S)=# FirstVT(E)=+,*,( ,i FirstVT(T)=*,( ,i FirstVT(F)=,( ,i FirstVT(P)=( ,i ,求FirstVT： FP,a=.T. aFirstVT(P),布尔数组F,若有P a 或P aQ 则 aLastVT(P) 若aLastVT(Q) ,且 PQ, 则 aLastVT(P),算法： 与计算 FirstVT集合类似,GS： S#E# EE + T | T TT

7、 * F | F FPF | P P(E) | i,LastVT(S)= # LastVT(E)=+,*,i , ) LastVT(T)=*, i , ) LastVT(F)=, i , ) LastVT(P)= i , ) ,7.计算LastVT集合,For ( A X1 X2 XN ) do For i:=1 To N1 do if (XiVT)and(Xi+1VT ) then Xi Xi+1 ; if (XiVT )and(Xi+1VN ) and (Xi+2VT ) then Xi Xi+2; if (XiVT)and(Xi+1VN ) then bFirstVT(Xi+1) Xi

8、Xi+1 ; ,8.构造优先表算法,S#E# # # # 2) EET (aLastVT(E) (bFirstVT(T) 3) ET 不影响,GS： S#E# EE + T | T TT * F | F FPF | P P(E) | i,GS： S#E# EE + T | T TT * F | F FPF | P P(E) | i,4) TT * F (aLastVT(T) * * (bFirstVT(F),7) FP 不影响 8) P( E ) ( ) () 9) Pi 不影响,GS： S#E# EE + T | T TT * F | F FPF | P P(E) | i,短语：令GS是一文

9、法，是文法G的一个句型；如果有：S A，且 A ； 称是句型相对于非终结符A的短语。 2. 素短语：一种短语，它至少包含一个终结符，且除自身外不再包含更小的素短语。 3.最左素短语：处于句型最左边的素短语。 算符优先分析法的可归约串最左素短语。,5.3.2 算符优先分析算法,句型：P1*(P2)+P3,短语：P1 , P2 , (P2), P1*(P2), P3 , P1*(P2)+P3 素短语：(P2) 最左素短语：(P2),GS：S#E# EE + T | T TT * F | F FPF | P P(E) | i,语法树,短语：P1 , P2 , P1*P2 , P3 , P4 , P3

10、*P4 , P1*P2+P3*P4 素短语： P1*P2 , P3*P4 最左素短语： P1*P2,句型：P1*P2+P3*P4,语法树,GS：S#E# EE + T | T TT * F | F FPF | P P(E) | i,若句型为：# N1 a1 N2 a2 .Nn an Nn+1 # Ni VN , ai VT 最左素短语是满足下列条件的最左子串 Nj aj Nj+1 aj+1 . Ni-1 ai-1 Ni ai Ni+1 1) aj-1. aj 2) 3) ai .ai+1,aj aj+1 . ai-1 ai,4. 定理,找出句型中的最左素短语，选择一条合适的产生式， 将最左素短

11、语归约为该产生式的左部符号。重复上述 过程，直至句型中只存在一个符号，并且是非终结符 号，则输入串是句子。 选用合适产生式的标准： 最左素短语 x1 x2 xn , 产生式右部 y1 y2 yn 若： xiVT 则 yiVT 且 xiyi 若： xiVN 则 yiVN (但可以 xiyi ） 即：终结符必须位置匹配且为同一符号； 非终结符必须位置匹配。,5.算符优先分析算法,k=1; Sk=# ; repeat 把下一个单词读进 a ; if (SkVT) then j=k else j=k-1 ; while (Sj a) do /* 可归约 */ repeat /*找最左素短语的左端终结符

12、号*/ Q:= Sj ; if (Sj-1VT ) then j=j-1 else j=j-2; until Sj Q; 把 Sj+1 Sj+2 Sk 归约为某个N; K=j+1; Sk=N; if (Sja) or (Sj a) then k=k+1; Sk=a else error ; Until a=#,输入串：i*i+i 设：x=最靠近栈顶的VT,GS：S# E # EE + T | T TT * F | F FPF | P P(E) | i,归约序列： i*i+i = P*i+i = P*P+i,归约序列：i*i+i=P*i+i=P*P+i=T+i=T+P=E ,输入串：i*i+i

13、设：x=最靠近栈顶的VT,GS：S# E # EE + T | T TT * F | F FPF | P P(E) | i,算符优先分析法，语法树分析树 省去了Q=P 的归约步骤，所以归约效率高。,6. 分析树,归约序列：i*i+i=P*i+i=P*P+i=T+i=T+P=E,语法树,用两个离散函数 f , g 来代表优先表， f(a) , g(a) 的函数值为自然数，其中：aVT ； 要求： 若a . b 则 f(a) g(b) f(a) 入栈优先函数 (a位于左边时的函数值) g(a) 出栈优先函数 (a位于右边时的函数值),5.3.2 优先函数,1. 优先函数表示方法,GS： S# E

14、# EE + T | T TT * F | F FPF | P P(E) | i,输入串：i*i,GS：S# E # EE + T | T TT * F | F FPF | P P(E) | i,归约序列： i*i= P*i= P*P= T,设：a=最靠近栈顶的VT, 优先函数比优先表节省空间（N2 = 2*N） 运算方便，优先关系比较 = 自然数比较,a a f(a)=g(a) b a f(b)=g(a) a . b f(a)g(b) b b f(b)=g(b) ,f(a) g(b) f(b) g(a) f(a) 即：f(a)f(a) 矛盾 ,2. 优先函数优点,3. 优先函数缺点, 优先关

15、系与优先函数不是一一对应关系。 （算符优先文法，但不存在优先函数）, 信息的丢失：两个终结符号之间可能存在4种关系 (大于，小于，等于，无关），引入优先函数后，只 有3种关系（大于，小于，等于）。使得原来不存在 优先关系的两个终结符，由于与自然数对应，变得可 比较了。当发生错误时不能准确指出错误位置。,用优先关系： 两个相邻i没有优先关系，报错。,用优先函数： f(i)=8,g(i)=7,相当于i.i 归约成 NN 时才发现错误。,例：i i, 结点： fa ， ga ， aVT ， 共有2n个结点。 如果a . b 或 a b，则画从fa 到gb 的有向边； 如果a . b 或 a b，则画

16、从gb 到fa 的有向边； f(a) = 从fa出发沿弧可到达的不重复结点个数 （包括自己）。 g(a) = 从ga出发沿弧可到达的不重复结点个数 （包括自己）。 检查构造出的函数，与原来的优先关系是否矛盾， 若不矛盾，就是所需的优先函数； 若矛盾，不存在优先函数。,4. 构造优先函数 作图法,例：表达式文法，取子集：VT=, i , # ,f+可达结点=f+ , g+ , f# , g# fi可达结点=fi , g+ , f# , g# f#可达结点=f# , g# g+可达结点=g+ , f# , g# gi可达结点=gi , f+ , g+ , f# , g# g#可达结点=g# , f

17、#,优先函数存在， 本组函数可行。,可选函数组2：,验证：,作业： P133 第 3 题 说明：为简单起见，不加#号,LR分析器 = 总控程序（对所有的LR分析器，相同） + 分析表（ACTION表 + GOTO表） + 分析栈 （状态栈 + 符号栈）,输入串：a+b#,输出,5.4 LR分析法介绍,不同文法、不同LR分析器，分析表不同, 动作部分ACTION 二维数组 ACTIONS,y当状态为S，向前看符号串y时，应该 采取的动作。( y的长度 = 1 或 k ) si：将状态 i 以及当前符号分别移入状态栈、符号栈； rj：按照第 j 个产生式，对栈顶的符号串进行归约； Acc：接受输入

18、符号串，识别出是一个句子； 报错：输入符号串不是句子； 状态转换部分GOTO 二维数组 GOTOS,P 当前状态S,面对非终结符号P时,转换 到的下一个状态。,LR分析表,书 P101, LR分析表,GE： 1.EE+T 2.ET 3.TT*F 4.TF 5.F(E) 6.F i,Si:移入 i=状态栈 a=符号栈 输入前移,0 =状态栈，# =符号栈,LR分析器 标准分析算法,开始,S栈顶状态号；a 输入符号,执行ACTIONS,a,Accept 分析 成功,空白 出错,rj : 按第j条产生式归约 L=候选式长度; P=左部符号 状态栈弹出L个状态； 符号栈弹出L个符号； Go新栈顶,P=

19、状态栈； P=符号栈,结束,GE： 1.EE+T 2.ET 3.TT*F 4.TF 5.F(E) 6.F i,LR分析表,例：i*i+i,最右推导：E=E+T=E+F=E+i=T+i=T*F+i=T*i+i=F*i+i=i*i+i,LR分析法 优点,LR分析法 缺点,1)、手工实现工作量大 2)、分析表占用空间大,1)、适用于大多数上下文无关文法 2)、分析效率高 3)、报错及时 4)、可以自动生成，如：YACC,分析表种类的不同，对应不同的LR分析器。,LR分析表种类, 字的前缀：字的任意首部。 如：abc的前缀有：，a，ab，abc。 可归前缀：是指规范句型的一个前缀，这种前缀不 含句柄之

20、后的任何符号。 若： 是句型，为句柄，则为可归前缀。 活前缀：可归前缀的任意首部。 因此，只要输入串的已扫描部分保持可规约成一个活前缀，则意味着扫描过的部分没有错误。,LR(0)项目集族的构造,文法GS： SE EaA|bB AcA|d BcB|d 产生式序号 0 1 2 3 4 5 6 项目: 1. SE 2. SE （ SE ） 3. EaA 4. EaA 5. EaA （ EaA ） 6. AcA 7. AcA 8. AcA （ AcA ） 9. Ad 10. Ad （ Ad ） 11.EbB 12. EbB 13. EbB （ EbB ） 14.BcB 15. BcB 16. BcB

21、（ BcB ） 17.Bd 18. Bd （ Bd ）, 项目：在文法G的每个产生式右部添加一个圆点， 就成为G的一个LR(0)项目。,根据圆点所在的位置和圆点后的符号，把项目分为四种： 移进项目，形如 A a aVT 如：3，6，9，11 等 待约项目，形如 A B BVN 如：1，4，7，12 等 归约项目，形如 A 如：2，5，8，10 等 接受项目，形如 SS 如：2,项目: 1. SE 2. SE 3. EaA 4. EaA 5. EaA 6. AcA 7. AcA 8. AcA 9. Ad 10. Ad 11.EbB 12. EbB 13. EbB 14.BcB 15. BcB 1

22、6. BcB 17.Bd 18. Bd, 构造识别活前缀的NFA,1). 状态：每一个项目对应一个状态； 2). 定义文法GS的拓广文法GS，增加SS，并 令项目SS 为初态，SS 称为接受项目； 3). 定义状态转换弧， 若状态i为：XX1 Xi-1Xi Xi+1 Xn ， 状态j为：XX1 Xi-1 XiXi+1 Xn ， 则从状态i 画一条标志为Xi的有向边到状态j ； 若状态i为XA ，AVN， 则从状态i 画一条 边到所有状态 A 。,识别活前缀的NFA,1.SE 2.SE 3.EaA 4.EaA 5.EaA 6.AcA 7.AcA 8.AcA 9.Ad 10.Ad 11.EbB 1

23、2.EbB 13.EbB 14.BcB 15.BcB 16.BcB 17.Bd 18. Bd,状态转换弧 状态i：XXi-1Xi 状态j：XXiXi+1 从i画标志为Xi的有向边到j 若状态i为XA，AVN 从i画边到所有状态A, 将NFA确定化，得到识别活前缀的DFA,归约项目,LR(0)分析表的构造,假若一个文法G的拓广文法G，识别活前缀的DFA 中，每个状态(项目集)不存在下述情况： 1) 既含移进项目，又含归约项目； A a，A 移进-归约冲突 2) 含有多个归约项目 A，B 归约-归约冲突 则称G是一个LR(0)文法。,若I是文法G的项目集，定义I的闭包CLOSURE(I)： a)

24、I的项目都在CLOSURE(I)中b) 若A B属于CLOSURE(I)，则每一形如B 的项目也属于CLOSURE(I)c) 重复b)直到CLOSURE(I)不再扩大 定义转换函数： GO（I，X）= CLOSURE（J）其中：I为项目集，X为一文法符号 J= 任何形如AX 的项目 | A X属于I ,分析表的ACTION和GOTO子表构造方法： .若项目AaIk，且GO(Ik,a)Ij，aVT， 则：ACTIONk,a=“sj”。 .若项目AIk，对aVT#， ACTIONk,a=“rj” (设 A 是文法G的第 j 个产生式)。 .若项目SSIk，则：ACTIONk,#=“acc”。 .若

25、GO(Ik,A)Ij，AVN，则：GOTOk,A=“j”。 .其他填上“报错标志”。,LR(0)分析表为,产生式： 0.SE 1.EaA 2.EbB 3.AcA 4.Ad 5.BcB 6.Bd,在出现移进-归约冲突，或归约-归约冲突时，通过观察 当前输入符号、非终结符的后跟符号集，来确定动作。 若LR(0)规范族中含有如下状态： IXb，A，B， 其中，FOLLOW(A)FOLLOW(B)，且不包含b，,SLR(1)分析法,移进-归约冲突 归约-归约冲突,那么，当状态I面临输入符号a时， 若a=b，则移进； 若aFOLLOW(A)，用产生式 A 进行归约； 若aFOLLOW(B)，用产生式 B 进行归约； 此外，报错。,冲突性动作的这种解决办法叫做SLR(1)解决办法。,该文法的LR(0)项目集规范族为：,I0: SE EE+T ET TT*F TT*F TF F (E) Fi,I1: SE EE+T,I2: ET TT*F,I3: TF,I4: