词法分析算符优先分析课程设计.doc

南华大学
计算机科学与技术学院
课程设计

课程名称：编译原理
题 目：词法分析和算符优先分析
班 级：01班
学 号：20104030113
姓 名：段检妹

2012年5月24日

设计一：词法分析器

1. 课程设计目的和要求 1
1.1实验目的 1
1.2实验要求 1
2.设计描述 2
3.函数模块 3
5.测试样例与测试结果 6
6. 结论 7

设计二： 算符优先语法分析
1.课程设计的目的和要求 8
1.1 课程设计的目的 8
1.2 课程设计的要求 8
2.设计描述 8
2.1 自底向上分析方法的描述： 8
2.2算符优先文法的描述： 9
3. 概要设计和详细设计 10
4.1功能结构 10
4.2模块的划分 10
5.源代码 11
5.测试样例与测试结果 21
6. 结论 22

设计一：词法分析器

1. 课程设计目的和要求
1.1实验目的
通过完成词法分析程序，了解词法分析的过程。编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。
1.2实验要求
通过词法分析器能够实现以下五种类型如单词等的识别。
(1)关键字"begin","end","if","then","else","while","write","read"等,
"do", "call","const","char","until","procedure","repeat"等
(2)运算符："+","-","*","/","="等
(3)界符："{","}","[","]",";",",",".","(",")",":"等
(4)标识符
(5)常量
2.设计描述
词法分析：逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。词法分析是编译过程中的一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。
表1 各种单词符号对应类型表
单词符号
类型编码
助记符
标识符
1
$SYMNOL
常量
2
$CNSTANT
int
3
$INT
if
4
$IF
else
5
$ELSE
while
6
$WHILE
for
7
$FOR
read
8
$READ
write
9
$WRITE
+
10
$ADD
-
11
$SUB
*
12
$MUL
/
13
$DIV
<
14
$L
<=
15
$LE
>
16
$G
>=
17
$GE
!=
18
$NE
==
19
$E
=
20
$ASSIGN
(
21
$LPAR
)
22
$RPAR
,
23
$COM
;
24
$SEM

3.函数模块
1. LexAnalyz()函数
实现整个分析的过程
2.main主函数：
主要实验将输入的字符串存进token中，和组织其他函数已完成功能。
3. print()函数
将识别的结果打印出来。
4.设计源码
#include
#include
#include
#include
using namespace std;
const char*reserchar[7]={"int", "if", "else", "while", "for", "read", "write" }; //关键字
const char*rememchar[25]={"","$SYMBOL", "$CNSTANT", "$INT", "$IF", "$ELSE", "$WHILE", "$FOR", "$READ", "$WRITE", "$ADD", "$SUB", "$MUL", "$DIV", "$L", "$LE", "$G", "$GE", "$NE", "$E", "$ASSIGN", "$LPAR", "$RPAR", "$COM", "$SEM" }; //助记符
void LexAnalyz();
void Print();
char prog[100];
char token[10];
int syn,p;
char ch;
int main()
{
char sym;
Print();
p=0;
do {
ch=getchar();
prog[p++]=ch;
}while( ch!='#' );
p=0;
do{
LexAnalyz();
if( syn==-1 )
printf("error\n");
else if( syn!=0 ){

printf("%s %d %s\n", token, syn, rememchar[syn]);
}
// system("pause") ;
}while( syn!=0 );
system("pause");
return 0;
}

void LexAnalyz()
{
int j=0,i=0;
syn=0;
for( i=0; i<10; i++)
token[i]='\0';
ch=prog[p++];
while( ch ==' ' )
ch= prog[p++];

if(isalpha( ch )){
while(isalpha( ch ) || isdigit( ch )){
token[j++] = ch;
ch= prog[p++] ;
}
ch=prog[p--];
syn=1;
for( i=0; i<7; i++ )
if( strcmp( token, reserchar[i])==0 ){
syn=i+3;
break;
}
}

else if( isdigit( ch ) ){
while( isdigit( ch ) ){
token[j++] = ch;
ch = prog[p++];
}
ch= prog[p--];
syn=2;
}

else{
switch( ch ){

case '<': token[j++] = ch; ch = prog[p++];
if( ch == '=' ){
token[j++] = ch;
syn=15; }
else{
syn=14;
ch= prog[p--];
}
break;

case '>': token[j++] = ch; ch = prog[p++];
if( ch == '=' ){
token[j++] = ch;
syn=17; }
else{
syn=16;
ch= prog[p--];}
break;

case '!': token[j++] = ch; ch = prog[p++];
if(ch == '='){
token[j++] = ch;
syn=18; }
else
ch= prog[p--];
break;

case '=': token[j++] = ch; ch = prog[p++];
if( ch == '=' ){
token[j++] = ch;
syn=19; }
else{
ch= prog[p-];
syn=20;
}
break;

case '+': token[j++]=ch; syn=10; break;
case '-': token[j++]=ch; syn=11; break;
case '*': token[j++]=ch; syn=12; break;
case '/': token[j++]=ch; syn=13; break;
case '(': token[j++]=ch; syn=21; break;
case ')': token[j++]=ch; syn=22; break;
case ',': token[j++]=ch; syn=23; break;
case ';': token[j++]=ch; syn=24; break;
case '#': syn=0; break;
default: syn=-1;
}
}
}

