编译原理实验.doc

编译原理实验报告
实验一 词法分析
一、 实验目的
编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。
二、 实验题目
如源程序为C语言。输入如下一段：
main()
{
int a=-5,b=4,j;
if(a>=b)
j=a-b;
else j=b-a;
}
要求输出如下：
（2，”main”） （5，”（”） （5，”）”）
（5，”{”） （1，”int”） （2，”a”）
（4，”=”） （3，”-5”） （5，”,”）
（2，”b”） （4，”=”） （3，”4”）
（5，”,”） （2，”j”） （5，”;”）
（1，”if”） （5，”（”） （2，”a”）
（4，”>=”） （2，”b”） （5，”）”）
（2，”j”） （4，”=”） （2，”a”）
（4，”-”） （2，”b”） （5，”;”）
（1，”else”） （2，”j”） （4，”=”）
（2，”b”） （4，”-”） （2，”a”）
（5，”;”） （5，”}”）
三、 实验理论依据
(一)识别各种单词符号
程序语言的单词符号一般分为五种：
关键字（保留字/ 基本字）if 、while 、begin…
标识符：常量名、变量名…
常数：34 、56.78 、true 、‘a’ 、…
运算符：+ 、- 、* 、/ 、〈 、and 、or 、….
界限符：， ； （ ） { } /*…
识别单词：掌握单词的构成规则很重要
标识符的识别：字母| 下划线+( 字母/ 数字/ 下划线)
关键字的识别：与标识符相同，最后查表
常数的识别
界符和算符的识别
大多数程序设计语言的单词符号都可以用转换图来识别，如图1-1

图1-1

词法分析器输出的单词符号常常表示为二元式：（单词种别，单词符号的属性值）
单词种别通常用整数编码，如1 代表关键字，2 代表标识符等
关键字可视其全体为一种，也可以一字一种。采用一字一种得分法实际处理起来较为方便。
标识符一般统归为一种
常数按类型（整、实、布尔等）分种
运算符可采用一符一种的方法。
界符一般一符一种的分法。
(二)超前搜索方法
词法分析时，常常会用到超前搜索方法。
如当前待分析字符串为“a>+” ，当前字符为“>” ，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？
显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符’+’ ，这时可知应将’>’ 解释为大于运算符。但此时，超前读了一个字符’+’ ，所以要回退一个字符，词法分析器才能正常运行。又比如：‘+’ 分析为正号还是加法符号
(三)预处理
预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。由一个预处理子程序来完成。
四、 词法分析器的设计
1、 设计方法：
2、 写出该语言的词法规则。
3、 把词法规则转换为相应的状态转换图。
4、 把各转换图的初态连在一起，构成识别该语言的自动机
5、 设计扫描器
6、 把扫描器作为语法分析的一个过程，当语法分析需要一个单词时，就调用扫描器。
7、 扫描器从初态出发，当识别一个单词后便进入终态，送出二元式

开始
读标识符
是字母
掠过空格和回车符
查保留字表
是否查到
换成属性字
结束
是数字
是特殊符号
error
取数
换成属性字
换成属性字
换成属性字
Y
N
Y
Y
Y
N
N
N

图1-2 取单词程序框图

五、 程序代码

#include <stdio.h>
#include <string.h>
FILE *fp;
char cbuffer;
char *key[8]={"if","else","for","while","do","return","break","continue"};
int atype,id=4;

int isalpha( char c)
{
if((c<='z')&&(c>='a')||(c<='Z')&&(c>='A'))
return 1;
else return 0;
}

int isdigit(char c)
{
if(c>='0'&&c<='9')
return 1;
else return 0;
}

int search(char searchchar[ ],int wordtype) /*判断单词是保留字还是标识符*/
{
int i=0;
int p;
switch (wordtype)
{
case 1:for (i=0;i<=7;i++)
{
if (strcmp(key[i],searchchar)==0)
{ p=i+1; break; } /*是保留字则p为非0且不重复的整数*/
else p=0; /*不是保留字则用于返回的p=0*/
}
return(p);
}
}

char alphaprocess(char buffer)
{ int atype; /*保留字数组中的位置*/
int i=-1;
char alphatp[20];
while ((isalpha(buffer))||(isdigit(buffer))||buffer=='_')
{
alphatp[++i]=buffer;
buffer=fgetc(fp);
} /*读一个完整的单词放入alphatp数组中*/
alphatp[i+1]='\0';
atype=search(alphatp,1);/*对此单词调用search函数判断类型*/
if(atype!=0)
{ printf("(%d,\"%s\")\n",atype-1,alphatp); id=1; }
else
{ printf("(2,\"%s\")\n",alphatp); id=2; }
return (buffer);
}

