编译原理-国防科技大学课件Chapt4.ppt

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

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

2、终结符集合(非空)，且VTVN=S：文法的开始符号，SVNP：产生式集合(有限)，每个产生式形式为P，PVN，(VTVN)*开始符S至少必须在某个产生式的左部出现一次。国防科技大学计算机系602教研室例，定义只含+，*的算术表达式的文法G=<{i，+，*，(，)}，{E}，E，P>，其中，P由下列产生式组成：EiEE+EEE*EE(E)国防科技大学计算机系602教研室定义：称A直接推出，即A仅当A是一个产生式，且，(VTVN)*。如果12n，则我们

3、称这个序列是从1到n的一个推导。若存在一个从1到n的推导，则称1可以推导出n。例：对文法(1)E(E)(E+E)(i+E)(i+i)国防科技大学计算机系602教研室通常，用表示：从1出发，经过一步或若干步，可以推出n。用表示：从1出发，经过0步或若干步，可以推出n。所以：即或定义：假定G是一个文法，S是它的开始符号。如果，则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。国防科技大学计算机系602教研室4.1语法分析器的功能语法分析的任务是分

4、析一个文法的句子结构。语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)。国防科技大学计算机系602教研室源程序单词符号取下一单词...语法分析树词法分析器语法分析器符号表编译程序后续部分国防科技大学计算机系602教研室语法分析的方法：自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分

5、析。适合分析表达式。LR分析法：规范归约国防科技大学计算机系602教研室G(E)：Ei

6、E+E

7、E-E

8、E*E

9、E/E

10、(E)i*i+iE*i+iE*E+iE+iE+EEi+*EiiEEEE国防科技大学计算机系602教研室语法分析的方法：自下而上分析法(Bottom-up)自上而下分析法(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识

11、别。预测分析程序优点：直观、简单和宜于手工实现。国防科技大学计算机系602教研室4.2自上而下分析面临的问题自上而下就是从文法的开始符号出发，向下推导，推出句子。带“回溯”的不带回溯的递归子程序(递归下降)分析方法。自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。国防科技大学计算机系602教研室例3.4.1假定有文法G(S):(1)S→xAy(2)A→**

12、*分析输入串x*y(记为)。Sx*yIPSx*yIPAxy

13、Sx*yIPAxySx*yIPAxy**Sx*yIPAxy**Sx*yIPAxy*Sx*yIPAxy*国防科技大学计算机系602教研室当某个非终结符有多个产生式候选时，可能带来如下问题:1.分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。2.文法左递归问题。一个文法是含有左递归的，如果存在非终结符P含有左递归的文法将使自上而下的分析陷入无限循环。国防科技大学计算机系602教研室4.3LL(1)分析法构造不带回溯的自上而下分析算法要消除文法的左递归性克服回溯国防科技大学计算机

14、系602教研室4.3.1左递归的消除直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为P→P

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

16、左递归变右递归国防科技大学计算机系602教研室一般而言，假定P关于的全部产生式是P→P1

17、P2

18、…

19、Pm

20、