第五章自上而下的语法.ppt

构造递归下降分析程序： 构造递归下降分析程序时,每个函数名是相应的非终结符,函数体则是根据规则右部符号串的结构编写。 当遇到终结符a 时,则编写语句 if (当前读来的输入符号==a) 读下一个输入符号; 当遇到非终结符A 时,则编写语句调用A(); 当遇到A →ε规则时,则编写语句 if (当前读来的输入符号 FOLLOW(A) ) error() ; 当某个非终结符的规则有多个候选式时,按LL(1)文法的条件能唯一地选择一个候选式进行推导。 文法的扩展BNF表示(Extended BNF，EBNF)的产生式事实上已经可以被看作是程序的抽象。用某种程序设计语言表示出来，并且加上适当的数据结构与基本函数，就形成了非终结符的递归下降子程序。 递归下降分析： 递归下降分析程序 例:对文法G： Sym:输入串指针IP所指符号; Advance:把IP调至下一个输入符号； Error:出错诊断程序 即E有两个候选；第一个候选的开头终结符为+，第二个候选为ε。这就是说，当E面临输入符号“+”时就令第一个候选进入工作，而当面临任何其它符号时，E就自动认为获得了匹配。递归函数E就是根据这一原则设计的。 例如，我们将递归函数的调用以栈的形式模拟来分析输入串 # i1*(i2+i3)# 的语法分析过程；在此，“#”为输入串i1*( i2+i3)的分隔符。进行语法分析时，首先将“#”和文法开始符E压入栈中，当语法分析进行到栈中仅剩“#”而输入串扫描指针已指向输入串尾部的“#”时，则语法分析成功，分析过程如下图所示。 关于E的产生式:E→+TE∣ε 图 输入串i1*( i2+i3)的语法分析 E→TE E→+TE∣ε T→FT T→?FT∣ε F→(E)∣i 对文法： LL(1)分析法又称预测分析法，是一种不带回溯的非递归自上而下分析法。LL(1)的含义是：第一个L表明自上而下分析是从左至右扫描输入串的；第二个L表明分析过程中将用最左推导；“1”表明只需向右查看一个符号就可决定如何推导(即可知用哪个产生式进行推导)。类似地，也可以有LL(k)文法，也就是向前查看k个符号才能确定选用哪个产生式，不过LL(k)(k1)在实际中极少使用。 预测分析法: 对给定的输入串按照LL(1)文法进行分析，其分析器模型如下: 输入缓冲区 输入缓冲区：存放要分析的词汇串 分析栈：存放当前句型中尚待分析的文法符号 分析表M：是个矩阵。每行对应文法的一个非终极符A，每列对应终极符号a，矩阵M[A，a]表示当前栈顶为A、输入符号为a时应选用的产生式 LL（1）分析算法 LL（1）分析表M X Y Z … … a + b … # 分析栈 输出 # 预测分析程序 先进后出栈 预测分析表 预测分析器组成 （1）如果 X = a = #，算法结束并报告分析成功。接受输入串 （2）如果 X = a ≠ #，则从栈中弹出X，并使缓冲区指针前进到下一个输入符号。 （3）如果X是一个非终极符，则查分析表，若M[A，a]为X的产生式，用该产生式右部的逆替换栈顶符号，否则出错。 ? LL（1）分析算法执行如下： LL(1)分析算法 输入：串w, 文法G的分析表M 输出：如果w ?L（G）则产生w的最左推导，否则输出错误信息。 方法：初态时，分析栈为 #S ，栈顶S是文法的开始符号；缓冲区为 w #。分析器按下列操作进行语法分析： 1） Push #,S；指针 ip 指向串 w # 的第一个符号； 2） repeat 3） 令X为栈顶符号，a为ip所指的符号； 4） if X 为终结符或# then 5） if X = a = # then 接收 w 6） else if X = a ≠ # then 弹出 X，并使ip前进 7） else error 8） else /* X为非终结符 */ 9） if M[X,a] = X → Y1Y2… Yk then begin 10） 弹出X； 11） push Yk，…，Y2，Y1 /* Y1在栈顶 */ 12） end 13） else error 14） until X = # ；/ * 栈为空 */ 预测分析程序框图 表5.3 表达式文法的预测分析表 E →E+T |T T→T*F|F F→i |(E) 例如有文法为: 1.判断文法