void Print()
{
for(int i=0; i<=25 i++ )
printf("*");
printf("\n");

for(int i=0; i<=8; i++ )
printf(" ");
printf("词法分析器\n");

for(int i=0; i<=25; i++ )
printf("*");
printf("\n");
printf("输入一串句子以#+enter键结束：\n");
}

5.测试样例与测试结果
输入的是字符串；识别出的是单词，且输出单词的类别编码和助记符。

6. 结论
通过本次课程设计的练习，熟悉了用C++语言编写词法分析器的过程，掌握了词法分析器的原理以及功能。词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。词法分析程序的主要任务：读源程序，产生单词符号。
词法分析程序的其他任务：滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序，宏展开，等等等等。
词法分析工作从语法分析工作独立出来的原因：简化设计，改进编译效率，增加编译系统的可移植性 。
而且从划分关键字，运算符，界符，标识符和常量，才发现数字，字母及符号组合有很多很多，无法全部枚举，所以在新建的文本文档中只象征性的列出几种符号，但这并不影响此法分析结果的完成。
总之，通过本次实验，一点点分析词法分析器的功能，并努力实现它，掌握了课程设计内容的同时也锻炼了自己分析解决问题的能力以及编程能力，收获颇丰！

设计二： 算符优先语法分析
1.课程设计的目的和要求
1.1 课程设计的目的
本次设计的时间为一个月，目的是件通过使用高级语言实现部分加强对编译技术和理论的理解。设计的题目要求具有一定的规模，应蕴含本课程内容和世纪应用相关的主要技术。
1.2 课程设计的要求
1. 文法使用产生式来定义；
2. 用大写字母和小写字母分别表示非终结符和终结符；产生式使用->；
3. 文法中的空字符串统一使用@表示；
4. 分别给出每一个终结符的FIRSTVT 集和LASTVT集；
5. 版定给定的文法是否是算符优先文法；
6. 画出算符优先关系表；、
7. 给定富豪穿是否是文法中的句子，分析过程用分析表格的方式打印出来。
2.设计描述
本次实验使用windows vista操作系统下visiual c++6.0平台，使用c语言，利用读文件方式将待分析的文法读入到程序中，通过定义数组和结构体作为具有一定意义或关系的表或栈，存放FIRSTVT 、LASTVT、算符有限关系表的元素。
系统能够对由文件读入的文法进行分析，构造出FIRSTVT LASTVT表以及算符优先关系表。可以根据构造的有限关系表对输入的任意字符串进行分析，判断是否为本文法的句子，若是则打印归约过程。结果显示到DOS界面上。
2.1 自底向上分析方法的描述：
对输入的字符串自左向右进行扫描，并将输入字符逐个移入栈中，边移入边分析，一旦栈顶富豪穿形成摸个矩形的句柄时（该句柄对应某个产生式的右部），就用该产生式的非终结符代替邮编的文法字符串，这一过程成为归约。重复这一过程，知道栈中只剩下文法的开始负责分析成功。
2.2算符优先文法的描述：
之规定酸腐之间的优先关系，也就是说只考虑终结符之间的有限关系。由于算符优先分析不考虑终结符之间的优先关系，在归约过程中只要找到最左素短语就可以规约了。
如给定一个文法G[S]：
S->#E#
E->E+T
E->T
T->T*F
T->F
F->(E)
F->i
利用算符优先文法分析过程处理如下：
1. 计算给定文法中任意两个终结符对（a,b）之间的优先关系，首先计算两个几何
FIRSTVT(B)={b|B->b.......或B->Cb.......}
LASTVT(B)={a|B->....a或B->.......aC}

2.构造firstvt和lastvt集
下表是FIRSTVT集和LASTVT集

根据firstvt 和lastvt集构造算符优先关系表
下表是算符优先关系表

3.进行移进和归约
3. 概要设计和详细设计
4.1功能结构

