词法分析器
- 格式:doc
- 大小:416.00 KB
- 文档页数:11
《编译原理》课程实验报告
课程实验题目:词法分析器
学院:计算机科学与技术班级:软件1503
学号:04153094
姓名:刘欣
指导教师姓名:陈燕
完成时间:
词法分析
定义:
词法分析器的功能输入源程序,按照构词规则分解成一系列单词符号。
单词是语言中具有独立意义的最小单位,包括关键字、标识符、运算符、界符和常量等
(1) 关键字是由程序语言定义的具有固定意义的标识符。
例如,Pascal 中的begin,end,if,while都是保留字。
这些字通常不用作一般标识符。
(2) 标识符用来表示各种名字,如变量名,数组名,过程名等等。
(3) 常数常数的类型一般有整型、实型、布尔型、文字型等。
(4) 运算符如+、-、*、/等等。
(5) 界符如逗号、分号、括号、等等。
输出:
词法分析器所输出单词符号常常表示成如下的二元式:
(单词种别,单词符号的属性值)
单词种别通常用整数编码。
标识符一般统归为一种。
常数则宜按类型(整、实、布尔等)分种。
关键字可将其全体视为一种。
运算符可采用一符一种的方法。
界符一般用一符一种的方法。
对于每个单词符号,除了给出了种别编码之外,还应给出有关单词符号的属性信息。
单词符号的属性是指单词符号的特性或特征。
示例:
比如如下的代码段:
while(i>=j) i--
经词法分析器处理后,它将被转为如下的单词符号序列:
<while, _>
<(, _>
<id, 指向i的符号表项的指针>
<>=, _>
<id, 指向j的符号表项的指针>
<), _>
<id, 指向i的符号表项的指针>
<--, _>
<;, _>
词法分析分析器作为一个独立子程序
词法分析是编译过程中的一个阶段,在语法分析前进行。
词法分析作为一遍,可以简化设计,改进编译效率,增加编译系统的可移植性。
也可以和语法分析结合在一起作为一遍,由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。
词法分析器设计
输入、预处理
词法分析器工作的第一步是输入源程序文本。
在许多情况下,为了更好地对单词符号识别,把输入串预处理一下。
预处理主要滤掉空格,跳过注释、换行符等。
超前搜索
词法分析过程中,有时为了确定词性,需超前扫描若干个字符。
对于FORTRAN 语言,关键字不作为保留字,可作为标识符使用,空格符号没有任何意义。
为了确定词性,需超前扫描若干个字符。
在FORTRAN中
1 DO99K=1,10
2 IF(5.EQ.M) I=10
3 DO99K=1.10
4 IF(5)=55
这四个语句都是正确的语句。
语句1和2 分别是DO和IF语句,语句3和4是赋值语句。
为了正确区别1和3,2和4语句,需超前扫描若干个字符。
1 DO99K=1,10
2 IF(5.EQ.M) I=10
3 DO99K=1.10
4 IF(5)=55
语句1和3的区别在于符号之后的第一个界符:一个为逗号,另一个为句末符。
语句2和4的主要区别在于右括号后的第一个字符:一个为字母,另一个为等号。
为了识别1、2中的关键字,必须超前扫描多个字符。
超前到能够肯定词性的地方为止。
为了区别1和3,必须超前扫描到等号后的第一个界符处。
对于语句2、4来说,必须超前扫描到与IF后的左括号相对应的那个右括号之后的第一个字符为止。
状态转换图
词法分析器使用状态转换图来识别单词符号。
状态转换图是一张有限方向图。
在状态转换图中,有一个初态,至少一个终态。
其中0为初态,2为终态。
这个转换图识别(接受)标识符的过程是:从初态0开始,若在状态0之下输入字符是一个字母,则读进它,并转入状态1。
在状态1之下,若下一个输入字符为字母或数字,则读进它,并重新进入状态1。
一直重复这个过程直到状态1发现输入字符不再是字母或数字时(这个字符也已被读进)就进入状态2。
状态2是终态,它意味着到此已识别出一个标识符,识别过程宣告终止。
终态结上打个星号意味着多读进了一个不属于标识符部分的字符,应把它退还给输入口中。
如果在状态0时输入字符不为“字母”,则意味着识别不出标识符,或者说,这个转换图工作不成功。
正规表达式与正规集
正规表达式是说明单词的一种重要的表示法(记号),是定义正规集的工具。
在词法分析中,正规表达式用来描述标示符可能具有的形式。
定义(正规式和它所表示的正规集):
设字母表为S,
1. e和Ø都是S上的正规式,它们所表示的正规集分别为{e}和{ };
2. 任何aÎ S,a是S上的一个正规式,它所表示的正规集为{a};
3. 假定U和V都是S上的正规式,它们所表示的正规集分别为L(U)和L(V),那么,(U), U|V, U·V, U*也都是正规式,它们所表示的正规集分别为L(U), L(U)ÈL(V), L(U)L(V)和(L(U))*;
4. 仅由有限次使用上述三步骤而定义的表达式才是S上的正规式,仅由这些正规式所表示的字集才是S上的正规集。
正规式的运算符的“½”读为“或” ,“· ”读为“连接”;“*”读为“闭包”(即,任意有限次的自重复连接)。
在不致混淆时,括号可省去,但规定算符的优先顺序为“(”、“)”、“*”、“· ”、“½” 。
连接符“· ”一般可省略不写。
“*”、“· ”和“½” 都是左结合的。
例令S={a,b},S上的正规式和相应的正规集的例子有:
正规式正规集
a {a}
a½b {a,b}
ab {ab}
(a½b)(a {aa,ab,ba,bb}
a * {e ,a,a, ……任意个a的串}
ba* {b, ba, baa, baaa, …}
(a½b)* {e ,a,b,aa,ab ……所有由a和b
组成的串}
(a½b)*(aa½bb)(a½b)* {S*上所有含有两个相继的a
或两个相继的b组成的串}
定理:若两个正规式U和V所表示的正规集相同,则说U和V等价,写作U=V。
证明b(ab)*=( ba)*b
证明:因为L(b(ab)*)={b}{e, ab, abab, ababab, …}
={b, bab, babab, bababab, …}
L((ba)*b) ={e, ba, baba, bababa, …}{b}
={b, bab, babab, bababab, …}
= L(b(ab)*)
所以, b(ab)*=( ba)*b
设U,V,W为正规式,正规式服从的代数规律有:
(1) U½V=V½U (交换律)
(2) U½(V½W)=(U½V)½W (结合律)
(3) U(VW)=(UV)W (结合律)
(4) U(V½W)=UV½UW (V½W)U=VU½WU (分配律)
(5) eU=U e=U
分析器的简单实现
上文主要介绍了词法分析的一些相关的知识,而对词法分析器的具体实现还没有具体提到,为了能更好的理解词法分析,我写了一个简单的词法分析器。
虽然说是语法分析器,但实现的功能很简单,只是对输入的程序把注释去掉,其中用到了上面关于状态转换图部分的知识。
分析:
一般的程序设计语言,注释部分的形式为;
/* 注释部分、、、、*/
我们的程序总是顺序的一个一个字符读取输入文件的。
我们的目的是把注释部分去掉,那么对于输入的字符流,我们只要识别出“/*”就知道后面的部分是注释部分,直到识别输入流中出现"*/"为止。
对字符流的处理是一个一个进行的,每读入一个字符,就判断,如果字符是“/”,就说明后面的部分可能是注释,再看下一个输入字符,如果是“*”, 就是上面所说的情况:“ /*”那么后面的部分就是注释部分,然后再用相同的方法找出"*/"就可以了。
这个识别的过程就可以用状态转换图来清晰的表示:
对于读入的每个符号都要进行判断,如果是“/”说明后面的部分有可能是注释,进入状态1。
如果后面的输入是“*”那么就可以确定以后的内容为注释内容,如果后面的输入不是"*",说明后面的内容不是注释,前面出现的"/"可能是做除号使用,如“5/3”
其实上面的流程图也就对应了程序实现的逻辑,可以用switch-case 来实现,对于每个输入,判断后跳转到相应的状态,然后继续判断。
下面是程序伪代码:
while((ch=getchar())!=EOF)
switch(state)
case 1 :if ch=="/",state=2,break;
case 2: if ch=="*",state=3
else state=1;break;
case 3:..........
case 4:..........
词法分析器
这个程序比较简单,就不给出源代码了。
接下来是一个简单的词法分析器的代码,可以实现对关键字(如while end if 等),对数字的识别,去掉空格符等。
下面是这个分析器的功能:
1、待分析的简单语言的词法
(1)关键字:
begin if then while do end
所有关键字都是小写。
(2)运算符和界符:
:= + –* / < <= <> > >= = ; ( ) #
(3)其他单词是标识符(ID)和整型常数(NUM),通过以下正规式定义:
ID=letter(letter| digit)*
NUM=digit digit *
(4)空格由空白、制表符和换行符组成。
空格一般用来分隔ID、NUM,运算符、界符和关键字,词法分析阶段通常被忽略。
2、各种单词符号对应的种别码
词法分析程序的功能
输入:所给文法的源程序字符串。
输出:二元组(syn,token或sum)构成的序列。
其中:syn为单词种别码;
token为存放的单词自身字符串;
sum为整型常数。
运行结果:
源代码:
#include<stdio.h>
#include<string.h>
#include<iostream.h>
char prog[80],token[8];
char ch;
int syn,p,m=0,n,row,sum=0;
char *rwtab[6]={"begin","if","then","while","do","end"};
void scaner()
{
/*
共分为三大块,分别是标示符、数字、符号,对应下面的if else if 和else
*/
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;
case'\n':syn=-2;break;
default: syn=-1;break;
}
}
int main()
{
p=0;
row=1;
cout<<"Please input string:"<<endl;
do
{
cin.get(ch);
prog[p++]=ch;
}
while(ch!='#');
p=0;
do
{
scaner();
switch(syn)
{
case 11: cout<<"("<<syn<<","<<sum<<")"<<endl; break;
case -1: cout<<"Error in row "<<row<<"!"<<endl; break;
case -2: row=row++;break;
default:
cout<<"("<<syn<<","<<token<<")"<<endl;break;
}
}
while (syn!=0);
}。