词法分析器编译原理.doc

编译原理词法分析器 学院：专业： 姓名： 学号： 1、 序言 编译，简单的说，就是把源程序转换为可执行程序。编译程序的工作，从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的。而此法分析是编译程序工作过程的第一环节。这篇报告主要讲了词法分析器的原理，最后会给出一个词法分析器的简单实现。2、 实验目的 设计一个词法分析程序，理解词法分析器实现的原理，掌握程序设计语言中的各类单词的词法分析方法，加深对词法分析原理的理解。3、 词法分析原理3.1 词法分析的任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称为单词符号或简称符号），如基本字（begin、end、for、if、while等），标识符、常数、算符、和界符（标点符号、左右括号等等）。例如，对于pascal的循环语句For I:=1 to 100 do词法分析的结果是识别出如下的单词符号： 基本字 for 标识符 I 赋值号 := 整常数 1 基本字 to 整常数 100 基本字 do 3.2 输出：词法分析器所输出单词符号常常表示成如下的二元式：(单词种别，单词符号的属性值)单词种别通常用整数编码。标识符一般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可将其全体视为一种。运算符可采用一符一种的方法。界符一般用一符一种的方法。对于每个单词符号，除了给出了种别编码之外，还应给出有关单词符号的属性信息。单词符号的属性是指单词符号的特性或特征。例子：C+代码段：while(i=j) i-经词法分析器处理后，它将被转为如下的单词符号序列：=, _3.3 词法分析分析器作为一个独立子程序词法分析是编译过程中的一个阶段，在语法分析前进行。词法分析作为一遍，可以简化设计，改进编译效率，增加编译系统的可移植性。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。4、 实验说明(1)关键字：begin,end,if,then,else,while,write,read,do, call,const,char,until,procedure,repeat(2)运算符：+,-,*,/,=(3)界符：,;,.,(,),:(4)其他标记 如字符串，表示以字母开头的标识符 (5)空格、回车、换行符跳过(6)运行结果在屏幕上以如下格式显示： 1 $无符号整数begin $关键字 if $关键字 + $运算符 ； $界符 a $普通标识符 /“$“为美元符号，不是大写字母S5、 词法分析器的设计 5.1 输入、预处理 词法分析器工作的第一步是输入源程序文本。把输入串预处理一下，对单词符号的识别工作将是比较方便的。预处理可以剔掉空白符、跳格符、回车符和换行符等编辑性字符。 5.2 单词符号的识别：超前搜索 单词符号识别的一个简单方法超前搜索。 在FORtRAN语言中，关键字不加特殊保护，可用作普通标识符。为确定词性，需超前搜索若干个字符。在FORTRAN中1 DO99K=1,102 IF(5.EQ.M) I=103 DO99K=1.104 IF(5)=55这四个语句都是正确的语句。语句1和2 分别是DO和IF语句，语句3和4是赋值语句。为了正确区别1和3，2和4语句，需超前扫描若干个字符。1 DO99K=1,10 2 IF(5.EQ.M) I=103 DO99K=1.10 4 IF(5)=55语句1和3的区别在于符号之后的第一个界符：一个为逗号，另一个为句末符。语句2和4的主要区别在于右括号后的第一个字符：一个为字母，另一个为等号。为了识别1、2中的关键字，必须超前扫描多个字符。超前到能够肯定词性的地方为止。为了区别1和3，必须超前扫描到等号后的第一个界符处。对于语句2、4来说，必须超前扫描到与IF后的左括号相对应的那个右括号之后的第一个字符为止。5.3 状态转换图 词法分析器使用状态转换图来识别单词符号。状态转换图是一张有限方向图。在状态转换图中，有一个初态，至少一个终态。其中0为初态，2为终态。这个转换图识别（接受）标识符的过程是：从初态0开始，若在状态0之下输入字符是一个字母，则读进它，并转入状态1。在状态1之下，若下一个输入字符为字母或数字，则读进它，并重新进入状态1。一直重复这个过程直到状态1发现输入字符不再是字母或数字时（这个字符也已被读进）就进入状态2。状态2是终态，它意味着到此已识别出一个标识符，识别过程宣告终止。终态结上打个星号意味着多读进了一个不属于标识符部分的字符，应把它退还给输入口中 。如果在状态0时输入字符不为“字母”，则意味着识别不出标识符，或者说，这个转换图工作不成功。 5.4 正规表达式与正规集 正规表达式是说明单词的一种重要的表示法(记号)，是定义正规集的工具。在词法分析中，正规表达式用来描述标示符可能具有的形式。定义(正规式和它所表示的正规集)：设字母表为S，1. e和都是S上的正规式，它们所表示的正规集分别为e和 ；2. 任何a S，a是S上的一个正规式，它所表示的正规集为a；3. 假定U和V都是S上的正规式，它们所表示的正规集分别为L(U)和L(V)，那么，(U), U|V, UV, U*也都是正规式,它们所表示的正规集分别为L(U), L(U)L(V), L(U)L(V)和(L(U)*；4. 仅由有限次使用上述三步骤而定义的表达式才是S上的正规式，仅由这些正规式所表示的字集才是S上的正规集。正规式的运算符的“”读为“或” ,“ ”读为“连接”；“*”读为“闭包”(即，任意有限次的自重复连接)。在不致混淆时，括号可省去，但规定算符的优先顺序为“(”、“)”、“*”、“ ”、“” 。连接符“ ”一般可省略不写。“*”、“ ”和“” 都是左结合的。例 令S=a,b， S上的正规式和相应的正规集的例子有：正规式 正规集a aab a,bab ab(ab)(a aa,ab,ba,bba * e ,a,a, 任意个a的串ba* b, ba, baa, baaa, (ab)* e ,a,b,aa,ab 所有由a和b组成的串(ab)*(aabb)(ab)* S*上所有含有两个相继的a或两个相继的b组成 的串定理：若两个正规式U和V所表示的正规集相同,则说U和V等价,写作U=V。证明b(ab)*=( ba)*b证明：因为L(b(ab)*)=be, 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) UV=VU (交换律)(2) U(VW)=(UV)W (结合律)(3) U(VW)=(UV)W (结合律)(4) U(VW)=UVUW (VW)U=VUWU (分配律)(5) eU=U e=U六、词法分析器简单实现6.1、待分析的简单语言的词法(1)关键字begin,end,if,then,else,while,write,read,do, call,const,char,until,procedure,repeat(2)运算符：+,-,*,/,=(3)界符：,;,.,(,),:(4)其他标记 如字符串，表示以字母开头的标识符。(5)空格、回车、换行符跳过。在屏幕上显示如下：( 1 , 无符号整数)( begin , 关键字 )( if , 关键字 )( +, 运算符 )( ； , 界符 )( a , 普通标识符 )6.2 程序调试文件位置：f：编译.txt目标程序如下： beginx:=9if x0 then x:=x+1;while a:=0 dob:=2*x/3;end;6.3 运行结果7、 程序源代码#include #includeusing namespace std;#define MAX 22 char ch = ;string key15=begin,end,if,then,else,while,write,read,do, call,const,char,until,procedure,repeat;int Iskey(string c) /关键字判断 int i; for(i=0;iMAX;i+) if(pare(c)=0) return 1; return 0;int IsLetter(char c) /判断是否为字母 if(c=a)|(c=A) return 1; else return 0;int IsDigit(char c) /判断是否为数字 if(c=0&c=9) return 1; else return 0;void analyse(FILE *fpin) string arr=; while(ch=fgetc(fpin)!=EOF) arr=; if(ch= |ch=t|ch=n) else if(IsLetter(ch) while(IsLetter(ch)|IsDigit(ch) if(ch=A) ch=ch+32; arr=arr+ch; ch=fgetc(fpin); fseek(fpin,-1L,SEEK_CUR); if (Iskey(arr)coutarrt$关键字endl; else coutarrt$普通标识符endl; else if(IsDigit(ch) while(IsDigit(ch)|ch=.&IsDigit(fgetc(fpin) arr=arr+ch; ch=fgetc(fpin); fseek(fpin,-1L,SEEK_CUR); coutarrt$无符号实数endl; else switch(ch) case+: case- : case* : case= : case/ :coutcht$运算符endl;break; case( : case) : case : case : case; : case. : case, : case : case :coutcht$界符endl;break; case: :ch=fgetc(fpin); if(ch=) cout:=t$运算符endl; else cout=t$运算符 :ch=fgetc(fpin); if(ch=) cout=t$运算符)coutt$输入控制符endl; else coutt$运算符endl; fseek(fpin,-1L,SEEK_CUR); break; case :ch=fgetc(fpin); if(ch=)cout=t$运算符endl; else if(ch=)coutt$输出控制符) coutt$运算符endl; elsecoutt$运算符endl; fseek(fpin,-1L,SEEK_CUR); break; default : coutcht$无法识别字符endl; void mai