编译原理电子课件教案-第5章-自顶向下语法分析方法.pptx

1,5.1语法分析概述5.2自顶向下语法分析概述5.3LL分析法（预测分析法）5.4递归子程序,第五章自顶向下语法分析方法,2,5.1语法分析概述,1.语法分析器的作用,3,(1)根据词法分析器提供的单词流，为语法正确的输入构造分析树（或语法树）。(2)检查输入中的语法错误，并调用出错处理器进行适当处理。,5.1语法分析概述,1.语法分析器的作用,4,例如：对C程序语句“IF(aaUb=aeb,Z(U)|aUb,对输入串aeb#进行语法分析,93,例：为下列文法的每个非终极符构造相应的递归函数文法GZ：Z(U)|aUbUdZ|e解：main()sym=getsym();/读取当前输入串的第一个符号Z();/从文法开始符号对应的子程序开始识别if(sym=#)OK;/”#”是程序结束的标志elseerror(“errorinmain”);,对输入串aeb#进行语法分析,94,Z()/Z(U)|aUbif(sym=()sym=getsym();U();if(sym)error(“缺)”);exit(0);elsesym=getsym();elseif(sym=a)sym=getsym();U();if(symb)error(“缺b”);exit(0);elsesym=getsym();elseerror(“缺(或a”);exit(0);,对输入串aeb#进行语法分析,95,U()/UdZ|eif(sym=d)sym=getsym();Z();elseif(sym=e)sym=getsym();elseerror(“缺d或e”);exit(0);,对输入串aeb#进行语法分析,96,例：为下列文法的每个非终极符构造相应的递归函数.文法GE：ETEE+TE|TFTT*FT|Fi|(E)解：main()sym=getsym();/*读取当前输入串的第一个符号。*/E();if(sym=#)OK;elseerror(“inmain”);,97,E()/ETEif(sym=i|sym=()/*if(symfirst(T)*/T();E();elseerror(“非法符号”,sym);exit(0);,98,E()/E+TE|if(sym=+)sym=getsym();T();E();elseif(sym#sym)/*if(symfollow(E)*/error(“非法符号”,sym);exit(0);/意味着用E推导,99,T()/TFTif(sym=i|sym=()/*if(symfirst(F)*/F();T();elseerror(“非法符号”,sym);exit(0);,100,T()/T*FT|if(sym=*)sym=getsym();F();T();elseif(sym#sym+sym)/if(symfollow(T)error(“非法符号”,sym);exit(0);/意味着用T推导,101,F()/Fi|(E)if(sym=i)sym=getsym();elseif(sym=()sym=getsym();E();if(sym=)sym=getsym();elseerror(“缺)”);exit(0);elseerror(“缺（或i”);exit(0);,102,例：文法GE：EE+T|TTT*F|FFi|(E)设计递归子程序。解:对文法G消除左递归为G(E):E+|-T+T/考虑表达式有形如+5或-5的情况TF*FFi|(E),103,E()/E+|-T+Tif(sym=+|sym=-)sym=getsym();if(sym=i|sym=()T();elseerror;exit(0);elseif(sym=i|sym=()T();elseerror;exit(0);while(sym=+)sym=getsym;if(sym=i|sym=()T();elseerror;exit(0);,104,T()/TF*Fif(sym=i|sym=()F();elseerror;exit(0);while(sym=*)sym=getsym;if(sym=i|sym=()F();elseerror;exit(0);F()/Fi|(E)内容同前一个例子：p76,105,5.自顶向下语法分析总结,自顶向下的分析方法就是从文法的开始符号出发，按最左推导方式向下推导，试图推出要分析的输入串。自顶向下分析常用的方法有：递归下降分析：利用程序设计语言的递归函数实现，每个函数对应文法的一个非终极符。LL(1)分析：由一张预测分析表和一个总控程序组成。预测分析表给出了当面临输入符号时，运用到非终极符的推导所选用的产生式。,106,5.自顶向下语法分析总结,自顶向下语法分析,确定的自顶向下语法分析（消除左递归和回溯）,递归下降分析,预测分析法（LL(1)）,非确定的自顶向下语法分析,主要缺点：不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置。在实际应用中价值不大，效率很低。,107,5.自顶向下语法分析总结,递归下降分析方法实用性强，便于手工编写语法分析器。LL(1)分析法在实际中不常用，但给出了一些重要、形式化的定义，用于指导歧义文法的改造、文法左递归和回溯的消除。为学习更强大和复杂的LR分析法做准备。,108,60年代以来，上下文无关文法在编译技术中扮演着重要角色。它能把语法分析器的实现从一种费时的、不独特的设计工作转变成一种能够很快完成的工作CFG也被用来描述文档格式XML中使用的DTD（文档类型定义），用来描述Web上的信息交换格式。,109,等价的自动机-PDA，其描述并且只描述所有的上下文无关语言。例：“回文”的语言：正向和反向读起来都一样的串,如：madamimadamMadam,ImAdam串是一个回文iff=R基础：，0和1都是回文，=0,1上的回文归纳：如果是回文，那么00和11也都是回文,110,作业补充：,1.判断文法是否是LL(1)文法。(1)A(A)A|(2)AA(A)|2.能否将文法转换为LL(1)文法？1)lexpatom|list2)atomnum|id3)list(lexp-seq)4)lexp-seqlexp-seqlexp|lexp,111,解：a.消除左递归4）lexp-seqlexpAAlexpA|且select(A)=)而select(AlexpA)=num,id,C，不相交。因此是LL(1)文法。,1)lexpatom|list2)atomnum|id3)list(lexp-seq)4)lexp-seqlexp-seqlexp|lexp,112,1)lexpatom|list2)atomnum|id3)list(lexp-seq)4)lexp-seqlexp-seqlexp|lexp,3.在第2题中，规则不变，变为：lexp-seqlexp,lexp-seq|lexp，能否将文法转换为LL(1)文法？解：提取左因式：lexp-seqlexpAA,lexp-seq|，且select(A)=)，与,不相交所以，可改造成LL(1)文