编译原理：第四章语法分析-自上而下分析.ppt

《编译原理：第四章语法分析-自上而下分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理第四章语法分析—自上而下分析四元式单词符号语法单位四元式目标代码词法分析器语法分析器语义分析与中间代码生成器优化段源程序表格管理出错处理目标代码生成器第四章语法分析—自上而下分析本章主要介绍语法分析的处理要进行语法分析，必须对语言的语法结构进行描述。采用正规式和有限自动机可以描述和识别语言的单词符号；用上下文无关文法来描述语法规则。上下文无关文法的定义：一个上下文无关文法G是一个四元式G=(VT，VN，S，P)，其中VT：终结符集合(非空)VN：非终结符集合(非空)，且VTVN=S：文法的开始符号，SVN

2、P：产生式集合(有限)，每个产生式形式为P，PVN，(VTVN)*开始符S至少必须在某个产生式的左部出现一次。例，定义只含+，*的算术表达式的文法G=<{i，+，*，(，)}，{E}，E，P>，其中，P由下列产生式组成：EiEE+EEE*EE(E)定义：称A直接推出，即A仅当A是一个产生式，且，(VTVN)*。如果12n，则我们称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n。例：对文法(1)E(E)(E+E

3、)(i+E)(i+i)通常，用表示：从1出发，经过一步或若干步，可以推出n。用表示：从1出发，经过0步或若干步，可以推出n。所以：即或定义：假定G是一个文法，S是它的开始符号。如果，则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。4.1语法分析器的功能语法分析的任务是分析一个文法的句子结构。语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)。注：语法分析是编译程序的核心部分源程序单词符号取下一单词...语法分析

4、树词法分析器语法分析器符号表编译程序后续部分语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约G(E)：Ei

5、E+E

6、E-E

7、E*E

8、E/E

9、(E)i*i+iE*i+iE*E+iE+iE+EEi+*EiiEEEE语法分析的方法：自下而上分析法(Bottom-up)自上而

10、下分析法(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序优点：直观、简单和宜于手工实现。4.2自上而下分析面临的问题自上而下就是从文法的开始符号出发，向下推导，推出句子。带“回溯”的不带回溯的递归子程序(递归下降)分析方法。自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地

11、为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。例3.4.1假定有文法G(S):(1)S→xAy(2)A→**

12、*分析输入串x*y(记为)。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy**Sx*yIPAxy**Sx*yIPAxy*Sx*yIPAxy*当某个非终结符有多个产生式候选时，可能带来如下问题:1.分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。2.文法左递归问题。一个文法是含有左递归的，如果存在非终结符P含有左递归的文法将使自上而

13、下的分析陷入无限循环。4.3LL(1)分析法构造不带回溯的自上而下分析算法要消除文法的左递归性克服回溯4.3.1左递归的消除直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为P→P

14、其中不以P开头。我们可以把P的规则等价地改写为如下的非直接左递归形式：P→PP→P

15、左递归变右递归一般而言，假定P关于的全部产生式是P→P1

16、P2

17、…

18、Pm

19、1

20、2

21、…

22、n其中，每个都不等于，每个都不以P开头那么，消除P的直接左递归性就是把这些规则改写成：P→1P

23、2P

24、…

25、nPP→

26、1P

27、2P

28、…

29、mP

30、左递归变右递归例文法G(E):E→E＋T

31、TT→T*F

32、FF→(E)

33、i经消去直接左递归后变成：E→TEE→+TE

34、T→FTT→*FT

35、F→(E)

36、i(4.2)P→P1

37、P2

38、…

39、Pm

40、1

41、2

42、…

43、nP→1P

44、2P

45、…

46、nPP→1P

47、2P

48、…

49、