char digitprocess(char buffer)
{
int i=-1;
char digittp[20];
while ((isdigit(buffer))||buffer=='.') /*1 判断小数*/
{
digittp[++i]=buffer;
buffer=fgetc(fp);
}
digittp[i+1]='\0';
printf("(3,\"%s\")\n",digittp);
id=3;
return(buffer);
}

char otherprocess(char buffer)
{
char ch[20];
ch[0]=buffer;
ch[1]='\0';
if(ch[0]==','||ch[0]==';'||ch[0]=='{'||ch[0]=='}'||ch[0]=='('||ch[0]==')')
{ printf("(5,\"%s\")\n",ch);
buffer=fgetc(fp);
id=5;
return(buffer);}
if(ch[0]=='/')
{
buffer=fgetc(fp);
if(buffer=='*') /*2 区分注释符号和除号*/
{
ch[1]=buffer;
buffer=fgetc(fp);
while(buffer!='*')
{
buffer=fgetc(fp);
}
ch[2]=buffer;
buffer=fgetc(fp);
if(buffer=='/')
{
ch[3]=buffer;
ch[4]='\0';
}
printf("(5,\"%s\")\n",ch);
}
else{
printf("(4,\"%s\")\n",ch);
id=4;
return(buffer);
}
buffer=fgetc(fp);
id=5;
return(buffer);
}

if(ch[0]=='*')
{ printf("(4,\"%s\")\n",ch);
buffer=fgetc(fp);
id=4;
return(buffer);
}

if(ch[0]=='='||ch[0]=='!'||ch[0]=='<'||ch[0]=='>')
{ buffer=fgetc(fp);
if(buffer=='=')
{ ch[1]=buffer;
ch[2]='\0';
printf("(4,\"%s\")\n",ch);
}
else
{ printf("(4,\"%s\")\n",ch);
id=4;
return(buffer);
}
buffer=fgetc(fp);
id=4;
return(buffer);
}

if(ch[0]=='+'||ch[0]=='-')
{ if(id==4) /*在当前符号以前是运算符，则此时为正负号*/
{ buffer=fgetc(fp);
ch[1]=buffer;
ch[2]='\0';
printf("(3,\"%s\")\n",ch);
id=3;
buffer=fgetc(fp);
return(buffer);
}
ch[1]='\0';
printf("(4,\"%s\")\n",ch);
buffer=fgetc(fp);
id=4;
return(buffer);
}

if(ch[0]=='#') /*3 识别头文件*/
{
char t[20];
int i=0;
t[0]=ch[0];
buffer=fgetc(fp);
while((isalpha(buffer))||buffer==' '||buffer=='<'||buffer=='>')
{

t[++i]=buffer;
buffer=fgetc(fp);
}
t[i+1]='\0';
printf("(6,\"%s\")\n",t);
id=6;
return (buffer);
}

if(ch[0]=='\\') /*4 识别转义符号*/
{
buffer=fgetc(fp);
ch[1]=buffer;
printf("(6,\"%s\")\n",ch);
buffer=fgetc(fp);
return(buffer);
}

if(ch[0]=='|'||ch[0]=='&') /*5 判断或与*/
{
buffer=fgetc(fp);
if(ch[0]==buffer)
{
ch[1]=buffer;
}
ch[2]='\0';
printf("(4,\"%s\")\n",ch);
buffer=fgetc(fp);
return(buffer);
}

if(ch[0]=='"'||ch[0]=='\'') /*6 判断双引号和单引号*/
{
printf("(5,\"%s\")\n",ch);
id=5;
buffer=fgetc(fp);
return(buffer);
}
}

int main()
{

if ((fp=fopen("example.c","r"))==NULL) /*只读方式打开一个文件*/
printf("error");
else
{
cbuffer = fgetc(fp); /*fgetc( )函数：从磁盘文件读取一个字符*/
while (cbuffer!=EOF)
{
if(cbuffer==' '||cbuffer=='\n') /*掠过空格和回车符*/
cbuffer=fgetc(fp);
else
if(isalpha(cbuffer))
cbuffer=alphaprocess(cbuffer);
else
if (isdigit(cbuffer))
cbuffer=digitprocess(cbuffer);
else cbuffer=otherprocess(cbuffer);
}
}
return 0;
}
六、 实验结果
程序添加了识别小数，识别注释符，识别自加自减符号，识别头文件，识别转义符号，识别或与符号，识别单引号和双引号，识别中括号，识别格式符，结果如图1-3所示：

