语法分析和语法分析程序.ppt

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

1、第四章语法分析和语法分析程序对象：单词流形式的源程序任务：根据语法规则，分析源程序的语法结构，同时进行语法检查输出：语法树假定：先不考虑语义问题常见分析方法：自顶向下()和自底向上():递归下降法,预测分析法(LL分析法):优先分析法,LR分析法4.1自顶向下的语法分析:对已给的输入串w,试图自上而下地建立一棵语法树;或者说,从S出发,为w构造一个最左推导.若成功,则wL(G),否则拒绝.一般说来,在为w寻求最左推导的每一步,都涉及使用何产生式进行替换的问题.最简单的方法是,逐一试探.遗憾的是,逐一试探也不能完全

2、解决问题.例如,在含有左递归的文法中,就会出现不能终止的替换现象.例:ET

3、EATTF

4、TMFF(E)

5、iA+

6、-M*

7、/(4.1)设w=i+i*i,每个产生式从左至右试验.从E出发:ETF(E)iTMFFMF(E)MFiMFi*Fi/FTMFMF…TMFMFMF...自顶向下分析方法的特点1.若G有左递归,则分析不能正常进行.因此,分析必须先消除文法的左递归;2.分析过程是反复进行试探的过程,因此,难免会出现大量的回溯.特别是当wL(G)时,只有在穷举完所有的试探后才能拒绝w.由于回

8、溯,就需将从出错点到迄今为止已做过的大量工作废弃,显然会大大降低分析的效率.特别是在语法分析阶段还往往要进行同步的语义分析和处理,这些工作也就白做了.因此,消除回溯是分析的另一目标.3.当拒绝w时,只能知道w不是句子,不知出何错及出在何处4.1.1消除文法的左递归设文法是已简化的.若文法含直接左递归式:AA

9、(V+),则类似正规式求解方法,我们有A{}(*).引入新的非终结符A’,令其产生*,则有:AA’A’A’

10、由于不以A打头,A非左递归.对P105的文法(4.1),可改写为ETE’E

11、’ATE’

12、TFT’T’MFT’

13、F(E)

14、iA+

15、-M*

16、/一般地,设文法中全部A-产生式为AA1

17、A2

18、…

19、An

20、1

21、…

22、m,其中,i不以A打头,则消除直接左递归后的产生式为A1A’

23、…

24、mA’及A’1A’

25、…

26、nA’上述方法可消除直接左递归,但对于间接左递归的文法来说,需将原文法进行变换后才适用.例如,SAb

27、cASa,可将其变换为SSab

28、c,再使用上述方法,得ScS’S’abS’消除文法左递归的矩阵方法设文法的非终结符为X1,X2,…,Xn,其中,Xi的产生式可分

29、为以VN符和VT符打头的两类.类似正规式方法,将‘

30、’改写为‘+’,有Xi=X11i+X22i+…+Xnni+i其中,i是以VT符打头的产生式之和,ki可以为这样,文法G可表示为该方程有解:X=BA*为得到A*,由或:X=XA+B则有:X=BZZ=I+AZ其中X的产生式以VT符打头,而Z的产生式以ijV*打头,因此将不含左递归.注意,由此所得的文法含有无用符号和无用产生式,需化简消除文法左递归的例子例4.1SSa

31、Ab

32、aASc相应的矩阵为展开矩阵,得SaZ11AaZ12Z11aZ11

33、cZ21

34、

35、Z12aZ12

36、cZ22Z21bZ11Z22

37、bZ12文法中含有无用产生式,消除之.最后,有SaZ11Z11aZ11

38、cZ21

39、Z21bZ11搞掂!4.1.1回溯的消除及LL(1)文法为解决回溯问题,我们从句子的最左推导开始讨论.设G=(VN,VT,P,S)为一CFG,w=a1a2…an是VT上的符号串,现需判明w是否是L(G)中的句子.为此,从S开始进行最左推导.设经若干步推导后我们得到注意,i=1时,w1=,A=S由假设可知,到目前为止,w的前缀w1已匹配,现在需对A进行推导.对于当前输入符号ai,

40、若只有一个j(称为候选式)使得从j出发可以推导出一个以ai打头的符号串:而其它的k(kj),k都推导不出以ai打头的符号串,则选定产生式Aj就是唯一可行的推导,即wL(G)选Aj正确;wL(G)选任何产生式均不能匹配显然,若P中产生式能满足上述要求,则回溯可消除为得到w的剩余部分aiai+1…an.由最左推导的定义,考虑A的所有产生式:消除回溯的条件由前面的讨论可知，要实现无回溯的分析,文法必须满足一定的条件。为导出这些条件,我们定义候选式的终结首符集FIRST()={a

41、*a,aV

42、T,V*}并约定*时,FIRST()若对于A-产生式的每个候选式i(i=1,2,…,m)都推不出,且FIRST(i)互不相交,则当正扫描的当前输入符号为aiFIRST(j)时,唯一可用于推导的产生式只能是Aj.例如,文法G1[S]:SAAAaAb

43、*,A-