【编译原理】程序段的单词识别

报

实 告

实验项目列表

序号 实验项目名称 成绩 01 DFA的生成与字符串的识别 02 程序段的单词识别 03 04 05 06 07 08 09 10 11 12 13 14 15 16 总评成绩： 教员签字：

2

一、 实验名称

程序段的单词识别

二、实验目的

1.掌握根据DFA构造词法分析程序的方法； 2.解决词法分析程序构造的相关问题。

三、实验内容和要求

给定一个小语言SIM，其字符集及单词定义如下： 字符集：<字符集>::<字母>|<数字>|<界符>

<字母>::=A|B|C|…|Z|a|b|c|…|z <数字>::=0|1|2|…|9 <界符>::=+|-|=|:|;|,|’

单词集：<单词集>::=<保留字>|<标识符>|<整数>|<界符>

<保留字>::=var|begin|end|str|integer

<标识符>::=<字母>|<标识符><数字>|<标识符><字母> <整数>::=<数字>|<整数><数字>

<字符串常数>::=’除单引号’外的任意字符集中的字符’ 单词类别可以用整数表示，如下表1：

3

表1单词类别 单词 var begin end str integer 界符 标识符 整数 字符串常数 类别 1 要求： (1)输入输出

输入：SIM语言程序段

输出：SIM语言程序段的单词序列。 (2)具体功能

根据识别SIM程序段的DFA手工编写一个识别SIM语言单词的程序，运行该程序即可识别SIM语言程序段的所有单词。程序的具体功能如下：

1)输入一个SIM语言的程序段

2)对SIM语言程序段进行扫描，根据程序段的字符进行单词的拼写和识别，直到识别出一个单词，给出该单词的二元式。

3)重复2)，依次识别SIM程序段的每个单词，直到程序段扫描完毕，程序结束。

4)数据结构

这个程序中涉及的数据结构只有单词的二元式。

2 3 4 5 6 7 8 9 四、实验环境

1．硬件环境：PC机

2．软件环境：Windows操作系统，VC++集成开发环境

4

五、算法设计思想

六、主要问题与解决方法

七、实验结果

以下是程序的用户运行界面截图：

5

6

7

八、体会、质疑、建议

8

九、源代码

#include #include #include #include #include #include #include #include using namespace std;

typedef struct s//DFA的结构体 { char A; char B;

char C;

}node;

struct token//单词序列的结构体{

9

};

string type; int code;

void gotoxy(int x,int y){//光标转移函数

COORD coord; coord.X=x; coord.Y=y;

SetConsoleCursorPosition( GetStdHandle( STD_OUTPUT_HANDLE ),

coord ); }

char def(char c)//判断读入的单个字符的类型 {

char num[]=\"0123456789\"; char ch[]=

\"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ\"; char sym[]=\"+-=:;,'\";

vector vecnum(num,num+strlen(num));

10

}

vector vecch(ch,ch+strlen(ch)); vector vecsym(sym,sym+strlen(sym));

if(find(vecnum.begin(),vecnum.end(),c)!=vecnum.end()) { }

else if(find(vecch.begin(),vecch.end(),c)!=vecch.end()) { }

else if(find(vecsym.begin(),vecsym.end(),c)!=vecsym.end()) { }

else return 0; return 'k'; return 'c'; return 'd';

void InputDFA(vector &DFA) {

11

int cnt=0; char endget; node t;

cout<<\"请输入DFA,字符间用空格分隔:\\n\"; do { cin>>t.A; cin>>t.B; cin>>t.C; DFA.push_back(t); cnt++;

cout<<\"是否结束输入？(Y/N):\"; cin>>endget; gotoxy(0,cnt+1);

cout<<\"

gotoxy(0,cnt+1);

}while(endget!='Y');

}

void ImplyDFA(vector &DFA)

12

\"; { node t; FILE*dfa_in;

if((dfa_in=fopen(\"dfadata.txt\",\"r\"))==NULL) { cout<<\"文件打开错误！\\n\"; exit(0);

}

while(!feof(dfa_in)) { t.A=fgetc(dfa_in); fgetc(dfa_in); t.B=fgetc(dfa_in); fgetc(dfa_in); t.C=fgetc(dfa_in); fgetc(dfa_in); DFA.push_back(t); }

fclose(dfa_in); }

13

void recognize(const vector &DFA,vector &tch) { token t;

char a; char start;

//打开程序串文件

FILE*in;

if((in=fopen(\"programdemo.txt\",\"r\"))==NULL) { }

start=DFA[0].A;

vector::const_iterator iter=DFA.begin(); while(!feof(in)) {

while(def(a=fgetc(in))) {

for(iter=DFA.begin();iter!=DFA.end();iter++)

14

cout<<\"文件打开错误！\\n\"; exit(0);

{

if(start==(*iter).A&&def(a)==(*iter).B)

//若DFA配对成功，则将单个字符合并到已识别串中，作

为单词的一部分

}

}

{ }

t.type=t.type+a;

start=(*iter).C;//对DFA状态转换 break;

if(iter==DFA.end()) { } break;

if(t.type!=\"\") { }

15

tch.push_back(t);//处理空格和换行符的情况

}

}

if(def(a)=='k') { }

start=DFA[0].A;//恢复开始状态

t.type.erase();//识别完一个单词，识别串存储空间清零 t.type=a; tch.push_back(t);

fclose(in);

void fillcode(vector &tch) {

int sign=0;

vector keyword;//存储语言的关键字 keyword.push_back(\"var\");//写入关键字 keyword.push_back(\"begin\"); keyword.push_back(\"end\"); keyword.push_back(\"str\"); keyword.push_back(\"integer\");

16

for(int jcnt=0;jcntsign=0;

for(int icnt=0;icntif(sign==0) {

if(def(tch[jcnt].type[0])=='d')//对整数进行处理 { }

else if(def(tch[jcnt].type[0])=='c')//对标识符进行处理

17

if(tch[jcnt].type==keyword[icnt]) { }

tch[jcnt].code=icnt+1; sign=1; break;

tch[jcnt].code=8;

}

{ }

else if(def(tch[jcnt].type[0])=='k')//对界符进行处理 { }

tch[jcnt].code=6; tch[jcnt].code=7;

if(jcnt>0&&tch[jcnt-1].type==\"'\"&&tch[jcnt+1].type==\"'\")//对字符串

常量进行处理 }

void write(const vector &tch)

18

}

{ }

tch[jcnt].code=9;

{ }

void main() {

cout<<\"识别得到单词序列如下：\\n\"; vector::const_iterator iter1=tch.begin(); for(;iter1!=tch.end();iter1++) { }

cout<<'('<<(*iter1).type<<','<<(*iter1).code<<')'<int cnt=0,choice=2;

//读入DFA vector DFA;

cout<<\"请选择DFA：\\n1、手动输入 2、系统调用\\n\"<>choice;

system(\"cls\");//清屏操作 if(choice==1)

19

}

{ } else { }

vector tch;

recognize(DFA,tch);//识别单词 fillcode(tch);//填写单词类别值 write(tch);//输出识别到的单词序列

ImplyDFA(DFA);//调用默认的DFA InputDFA(DFA);//输入DFA

20