图1-3

实验二 LL（1）分析法
一、实验目的：
根据某一文法编制调试LL(1)分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对预测分析LL(1)分析法的理解。
二、实验题目
实验规定对下列文法，用LL（1）分析法对任意输入的符号串进行分析：
（1）E::=TG
（2）G::=+TG
（3）G::=ε
（4）T::=FS
（5）S::=*FS
（6）S::=ε
（7）F::=(E)
（8）F::=i
若输入串为i+i*i# ，则输出为：
#E
i+i*i#
#GT
i+i*i#
#GSF
i+i*i#
#GSi
i+i*i#
#GS
+i*i#
#G
+i*i#
#GT+
+i*i#
…
…
…
…
T→FS

2
…
…
….
…
+

7
G→+TG

6
S→є

5
i

4
F→i

3
E→TG

1
产生式
剩余串
分析栈
步骤

LL(1)的分析表为：

i
+
*
(
)
#
说 明
E
e

e

Select(E→TG)=｛(,i｝
G

g

g1
g1
Select (G→+TG)=｛+｝
Select (G→є)=｛#,)｝
T
t

t

Select (T→FS)=｛(,i｝
S

s1
s

s1
s1
Select (S→*FS)=｛*｝Select (S→є)=｛#,) +｝
F
f1

f

Select (F→(E))=｛(｝
Select (F→i)=｛i｝

三、程序代码
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char A[20];/*分析栈*/
char B[20];/*剩余串*/
char v1[20]= {'i','+','*','(',')','#'}; /*终结符 */
char v2[20]= {'E','G','T','S','F'}; /*非终结符 */

int j=0,b=0,top=0,l;/*L为输入串长度 */

typedef struct type/*产生式类型定义 */
{
char origin;/*大写字符 */
char array[5];/*产生式右边字符 */
int length;/*字符个数 */
} type;

type e,t,g,g1,s,s1,f,f1;/*结构体变量 */
type C[10][10],cha;/*预测分析表 */

void print()/*输出分析栈 */
{
int a;/*指针*/
for(a=0; a<=top+1; a++)
printf("%c",A[a]);
printf("\t\t");
}

void print1() /*输出剩余串*/
{
int j;
for(j=0; j<b; j++) /*输出对齐符*/
printf(" ");
for(j=b; j<=l; j++)
printf("%c",B[j]);
printf("\t\t\t");
}

int main()
{
/*把文法产生式赋值结构体*/
e.origin='E';
strcpy(e.array,"TG");
e.length = 2;

t.origin='T';
strcpy(t.array,"FS");
t.length = 2;

g.origin='G';
strcpy(g.array,"+TG");
g.length = 3;

g1.origin='G';
//g1.array[0]='^';
strcpy(g1.array,"^");
g1.length = 1;

s.origin='S';
strcpy(s.array,"*FS");
s.length = 3;

s1.origin='S';
//s1.array[0]='^';
strcpy(s1.array,"^");
s1.length = 1;

f.origin='F';
strcpy(f.array,"(E)");
f.length = 1;

f1.origin='F';
strcpy(f1.array,"i");
f1.length = 1;

for(int m=0; m<=4; m++) /*初始化分析表*/
for(int n=0; n<=5; n++)
C[m][n].origin='N';/*全部赋为空*/
cha.origin = 'N';
/*填充分析表*/
C[0][0]=e;
C[0][3]=e;
C[1][1]=g;
C[1][4]=g1;
C[1][5]=g1;
C[2][0]=t;
C[2][3]=t;
C[3][1]=s1;
C[3][2]=s;
C[3][4]=C[3][5]=s1;
C[4][0]=f1;
C[4][3]=f;

char ch;
do/*读入分析串*/
{
scanf("%c",&ch);
if ((ch!='i') &&(ch!='+') &&(ch!='*')&&(ch!='(')&&(ch!=')')&&(ch!='#'))
{
printf("输入串中有非法字符\n");
break;
}
B[j]=ch;
j++;
}
while(ch!='#');

l=j; /*分析串长度*/
ch=B[0]; /*当前分析字符*/
A[top]='#';
A[++top]='E'; /*'#','E'进栈*/
printf("步骤\t\t分析栈 \t\t剩余字符 \t\t所用产生式 \n");
int k = 1;
int flag = false;
int finish = false;
int n,m;
do
{
char x;
x=A[top--]; /*x为当前栈顶字符*/
printf("%d",k++);
printf("\t\t");
for(j=0; j<=5; j++) /*判断是否为终结符*/
if(x==v1[j])
{
flag=1;
break;
}
if(flag==1)/*如果是终结符*/
{
if(x=='#' && ch == '#')
{
finish=1;/*结束标记*/
print();
print1();
printf("acc!\n");
getchar();;/*接受 */
getchar();
break;
}
if(x==ch)
{
print();
print1();
printf("%c匹配\n",ch);
ch=B[++b];/*下一个输入字符*/
flag=0;/*恢复标记*/
}
else/*出错处理*/
{
print();
print1();
printf("%c出错\n",ch);/*输出出错终结符*/
break;
}
}
else/*非终结符处理*/
{
for(j=0; j<=4; j++)
if(x==v2[j])
{
m=j; /*行号*/
break;
}
for(j=0; j<=5; j++)
if(ch==v1[j])
{
n=j;/*列号*/
break;
}
cha=C[m][n];
if(cha.origin!='N')/*判断是否为空*/
{
print();
print1();
printf("%c->",cha.origin);/*输出产生式*/
for(j=0; j<cha.length; j++)
printf("%c",cha.array[j]);
printf("\n");
for(j=(cha.length-1); j>=0; j--) /*产生式逆序入栈*/
A[++top]=cha.array[j];
if(A[top]=='^')/*为空则不进栈*/
top--;
}
else
{
print();
print1();
printf("%c出错 C表不存在\n",ch);/*输出出错终结符*/
break;
}

}
}
while(true);
return 0;
}

四、 实验结果
输入字符串i+i*i#进行分析，如图2-1所示：

图2-1
输入字符串i)#进行分析，如图2-2所示：

图2-2

实验三 逆波兰式的产生及计算
一、 实验目的
将用中缀式表示的算术表达式转换为用逆波兰式表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值
二、 实验题目
如输入如下：21+（（42-2）*15+6 ）-18#
输出为：
原来表达式： 21+（（42-2）*15+6 ）- 18#
后缀表达式：21&42&2&-15&*6&++18&-
计算结果：609
三、 算法流程图
开始
从左到右扫描中缀表达式
结束
运算分量
error
退栈输出
当前运算符与栈顶运算符比较优先级

N
Y
Y
N
运算符
左括号(
右括号）
栈为空
栈为空
入栈
error
入栈
栈顶为（
退栈
栈为空
栈顶为（
退栈输出
入栈
Y
输出
Y
Y
当前大
N
Y
Y
N
Y
N
N
N
N
Y
N
退栈输出
N
Y

图3-1 生成逆波兰式的程序流程图

读入一个逆波兰算术表达式
Ch=当前输入符号
程序结束

Y

N
Ch是运算符
Ch=‘#’
N

Y

将该字符入栈

根据运算符的特点从栈顶部
取出若干个运算对象进行
该运算，将运算结果入栈

图3-2 计算逆波兰式的程序流程图
四、 程序代码
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char ch;
int top,length,t;
char ex[100];
char str[100];

double calculate()
{
double d;
double stack[100],xx = 0;
top = -1;
for(int t = 0; t < length; )
{
ch = ex[t];
switch(ch)
{
case '+':
stack[top-1]=stack[top-1]+stack[top];
top--;
t++;
break;
case '-':
stack[top-1]=stack[top-1]-stack[top];
top--;
t++;
break;
case '*':
stack[top-1]=stack[top-1]*stack[top];
top--;
t++;
break;
case '/':
if(stack[top]!=0)
stack[top-1]=stack[top-1]/stack[top];
else
{
printf("\n\t除零错误!\n");
break; /*异常退出*/
}
top--;
t++;
break;
case '^':
//stack[top]=stack[top]*stack[top];
xx = stack[top-1];
for(int i = 0; i < stack[top]-1; i++)
{
xx = xx*stack[top-1];
}
stack[top-1] = xx;
top--;
t++;
break;
default :
d=0;
int flag = false;
while(ch == '@' || (ch>='0'&&ch<='9'))
{
if(ch == '@')
{
flag = true;
t++;
ch = ex[t];
continue;
}
d=10*d+ch-'0';
t++;
ch=ex[t];
}
if(ch == '.')
{
double temp = 0;
t++;
ch = ex[t];
int k = 1;