编译原理第四章 语法分析和语法分析程序.ppt

《编译原理第四章 语法分析和语法分析程序.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编译原理——语法分析和语法分析程序编译程序的逻辑结构词法分析程序语法分析程序语义分析程序中间代码生成代码优化程序目标代码生成信息表管理程序错误检查和处理程序源程序目标代码编译程序的组织语法分析程序语义分析及代码生成程序词法分析程序整理目标程序源程序目标程序停机开始语法树语法树（分析树、推导树）每个结点均有标记VNVT根的标记为开始符号S内部结点标记VN若以A为标记的结点有k个孩子分别标记为X1,X2,…,Xk,则AX1X2…Xk必然是G的一个产生式文法的二义性：一个句子对应多个语法树对无二义文法，一个句子只对应一个语法

2、树两类语法分析方法按产生语法树的方向分自顶向下递归下降法LL自底向上算符优先法LR自顶向下的语法分析例子文法G[E]:ET

3、EATTF

4、TMFF(E)

5、iA+

6、-M*

7、/建立从E到i+i*i的最左推导左递归与死循环：EEAT,必须消除左递归直接左递归的消除前提：掌握算法2.1-2.6消除无用符号和产生式、产生式和单产生式直接左递归的形式：AA，V+直接左递归的消除方法一：将AA

8、改写为A{}方法二：引入A'，改写为AA'和A'A'

9、一般化：将AA1

10、A2

11、…

12、An

13、1

14、2

15、

16、…

17、m改写为：A1A'

18、2A'

19、…

20、mA'和A'1A'

21、2A'

22、…

23、nA'

24、左递归的消除从线性方程组到矩阵方程从3类文法到2类文法只关心产生式右部各符号串的首字符对n个非终结符X1…Xn，得到矩阵方程或表示为：X=XA+B方程的解为：X=BA*回避闭包A*的计算由于A*=I+A+A2+…=I+AA*(r*=

25、rr*)若令A*=Z，则对X=BA*可得X=BZ和Z=I+AZX会不会产生左递归Z会不会产生左递归例子与练习消除下列文法的左递归1）SSa

26、Ab

27、a，ASc2）SAS

28、b,ASA

29、aFIRS

30、T集的定义对符号串,FIRST()={a

31、*a,且aVT,V*},(当*,约定FIRST()),即FIRST()由推导出的每个符号串的首个终结符组成。若以终结符a打头，则FIRST()=FIRST(a)={a}若以非终结符X打头，则FIRST()=FIRST(X)={…}XaiX构造FIRST(X)集1/2令X，YiVN，aVT，X的产生式具有下述3种形式：Xa或XaXa…2.XX3.XY1Y2…Yk，其中Y1Y1Y2Yk…X构造FIRST(X)集2/2SetFI

32、RST(X){ft=;if(XVT)return{X};if(XP)ft+={};forEach(XY1Y2…YkP){forEach(Yi){if(FIRST(Yi)){ft+=(FIRST(Yi)-{});if(i==k)ft+={};}else{ft+=FIRST(Yi);break;}}}returnft;}例题与练习对文法G[E]:ETE’E’ATE’

33、TFT’T’MFT’

34、F(E)

35、iA+

36、-M*

37、/求每个非终结符的FIRST集合。练习：P173,4-4之求FIRST集FO

38、LLOW集的定义对非终结符X，FOLLOW(X)={a

39、S#*Xa,且aVT{#},,V*},即FOLLOW(X)由语言中可能出现在X后面的终结符组成。aXSX##SX##S构造FOLLOW集1/2令XVN，,V*，X的产生式具有下述4种形式：1.X=SG[S]X…#2.AXXAaa3.AX*XAaba4.AX*AbX构造FOLLOW集2/2SetFOLLOW(X){if(X==SG[S])return{#}fw=;forEach(A

40、XP){if(FIRST()){fw+=(FIRST()–{});fw+=FOLLOW(A);}elsefw+=FIRST();}forEach(AXP)fw+=FOLLOW(A);returnfw(X);}例题与练习对文法G[E]:ETE’E’ATE’

41、TFT’T’MFT’

42、F(E)

43、iA+

44、-M*

45、/求每个非终结符的FOLLOW集合。练习：P173,4-4之求FOLLOW集4.1FIRST和FOLLOW的区别令XVN，有如下断言：FIRST(X)，FOLLOW(X)，#F

46、IRST(X)，#FOLLOW(X)，可能为真一定不为真一定不为真可能为真#FOLLOW(X)为真的条件是什么？LL(1)文法自顶向下的语法分析过程：为了实现无回溯的自顶向下语法分析，需满足对于G中的每个产生式A1

47、2

48、…

49、m,满足FIRST(i)FIRST(