南华大学
计算机科学与技术学院
实 验 报 告
（ 20## ~2008 学年度 第二学期 ）
1.实验目的及要求
编制一个递归下降分析程序，实现对词法分析程序所提供得单词序列得语法检查和结构分析。
软件、硬件环境
VC6.0
要求：
利用C语言编制递归下降分析程序，并对简单语言进行语法分析。
待分析的简单语言得语法：
EàE+T | E-T | T
TàT*F | T/F |F
Fà(E) | i
输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“Accept! Right Expression!”，否则输出“Error!!!”。
语法分析：
a) ∵E=>E+T=>E+T*F=>E+T*(E)即有E=>E+T*(E)存在左递归。用直接改写法消除左递归，得到如下：
E à TE’
E’ à +TE’ | ?TE’|ε
T à FT’
T’ à *FT’ | /FT’|ε
F à (E) | i
b) 对于以上改进的方法。可得：
对于E’: FIRST( E’ )=FIRST(+TE’)∪FIRST(-TE’)∪{ε}={+，?，ε}
对于T’: FIRST( T’ )=FIRST(*FT’)∪FIRST(/FT’)∪{ε}={*，∕，ε}
而且： FIRST( E ) = FIRST( T ) = FIRST( F )=FIRST((E))∪FIRST(i)={(，i }
由此我们容易得出各非终结符的FOLLOW集合如下：
FOLLOW( E )= { )，#}
FOLLOW(E’)= FOLLOW(E)={ )，#}
FOLLOW( T )= FIRST(E’)\ε∪FOLLOW(E’)={+，?，)，#}
FOLLOW( T’ ) = FOLLOW( T ) ={+，?，)，#}
FOLLOW( F )=FIRST(T’)\ε∪FOLLOW(T’)={*，∕，+，?，)，#}
由以上FOLLOW集可以我们可以得出SELECT集如下：
对E SELECT（EàTE’）=FIRST(TE’)=FIRST(T)={ (，i }
对E’ SELECT（E’ à+TE’）={ + }
SELECT（E’ à ?TE’）={ ? }
SELECT（E’ àε）={ε，)，#}
对T SELECT（TàFT’）={(，i}
对T’ SELECT（T’ à*FT’）={ * }
SELECT（T’ à ∕FT’）={ ∕ }
SELECT（T’ àε）={ε，+，?，)，#}
对F SELECT（Fà(E) ）={ ( }
SELECT（Fài）={ i }
∴ SELECT(E’ à+TE’)∩SELECT（E’ à ?TE’）∩SELECT（E’ àε）=F
SELECT(T’ à*FT’)∩SELECT（T’ à ∕FT’）∩SELECT（T’ àε）=F
SELECT（Fà(E) ）∩SELECT（Fài）= F
由上可知，有相同左部产生式的SELECT集合的交集为空，所以文法是LL（1）文法。因此，转化后的文法可以用递归下降分析法作语法分析。
2.实验步骤
1、 分析试验资料，结合书本得出实验大体思路；
2、 根据资料画出语法分析程序的流程图；
3、 根据流程图与程序大体框架完善程序；
4、 将代码输入电脑中，调试；
5、 根据资料中数据测试程序得基本功能；
6、 根据测试结果，设计测试数据完善程序；
7、 根据实验结果分析总结。
3. 实验内容
词法分析程序的主要子函数模块流程图
\
程序：
#include <stdio.h>
#include<dos.h>
#include<stdlib.h>
#include<string.h>
char a[50] ,b[50],d[200],e[10];
char ch;
int n1,i1=0,flag=1,n=5;
int total=0;
int E();
int E1();
int T();
int G();
int S();
int F();
void input();
void input1();
void output();
void main() /*递归分析*/
{
int f,p,j=0;
char x;
d[0]='E';
d[1]='=';
d[2]='>';
d[3]='T';
d[4]='G';
d[5]='#';
printf("Please input character string(length<50,end of '#'):\n");
do{
scanf("%c",&ch);
a[j]=ch;
j++;
}while(ch!='#');
n1=j;
ch=b[0]=a[0];
printf("步骤\t文法\t分析串\t\t分析字符\t剩余串\n");
f=E1();
if (f==0) return;
if (ch=='#')
{ printf("\nAccept! Right Expression!\n\n");
p=0;
x=d[p];
while(x!='#') {
printf("%c",x);p=p+1;x=d[p]; /*输出推导式*/
}
}
else {
printf("\nError!!!\n");
printf("回车返回\n");
getchar();getchar();
return;
}
printf("\n");
printf("回车返回\n");
getchar();
getchar();
}
int E1()
{ int f,t;
printf("%d\tE-->TG\t",total);total++;
flag=1;
input();
input1();
f=T();
if (f==0) return(0);
t=G();
if (t==0) return(0);
else return(1);
}
int E()
{ int f,t;
printf("%d\tE-->TG\t",total);total++;
e[0]='E';e[1]='=';e[2]='>';e[3]='T';e[4]='G';e[5]='#';
output();
flag=1;
input();
input1();
f=T();
if (f==0) return(0);
t=G();
if (t==0) return(0);
else return(1);
int T()
{ int f,t;
printf("%d\tT-->FS\t",total);total++;
e[0]='T';e[1]='=';e[2]='>';e[3]='F';e[4]='S';e[5]='#';
output();
flag=1;
input();
input1();
f=F();
if (f==0) return(0);
t=S();
if (t==0) return(0);
else return(1);
}
int G()
{ int f;
if(ch=='+') {
b[i1]=ch;
printf("%d\tG-->+TG\t",total);total++;
e[0]='G';e[1]='=';e[2]='>';e[3]='+';e[4]='T';e[5]='G';e[6]='#';
output();
flag=0;
input();
input1();
ch=a[++i1];
f=T();
if (f==0) return(0);
G();
return(1);
}
printf("%d\tG-->^\t",total);total++;
e[0]='G';e[1]='=';e[2]='>';e[3]='^';e[4]='#';
output();
flag=1;
input();input1();
return(1);
}
int S()
{
int f,t;
if(ch=='*') {
b[i1]=ch;printf("%d\tS-->*FS\t",total);total++;
e[0]='S';e[1]='=';e[2]='>';e[3]='*';e[4]='F';e[5]='S';e[6]='#';
output();
flag=0;
input();input1();
ch=a[++i1];
f=F();
if (f==0) return(0);
t=S();
if (t==0) return(0);
else return(1);}
printf("%d\tS-->^\t",total);total++;
e[0]='S';e[1]='=';e[2]='>';e[3]='^';e[4]='#';
output();
flag=1;
a[i1]=ch;
input();
input1();
return(1);
}
int F()
{ int f;
if(ch=='(') {
b[i1]=ch;printf("%d\tF-->(E)\t",total);total++;
e[0]='F';e[1]='=';e[2]='>';e[3]='(';e[4]='E';e[5]=')';e[6]='#';
output();
flag=0;
input();
input1();
ch=a[++i1];
f=E();
if (f==0) return(0);
if(ch==')') {
b[i1]=ch;printf("%d\tF-->(E)\t",total);total++;
flag=0;input();input1();
ch=a[++i1];
}
else {
printf("\nError!!!\n");
return(0);
}
}
else if(ch=='i') {
b[i1]=ch;printf("%d\tF-->i\t",total);total++;
e[0]='F';e[1]='=';e[2]='>';e[3]='i';e[4]='#';
output();
flag=0;input();input1();
ch=a[++i1];
}
else {printf("\nError!!!\n");return(0);}
return(1);
}
void input()
{
int j=0;
for (;j<=i1-flag;j++)
printf("%c",b[j]); /*输出分析串*/
printf("\t\t");
printf("%c\t\t",ch); /*输出分析字符*/
}
void input1()
{
int j;
for (j=i1+1-flag;j<n1;j++)
printf("%c",a[j]); /*输出剩余字符*/
printf("\n");
}
void output(){ /*推导式计算*/
int m,k,j,q;
int i=0;
m=0;k=0;q=0;
i=n;
d[n]='=';d[n+1]='>';d[n+2]='#';n=n+2;i=n;
i=i-2;
while(d[i]!='>'&&i!=0) i=i-1;
i=i+1;
while(d[i]!=e[0]) i=i+1;
q=i;
m=q;k=q;
while(d[m]!='>') m=m-1;
m=m+1;
while(m!=q) {
d[n]=d[m];m=m+1;n=n+1;
}
d[n]='#';
for(j=3;e[j]!='#';j++){
d[n]=e[j];
n=n+1;
}
k=k+1;
while(d[k]!='=') {
d[n]=d[k];n=n+1;k=k+1;
}
d[n]='#';
}
4.实验结果
5. 实验总结分析
通过这次实验，我对语法分析有了更深刻的了解，对它的形成有了更清楚得认识。本次实验我主要是基于试验资料上的程序流程图和程序框架完成的。由一个简单一些的产生式得出程序的各个分函数。
此次所编写的语法分析程序是递归下降语法分析分析器，通过分析文法产生式得FFIRST、FOLLOW和SELECT集合来判断LL（1）方法，然后用递归下降语法分析法分析LL（1）方法得基本递归流，用C语言编程实现分析器。
本次所写的语法分析器过于简单，相信以后会再接再厉写出更复杂，更好的分析器来。