《语法分析》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’

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

11、TFT’T’MFT’

12、F(E)

13、iA+

14、-M*

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

16、A2

17、…

18、An

19、1

20、…

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

22、…

23、mA’及A’

24、1A’

25、…

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

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

28、c,再使用上述方法,得ScS’S’abS’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,若只有一个j(称为候选式)使

29、得从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

30、*a,aVT,V*}并约定*时,FIRST()若对于A-产生式的每个候选式i(i=1,

31、2,…,m)都推不出,且FIRST(i)互不相交,则当正扫描的当前输入符号为aiFIRST(j)时,唯一可用于推导的产生式只能是Aj.例如,文法G1[S]:SAAAaAb

32、*,A-产生式有两个候选式,且FIRST(aAb)={a}FIRST(*)={*},两集不相交,设输入串为aa*bb*,其最左推导为SAA(a)aAbA(a)aaAbbA(*)aa*bbA(*)aa*bb*(#)注:上面第每步推导右侧括号内为当前扫描的输入符号,#为结束符.我们得到了一个无回溯的条件:FIRST(i)FIRST(j)=消除回溯的条件然而还存在另外一种情况,可能存在某个候

33、选式i,i*,即FIRST(i)(这样的是唯一的(?!)),此时,为匹配当前扫描的符号a就可能有两种选择,一是存在某j,使j推导出以a打头的符号串,另一种选择是让A推导出i,并让跟随在A后的符号串推导出以a打头的符号串.若这两种选择都可行,则回溯不可避免.因此,就必须要求当i*时,跟在A后的符号串不能推导出其它j所能推导出的首终结符符号串.为此,我们定义可紧跟在A后的所有终结符之集FOLLOW(A)={a