编译原理Chapt4.ppt

《编译原理Chapt4.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、形式为Q，Q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)(i+E)(i+i)江西财经大学信息

3、管理学院通常，用表示：从1出发，经过一步或若干步，可以推出n。用表示：从1出发，经过0步或若干步，可以推出n。所以：即或定义：假定G是一个文法，S是它的开始符号。如果，则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。江西财经大学信息管理学院4.1语法分析器的功能语法分析的任务是分析一个文法的句子结构。语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式的程序)。江西财经大学信息管理学院语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，

4、直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。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)自上而下分析法(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。递归下降分析法：对每一语法变量(非终结符)构

10、造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析法（不含递归）优点：直观、简单和宜于手工实现。江西财经大学信息管理学院4.2自上而下分析面临的问题自上而下就是从文法的开始符号出发，向下推导，推出句子。带“回溯”的不带回溯的递归子程序(递归下降)分析方法。自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。江西财经大学信息管理学院例3.4.1假定有文法G(S):(1)S→xAy(2)A→**

11、*分析输入串x*y(记

12、为)。Sx*yIPSx*yIPAxySx*yIPAxySx*yIPAxy**Sx*yIPAxy**Sx*yIPAxy*Sx*yIPAxy*江西财经大学信息管理学院当某个非终结符有多个产生式候选时，可能带来如下问题:1.分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。2.文法左递归问题。一个文法是含有左递归的，如果存在非终结符P含有左递归的文法将使自上而下的分析陷入无限循环。江西财经大学信息管理学院困难①对于左递归文法定义的语言，不能采用自上而下的语法分析法。②存在虚假匹配，回溯不可避免。③编译程序的语法分析和语义分析通常是同

13、时进行的。由于回溯，编译程序所做的一大堆语义分析工作必须推倒重来。④当选用所有的不同候选组合，都不能为输入串建立一棵语法树，那么输入串存在语法错误。这种分析法最终只能告知输入串不是文法的一个句子，而无法告知输入串错在何处。⑤带回溯的自上而下分析法实际上是一种穷尽一切可能的试探法，效率很低，这种分析法几乎没有实用价值。江西财经大学信息管理学院4.3LL(1)分析法构造不带回溯的自上而下分析算法消除文法的左递归性克服回溯江西财经大学信息管理学院4.3.1左递归的消除直接消除见诸于产生式中的左递归：假定关于非终结符P的规