编译原理总结4语法.ppt

《编译原理总结4语法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、分析的任务+若xS则xL(G[S])否则xL(G[S])G[S]4自顶向下分析的一般过程从S出发采用最左推导，试图逐步推出输入串α,αL(G[S])?S作为语法树的根，试图自上而下地为α构造一棵语法树：若叶结点从左向右排列恰好α，则表示α是文法的句子，而这棵语法树就是句子α的语法结构；若构造不出语法树，则α不是文法的句子。4.2自顶向下分析法概述5自上而下分析中的关键问题：左递归：当文法中出现左递归时，会使分析过程陷入无限循环。回溯：假定要被代换的非终结符号是V，且有n条规则：V→A1

3、A2

4、…

5、An

6、，那么如何确定用哪个右部Ai去替代V呢？会造成回溯。4.2自顶向下分析法概述回溯问题左递归问题61.回溯问题什么是回溯（backtracking）?分析工作要部分地或全部地退回去重做叫回溯造成回溯的条件：文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。回溯带来的问题：严重的低效率，只有在理论上的意义而无实际意义。4.2自顶向下分析法概述7消除回溯的途径：改写文法对具有多个右部的规则反复提取左因子例：对下述两个产生式，提取公共左因子改造文法。

7、f语句>→ifEthenS1elseS2→ifEthenS1改造为：→ifEthenS1UU→elseS2

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

9、αβ2

10、…

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

12、β2

13、…

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

15、BqAaAp

16、dBaBq

17、eSaApp

18、aBqqSdp

19、eqAaAp

20、dBaBq

21、eSa(Ap

22、p

23、Bqq)SaSSApp

24、BqqSdp

25、eqAaAp

26、dBaBq

27、eSaSSdp

28、eqSaAppp

29、aBqqqS'dpp

30、eqqAaAp

31、dBaBq

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

33、(1)文法。否则还需用LL(1)文法的定义进行判断才能确定是否为LL(1)文法。4.2自顶向下分析法概述102.左递归问题例：文法G[E]：E→E+T

34、TT→T*F

35、FF→(E)

36、i给出i*i+i自顶向下的分析过程。左递归文法会使自顶向下分析法陷入死循环如果文法具有间接左递归，则也将发生上述问题，只不过循环的圈子兜的更大。要实行自顶向下分析，必须要消除文法的左递归从左向右扫描源程序，同时实施最左推导。4.2自顶向下分析法概述11（1）消除直接左递归方法一：使用EBNF表示来改写文法例：文法G[E]：E→E+T

37、

38、TT→T*F

39、FF→(E)

40、iE→T{+T}T→F{*F}F→(E)

41、iA→

42、A规则一A→{}4.2自顶向下分析法概述12例：文法G[E]：E→E+T

43、E-T

44、TT→T*F

45、T/F

46、FF→(E)

47、iE→T{(+

48、−)T}T→F{(*

49、/)F}F→(E)

50、iA→A

51、A规则二A→A(

52、)4.2自顶向下分析法概述13方法二：将左递归规则改为右递归规则A→A

53、课堂练习文法G[E]：E→E+T

54、E-T

55、TT→T*F

56、T/F

57、FF→(E)

58、iE→TE'E'→+TE'

59、T→FT'T'→*FT'

60、F

61、→(E)

62、i消除左递归A→A'A'→A'

63、4.2自顶向下分析法概述14间接左递归直接左递归右递归【例】文法G:AaBABbBAcBdAaBABbBaBcBBbcBdBaBc

64、dBBbcB(aBc

65、d)B'B'bcB'

66、AaBABbB(aBc

67、d)BBbcB

68、ε4.2自顶向下分析法概述(2)消除间接左递归15对文法中一切左递归的消除要求文法中不含回路