编译原理语法分析实验报告.doc

(完整word版)编译原理语法分析实验报告

南华大学
计算机科学与技术学院
实 验 报 告

（ 2007 ~2008 学年度 第二学期 ）

课程名称
编译原理

实验名称
语法分析

姓名
寻友旭
学号
20054350227

专业
软件工程
班级
软件工程052班

地点
6—413
教师
陈星

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语言编程实现分析器。
本次所写的语法分析器过于简单，相信以后会再接再厉写出更复杂，更好的分析器来。

14
软件工程052班 20054350227 寻友旭