高级语言编译器中词法分析器的设计与实现

四川师范大学本科毕业设计高级语言编译器中词法分析器的设计与实现学生姓名张彪院系名称物理与电子工程学院专业名称通信工程班级2008级4班学号2008070468指导教师陈万川完成时间2012年5月12日高级语言编译器中的词法分析器的设计与实现学生姓名：张彪指导老师：陈万川内容摘要：编译器是程序员使用的关键工具，程序员毎天都在使用编译器，并且非常依赖于其正确性和可靠性。本文首先介绍了C语言及C语言编译器的发展历程，其次对本次开发所用到的工具VisualStudioC++2005以及面向对象的程序设计方法做一下简单介绍。最后重点介绍了编译器的详细开发过程，分为四个部分分别阐述：词法分析器的设计；语法分析器的设计；语义分析；以及系统的用户界面部分。每个部分又分别从总体框架，详细流程，重点数据结构和函数，以及与其他部分的接口等方面予以阐述。由于C语言本身的复杂性，很难面面倶到实现所有标准定义，所以本次设计只象征性的选择部分具有代表性的功能。在本文的第四章详细给出了此次设计所实现的功能和语法规范，同时也给出了编译器的运行方式。关键词：编译器C源程序VC++Thelexicalanalyzer’sDesignandImplementationofhigh-levellanguagecompilerAbstract:Thecompilerisakeytoolusedbytheprogrammer.Programmerseverydayinthecompiler,andisverydependentonitsaccuracyandreliability.ThispaperfirstdescribestheClanguageandClanguagecompilerdevelopmentprocess,makeabriefintroductionfollowedbythetoolsusedtodevelopVisualStudioC++2005aswellasobject-orientedprogrammingmethod.Finally,highlightthecompilerdevelopmentprocessisdividedintofourparts,respectively,explained:Thedesignoflexicalanalyzer,parserdesign,semanticanalysis,aswellasthesystem'suserinterfacepart.Eachpartseparatelyfromtheoverallframeworkoftheprocess,focusingondatastructuresandfunctions,aswellasotherpartsoftheinterfacetobeelaborated.DuetothecomplexityoftheClanguageitself,difficulttoPowerphonesJutoallstandarddefinition,sothewooddesignisonlysymbolicchoiceofrepresentativefunctions.ChapterIVofthispaperisgivenindetailthedesignfeaturesandsyntaxspecification,butalsogivesthecompilerrun.Keywords:compilertheCsourceVC++目录1绪论....................................................................11.1C语言及编译器概述...................................................11.2C编译器设计思想.....................................................11.3开发工具的选用及介绍.................................................21.4论文组织结构.........................................................32C语言词法分析器的总体分析与设计.........................................42.1系统设计目标与功能分析...............................................42.2词法分析.............................................................42.3语法分析.............................................................42.3.1自顶向下的语法分析.............................................52.3.2自底向上的语法分析.............................................52.4语义分析.............................................................52.5符号表...............................................................62.6类型检查.............................................................73系统详细设计.............................................................73.1系统设计基本思路.....................................................73.2词法分析模块设计.....................................................83.3语法分析模块设计....................................................103.4语义分析模块设计....................................................133.5界面设计考量........................................................143.5.1可用性原则....................................................143.5.2可视性原则....................................................153.5.3系统主要界面组成..............................................164系统原型测试............................................................184.1系统测试基本原则....................................................184.2系统测试的步骤......................................................184.3测试结果............................................................195结束语.................................................................19致谢......................................................................20参考文献..................................................................201高级语言编译器中的词法分析器的设计与实现1绪论1.1C语言及编译器概述C语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie于1972年推出。1978后，C语言已先后被移植到大、中、小及微型机上。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画。具体应用比如单片机以及嵌入式系统开发。词法分析代表了一类问题的集合，即如何对输入字符串中的特定模式进行具备特定动作的匹配。解决此类问题，不仅对于编译器开发中的阶段抽象具有重要意义，更对应用领域中有关字符处理的需求具有深刻价值。设计和实现词法分析器，要用到词素、记号、正则表达式、输入字符双缓冲区、符号表、状态转换图设计等概念。抽象地阐述这些概念往往晦涩难懂，而结合某一具体编译器的前端实现来分析探讨，则容易使概念条理清晰，目的明确。因此，从设计一个轻量级语言开始，根据语言编译的要求设计和实现词法分析器，将原理与实践结合，将是研究此类问题的最佳途径。编译是从源代码(通常为高阶语言)到能直接被计算机或虚拟机执行的目标代码(通常为低阶语言或机器语言)的翻译过程。然而，也存在从低阶语言到高阶语言的编译器，这类编译器中用来从由高阶语言生成的低阶语言代码重新生成高阶语言代码的又被叫做反编译器。也有从一种高阶语言生成另一种高阶语言的编译器，或者生成一种需要进一步处理的的中间代码的编译器(又叫级联)。典型的编译器输出是由包含入口点的名字和地址，以及外部调用(到不在这个目标文件中的函数调用)的机器代码所组成的目标文件。一组目标文件，不必是同一编译器产生，但使用的编译器必需采用同样的输出格式，可以链接在一起并生成可以由用户直接执行的可执行程序。1.2C编译器设计思想一个编译器的主要工作过程可以概括为以下几个步骤：(1)词法分析词法分析器根据词法规则识别出源程序中的各个记号（token），每个记号代表一类单词（lexeme）。源程序中常见的记号可以归为几大类：关键字、标识符、字面量和特殊符号。词法分析器的输入是源程序，输出是识别的记号流。词法分析器的任务2是把源文件的字符流转换成记号流。本质上它查看连续的字符然后把它们识别为“单词”。(2)语法分析语法分析器根据语法规则识别出记号流中的结构〔短语、句子〉，并构造一棵能够正确反映该结构的语法树。(3)语义分析语义分析器根据语义规则对语法树中的语法单元进行静态语义检查，如果类型检查和转换等，其目的在于保证语法正确的结构在语义上也是合法的。(4)中间代码生成中间代码生成器根据语义分析器的输出生成中间代码。中间代码可以有若干种形式，它们的共同特征是与具体机器无关。最常用的一种中间代码是三地址码，它的一种实现方式是四元式。三地址码的优点是便于阅读、便于优化。(5)中间代码优化优化是编译器的—个重要组成部分，由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进行的，因此，生成的中间代码往往在时间和空间上有很大浪费。当需要生成高效目标代码时，就必须进行优化。(6)目标代码生成目标代码生成是编译器的最后一个阶段。在生成目标代码时要考虑以下几个问题：计算机的系统结构、指令系统、寄存器的分配以及内存的组织等。编译器生成的目标程序代码可以有多种形式：汇编语言、可重定位二进制代码、内存形式。（7）符号表管理符号表的作用是记录源程序中符号的必要信息，并加以合理组织，从而在编译器的各个阶段能对它们进行快速、准确的查找和操作