实验二编写语法分析程序
2.1 实验类型
设计型实验，6学时(2学时完成文法改造；2学时完成程序编码；2学时完成程序测试)
2.2 实验目的
通过设计、编写、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握递归下降语法分析方法。
2.3 背景知识
2.3.1 递归下降分析
自顶向下语法分析过程中，如果产生回溯，则分析过程需要穷举所有可能的推导，看是否能推导出待检查的单词序列，导致分析程序时间和空间开销增大，降低分析效率。
而无回溯的自顶向下分析技术可根据输入串的当前单词，选择唯一的产生式构造推导过程，从而提高分析效率。
无回溯的自顶向下分析要求文法是LL(1)文法。
递归下降分析程序的实现思想是：(1) 分析程序由一组子程序组成，每个子程序对应于一个非终结符号。
(2) 每一个子程序的功能：选择正确的产生式右部，扫描相应的单词；产生式右部有非终结符号时，调用该非终结符号对应的子程序来完成。
2.3.2 LL(1)文法
LL(1)文法满足以下三个条件：
（1）文法不含左递归
（2）文法的任何一个非终结符A的各个产生式的右部符号串的FIRST集两两不相交，即：
若有A→α1|α2|…|αn，则
FIRST (a i)∩FIRST (a j) = φ(i ≠j，1≤i,j≤n)
（3）文法的任何一个非终结符A,
若有A→α1|α2|…|αn且存在a i，有ε∈FIRST (αi)，则
FIRST (αj)∩FOLLOW (A) = φ（i ≠j，j=1,2,. . .,n ）
2.3.3 文法改造
1、消除直接左递归（将左递归改为右递归）：
直接左递归形式：U→Ux|y；其中：x，y∈(V N∪V T)* ，y不以U打头。
直接左递归的消除：
U→yU’
U’→xU’|ε
直接左递归的一般形式：U→Ux1|Ux2|…|Ux m|y1|y2|…|y n；其中：x i≠ε ,y i都不以U打头。
一般形式直接左递归的消除:
U→y1U’| y2U’ |…| y n U’
U’→x1U’| x2U’| …| x m U’|ε
2、消除间接左递归：
要求无环路（形如A⇒+ A的推导）和无ε-产生式。
（1）把非终结符按某一顺序排序为A1,A2…An 。
（2）for(i=1;i<=n;i++)
{
for(j=1;j<=i-l;j++)
{
if(Aj→δ1|δ2|…|δk ,Ai→Ajγ)
把Ai→Ajγ改写成
Ai→δ1γ|δ2γ|…|δkγ;
}
消除关于Ai产生式的直接左递归;
}
（3）化简由（2）所得到的文法。
（4）化简改写之后的文法，删除多余产生式。
3、提取左公因子
A→αβ1|αβ2……|αβn |γ1……|γm
改写成:
A→αA’|γ1……|γm
A’→β1|β2……|βn
2.3.4递归下降分析程序的基本架构
定义：
变量：ch，为当前符号；
函数：READ(ch)：读输入串下一符号；
对于每个非终结符号U→α 1|α 2|…|α n处理的方法如下：
U（）
{
if ch∈FIRST(α1 ) then P(α1) //处理α1的程序部分。
else if ch∈FIRST(α2 ) then P(α2) //处理α2的程序部分。
…
else if ch∈FIRST(αn ) then P(αn)
else if ch∈FOLLOW(U) then return //处理ε产生式情况。
else error
}
对于每个右部α =x1x2…x n的处理架构如下：
P(α )
{
P(x1 ); //处理x1的程序。
P(x2 ); //处理x2的程序。
… … …
P(x n ); //处理x n的程序。
}
对于右部中的每个符号x i；
如果x i为终结符号：
if(ch== a)
READ (ch)
else
error
如果x i为非终结符号，直接调用相应的过程：P (x i)。
2.3.5编写递归下降分析程序一般步骤
1) 改写文法，消除二义性；
2) 消除左递归、提取左因子；
3) 求FIRST集、FOLLOW集；
4) 检查是不是LL(1) 文法，若不是LL(1)，说明文法的复杂性超过自顶向下方法的
分析能力（对文法的改造会影响文法的可读性，可以采用超前读一个单词的来处理）。
5) 直接根据产生式设计相应的程序
2.4 实验内容
1、语法规则
TEST语言的语法规则如下：
1) <program>→{<declaration_list><statement_list>}
2) <declaration_list>→<declaration_list><declaration_stat> | ε
3) <declaration_stat>→int ID;
4) <statement_list>→<statement_list><statement>| ε
5) <statement>→<if_stat>|<while_stat>|<for_stat>|<read_stat>
|<write_stat>|< compound_stat > |<expression_stat>
6) <if_stat>→if (<expr>) <statement >| if (<expr>) <statement >else < statement >
7) <while_stat>→while (<expr >) < statement >
8) <for_stat>→for (<expr>;<expr>;<expr>)<statement>
9) <write_stat>→write <expression>;
10) <read_stat>→read ID;
11)<compound_stat>→{<statement_list>}
12)<expression_stat>→< expression >;|;
13)< expression >→ID=<bool_expr>|<bool_expr>
14)<bool_expr>→<additive_expr> |< additive_expr >(>|<|>=|<=|==|!=)< additive_expr >
15)< additive_expr>→< additive_expr>+<term>|< additive_expr>-<term>|< term >
16)< term >→< term >*<factor>|< term >/<factor>|< factor >
17)< factor >→(< expression >)|ID|NUM
2、要求：
根据递归下降分析方法，完成TEST语言的递归下降语法分析程序的构造，主要完成：(1) 改造文法，使之满足无回溯的递归下降分析条件，给出改写后的文法（写入实验报告）；说明：
A、规则6能否提取左公因子？如果提取后会有什么后果？分析原因后给出你的处理方案。
B、规则13可以采用采用超前读一个单词来解决，避免对该规则进行改写，保持文法的可读性。
C、红色标注的文法均需要进行改写。
D、对改写后的文法，计算所有右部符号串的FIRST集合；如有ε产生式，计算该产生式左部非终结符的FOLLOW集。
(2) 编写递归下降分析程序；（将<statement>，< expression >的程序流程图写入实验报告）
(3) 使用下述的TEST语言代码测试编写的递归下降分析程序（先使用实验一的词法分析程序进行词法分析，要求标识符类别记为ID，整数记为NUM，其它单词采用单词本身，比如int的类别就是int，，<=的类别就是<+）。
{
int a;
int i;
int b,c;
for (i=1; i <= 10; i=i+1)
{
;
a=a+i
b=b*i;
{
c=a+b;
}
}
if (a>b)
{
write a;
}
else
{
write b;
}
}
write c
}
2.5 实验分析与思考
1、TEST语言语法规则中哪些不满足无回溯的递归下降分析条件？你是怎么处理的？给出你的处理方案。
2、所有文法都可以改写为满足递归下降分析条件的文法吗？如果不能，请给出一个反例。
3、改写文法有什么弊端？。