南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
自顶向下分析的过程是从识别符号出发，试图构造一个推导，该推导得出的符号串与输入符号串相同。
这种推导是最左推导。
从语法的角度看，自顶向下是从根节点构造语法树的过程。
在进行语法分析的时候不再考虑具体的符号是怎么构成的。
1引言南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
1引言（续）
由于自顶向下分析技术是一个从识别符号开始逐步构造最左推导的过程。每一步都将最左的非终结符号替换为其相应规则的右部。
开始时，句型就是由一个识别符号组成的。
每次选择规则之后，替换最左非终结符号，
得到一个新的句型。
由于在一般的情况下，一个非终结符号对应有多个规则。具体选择哪个规则将是自顶向下分析技术所需要解决的主要问题。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
1引言（续）
自顶向下分析技术的基础是定理 2.7。在不停构造推导的过程中，所得到的句型中最长的不包含非终结符号的头必须也是输入符号串的头。
如果在构造到某一步时，没有办法得到满足上面要求的规则。那么当前得到的句型就不能推倒出输入符号串。这个时候有两个处理办法：或回溯并重新构造前面的推倒，或者认为输入符号串不是句型。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
2 带回溯的自顶向下分析技术
现在我们考虑在推导构造不下去的时候进行回溯的分析技术技术。基本方法是，推导的时候从候选的规则中任意取一个规则。当发现这个规则不能继续推导的时候，在选一个新的规则从新做起。
在进行回溯的时候，主要要做的事情就是将状态恢复到上一次选择时的状态。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术带回溯的自顶向下分析技术的算法实现
这里我们采用和书上的描述不同的算法。利用递归技术来实现这个算法。这里描述的方法不考虑细节的问题。
算法的输入参数是：一个包含非终结符号的符号和一个终结符号串（它必然是输入符号串的尾）。当从第一个符号推倒出输入符号串的头的时候，输出是剩余的符号串。否则输出错误信息。这是一个递归调用自己的程序。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术带回溯的自顶向下分析技术的算法实现续
Match(X1X2…X n,X)
var Input:array [1..Max] of SymbolStrings;
begin
I=1; Input[I]:= X;
flag = 0;
while (I >= 0 and I<=n) do begin
if X1是终结符号
then begin
if X1 != Input[I]的首符号 or flag = 1;
then beginI,= I-1; flag,= 1; end
else begin Input[I+1]:=tail(Input[I]); I:=I+1; flag = 0;end;
end
else
begin
选取新的关于 XI的规则，设其右部为 Y1Y2….Y m;
Input[I+1]:=Match(Y1Y2…Y m,Input[I]));
if (Input[I+1] = ERROR)
then begin
if 没有更多 Xi的规则 then begin I:=I-1; flag = 1; end
else flag,= 0;
end
else begin I:=I+1; flag,= 0; end
end
end{of while}
if(I>n)
then return Input[n+1];
else return ERROR;
end
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术回溯自顶向下技术的问题
效率问题
语义处理问题
语法错误的显示
左递归问题南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
3,无回溯的自顶向下分析技术先决条件：
1：无左递归，既不能有规则左递归，又不能有文法左递归。否则自顶向下技术就可能进入死循环。
2：无回溯，要求对任何一个非终结符号对应的规则，其右部的符号串所能推导出来的终结符号串的头部是两两不相交的。回顾在带回溯的算法，可以知道这使得在选择规则的时候唯一确定适合的规则。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术预测分析技术
预测分析技术是一种无回溯的分析技术。
它使用一个预测分析表和一个栈来完成对输入符号串的分析。
预测分析表是一个二维数组。它给出了当需要对 A进行推导，并且当前输入符号是 T
的时候，应该选择哪个规则。没有规则可选，此时输入符号串不是句子。
在输入符号串后面都跟有一个 #。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术预测分析过程
在这个过程中，设已经扫描过的字符串 u而栈中的符号串（自顶向下）为 v,那么 uv联合起来就是一个句型。
整个过程就是要试图将这个句型推导到输入符号串。
当栈顶符号为 X的时候，过程的下一步动作就是要对这个符号选取一个规则进行推导。
过程使用预测分析表，以及当前的输入符号来确定选取哪个规则。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术预测分析表的生成
如果有规则 U::= x,A[U,T]=‘U::=x’当且仅当相对于 U的短语的首符号可以是 T,且这个短语是对应于规则 U::=x。
所以，我们需要求得每个规则的右部可以推导到的短语的头符号有那些。如果不考虑空规则，可能的头符号可以使用右部的第一个符号确定。如果该符号是非终结符号，那么右部就是所有这个非终结符号的头符号。如果第一个符号是终结符号，对应的头符号就是该终结符号。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术预测分析表的生成（续）
如果考虑空规则，那么解决这个问题会有一点复杂。
对于一个 U的规则的右部 XY…,如果 X可以推导出空符号串，那么 这个右部头符号可以是 Y的头符号。而如果 Y可以推导出空符号，
那么右部的头符号可以是紧接的符号的头符号 … 。如果所有的符号都可以推导出空符号，
那么这个规则的‘头符号’可以是可能跟随
U的符号的头符号。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术预测分析表的生成（续）
定义 First(u)和 Follow(U)。 First(u)表示了所有可能对应于 u的‘短语’的头符号。考虑到空规则，那么：‘空’在 First(u)中当且仅当 u=>*空。而 Follow(U)表示在句型中可能跟在 U后面的终结符号的集合。
在构造 First(u)的时候，首先构造单个符号的 First(U)。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
First(U)的构造算法反复使用下面的规则（包括后一页）直到稳定
首先对于终结符号 X,First(X)={X}。
对于非终结符号 X，如果有一个 X的规则的右部的头符号是非终结符号 T,那么 T在
First(X)中。如果右部是空符号，那么‘空’
也在其中。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
First(U)的构造算法
对于一个规则 U::=X1X2…X n。这 First(U)包括这些符号,First(X1)，并且如果对于整数 K,所有 First(Ui),0<i<K都包含空，那么
First(Xk)也在 First(U)中。若所有 First(Xi)都包含空，那么 U也包含空。
对于 First(u)的构造直接可以由 First(U)得到。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
FOLLOW(U)的构造算法需要重复使用以下步骤（包括下一页）直到稳定。
#在 Follow(Z)中，其中 Z是识别符号。
如果有一个规则 U::=xWy,那么 FIRST(y)中所有的符号，除空之外，都在 Follow(W)
中。
如果存在规则 U::=xW或 U::=xWy且 First(y)
包含有空，那么 Follow(U)也在 Follow(W)
中。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术构造分析表
分析表的作用是：通过当前输入符号，和最左的非终结符号来确定应该使用哪一个规则。
显然：如果这个符号不能推导到空的话，
那么必须选择规则使得规则的右部的短语的头符号是当前输入符号。如果这个规则可以推导到空串，那么这个符号必然是可以紧跟在这个符号后边。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术构造分析表
算法：
对于每个规则 U::=u,执行下面的步骤：
– 每个终结符号 a,如果 a在 First(u)中,A[U,a]设置为‘ U::=u’。
– 如果 First(u)中包含空，那么对于所有的在
Follow(U)中的符号 b,A[U,b]设置为‘ U::=u’。
当处理过所有的规则后，将空白的地方设置为 Error。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术分析表中不可确定项的处理
在某些情况下，一个 A[U,T]可能有多个候选值。这表示在有些时候，通过分析表不能确定使用哪个规则。
在一些时候，我们可以通过选定 A[U,T]的候选值来影响语法分析的执行。
比如例 4.7。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
LL(1)文法定义
当文法的预测分析表中的元素没有多重定义的时候，该文法称为 LL(1)文法。
定理 4.1：一个文法是 LL(1)文法的充分必要条件。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术使用预测表的自顶向下分析技术（无回溯）
使用预测表可以在自顶向下分析的时候确定选取哪个规则。
递归下降法和预测分析法都可以使用这个表。
递归下降法也可以使用其它的方法来选择推导规则。
这两个方法的基本思想是一致的。所不同的是：预测分析技术的栈的显式的，而递归下降法的栈是和过程调用栈以及程序执行路径联系在一起的。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术递归下降分析技术
对于每个非终结符号编写一个过程。
在过程的开始部分进行规则的选择。（可以使用预测分析表）
如果选择不到合适的规则，那么进行出错处理。
对于选定的规则 U::=X1X2…X n，依次调用相应的程序（如果 Xi是非终结符号）或将 Xi和当前输入符号比较，相同则读取下一个符号
（ Xi是终结符号）。否则进行出错处理。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术递归下降分析技术的优点
简单明了，可以和非终结符号直接对应。
容易进行语义处理。
自顶向下分析的过程是从识别符号出发，试图构造一个推导，该推导得出的符号串与输入符号串相同。
这种推导是最左推导。
从语法的角度看，自顶向下是从根节点构造语法树的过程。
在进行语法分析的时候不再考虑具体的符号是怎么构成的。
1引言南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
1引言（续）
由于自顶向下分析技术是一个从识别符号开始逐步构造最左推导的过程。每一步都将最左的非终结符号替换为其相应规则的右部。
开始时，句型就是由一个识别符号组成的。
每次选择规则之后，替换最左非终结符号，
得到一个新的句型。
由于在一般的情况下，一个非终结符号对应有多个规则。具体选择哪个规则将是自顶向下分析技术所需要解决的主要问题。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
1引言（续）
自顶向下分析技术的基础是定理 2.7。在不停构造推导的过程中，所得到的句型中最长的不包含非终结符号的头必须也是输入符号串的头。
如果在构造到某一步时，没有办法得到满足上面要求的规则。那么当前得到的句型就不能推倒出输入符号串。这个时候有两个处理办法：或回溯并重新构造前面的推倒，或者认为输入符号串不是句型。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
2 带回溯的自顶向下分析技术
现在我们考虑在推导构造不下去的时候进行回溯的分析技术技术。基本方法是，推导的时候从候选的规则中任意取一个规则。当发现这个规则不能继续推导的时候，在选一个新的规则从新做起。
在进行回溯的时候，主要要做的事情就是将状态恢复到上一次选择时的状态。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术带回溯的自顶向下分析技术的算法实现
这里我们采用和书上的描述不同的算法。利用递归技术来实现这个算法。这里描述的方法不考虑细节的问题。
算法的输入参数是：一个包含非终结符号的符号和一个终结符号串（它必然是输入符号串的尾）。当从第一个符号推倒出输入符号串的头的时候，输出是剩余的符号串。否则输出错误信息。这是一个递归调用自己的程序。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术带回溯的自顶向下分析技术的算法实现续
Match(X1X2…X n,X)
var Input:array [1..Max] of SymbolStrings;
begin
I=1; Input[I]:= X;
flag = 0;
while (I >= 0 and I<=n) do begin
if X1是终结符号
then begin
if X1 != Input[I]的首符号 or flag = 1;
then beginI,= I-1; flag,= 1; end
else begin Input[I+1]:=tail(Input[I]); I:=I+1; flag = 0;end;
end
else
begin
选取新的关于 XI的规则，设其右部为 Y1Y2….Y m;
Input[I+1]:=Match(Y1Y2…Y m,Input[I]));
if (Input[I+1] = ERROR)
then begin
if 没有更多 Xi的规则 then begin I:=I-1; flag = 1; end
else flag,= 0;
end
else begin I:=I+1; flag,= 0; end
end
end{of while}
if(I>n)
then return Input[n+1];
else return ERROR;
end
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术回溯自顶向下技术的问题
效率问题
语义处理问题
语法错误的显示
左递归问题南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
3,无回溯的自顶向下分析技术先决条件：
1：无左递归，既不能有规则左递归，又不能有文法左递归。否则自顶向下技术就可能进入死循环。
2：无回溯，要求对任何一个非终结符号对应的规则，其右部的符号串所能推导出来的终结符号串的头部是两两不相交的。回顾在带回溯的算法，可以知道这使得在选择规则的时候唯一确定适合的规则。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术预测分析技术
预测分析技术是一种无回溯的分析技术。
它使用一个预测分析表和一个栈来完成对输入符号串的分析。
预测分析表是一个二维数组。它给出了当需要对 A进行推导，并且当前输入符号是 T
的时候，应该选择哪个规则。没有规则可选，此时输入符号串不是句子。
在输入符号串后面都跟有一个 #。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术预测分析过程
在这个过程中，设已经扫描过的字符串 u而栈中的符号串（自顶向下）为 v,那么 uv联合起来就是一个句型。
整个过程就是要试图将这个句型推导到输入符号串。
当栈顶符号为 X的时候，过程的下一步动作就是要对这个符号选取一个规则进行推导。
过程使用预测分析表，以及当前的输入符号来确定选取哪个规则。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术预测分析表的生成
如果有规则 U::= x,A[U,T]=‘U::=x’当且仅当相对于 U的短语的首符号可以是 T,且这个短语是对应于规则 U::=x。
所以，我们需要求得每个规则的右部可以推导到的短语的头符号有那些。如果不考虑空规则，可能的头符号可以使用右部的第一个符号确定。如果该符号是非终结符号，那么右部就是所有这个非终结符号的头符号。如果第一个符号是终结符号，对应的头符号就是该终结符号。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术预测分析表的生成（续）
如果考虑空规则，那么解决这个问题会有一点复杂。
对于一个 U的规则的右部 XY…,如果 X可以推导出空符号串，那么 这个右部头符号可以是 Y的头符号。而如果 Y可以推导出空符号，
那么右部的头符号可以是紧接的符号的头符号 … 。如果所有的符号都可以推导出空符号，
那么这个规则的‘头符号’可以是可能跟随
U的符号的头符号。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术预测分析表的生成（续）
定义 First(u)和 Follow(U)。 First(u)表示了所有可能对应于 u的‘短语’的头符号。考虑到空规则，那么：‘空’在 First(u)中当且仅当 u=>*空。而 Follow(U)表示在句型中可能跟在 U后面的终结符号的集合。
在构造 First(u)的时候，首先构造单个符号的 First(U)。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
First(U)的构造算法反复使用下面的规则（包括后一页）直到稳定
首先对于终结符号 X,First(X)={X}。
对于非终结符号 X，如果有一个 X的规则的右部的头符号是非终结符号 T,那么 T在
First(X)中。如果右部是空符号，那么‘空’
也在其中。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
First(U)的构造算法
对于一个规则 U::=X1X2…X n。这 First(U)包括这些符号,First(X1)，并且如果对于整数 K,所有 First(Ui),0<i<K都包含空，那么
First(Xk)也在 First(U)中。若所有 First(Xi)都包含空，那么 U也包含空。
对于 First(u)的构造直接可以由 First(U)得到。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
FOLLOW(U)的构造算法需要重复使用以下步骤（包括下一页）直到稳定。
#在 Follow(Z)中，其中 Z是识别符号。
如果有一个规则 U::=xWy,那么 FIRST(y)中所有的符号，除空之外，都在 Follow(W)
中。
如果存在规则 U::=xW或 U::=xWy且 First(y)
包含有空，那么 Follow(U)也在 Follow(W)
中。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术构造分析表
分析表的作用是：通过当前输入符号，和最左的非终结符号来确定应该使用哪一个规则。
显然：如果这个符号不能推导到空的话，
那么必须选择规则使得规则的右部的短语的头符号是当前输入符号。如果这个规则可以推导到空串，那么这个符号必然是可以紧跟在这个符号后边。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术构造分析表
算法：
对于每个规则 U::=u,执行下面的步骤：
– 每个终结符号 a,如果 a在 First(u)中,A[U,a]设置为‘ U::=u’。
– 如果 First(u)中包含空，那么对于所有的在
Follow(U)中的符号 b,A[U,b]设置为‘ U::=u’。
当处理过所有的规则后，将空白的地方设置为 Error。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术分析表中不可确定项的处理
在某些情况下，一个 A[U,T]可能有多个候选值。这表示在有些时候，通过分析表不能确定使用哪个规则。
在一些时候，我们可以通过选定 A[U,T]的候选值来影响语法分析的执行。
比如例 4.7。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术
LL(1)文法定义
当文法的预测分析表中的元素没有多重定义的时候，该文法称为 LL(1)文法。
定理 4.1：一个文法是 LL(1)文法的充分必要条件。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术使用预测表的自顶向下分析技术（无回溯）
使用预测表可以在自顶向下分析的时候确定选取哪个规则。
递归下降法和预测分析法都可以使用这个表。
递归下降法也可以使用其它的方法来选择推导规则。
这两个方法的基本思想是一致的。所不同的是：预测分析技术的栈的显式的，而递归下降法的栈是和过程调用栈以及程序执行路径联系在一起的。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术递归下降分析技术
对于每个非终结符号编写一个过程。
在过程的开始部分进行规则的选择。（可以使用预测分析表）
如果选择不到合适的规则，那么进行出错处理。
对于选定的规则 U::=X1X2…X n，依次调用相应的程序（如果 Xi是非终结符号）或将 Xi和当前输入符号比较，相同则读取下一个符号
（ Xi是终结符号）。否则进行出错处理。
南京大学计算机系 赵建华语法分析 ----自顶向下分析技术递归下降分析技术的优点
简单明了，可以和非终结符号直接对应。
容易进行语义处理。
