编译原理

实验一 词法分析程序设计与实现

一、实验目的

加深对词法分析器的工作过程的理解；加强对词法分析方法的掌握；能够采用一种编程语言实现简单的词法分析程序；能够使用自己编写的分析程序对简单的程序段进行词法分析。

 

二、实验内容

自定义一种程序设计语言，或者选择已有的一种高级语言，编制它的词法分析程序。词法分析程序的实现可以采用任何一种编程语言和编程工具。

从输入的源程序中，识别出各个具有独立意义的单词，即关键字、标识符、常数、运算符、界符。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）

 

三、实验要求：

1. 对单词的构词规则有明确的定义；

2. 编写的分析程序能够正确识别源程序中的单词符号；

3. 识别出的单词以<种别码，值>的形式保存在符号表中，正确设计和维护符号表；

4. 对于源程序中的词法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成整个源程序的词法分析；

 

四、实验步骤

1. 定义目标语言的可用符号表和构词规则；

2. 依次读入源程序符号，对源程序进行单词切分和识别，直到源程序结束；

3. 对正确的单词，按照它的种别以<种别码，值>的形式保存在符号表中；

4. 对不正确的单词，做出错误处理。

 

五、实验报告要求

详细说明你的程序的设计思路和实现过程。用有限自动机或者文法的形式对词法定义做出详细说明，说明词法分析程序的工作过程，说明错误处理的实现。

参考资料

一、程序要求

1、以下面一段程序为例

main()

{

int a,b;

a = 10;

b = a + 20;

}

2、需要识别的词

1. 关键字：if、int、for、while、do、return、break、continue；单词种别码为1。

2. 标识符；单词种别码为2。

3. 常数为无符号整形数；单词种别码为3。

4. 运算符包括：+、-、*、/、=、 、<、 =、<=、!= ；单词种别码为4。

5. 分隔符包括：,、;、{、}、(、)； 单词种别码为5。

3、程序输出形式

要求输出下面的形式：

（2，”main”）

（5，”（“）

（5，”）“）

（5，”{“）

（1，”int”）

（2，”a”）

（5，”,”）

（2，”b”）

（5，”;”）

（2，”a”）

（4，”=”）

（3，”10”）

（5，”;”）

（2，”b”）

（4，”=”）

（2，”a”）

（4，”+”）

（3，”20”）

（5，”;”）

（5，”}“）

 

二、模块结构

 

 

三、程序设计思路

这里以开始定义的C语言子集的源程序作为词法分析程序的输入数据。在词法分析中，自文件头开始扫描源程序字符，一旦发现符合“单词”定义的源程序字符串时，将它翻译成固定长度的单词内部表示，并查、填适当的信息表。经过词法分析后，源程序字符串（源程序的外部表示）被翻译成具有等长信息的单词串（源程序的内部表示），并产生两个表格：常数表和标识符表，它们分别包含了源程序中的所有常数和所有标识符。

1. 定义部分：定义常量、变量、数据结构。

2. 初始化：从文件将源程序全部输入到字符缓冲区中。

3. 取单词前：去掉多余空白。

4. 取单词：利用实验一的成果读出单词的每一个字符，组成单词，分析类型。

5. 显示结果。

 

 

词法分析代码

#include <iostream>

#include <string>

#include <cctype>

using namespace std;

//词法分析

void main()

{

stringstr;

getline(cin,str);

if(str.find("main")!=string::npos)

{

cout<<"(2,"<<"main"<<")"<<'\n';

while(1)

{

string sub_str="main";

int index = 0;

index = str.find(sub_str,index);

if (index!=-1)

{

str.erase(index,sub_str.length());

}

else break;

}

}

stringstr1[9]={"void","if","int","for","while","do","return","break","continue"};

for(int j=0;j<9;j++)

{

if(str.find(str1[j])!=string::npos)

{

cout<<"(1,"<<str1[j]<<")"<<'\n';

}

while(1)

{

string sub_str=str1[j];

int index = 0;

index = str.find(sub_str,index);

if (index!=-1)

{

str.erase(index,sub_str.length());

}

else

break;

}

}

stringstr2[10]={"+","-","*","/",">","<","=",">=","<=","!="};

for(int j=0;j<10;j++)

{

if(str.find(str2[j])!=string::npos)

{

cout<<"(4,"<<str2[j]<<")"<<'\n';

}

while(1)

{

string sub_str=str2[j];

int index = 0;

index = str.find(sub_str,index);

if (index!=-1)

{

str.erase(index,sub_str.length());

}

else

break;

}

}

stringstr3[6]={",",";","{","}","(",")"};

for(int j=0;j<6;j++)

{

if(str.find(str3[j])!=string::npos)

{

cout<<"(5,"<<str3[j]<<")"<<'\n';

}

while(1)

{

string sub_str=str3[j];

int index = 0;

index = str.find(sub_str,index);

if (index!=-1)

{

str.erase(index,sub_str.length());

}

else

break;

}

}

 

for(int i=str.length();i>=0;i--)

{

if(isdigit(str[i])&&isalpha(str[i+1]))

{

cout<<str[i]<<"处出现错误！"<<'\n';

break;

//exit(0);

}

elseif (isalpha(str[i]))

{

cout<<"(2,"<<str[i]<<")"<<'\n';

}

elseif (isdigit(str[i]))

{

cout<<"(3,"<<str[i]<<")"<<'\n';

}

}

system("pause");

}

