编译原理精华总结4语法1.doc

《编译原理精华总结4语法1.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、编译原理精华总结4语法1　　1S.PO.P语义分析、生成中间代码生成目标程序代码优化语法分析程序词法分析程序错误处理错误处理符号表管理符号表管理语法分析2任务根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。　　根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。　　两大类分析方法自顶向下分析自底向上分析4.1语法分析的任务3存在主要问题:回溯问题,左递归问题主要方法递归下降分析法、LL分析法自顶向下分析算法的基本思想为自底向上分析算法的基本思想为+若S?x则x∈∈L(G[S])否则x??L(G[S])G[S]存在主要问题:“可归约串”的识别问题主要方

2、法算符优先分析法、LR分析法4.1语法分析的任务+若x?S则x∈∈L(G[S])否则x??L(G[S])G[S]4自顶向下分析的一般过程?从S出发采用最左推导，试图逐步推出输入串α,αα∈∈L(G[S])??S作为语法树的根，试图自上而下地为α构造一棵语法树?若叶结点从左向右排列恰好α，则表示α是文法的句子，而这棵语法树就是句子α的语法结构；若叶结点从左向右排列恰好α，则表示α是文法的句子，而这棵语法树就是句子α的语法结构；?若构造不出语法树，则α不是文法的句子。　　4.2自顶向下分析法概述5?自上而下分析中的关键问题–左递归当文法中出现左递归时，会使分析过程陷入无限循环。　　当文

3、法中出现左递归时，会使分析过程陷入无限循环。　　–回溯假定要被代换的非终结符号是V，且有n条规则V→A假定要被代换的非终结符号是V，且有n条规则V→A11

4、A22

5、

6、…

7、Ann，那么如何确定用哪个右部A，那么如何确定用哪个右部Aii去替代V呢？会造成回溯。　　4.2自顶向下分析法概述回溯问题左递归问题61.回溯问题什么是回溯（backtracking）?分析工作要部分地或全部地退回去重做叫回溯造成回溯的条件文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。　　，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现

8、回溯。　　回溯带来的问题严重的低效率，只有在理论上的意义而无实际意义。　　4.2自顶向下分析法概述7消除回溯的途径改写文法对具有多个右部的规则反复提取左因子例对下述两个产生式，提取公共左因子改造文法。　　→ifEthenS例对下述两个产生式，提取公共左因子改造文法。　　→ifEthenS11elseS22→ifEthenS11改造为→ifEthenS1UU→elseS2

9、ε4.2自顶向下分析法概述8A→αβ1

10、αβ2

11、…

12、αβn如果β1~βn中还有几个首符号相同，可反复提取引入了许多非终结符和ε产生式。　　中还有几个首符号相同，可反复提取引入了许多非终结符和ε产生式。　　A→αA′

13、A′→β1

14、β2

15、…

16、βn提取公共左因子4.2自顶向下分析法概述9某些文法不能在有限步骤内提取左公共因子。　　S【例】文法G:S→Ap

17、BqAAp

18、BqA→aAp

19、dBaAp

20、dB→aBq

21、eSS→aApp

22、aBqqSaApp

23、aBqqS→dp

24、eqAdp

25、eqA→aAp

26、dBaAp

27、dB→aBq

28、eSS→a(App

29、Bqq)SS→aS′′SS′→App

30、BqqSApp

31、BqqS→dp

32、eqAdp

33、eqA→aAp

34、dBaAp

35、dB→aBq

36、eSS→aS′′SS→dp

37、eqSdp

38、eqS′→aAppp

39、aBqqqSaAppp

40、aBqqqS''→dpp

41、eqqAdpp

42、eqqA→aAp

43、

44、dBaAp

45、dB→aBq

46、e可以看出产生式A、B继续替换，只能使文法的产生式愈来愈多无限增加下去，变成循环递归，不能得到提取左公共因子的预期结果。　　可以看出产生式A、B继续替换，只能使文法的产生式愈来愈多无限增加下去，变成循环递归，不能得到提取左公共因子的预期结果。　　不一定每个文法的公共左因子都能在有限的步骤内替换成无公共左因子的文法。　　一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL　　(1)文法。　　否则还需用LL　　(1)文法的定义进行判断才能确定是否为LL　　(1)文法。　

47、　不一定每个文法的公共左因子都能在有限的步骤内替换成无公共左因子的文法。　　一个文法提取了左公共因子后，只解决了相同左部产生式右部的FIRST集不相交问题，当改写后的文法不含空产生式，且无左递归时，则改写后的文法是LL　　(1)文法。　　否则还需用LL　　(1)文法的定义进行判断才能确定是否为LL　　(1)文法。　　4.2自顶向下分析法概述102.左递归问题例文法G[E]E→E+T

48、TT→T*F

49、FF→(E)

50、i给出i*i+i自顶向下的分析过程。　　例文法G[E]E→