4.2模块的划分
1. 文件的导入：
int ReadFile(char exp[][col]);
文法以文件的形式输入而且保存在二维数组中。
2. Firstvt和Lastvt集的构造：
void FirstVT(char exp[][col],char firstvt[][col],const int&exp_len,const int&first_len);
//构造firstvt集
void LastVT(char exp[][col],char lastvt[][col],const int&exp_len,const int&first_len);
//构造lastvt集
3. 算符优先关系表的构造：
bool OperPriTable(char exp[][col],char opertable[][col],char firstvt[][col],char lastvt[][col],int exp_len,int first_len,int&oper_len);
//构造算符优先表如果不是算符优先文法则返回false。
4. 归约的过程：
bool GuiYue(char input[],char opertable[][col],char exp[][col],int oper_len,int exp_len);
//在其他的小函数的帮助下归约
5. 主函数
Main函数,将模块组合，完成整个设计的功能。

5.源代码
#include
#include
#include
#define col 50
#define row 50
using namespace std;
struct Element
{
char nont; //非终结符
char ternal; //终结符
};
void Init(char exp[][col],char firstvt[][col],char lastvt[][col],int&exp_len,int&first_len);
//first和lastvt的非终结符
bool FindRecord(Element record[],Element &a, int &r);
//在构造first集时，判断是否已经添加了A->a
bool TerminalJug(char ch); //判断是否是终结符
void FirstVT(char exp[][col],char firstvt[][col],const int&exp_len,const int&first_len); //构造firstvt集
void LastVT(char exp[][col],char lastvt[][col],const int&exp_len,const int&first_len); //构造lastvt集
int ReadFile(char exp[][col]); //文法以文件的形式输入
bool InsertTable(char opertable[][col],int&i,int&j,char oper);
int FindItem( char firstvt[][col],int first_len,char ch);
//判断此终结符是否在firsrvt集 0列中
int FindPosition(char term[],const char&c1,const int&term_len) ;
bool OperPriTable(char exp[][col],char opertable[][col],char firstvt[][col],char lastvt[][col],int exp_len,int first_len,int&oper_len); //构造算符优先表
void Print(char array[][col],int r); //输出查看
bool GuiYue(char input[],char opertable[][col],char exp[][col],int oper_len,int exp_len); //归约函数
char Match(char sk[],int s,int e,char exp[][col],int&exp_len);
//在产生式中查找匹配式子并返回规约后的非终结符

int main()
{
char firstvt[row][col]={'\0'},lastvt[row][col]={'\0'};
char exp[row][col]={'\0'},opertable[row][col]={'\0'};
int first_len,exp_len,oper_len;
exp_len=ReadFile(exp);
Init(exp,firstvt,lastvt,exp_len,first_len);

FirstVT(exp,firstvt,exp_len,first_len);
cout<<"\n\t文法中非终结符的firstvt集： "<st_len);

if( OperPriTable(exp,opertable,firstvt,lastvt,exp_len,first_len,oper_len) ){
cout<<"\n\t算符优先分析表： "<\0'};
cout<<"输入要分析的串 （以#+enter键结束）："<>input;

cout<<"\t\t分析过程描述 "<的句子"< expstack;
Element temp;
Element record[col];

recor_len=0;
for( i=0; ia入栈
for( int j=3; exp[i][j]!='\0'; j++){
if( TerminalJug( exp[i][j] ) ){ //判断是否是终结符
temp.nont=exp[i][0];
temp.ternal=exp[i][j];

if( recor_len==0 || !FindRecord(record,temp, recor_len) ){ //没记录就添加到记录
expstack.push(temp);
record[recor_len].nont=temp.nont;
record[recor_len].ternal=temp.ternal;
recor_len++;
}
break;
}
}
}
Element DL,DE;
int location[col]; //用来记录firstvt集中每行的长度
for( i=0; iexpstack.top();
// cout<"<
firstvt[i][len]=DE.ternal;
location[i]++;
break;
}
}

for( i=0; iB
if( exp[i][3]==DE.nont ){
DL.nont=exp[i][0];
DL.ternal=DE.ternal;
if( !FindRecord(record, DL, recor_len) ){//没记录就添加到记录
expstack.push(DL);
record[recor_len].nont=DL.nont;
record[recor_len].ternal=DL.ternal;
recor_len++;
}
}
}
}

}

void LastVT(char exp[][col],char lastvt[][col],const int&exp_len,const int&first_len) //构造lastvt集
{
int i,j,k;
char ch;
char temp[row][col]={'\0'};
for( i=0; i
}
}
FirstVT(temp,lastvt,exp_len,first_len);
}

void Init(char exp[][col],char firstvt[][col],char lastvt[][col],int&exp_len,int&first_len)
//first和lastvt的非终结符
{
first_len=0;
for( int i=0; iItem(firstvt,first_len,exp[i][0]) == -1 ){
firstvt[first_len][0]=exp[i][0];
lastvt[first_len][0]=exp[i][0];
first_len++;
}
}
}

int ReadFile(char exp[][col]) //文法以文件的形式输入
{
ifstream fin;
int i;
char address[30]
cout<<"输入文件的路径："<>address;
cout<