不存在错误的运行结果

 

 

 

 

 

 

存在错误的运行结果

int 33c处后面指出

 

 

四、总结：

词法分析的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。通过本试验的完成，更加加深了对词法分析原理的理解。

 

第二部分 语法分析（任选其中一个做实验）

实验三 算符优先分析法设计与实现

一、实验目的

加深对语法分析器工作过程的理解；加强对算符优先分析法实现语法分析程序的掌握；能够采用一种编程语言实现简单的语法分析程序；能够使用自己编写的分析程序对简单的程序段进行语法翻译。

 

二、实验内容

在实验1的基础上，用算符优先分析法编制语法分析程序，语法分析程序的实现可以采用任何一种编程语言和工具。

 

三、实验要求：

1. 对语法规则有明确的定义；

2. 编写的分析程序能够对实验一的结果进行正确的语法分析；

3. 对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程；

 

四、实验步骤

1. 定义目标语言的语法规则；

2. 求解预测分析方法需要的符号集和分析表；

3. 依次读入实验一的分析结果，根据预测分析的方法进行语法分析，直到源程序结束；

4. 对遇到的语法错误做出错误处理。

 

五、实验报告要求

详细说明你的程序的设计思路和实现过程。实验报告要求用文法的形式对语法定义做出详细说明，说明语法分析程序的工作过程，说明错误处理的实现。

 

 

 

 

语法分析代码：

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<stdlib.h>

using namespace std;

struct

{

char result[12];

char ag1[12];

char op[12];

char ag2[12];

}quad;

 

char prog[80],token[12];

char ch;

int syn,p,m=0,n,sum=0,kk; //p是缓冲区prog的指针，m是token的指针

char *rwtab[6]={"begin","if","then","while","do","end"};

void scaner();

char *factor(void);

char *term(void);

char *expression(void);

int yucu();

void emit(char *result,char *ag1,char *op,char *ag2);

char *newtemp();

int statement();

int k=0;

 

void emit(char *result,char *ag1,char *op,char *ag2)

{

strcpy(quad.result,result);

strcpy(quad.ag1,ag1);

strcpy(quad.op,op);

strcpy(quad.ag2,ag2);

cout<<quad.result<<"="<<quad.ag1<<quad.op<<quad.ag2<<endl;

}

 

char *newtemp()

{

char *p;

char m[12];

p=(char *)malloc(12);

k++;

itoa(k,m,10);

strcpy(p+1,m);

p[0]='t';

return (p);

}

 

void scaner()

{

for(n=0;n<8;n++)

token[n]=NULL;

ch=prog[p++];

while(ch==' ')

{

ch=prog[p];

p++;

}

if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))

{

m=0;

while((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))

{

token[m++]=ch;

ch=prog[p++];

}

token[m++]='\0';

p--;

syn=10;

for(n=0;n<6;n++)

if(strcmp(token,rwtab[n])==0)

{

syn=n+1;

break;

}

}

else if((ch>='0'&&ch<='9'))

{

sum=0;

while((ch>='0'&&ch<='9'))

{

sum=sum*10+ch-'0';

ch=prog[p++];

}

p--;

syn=11;

if(sum>32767)

syn=-1;

}

else switch(ch)

{

case'<':m=0;token[m++]=ch;

ch=prog[p++];

if(ch=='>')

{

syn=21;

token[m++]=ch;

}

else if(ch=='=')

{

syn=22;

token[m++]=ch;

}

else

{

syn=23;

p--;

}

break;

case'>':m=0;token[m++]=ch;

ch=prog[p++];

if(ch=='=')

{

syn=24;

token[m++]=ch;

}

else

{

syn=20;

p--;

}

break;

case':':m=0;token[m++]=ch;

ch=prog[p++];

if(ch=='=')

{

syn=18;

token[m++]=ch;

}

else

{

syn=17;

p--;

}

break;

case'*':syn=13;token[0]=ch;break;

case'/':syn=14;token[0]=ch;break;

case'+':syn=15;token[0]=ch;break;

case'-':syn=16;token[0]=ch;break;

case'=':syn=25;token[0]=ch;break;

case';':syn=26;token[0]=ch;break;

case'(':syn=27;token[0]=ch;break;

case')':syn=28;token[0]=ch;break;

case'#':syn=0;token[0]=ch;break;

default: syn=-1;break;

}

}

