编译原理实验
词
法
分
析
程
序
实验一：词法分析程序
1、实验目的
从左至右逐个字符的对源程序进行扫描，产生一个个单词符号，把字符串形式的源程序改造成单词符号形式的中间程序。
2、实验内容
表C语言子集的单词符号及内码值
单词符号种别编码助记符内码值
while 1 while --
if 2 if --
else 3 else --
switch 4 switch --
case 5 case --
标识符 6 id id在符号表中的位置
常数7 num num在常数表中的位置
+ 8 + --
- 9 - --
* 10 * --
<= 11 relop LE
< 11 relop LT
== 11 relop LQ
= 12 = --
; 13 ; --
输入源程序如下
if a==1 a=a+1;
else a=a+2;
输出对应的单词符号形式的中间程序
3、实验过程
实验上机程序如下：
#include "stdio.h"
#include "string.h"
int i,j,k;
char s ,a[20],token[20];
int letter()
{
if((s>=97)&&(s<=122))return 1;
else return 0;
}
int Digit()
{if((s>=48)&&(s<=57))return 1;
else return 0;
}
void get()
{
s=a[i];
i=i+1;
}
void retract()
{i=i-1;}
int lookup()
{
if(strcmp(token, "while")==0)
return 1;
else if(strcmp(token, "if")==0)
return 2;
else if(strcmp(token,"else")==0)
return 3;
else if(strcmp(token,"switch")==0)
return 4;
else if(strcmp(token,"case")==0)
return 5;
else return 0;
}
void main()
{
printf("please input you source program,end('#'):\n");
i=0;
do
{
i=i+1;
scanf("%c",&a[i]);
}while(a[i]!='#');
i=1;
memset(token,0,sizeof(char)*10);
j=0;
get();
while(s!='#')
{
if(s==' '||s==10||s==13)
get();
else
{
switch(s)
{
case'a':
case'b':
case'c':
case'd':
case'e':
case'f':
case'g':
case'h':
case'i':
case'j':
case'k':
case'l':
case'm':
case'n':
case'o':
case'p':
case'q':
case'r':
case's':
case't':
case'u':
case'v':
case'w':
case'x':
case'y':
case'z':
while(Digit()||letter())
{
token[j]=s;
j=j+1;
get();
}
retract();
k=lookup();
if(k==0)
printf("(6,%s)\n",token); else
printf("(%d,null)\n",k); break;
case'0':
case'1':
case'2':
case'3':
case'4':
case'5':
case'6':
case'7':
case'8':
case'9':
while(Digit())
{
token[j]=s;
j=j+1;
get();
}
retract();
printf("(%d,%s)\n",7,token); break;
case'+':printf("(+,null)\n"); break;
case'-':printf("(-,null)\n"); break;
case'*':printf("(*,null)\n"); break;
case'<':
get();
if(s=='=')
printf("(relop,LE)\n"); else
{
retract();
printf("(relop,LT)\n");
}
break;
case'=':
get();
if(s=='=')
printf("(relop,EQ)\n"); else
{
retract();
printf("(=,null)\n");
}
break;
case';':printf("(;,null)\n"); break;
default:printf("(%c,error)\n",s);
break;
}
memset(token,0,sizeof(char)*10);
j=0;
get();
}
}
}
4、实验结果
实验结果分析：
if是关键字，对应种别编码为2，输出（2，null）
a是标识符，对应种别编码为6，值为a，输出（6，a）==的助记符是relop，内码值为LE，输出（relop，LE）1是常数，对应种别编码为7，值为1，输出（7，1）a是标识符，对应种别编码为6，值为a，输出（6，a）=是赋值符号，直接输出，（=，null）
a是标识符，对应种别编码为6，值为a，输出（6，a）+是运算符，直接输出（=，null）
1是常数，对应种别编码为7，值为1，输出（7，1）；是语句结束符号，直接输出（；，null）
else是关键字，对应种别编码为3，输出（3，null）
a是标识符，对应种别编码为6，值为a，输出（6，a）=是赋值符号，直接输出，（=，null）
a是标识符，对应种别编码为6，值为a，输出（6，a）+是运算符，直接输出（=，null）
2是常数，对应种别编码为7，值为2，输出（7，2）；是语句结束符号，直接输出（；，null）
#是输入结束标志
编译原理实验
语
法
分
析
程
序
实验二：语法分析程序
1、实验目的：
将单词组成各类语法单位，讨论给类语法的形成规则，判断源程序是否符合语法规则3、实验内容：
给定文法：G[E]:E→E+E|E-E|E*E|E/E|(E)
E→0|1|2|3|4|5|6|7|8|9
首先把G[E]构造为算符优先文法，即：
G’[E]:E→E+T|T
T→T-F|F
F→F*G|G
G→G/H|H
H→(E)|i
得到优先关系表如下：
+ - * / i ( ) # + ·><·<·<·<·<··>·> - ·>·><·<·<·<··>·> * ·>·>·><·<·<··>·> / ·>·>·>·><·<··>·>
i ·>·>·>·>·>·>
( <·<·<·<·<·<·=
) ·>·>·>·>·>·> # <·<·<·<·<·<·=
构造出优先函数
+ - * / i ( ) #
f 6 8 10 12 12 2 12 2
g 5 7 9 11 13 13 2 2
要求输入算术表达式：（1+2）*3+2*（1+2）-4/2
输出其对应的语法分析结果
4、实验过程：
上机程序如下：
#include "stdio.h"
#include "string.h"
char a[20],optr[10],s,op;
int i,j,k,opnd[10],x1,x2,x3;
int operand(char s)
{
if((s>=48)&&(s<=57))
return 1;
else return 0;
}
int f(char s)
{
switch(s){
case'+':return 6;
case'-':return 8;
case'*':return 10;
case'/':return 12;
case'(':return 2;
case')':return 12;
case'#':return 2;
default:printf("error");
}
}
int g(char s)
{
switch(s){
case'+':return 5;
case'-':return 7;
case'*':return 9;
case'/':return 11;
case'(':return 13;
case')':return 2;
case'#':return 2;
default:printf("error");
}
}
void get()
{s=a[i];
i=i+1;
}
void main()
{
printf("请输入算数表达式，并以‘#’结束:\n");
i=0;
do
{
scanf("%c",&a[i]);
i++;
}while(a[i-1]!='#');
i=0;
j=0;
k=0;
optr[j]='#';
get();
while((optr[j]!='#')||(s!='#'))
{
if(operand(s))
{
opnd[k]=s-48;
k=k+1;
get();
}
else if(f(optr[j])<g(s))
{
j=j+1;
optr[j]=s;
get();
}
else if(f(optr[j])==g(s))
{
if(optr[j]=='('&&s==')')
{
j=j-1;
get();
}
else if(optr[j]=='('&&s=='#')
{
printf("error\n");
break;
}
else if(optr[j]=='#'&&s==')')
{
printf("error\n");
break;
}
}
else if(f(optr[j])>g(s))
{
op=optr[j];
j=j-1;
x2=opnd[k-1];
x1=opnd[k-2];
k=k-2;
switch(op){
case'+':x3=x1+x2;break;
case'-':x3=x1-x2;break;
case'*':x3=x1*x2;break;
case'/':x3=x1/x2;break;
}
opnd[k]=x3;
k=k+1;
printf("(%c,%d,%d,%d)\n",op,x1,x2,x3);
}
else
{
printf("error\n");
break;
}
}
if(j!=0||k!=1)
printf("error\n");
}
5、实验结果：
实验结果分析：
（1+2）*3+2*（1+2）-4/2#
因为‘）’优先级大于‘*’，先计算1+2=3，并输出（+，1，2，3）原式变为：3*3+2*（1+2）-4/2#
因为‘*’优先级大于‘+’，先计算3*3=9，并输出（*，3，3，9）原式变为：9+2*（1+2）-4/2#
因为‘）’优先级大于‘-’，先计算1+2=3，并输出（+，1，2，3）原式变为：9+2*3-4/2#
因为‘*’优先级大于‘-’，先计算2*3=6，并输出（*，2，3，6）原式变为：9+6-4/2#
因为‘/’优先级大于‘#’，先计算4/2=2，并输出（/，4，2，2）原式变为：9+6-2#
因为‘-’优先级大于‘#’，先计算6-2=4，并输出（-，6，2，4）
原式变为：9+4#
因为‘+’优先级大于‘#’，计算9+4=13，并输出（+，9，4，13）原式变为13
#优先级等于#，跳出while循环，运算结束！。
