课件编译原理语法分析

《课件编译原理语法分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第四章语法分析4.1语法分析方法一、语法分析程序的任务根据语言的语法规则，把川内部编码表示的单词符号串识别为各种语法单位而一个语言的语法也可以用相应的文法來描述，如果把程序看成是一个由终结符组成的符号串，则语法分析程序的任务就是检查程序是否是和应文法的一个句子。检查一个符号串是否是文法的一个句子，可以用推导或归约的方法。例：G[N]:N-D

2、NDD-0

3、2

4、3

5、l⑴推导:鼓右推导（2）归约:最左归约检查符号串23是否是文法G[N]的一个句子1234NnNDnN3nD3n234321NnNDnN3nD3n23二、两

6、种基本分析方法1•自顶向下分析法（自上而下）从文法的开始符号开始，构造一个推导过程，推导出句子的方法从语法树的角度来说，从根开始，构造一个分析树,使句子的各个终结符号都位于树的末端节点上，（称分析树与句了匹配）2.自底向上分析法（自下而上）逆过程:：从符号串木身开始，对它进行归约，若能归约成文法的开始符号，则符号串是该文法的句子，否则不是。4.2自上而下分析法从文法的开始符号开始推导：依次读入源程序输入串，根据当前读入的字符从产生式中寻找一个与该字符匹配的产牛式來构造推导过程.从而实现语法树与源程序输入串的匹配.

7、一、-•般过程例：G[E]:E-E+TlTT-T*F

8、FF-（E）

9、ip输入串为i*i+i

10、1.左递归在上例的语法树构造过程屮,若总以E+T作为E的子结点,则分析过程将陷入无限循环，永远无法与输入串匹配.原因：该文法是直接左递归的若一个文法是间接左递归的，也会使分析过程陷入无限循环,即：

11、i=>卩….解决办法:改写产生式,使文法不是左递归的改写规则：⑴若有产生式P~*Xa：IX0C2I…IXan(ai,(X2…6三厂)时,提取左因子，用P->X(ai

12、a2

13、-

14、a“)代替(2)若有产生式P—01132

15、-•IB

16、n

17、Pa】

18、Pa?

19、…

20、Pg改写成P-*01

21、02

22、-*-

23、Pn

24、P(a】I0I2I…

25、(Xm)PfBiP'l02P,

26、-

27、BPPJaiP,dP'l…

28、aJP'Ie(或者P-*(Pi

29、P2I•••I6n){aiI囲…

30、aj)直接左递归用直接右递归来表示例：E-E+TlTE->TE?EJ+TE，

31、eTT*F

32、F练习：T—FT，T'f*FT'

33、e-program:;end-*,i

34、i->

35、>:s

36、s->real

37、integer对于间接左递归，可以用下而的方法消除.条件是文法中不存在P=P（冋路）也没有£为右部的产牛式⑴将文法G的非终结符按某种顺序排列:P（,P2,…，P⑵for（i=l;i<=n;i++）for（j=l;j<=iT;j++）{把每个形如卩厂PjY的产牛式替换成Pi->81Y

38、52Y

39、……

40、5kY（其中Pj^81

41、82l……

42、8k）消除Pj产生式中的直接左递归}⑶化简，去掉多余的产生式（不会被使用的产生式）.例：G[S]:S-QclcQfRbjbR-*Sa

43、a顺序：RQS

44、改写过程：R-Sala不是直接左递归，带入QQ-*Sab

45、ab

46、b不是直接左递归，带入SS-^Sabcabc

47、be

48、c*S->abcS,

49、bcS'

50、Cs'S'-abcS'l£Q-Sab

51、ab

52、b多余产生式RfSa

53、a多余产生式非终结符的顺序本无关，但影响新牛成产住式的效率，不同顺序改写成生成的文法是等价的.顺序：SQRS->Qc

54、cQ-RbjbR-^Qca

55、ca

56、aR-^RbcalbcalcaaRfbcaR'

57、caR'

58、aR'R'-*bcdR'

59、e2.冋溯原因：当文法小某个非终结符可用多个候选式去替换它的时候，

60、即存在产生式：a-……

61、Pn(aev)N选用哪个候选式去匹配输入串如前例:E-E+TlTT->W

62、FF-(E)

63、i匹配i+i*i,采用试探性的自顶向下分析法，由于候选式选择不恰当而产牛回溯.缺点:效率低⑴语法分析过程效率低，因推倒重来，试探过程屮做了许多无用功.⑵与语法分析工作同步进行的具它工作在回溯时也作废.一般与语法分析同时进行的工作还有语义处理和中间代码生成.解决办法：对文法的任何一个非终结符(主要是产牛式右部有多个候选式的非终结符),当要用它去匹配输入串时，能根据当前的输入符号选择个候选式去替换该终结符，

64、并且替换结果是确定：要么肚配成功，并且无法从某一步开始重新作其他选择，要么找不到一个合适的候选式去进行匹配.首字符集(首终结符集、候选首字符集)设G是不具有左递归性的文法，设有产生式A-*ai

65、a2

66、---Ian定义任意候选式ai的所冇可能推导出的终结符串首字符的集合为ai的候选首字符集.+设为：FIRST(少)=⑷匕一>ci.....,agVT}为了避免回溯，要保证用某