2005.3引言?自顶向下的语法分析是一种典型的语法分析方法。它从文法的开始符号出发,向下推导推出句子。自顶向下的分析方法主要有两类:回溯分析方法和预测分析方法。其中,回溯分析方法反复使用不同产生式以试图匹配输入串,本质上是一种试探过程。由于带回溯的自顶向下分析实际上采用了一种穷尽一切可能的试探法,因此效率很低,代价极高。严重的低效使得这种分析法只有理论意义,而在对于实际得编译器并不合适。主要内容?递归程序实现预测语法分析器?非递归预测分析法?First和Follow集概念及构造?预测分析表构造?LL(1)文法?预测分析中的错误恢复方法递归程序实现预测语法分析器核心思想:将一个非终结符A的文法规则看作用于识别A的一个过程的定义;再利用对这些过程的递规调用组成整个分析程序。每个过程的代码结构由A的文法规则的右边决定:一个选中的终结符与非终结符序列与相匹配的输入以及对其它过程的调用相对应,而选择与代码中的替代情况(case语句和if语句)相对应。递归程序实现预测语法分析器例:expexpaddopterm|termaddop+|-termtermmulopfactor|factormulop*factor(exp)|number?????递归程序实现预测语法分析器?考虑factor的文法规则,我们可以编写如下伪代码来识别factor并用相同的名称调用这个子过程:procedurefactor;begincasetokenof(:match(();exp;match());number:match(number);elseerror;endcase;endfactor;递归程序实现预测语法分析器考虑表达式文法中的exp情况:如果要将它变成一个递归的exp过程,则首先应做的是调用exp本身,这将立即导致一个无限递归循环。我们可以通过扩充巴科斯范式(Backus-Naurform,BNF文法),加入一些语言符号来??决这个问题。扩充的元符号如下:(1){a}表示闭包运算a*。(2)[a]表示a|?。expexp|addoptermterm?递归程序实现预测语法分析器利用EBNF,我们可以将相关文法改写?procedureexp;beginterm;whiletoken=+ortoken=-domatch(token);term;endwhile;endexp;exp{}termaddopterm?非递归预测分析法实现自顶向下分析的另一种有效方法是LL(1)分析,它使用显式栈而不是递归调用来完成分析。非递归预测分析法考虑括号的串的简单文法:假设有这个文法和输入串"()",则自顶向下的分析程序的动作如下:表4.2.1$表示栈底和输入的结束()|SSS??分析栈输入动作1$S()$S→(S)S2$S)S(()$match3$S)S)$S→ε4$S))$match5$S$S→ε6$$accep非递归预测分析法自顶向下的分析程序中的两个基本动作如下:?1)利用文法选择将栈顶部的非终结符A替换成串α。?2)将栈顶部的记号与下一个输入记号匹配。第1个动作称为生成,它通过写出在替换中使用的BNF选择(它的左边必须是当前栈顶部的非终结符)来指出这个动作。第2个动作将栈顶部的一个记号与输入中的下一个记号匹配(并通过取出栈和将输入向前推进而将二者全部舍弃掉);这个动作是通过书写单词来指出的。非递归预测分析法?例如,在表4.2.1的分析的第1步中,栈和输入分别是$S()$且用来替换栈顶部的S的规则是,所以将串S)S(压入到栈中得到$S)S(()$现在已生成了下一个输入终结符,即在栈的顶部的一个左括号,我们还完成了一个匹配以得到以下的情况:$S)S)$表4.2.1中生成动作的列表与串()最左推导的步骤完全对应:()SSS?()[()]()[]()[]SSSSSSSSS??????????????First和Follow集概念及构造First定义:令X为一个文法符号(一个终结符或非终结符)或?,则集合First(X)由终结符组成,此外可能还有?,它的定义如下:1.若X是终结符或?,则First(X)={X}。2.若X是非终结符,则对于每个产生式,First(X)都包含了。若对于某个i语法错误。(1)栈顶的终结符与当前的输人符号不匹配。(2)非终结符A处于栈顶,面临的输入符号为a,但分析表M中的M「A,a」为空。预测分析中的错误恢复方法发现错误后,要尽快地从错误中恢复过来,使分析能继续进行下去。基本的做法就是跳过输入串中的一些符号直至??到"同步符号"为止。这种做法的效果有赖于同步符号集的选择。预测分析中的错误恢复方法考虑同步符号集的选择:(1)把FOLLOW(A)中的所有符号放入非终结符A的同步符号集。如果我们跳读一些输入符号直到出现FOLLOW(A)中的符号,把