递归下降分析法思想是：让每个非终结符对应一个过程（函数）。根据上述文法，构造递归下降分析程序，程序用类C语言描述。
struct code_val{
char code;char val[20];
} t; //定义结构变量，存放单词二元式。
ifstream cinf("lex_r.txt",ios::in); //从文件lex_r.txt输入数据
void E( ) // E→TE'
{
T;E';
}
void E'( ) // E'→+TE'|ε
{
if (t.code=='+'){
cinf>>t.code>>t.val; //读一个单词的二元式
T;E';
}
}
void T( ) // T→FT'
{
F;T';
}
void T'( ) // T'→*FT'|ε
{
if (t.code=='*'){ //最好写为(t.code in First(T'))
cinf>>t.code>>t.val; //读一个单词的二元式
F;T'
}
}
void F( ) // F→(E) | i | x | y
{
if (t.code=='('){
cinf>>t.code>>t.val; //读一个单词的二元式
E;
if (t.code==')') cinf>>t.code>>t.val; //读一个单词的二元式
}
else if (t.code=='i'|| t.code=='x'|| t.code=='y')
cinf>>t.code>>t.val; //读一个单词的二元式
}
void main( )
{
cinf>>t.code>>t.val; //读一个单词的二元式
E;
}
源程序经词法分析，改造为单词二元式序列形式，存放于文件lex_r.txt中。递归下降分析器从文件lex_r.txt读入数据进行处理。
4.7 预测分析法
㈠预测分析法基本原理
产生式的一般形式为：
A→α1|α2|…|αn|ε
设当前输入符号为a，根据下述原则
if (a∈first(αi))
用A→αi推导（1≤i≤n）
else if (a∈follow(A))
用A→ε推导
else
报错
构造分析表如下
|
|
+ |
* |
( |
) |
i |
x |
x |
# |
| E |
|
|
E→TE' |
|
E→TE' |
E→TE' |
E→TE' |
|
| E' |
E'→+TE' |
|
|
E'→ε |
|
|
|
E'→ε |
| T |
|
|
T→FT' |
|
T→FT' |
T→FT' |
T→FT' |
|
| T' |
T'→ε |
T'→*FT' |
|
T'→ε |
|
|
|
T'→ε |
| F |
|
|
F→(E) |
|
F→i |
F→x |
F→x |
|
以输入串“i + i#”为例，说明工作原理如下：
ETE'FT'E'iT'E'iE'i+TE'i+FT'E'i+iT'E'i+iE'i+i
i i i + + i i # #
㈡分析表构造规则
①构造所有候选式的first集，构造所有非终结符的follow集。
②对于文法的每个产生式A→α执行③和④。
③对于每个终结符a∈first(α)，把A→α加至M[A][a]。
④若ε∈first(α)，则对于每个终结符b∈follow(A)，把A→α加至M[A][b]。
⑤把所有未定义的M[A][c]标上“出错标志”（c∈VT）。
㈢预测分析控制程序实现
①数据结构
M： 二维数组，存放预测分析表。
stack： 符号栈，初始时为"#S"（S为开始符号）。
X： 表示栈顶符号
t.code： 当前处理单词种别
②算法描述
预测分析控制程序任何时刻的动作，都按照栈顶符号X和当前输入符号t.code行事，控制程序每次执行下述三种可能的动作之一（暂不考虑出错情况）。
l 若X 和 t.code 均为 '#'，则分析成功，输入串为合法句子，终止分析过程。
l 若X是终结符，并且X和t.code相等，表示期望的终结符号和输入符号相等。让X出stack栈，并输入下一个单词二元式。
l 若X是非终结符，则查预测分析表。若M[X][t.code]存放着一条关于X的一个产生式，那么，让X出stack栈，然后把产生式右部符号串按反序一一推进stack栈。若右部符号串为空字ε，则意味着无任何文法符号进栈。
㈣预测分析法讨论
①预测分析法是由分析表和控制程序构成的，控制程序与文法无关，分析表随文法而异。
②在预测分析表中，若某一单元持有一个以上产生式，则称该预测分析表含多重定义，多重定义使得控制程序无法工作。
③一个文法，若它的预测分析表不含多重定义，则称该文法是LL(1)文法、分析表为LL(1)分析表。
④一个文法是LL(1)的，对于文法的每一个非终结符的任何两个不同候选式（A→α|β），下述条件成立：
l first(α)∩first(β)={}
l 若βε，则first(α)∩follow(A)={}
⑤二义文法不是LL(1)文法
本文摘自《编译原理实用教程》(清华大学)