int lrparser()

{//cout<<"调用lrparser"<<endl;

int schain=0;

kk=0;

if(syn==1)

{

scaner();

schain=yucu();

if(syn==6)

{

scaner();

if(syn==0 && (kk==0))

cout<<"success!"<<endl;

}

else

{

if(kk!=1)

cout<<"缺end!"<<endl;

kk=1;

}

}

else

{

cout<<"缺begin!"<<endl;

kk=1;

}

return(schain);

}

int yucu()

{// cout<<"调用yucu"<<endl;

int schain=0;

schain=statement();

while(syn==26)

{

scaner();

schain=statement();

}

return(schain);

}

 

int statement()

{//cout<<"调用statement"<<endl;

char *eplace,*tt;

eplace=(char*)malloc(12);

tt=(char*)malloc(12);

int schain=0;

switch(syn)

{

case 10:

strcpy(tt,token);

scaner();

if(syn==18)

{

scaner();

strcpy(eplace,expression());

emit(tt,eplace,"","");

schain=0;

}

else

{

cout<<"缺少赋值符!"<<endl;

kk=1;

}

return(schain);

break;

}

return(schain);

}

 

char *expression(void)

{

char *tp,*ep2,*eplace,*tt;

tp=(char *)malloc(12);

ep2=(char *)malloc(12);

eplace=(char *)malloc(12);

tt =(char *)malloc(12);

strcpy(eplace,term ()); //调用term分析产生表达式计算的第一项eplace

 

while((syn==15)||(syn==16))

{

if(syn==15)strcpy(tt,"+");

else strcpy(tt,"-");

scaner();

strcpy(ep2,term()); //调用term分析产生表达式计算的第二项ep2

strcpy(tp,newtemp()); //调用newtemp产生临时变量tp存储计算结果

emit(tp,eplace,tt,ep2); //生成四元式送入四元式表

strcpy(eplace,tp);

}

return(eplace);

}

 

char *term(void)

{// cout<<"调用term"<<endl;

char *tp,*ep2,*eplace,*tt;

tp=(char *)malloc(12);

ep2=(char *)malloc(12);

eplace=(char *)malloc(12);

tt=(char *)malloc(12);

strcpy(eplace,factor());

 

while((syn==13)||(syn==14))

{

if(syn==13)strcpy(tt,"*");

else strcpy(tt,"/");

scaner();

strcpy(ep2,factor()); //调用factor分析产生表达式计算的第二项ep2

strcpy(tp,newtemp()); //调用newtemp产生临时变量tp存储计算结果

emit(tp,eplace,tt,ep2); //生成四元式送入四元式表

strcpy(eplace,tp);

}

return(eplace);

}

 

char *factor(void)

{

char *fplace;

fplace=(char *)malloc(12);

strcpy(fplace,"");

if(syn==10)

{

strcpy(fplace,token); //将标识符token的值赋给fplace

scaner();

}

else if(syn==11)

{

itoa(sum,fplace,10);

scaner(); }

else if(syn==27)

{

scaner();

fplace=expression(); //调用expression分析返回表达式的值

if(syn==28)

scaner();

else

{

cout<<"缺)错误!"<<endl;

kk=1;

}

}

else

{

cout<<"缺(错误!"<<endl;

kk=1;

}

return(fplace);

}

 

void main()

{

p=0;

cout<<"**********语义分析程序**********"<<endl;

cout<<"Pleaseinput string:"<<endl;

do

{

cin.get(ch);

prog[p++]=ch;

}

while(ch!='#');

p=0;

scaner();

lrparser();

system("pause");

}

运行结果

1.输入：begin a:=2+3*4;x:=(a+b)/c end#

输出：

 

2.输入：begina:=9; x:=2*3-1; b:=(a+x)/2end#

输出：

 

 

3.输入：a:=9;x:=2*3-1; #

输出：

 

4.输入：begina:=9; x:=2*3-1; b:=(a+x/2end#

输出：

 

 

5.输入：begina=9; x:=2*3-1; b:=(a+x/2end#

输出：

 

六、试验总结

通过此次实验，让我了解到如何设计、编制并调试语义分析程序，加深了对语法制导翻译原理的理解，掌握了将语法分析所识别的语法成分变换为中间代码的语义翻译方法。