下载文档原格式
第四章自顶向下语法分析方法语法分析是编译过程的核心部分。
语法分析的任务是：按照文法，从源程序符号串中识别出各类语法成份，同时进行语法检查，为语义分析和代码生成作准备。
执行语法分析任务的程序称为分析程序。
也称为语法分析器，它是编译程序的主要子程序之一。
在第二章中我们已经介绍过。
通过语法分析可建立起相应的语法树。
按语法树的建立方法，我们将语法分析方法分成两大类，即自顶向下分析和自底向上分析。
下面，我们先介绍自顶向下分析。
本章重点：自顶向下分析、LL（1）分析第一节自顶向下分析方法一、带回溯的自顶向下分析算法这是自顶向下分析的一般方法，即对任一输入符号串，试图用一切可能的方法，从识别符号出发，根据文法自上而下地为输入串建立一棵语法树。
下面用一个简单例子来说明这种过程：假定有文法G[S]：S→cＡdA→ab|a 以及输入串w=cad为了自上而下地构造w的语法树，我们首先按文法的识别符号产生根结点S，并让指示器IP指c的规则（此处左部为S的规则仅有一条）（ a）（b）（c）图3-1-1图3-1-1a。
我们希望用S的子结从左至右匹配整个输入串w。
首先，此树的最左子结是终结符c为标志的子结，它和输入串的第一个符号相匹配。
于是，我们就把IP调整为指向下一输入符号a，并让第二个子结A去进行匹配，非终结符A有二个选择，我们试着用它的第一个选择去匹配输入串，于是把语法树发展为图3-1-1b。
子树A的最左子结和IP所指的符号相符，然后我们再把IP调为指向下一符号d并让A的第二个子结进入工作。
但A 的第二个子结为终结符号b，与IP当前指的符号d不一致。
因此，A宣告失败。
这意味着A的第一个选择此刻不适用于构造w的语法树。
这时，我们应该回头（回溯）看A是否还有别的选择。
为了实现回溯，我们一方面应把A的第一个选择所生长的子树注销掉；另一方面，应把IP恢复为进入A时的原值，也就是让它重新指向第二输入符号a。
现在我们试探用A的第二个选择，即考虑生成图3-1-1c的语法树。
编译原理-⾃顶向下的语法分析1.代替部分由公因⼦就会出现回溯。
2.LL(1)⽂法（1）FIREST集这样说从⽂法的左部找右部相关的⾮终结符号。
若 X->BC..D,则将First（B）所有元素（除了ε）加⼊First（A），然后检测First（B），若First（B）中不存在ε,则停⽌，若存在则向B的后⾯查看，将First（C）中所有元素（除了ε）加⼊First（A），然后再检测First（C）中是否有ε...直到最后，若D之前的所有⾮终结符的First集中都含有ε,则检测到D时，将First（D）也加⼊First（A），若First（D）中含有ε,则将ε加⼊First（A）。
（2）FOLLOW集：记住是从⽂法的右部去找的。
1）S是开始符号,将#放到follow（S）中. 2）存在A→αBβ（且β！=ε），那么first（β）中除ε之外的所有符号都在follow（B）中。
3）存在A→αB或A→αBβ（且first（β）包含ε），那么follow（A）中的所有符号都在follow（B）中。
（注意都没有说α⼀定存在。
）（3）SELECT集对于产⽣式A—>α。
集合select（A—>α）定义如下：1. 若α不能推出ε，则select（A—>α） = first（α）。
2. 若α能推出ε，则select（A—>α）= first（α）∪ follow(A)。
（4）如何判断⼀个⽂法是不是LL（1）⽂法：第⼀消除左递归，先消除去直接左递归，然后看是否有相同最左公因⼦的，提取出来。
第⼆分别求出每个推导的SELECT集，同⼀左部的求SELECT集的交集，所有的这种交集为空的话就是LL(1)⽂法，否则不是。
3.递归下降分析法：只针对LL(1)⽂法的，所以没有左递归。
简单的来说就是为每个⾮终结符号编写⼀个处理程序，⽽处理程序的代码结构是由相应的⾮终结符号的规则右部所决定。
p68.4.预测分析表的构造:p74。
编译原理系列之四⾃顶向下语法分析⽅法⾃顶向下语法分析⽅法什么叫确定：两个确定：①确定对最左的⾮终结符进⾏替换（最左推导）②对于同⼀个⾮终结符，确定⼀个产⽣式进⾏推导（SELECT集，⽆回溯）。
⼀个上下⽂⽆关⽂法是LL(1)⽂法的充分必要条件：关于⼀个⾮终结符的各个产⽣式的可选集互不相交。
LL(1)⽂法的判定过程：1. 检查产⽣式中是否有含有左递归或左公因⼦：含有左递归或左公因⼦的⽂法⼀定不是LL(1)⽂法；不含有左递归或左公因⼦的⽂法也不能确定是否为LL(1)⽂法；2. 标记能推导出ε的⾮终结符：先找出能直接推出ε的⾮终结符，然后再查看其他产⽣式的右部，通过这些⾮终结符检查还有没有其他⾮终结符也可推出ε，直到没有发现为⽌。
3. 计算每个产⽣式的FIRST集：①如果这个产⽣式右部第⼀个字符是终结符，那么这个终结符就属于它的FIRST集。
②如果这个产⽣式右部第⼀个字符是⾮终结符，那么这个⾮终结符的FIRST集就属于它的FIRST集。
如果这个⾮终结符的FIRST集中含ε，那么后⾯的字符如果是终结符......③如果这个产⽣式右部可以推出ε，那么ε也属于它的FIRST集。
4. 计算每个⾮终结符的FOLLOW集：⾸先向开始符号的FOLLOW集中添加#，然后对于所有⾮终结符，不断的找含有它的产⽣式右部：①该⾮终结符后⾯的字符若是终结符，那么这个终结符就属于它的FOLLOW集；②该⾮终结符后⾯的字符若是⾮终结符，那么这个⾮终结符的FIRST()集中的所有元素就属于它的FOLLOW集；如果这个⾮终结符的FIRST()集中含ε，将ε删去，同时将这个产⽣式左部FOLLOW集中的所有元素添加⾄它的FOLLOW集中；注意：不需要考虑后⾯的字符了，因为已经包含在FIRST()集中了。
5. 计算每个产⽣式的SELECT集：①如果这个产⽣式可以推出ε，那么它的SELECT集是{FIRST(该产⽣式右部)-ε}∪FOLLOW(该产⽣式左部的⾮终结符)。
