自下而上语法分析.ppt

《自下而上语法分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、若文法G的任何产生式的右部都不含两个相继的非终结符，称文法为算符文法。即：不含形如：U···VW···的产生式，U、V、W∈VNG1[S]：√S→＃E＃E→E＋T

2、TT→T*F

3、FF→P↑F

4、PP→(E)

5、iG2[E]：×E→TE’E’→+TE’

6、ε§5.3算符优先分析法§5.3.1算符优先文法及优先表构造1.算符文法2.优先关系：设G是算符文法，不含P→ε产生式,对于任何一对终结符a，b⑴abG中存在形如：P→···ab···或P→···aRb···的产生式；⑵a＜.bG中存在形如：P→··

7、·aR···的产生式，且Rb···或RQb···；⑶a.＞bG中存在形如：P→···Ｒｂ···的产生式，且R···a或R···aQ；G1[S]：S→＃E＃E→E＋T

8、TT→T*F

9、FF→P↑F

10、PP→(E)

11、iS→#E#∴##P→(E)∴()2)S→#E#E=>E＋T∴#<·＋E→E＋TT=>T*F∴＋<·*3)S→#E#E=>E＋T∴＋·>#E→E＋TE=>E＋T∴＋·>＋设有算符文法G，如果其任意两个终结符号之间，最多只有一种算符优先关系成立，称G为算符优先文法。算符优先文法是无二义的。3.算

12、符优先文法4.优先表二维表，行标、列标∈VT，表项：存放优先关系A[a,b]=‘’abA[a,b]=‘＜·’a＜·bA[a,b]=‘·＞’a·＞b＋*↑i()#＋.＞＜.＜.＜.＜..＞.＞*.＞.＞＜.＜.＜..＞.＞↑.＞.＞＜.＜.＜..＞.＞i.＞.＞.＞.＞.＞(＜.＜.＜.＜.＜.).＞.＞.＞.＞.＞#＜.＜.＜.＜.＜.G1[S]：S→＃E＃E→E＋T

13、TT→T*F

14、FF→P↑F

15、PP→(E)

16、i优先表对优先关系：##()#<·＋＋<·*＋·>#＋·>＋没有优先关系FirstV

17、T(P)={a

18、Pa…或PQa…a∈VT,P、Q∈VN}(P推导出的符号串的第一个终结符构成的集合)LastVT(P)={a

19、P…a或P…aQa∈VT,P、Q∈VN}(P推导出的符号串的最后一个终结符构成的集合)6.计算FirstVT集合若有P→a…或P→Qa…，则a∈FirstVT(P)若a∈FirstVT(Q)，且P→Q…，则a∈FirstVT(P)5.定义集合若有P→a…或P→Qa…，则a∈FirstVT(P)若a∈FirstVT(Q)，且P→Q…，则a∈FirstVT(P)For(P∈VN

20、,a∈VT)doF[P,a]=.F.;For(P→a···或P→Qa···)doinsert(P,a);Whilestack非空do{弹出stack栈顶组对(P,a);R→P···doinsert(R,a);}Procinsert(P,a){ifF[P,a]=.F.then{F[P,a]=.T.；(P,a)入stack；}}引入：⑴栈stack，存放二元组对(P,a)⑵布尔数组F,F[P,a]=.T.a∈FirstVT(P)算法：G[S]：S→#E#E→E+T

21、TT→T*F

22、FF→P↑F

23、P

24、P→(E)

25、i＋*↑i()#S.T.E.T.T.T.F.T.P.T..T.(P,i)P→i(P,()P→(E)(F,↑)F→P↑F(T,*)T→T*F(E,+)E→E+T(S,#)S→#E#For(P∈VN,a∈VT)doF[P,a]=.F.;For(P→a···或P→Qa···)doinsert(P,a);Whilestack非空do{弹出stack栈顶组对(P,a);R→P···doinsert(R,a);}Procinsert(P,a){ifF[P,a]=.F.then{F[P,a]=

26、.T.；(P,a)入stack；}}For(P∈VN,a∈VT)doF[P,a]=.F.;For(P→a···或P→Qa···)doinsert(P,a);Whilestack非空do{弹出stack栈顶组对(P,a);R→P···doinsert(R,a);}Procinsert(P,a){ifF[P,a]=.F.then{F[P,a]=.T.；(P,a)入stack；}}G[S]：S→#E#E→E+T

27、TT→T*F

28、FF→P↑F

29、PP→(E)

30、i＋*↑i()#S.T.E.T..T..T.

31、.T..T.T.T..T..T..T.F.T..T..T.P.T..T.(P,i)(F,i)(T,i)(E,i)(P,()(P,()(P,()(P,()(F,()(T,()(E,()(F,↑)(F,↑)(F,↑)(F,↑)(F,↑)(F,↑)(F,↑)(T,↑)(E,↑)(T,*)(T,*)(T,*)(T,*)(T,*)(T,*)(T,*)(T,*)(T,*)(E,*)(E,+)(E,+)(E,+)(E,+)(E,+)(E,+)(E,+)(E,+)(E,+)(E,+)