《编译原理》实验报告
实验3 递归下降分析器的设计
姓名学号班级计科1001班
时间： 2012/4/15 地点:文波
同组人：无
指导教师：朱少林
实验目的
使用递归子程序法设计一个语法分析程序，理解自顶向下分析方法的原理，掌握手工编写递归下降语法分析程序的方法。
实验内容
a.运用所学知识，编程实现递归下降语法分析程序。使用递归下降分析算法分析表达
式是否符合下文法：
exp → exp addop term | term
Addop →+ | -
term→ term mulop factor | factor
mulop → * | /
factor → (exp) | id | number
其中number可以是多位的十进制数字串（整数即可），因此这里还需要一个小的词法分析器来得到id 和number的值。
b.从数据文件中读出符号串，输出表达式并给出其正误评判。
实验数据文件中应该有多个表达式，可能有正确的也应该有错误的表达式；表达式有形式简单的也应该有复杂的。每个表达式写在一行，以回车结束。
实验环境
软件：VC++6.0
实验前准备
1、方案设计：
①准备模拟数据：本实验中使用“work..cpp”
②程序思想：
为了使用递归向下的分析，为每个非终结符根据其产生式写一个分析程序，由于写入读出的操作频繁。所以程序中还有一个match(char t)函数，该函数是将字符写入文件打印输出同时从文件中读取下一个字符，而由于id和number可能是多个字符构成，故写了number()和id（）来分析数字和标识符，它们的功能仅仅是把整个number或id完整的读取出来并写入文件，打印输出。
由于分析的文件中可能出现非法字符，而一旦发现非法字符就无需再接着分析，所以在每次读取一个字符时调用islegal函数判断是否是合法字符，并返回0或1.
在main()函数中，while((lookahead=='\n'||lookahead==' ')&&lookahead!=EOF) fscanf(resource,"%c",&lookahead);
是为了忽略分析文件中的换行或空格，之后进入分析阶段，根据返回值判断是否是合法的表达式。在该程序中只有发现了非法字符才会返回0，否则就返回1，而对于合法的表达式，递归程序最后分析的字符就是换行符，不合法的表达式在未分析到换行符就会停止分析，所以根据最后分析的字符是否为换行符进一步确定是否为合法的表达式。
实验步骤
首先将上述文法改写成LL（1）文法
①消除左递归：
exp →term texp
texp → addop term texp | ε
Addop →+ | -
term→factor tterm
tterm →mulop factor tterm|ε
mulop → * | /
factor → (exp) | id | number
②求出每个非终结符的FIRST集合和FOLLOW集合：
FIRST(exp)= FIRST(term)= FIRST(factor)={id, number, ( }
FIRST(texp)={ ε,+, - }
FIRST(Addop)={+, - }
FIRST(tterm)={ ε,*, / }
FIRST(mulop)={*, / }
求出每个非终结符的FOLLOW集合：
FOLLOW(exp)=FOLLOW(texp)={#, ）}
FOLLOW(Addop)=FOLLOW(mulop)={id, number, ( }
FOLLOW(term)=FOLLOW(tterm)={+, -,#, ) }
FOLLOW(factor)={ *,/,+,-,#,) }
对于texp → addop term texp | ε：FIRST（Addop term texp）∩FOLLOW(texp)= φ；
对于tterm →mulop factor tterm|ε：FIRST(mulop factor tterm)∩FOLLOW(tterm)= φ；
而Addop →+ | - mulop → * | /factor → (exp) | id | number 显然也是符合LL（1）文法要求的，所以改写后的文法符合LL（1）文法，可以用自上而下的递归分析方法。
③为每个非终结符根据其产生式写一个分析子程序；
④编写数字和字母识别程序，以便分离数字和标识符。；
⑤主函数调用递归程序进行分析，根据分析结果判断是否是合法表达式，并将所有识
别到的表达式输出。
程序设计：
#include
#include
number();
id();
int exp();
int texp();
int addop();
int term();
int tterm();
int mulop();
int factor();
int islegal();
void match(char t);
FILE *resource;//测试文件
FILE *result;//结果文件
char lookahead;//全局变量
void match(char t)//写入result文件,打印输出，并读取下一个
{
fprintf(result,"%c",lookahead);//向result写入
printf("%c",lookahead);
fscanf(resource,"%c",&lookahead);//读数据
}
number()//识别数字，如果遇到数字就一直接着读直到不是数字
{
while('0'<=lookahead&&lookahead<='9')
{
fprintf(result,"%c",lookahead);//写入
printf("%c",lookahead);
fscanf(resource,"%c",&lookahead);//读出
}
}
id()
{//识别标识符
while((lookahead<='z'&& lookahead>='a')||(lookahead>='A'&& lookahead<='Z')||lookahead=='_')
{
while((lookahead<='z'&& lookahead>='a')||(lookahead>='A'&& lookahead<='Z')||lookahead=='_'
||lookahead>='0'&&lookahead<='9')
{
fprintf(result,"%c",lookahead);//写入
printf("%c",lookahead);
fscanf(resource,"%c",&lookahead);//读
}
}
}
