词法分析—编译原理结课论文.doc

编译原理实验编译原理结课论文题目： 词法分析 作者： 电话： email: 教师： 递交日期： 2013 年 11 月 28 日摘要 词法分析作为编译的基础，其主要任务是对构成源程序的字符流进行扫描，然后根据构词规则识别单词符号，而这恰是源代码逆向分析过程中必不可少的一步。随着软件逆向工程的不断发展，词法分析被广泛应用于源代码逆向分析。本文就词法分析在源代码逆向分析过程中的应用进行探讨，尝试用简明易懂的方式去获得逆向分析后续工作所需的单词符号的各类信息。 关键词词法分析；逆向分析；源代码；单词符号 前言编译原理是一个十分复杂的加工处理程序。它将便于人们阅读但不能直接在计算机上执行的源程序翻译成语义上等价并且可在计算机上执行的目标程序。为了处理各种使用于不同目的的源程序，一般将整个编译过程划分为五个处理阶段，分别是词法分析、语法分析、中间代码生成（语义分析）、代码优化和目标代码生成。在编译程序结构中，词法分析程序通常作为子例程被语法分析调用，每一次调用返回一个单词。一个源程序有许多单词组成，词法分析程序被调用较频繁，它的频率直接决定编译程序的效率。词法分析对源程序进行自左至右的扫描，将它从外部形式（字符串）变换成便于后几个阶段处理的内部形式，即分解出一个个有独立语法意义的单元，称之为单词（又称符号或者特征），同时识别出与其相关的属性。优化阶段对语义分析所产生的中间代码进行改造，以获得等价但更为高效（指时间和空间的节省）的中间代码。目标代码生成阶段根据中间代码和表格信息，进行存储分配，选择代码，形成可在计算机上执行的目标程序。如果目标代码生成阶段产生的代码为汇编语言程序，那么嗨应再经过汇编阶段才能产生机器代码程序。 基于上述，本文通过设计、编制、调试一个具体的词法分析程序，对词法分析器的具体实现。正文1、词法分析 词法分析程序又称扫描器，它是编译过程的第一个阶段。其主要任务是从左到右依次描描字符串形式的源程序的各个字符，逐个识别出其中的单词，并将其转换成为内部编码形式的单词符号串输出，用于进行语法分析。通常可采用二元式（class，value）来表示一个单词符号 的内 部 编 码，其 中 class为一整 数 码，用于表示该单词 的 类别；value则是单词之值（如变量名在符号表中的序号，常数的二进制表示，以及运算符和分隔符的编码，等等）。 概括的说，扫描器在其工作过程中，一般应完成下列的任务： （1）识别出源程序中的各个单词符号，并将其转换成内部编码形式； （2）删除无用的空白字符、回车字符以及其他非实质性字符； （3）删除注释； （4）进行词法检查，报告所发现的错误。 此外，视编译工作流程的组织，一些编译程序在进行词法分析时，还要完成将所识别出的标志符登录到符号表的工作。从功能上看，词法分析上把字符串形式的源程序转换为单词串形式，然后进行语法分析。从工作方式上看，他与语法分析之间存在两种接口方式。一种方式是将词法分析的输出结果存放在一个中间文件上，后面的语法分析程序将它作为输入进行语法分析。另一种方式是将词法分析编成一个子程序，该子程序由语法分析程序调用，当语法分析程序需要读出一个具有独立意义的单词。本设计采用前一种方式。1.1根据状态转换图直接编程编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。源程序词法分析程序记号文件具体任务有：（1）组织源程序的输入（2）拼出单词并查找其类别编号，形成二元式输出，得到单词流文件（3）删除注释、空格和无用符号（4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。（5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。常量表结构：常量名，常量值义1.2词法分析程序的功能：输入：所给文法的源程序字符串。输出：二元组（syn,token或sum）构成的序列。其中：syn为单词种别码；token为存放的单词自身字符串；sum为整型常数。例如：对源程序beginx:=9:ifx9thenx:=2*x+1/3;end#的源文件，经过词法分析后输出如下序列：(1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)2、词法分析程序的算法思想：算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。2.1 主程序示意图：主程序示意图如图3-1所示。其中初始包括以下两个方面： 关键字表的初值。关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下：char *rwtab6 = “begin”, “if”, “then”, “while”, “do”, “end”,;置初值调用扫描子程序输出单词二元组输入串结束 否 是结束 3. 词法分析的任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称为单词符号或简称符号），如基本字（begin、end、for、if、while等），标识符、常数、算符、和界符（标点符号、左右括号等等）。例如，对于pascal的循环语句 for i:=1 to 100 do 词法分析的结果是识别出如下的单词符号： 基本字 for 标识符 i 赋值号 := 整常数 1 基本字 to 整常数 100 基本字do 3.1 输出：词法分析器所输出单词符号常常表示成如下的二元式：(单词种别，单词符号的属性值) 单词种别通常用整数编码。标识符一般统归为一种。常数则宜按类型（整、实、布尔等）分种。关键字可将其全体视为一种。运算符可采用一符一种的方法。界符一般用一符一种的方法。对于每个单词符号，除了给出了种别编码之外，还应给出有关单词符号的属性信息。单词符号的属性是指单词符号的特性或特征。 例子：c+代码段：while(i=j) i- 经词法分析器处理后，它将被转为如下的单词符号序列： =, _ 3.3 词法分析分析器作为一个独立子程序词法分析是编译过程中的一个阶段，在语法分析前进行。词法分析作为一遍，可以简化设 计，改进 编译 效率，增加编译系统的可移植性。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。 四、实验说明 (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 $普通标识符 /“$“为美元符号，不是大写字母s 4、分析器的实现4.1分析一般的程序设计语言， 注释部分的形式为； /* 注释部分、*/我们的程序总是顺序的一个一个字符读取输入文件的。我们的目的是把注释部分去掉，那么对于输入的字符流，我们只要识别出“/*”就知道后面的部分是注释部分，直到识别输入流中出现*/为止。对字符流的处理是一个一个进行的，每读入一个字符，就判断，如果字符是“/”,就说明后面 的部分可能是注释，再看下一个输入字符，如果是“*”, 就是上面所说的情况：“ /*”那么后面的部分就是注释部分，然后再用相同的方法找出*/就可以了。 这个识别的过程就可以用状态转换图来清晰的表示:，如图二。图二对于读入的每个符号都要进行判断，如果是“/”说明后面的部分有可能是注释，进入状态1。如果后面的输入是“*”那么就可以确定以后的内容为注释内容，如果后面的输入不是*，说明后面的内容不是注释，前面出现的/可能是做除号使用，如“5/3”其实上面的流程图也就对应了程序实现的逻辑，可以用switch-case 来实现，对于每个输入，判断后跳转到相应的状态，然后继续判断。 下面是程序伪代码：while(ch=getchar()!=eof)switch(state)case 1 :if ch=/,state=2,break;case 2: if ch=*,state=3else state=1;break;case 3:.case 4:.4.2功能接下来是一个简单的词法分析器的代码，可以实现对关键字（如 while end if 等），对数字的识别，去掉空格符等。4.2.1 待分析的简单语言的词法（1） 关键字：begin if then while do end 所有关键字都是小写。（2） 运算符和界符：:= + * / = = = ; ( ) #（3） 其他单词是标识符（id）和整型常数（num），通过以下正规式定义：id=letter（letter| digit）*num=digit digit * 空格由空白、制表符和换行符组成。空格一般用来分隔id、num,运算符、界符和关键字，词法分析阶段通常被忽略。4.2.2各种单词符号对应的种别码单词符号种别码单词符号种别码begin1:17if2:=18then319while420do5=22end6=24digit digit *11=25*13;26/14(27+15)28-16#0 4.2.3词法分析程序的功能输入：所给文法的源程序字符串。输出：二元组（syn，token或sum）构成的序列。其中：syn为单词种别码；oken为存放的单词自身字符串；sum为整型常数。5、程序测试 测试截图如图三。总结这次的课程设计，在同学这段时间的努力下，和其他同学的帮助下，顺利地完成了编译原理课程设计词法分析。 这次课程设计是对我们这一学期所学知识的一次总结，也是一次检验，更是我们对我们自己的一次挑战。通过该课程设计，收获颇多。通过课程设计，进一步加深对课堂中讲授的编译原理（技术）内容的理解，掌握编译程序诸环节常用的实现方法和技术，并初步具有研究、设计、编制和调试编译系统的能力。这里主要说的是编译器中的词法分析，还介绍了词法分析的一些相关知识，最后给出了一个简单的词法分析器的实现。参考文献1 张素琴，蒋维社，戴桂兰. 编译原理第二版，清华大学出版社，20052 胡元义，邓亚玲编，编译原理实践教程，西安理工大学教程科，20003 陈火旺，钱家骅，孙永强编. 程序设计语言编译原理. 北京：国防工业出版社，19844 蒋立源等，编译原理. 西安工业大学出版社，20005 金成植，编译原理与实现. 高等教育出版社，1998附录#include stdafx.h#include#include#includeusing namespace std;bool isnoshow(char ch) /判断是不是空格、回车、换行符 if(ch=n|ch=t|ch= ) return true; return false;bool isletter(char ch) /判断是不是字母 if(ch=a&ch=a&ch=0&ch=9) return true; return false;bool isunline(char ch) /判断是不是下划线 if(ch=_) return true; return false;bool iscacus(char ch) /判断是不是运算符 if(ch=+|ch=-|ch=*|ch=/|ch=%| ch=|ch=&|ch=|ch=!|ch=) return true; return false;bool issplits(char ch) /判断是不是分界符 if(ch=|ch=|ch=|ch=|ch=(| ch=)|ch=;|ch=,|ch=.|ch=:|ch=) return true; return false;int _tmain(int argc, _tchar* argv) char b1000; ifstream ifile; ifile.open(d:1.txt); int i=0; while(ifile.get(bi) int a=i+1; if(ifile.eof()=1) break; if(isletter(bi)|isunline(bi) coutbi; else if(isnoshow(bi) if(isletter(bi-1)|isunline(bi-1) cout是标识符endl; else if( isdigital(bi-1) cout是数字endl; else if(issplits(bi-1) cout是分界符endl; else if(iscacus(bi-1) cout是运算符endl; else if(isdigital(bi) if(isletter(bi-1)|isunline(bi-1) cout是标识符endl; else if(issplits(bi-1) coutbi-1是分界符endl; else if(iscacus(bi-1) cout是运算符endl; coutbi; else if(iscacus(bi)/运算符 if(isletter(bi-1)|isunline(bi