一个简单文法的编译器前端的设计与实现

课程设计报告设计题目：一个简单文法的编译器前端的设计与实现班级：计算机1208班组长学号：20124016组长姓名：樊荣指导教师：张俐设计时间：2014年12月设计分工组长学号及姓名：20124016樊荣分工：四元式生成、语义分析(未定义、重定义等)、整体设计组员1学号及姓名：20124020李鑫分工：符号表建立及其输入输出设计组员2学号及姓名：20124032杨学良分工：词法分析组员3学号及姓名：20124018焦通分工：语法分析组员4学号及姓名：201240陈凤分工：简单C语言文法设计及部分简单函数编写摘要编译器是程序员使用的关键工具，程序员每天都在使用编译器，并且非常依赖于其正确性和可靠性。编译器作为广大IT从业者必须接触的系统软件，它的设计本身又是一个极其庞大的工程。编译器相关的各项技术经过近几十年的发展，已经日臻成熟，然而编译器构造原理和技术依然是计算机科学中理论与实践相结合的最好典范。本文重点介绍了编译器前端的详细开发过程，分为四个部分分别阐述：文法设计，词法分析器的设计，语法分析器的设计，语义分析部分。每个部分又分别从功能，数据结构和算法三个方面进行详尽阐述，。由于C语言本身的复杂性，很难面面俱到实现所有标准定义，所以本次设计只象征性的选择部分具有代表性的功能。在本文的第四章详细给出了此次设计所实现的功能和语法规范，同时也给出了编译器的运行方式。关键词：编译原理，编译器前端，C源程序……目录摘要······························11概述·····························22课程设计任务及要求·······················32.1设计任务··························32.2设计要求··························33算法与数据结构··························43.1算法的总体思想（流程）···················43.2词法分析模块·······················53.2.1功能························73.2.2数据结构······················83.2.3算法························93.3语法分析模块·······················103.3.1功能························113.3.2数据结构······················123.3.3算法························133.4符号表模块························133.4.1功能·······················133.4.2数据结构·····················144序设计与实现··························144.1程序流程图······················144.2程序说明······················154.3实验结果······················155.结论·····························166.参考文献。··························177.收获、体会和建议。······················171.概述经过一段时间的学习，我们在初步掌握了编译器的基本原理以后，设计了一个具有基本编译功能的编译器前端。该编译器前端接受类C语言语法的源代码输入，输出结果是四元式组。本编译器实现了基本高级语言所必须的语法要素，包括简单变量声明、条件判断语句和循环语句及跳转语句、基本代数运算、赋值等。由于编译程序本身涉及到词法分析、语法分析、中间代码生成等诸多模块，要在实验中做到面面俱到不太可能，所以本编译器不可避免的会存在各种问题，但作为一个具有基本功能的、可扩充的系统，完全达到了巩固编译原理的理论知识，并将其运用于实践的目的。2.课程设计任务及要求2.1设计任务在下列内容中任选其一：1、一个简单文法的编译器前端的设计与实现。2、基本块的划分及中间代码优化程序设计与实现。3、LL（1）、LR分析表的自动生成算法的设计实现。4、自选一个感兴趣的与编译原理有关的问题加以实现，要求难度相当。我们组由于人数较多，且综合代码编写能力不强，经多方面考虑选择了简单类C文法的编译前端设计与实现任务。2.2设计要求1.给出一个源程序文件，作为编译器前端的输入2.输出相关编译阶段的运行结果词法分析阶段：Token序列；关键字表、界符表、符号表系统。中间代码生成阶段：四元式序列；符号表系统。3.算法及数据结构3.1算法的总体思想（流程）输入文件程序整体上遵从上图所示流程图，源代码通过词法分析器，录入token序列，并纠察词法错误，接下来根据token序列进行语法分析，采用递归下降法对程序语法进行验证检查，在这过程中，建立和完善符号表，并进行语义差错（主要是类型检查、未定义和重定义），通过前面过程后，才能生成中间代码，并输出有关信息。3.2词法分析模块3.2.1功能词法分析程序又称扫描器，它是编译过程的第一个阶段。其主要任务是从左到右依次描描字符串形式的源程序的各个字符，逐个识别出其中的单词，并输入文件开始词法分析语法分析建立符号表类型检查语法树符号表输出信息错误检查将其转换成为内部编码形式的单词符号串输出，用于进行语法分析。概括的说语法分析器在工作中完成以下几项任务：（1）识别出源程序中的各个单词符号，并将其转换成内部编码形式；（2）删除无用的空白字符、回车字符以及其他非实质性字符；（3）进行词法检查，报告所发现的错误；（4）填写符号表。3.2.2数据结构structTokenType{intcode,value;}token[100];//token序列stringbsfwords[20];//标示符数组，code=0intbsf=0;charzifwords[20];//字符数组，code=1intzif=0;stringzfcwords[20];//字符串数组,code=2intzfc=0;floatnumwords[30];//数字常量数组,code=3intnum=0;3.2.3算法识别器算法流程图设计：总体算法流程图设计：fin.get(ch)有yyynynnyerror3.3语法分析模块3.3.1功能语法分析程序又称分析器，它以单词串形式的源程序作为输入或分析的对象，其基本任务是：根据程序设计语言的语法规则（即定义该语言的前后无关文法），分析源程序的语法结构，即分析如何由这些单词组成该源程序的各种语法成分（如下标变量、函数、各种表达式、各种程序语句等），并在分析过程中关联文件，读文件#?结束获取字符串，查关键字表生成标示符token，存储字符串，填写符号表；生成关键字token数字？字符？获取数字常量，生成数字常量token，填写符号表查界符表，生成界符token界符？开始进行语法正确性检查，产生内部形式的中间代码，供编译程序后续阶段处理。3.3.2数据结构intsem[20];模拟语义栈，存储单词token码3.3.3算法⑴扩展文法：增设一个产生式，作为主程序：Z`-Z，⑵入出口约定：子程序入口时，其首符号已经读来！子程序出口时，其后继符应该读来！⑶子程序内容设计：遇终结符，判定之，确认后读下一单词；遇非终结符,调用之,返回后不读下一单词；遇空串()，直接出口；根据定义的文法和算法编写部分递归下降程序框图如下：P:NerroryNEXT（W）nErroryNEXT（W）nerror入口Void？入口Main？{？yNEXT（W）nErroryIT：nErroryNEXT（w）nyNEXT（w）nyNEXT（w）}？结束入口标示符？=？E，？出口诸如上面框图，实现文法内容，在相应的地方加入语法动作，可生成四元式，调用符号表系统，可以填写符号表和语义查错。3.4符号表模块3.4.1功能符号表是标识符的动态语义词典，属于编译中语义分析的知识库；主要内容：⑴名字—标识符源码，用作查询关键字；⑵类型--该标识符的数据类型及其相关信息；⑶种类--该标识符在源程序中的语义角色；⑷地址--与值单元相关的一些信息；由于文法比较简单，只是实现一部分功能，所以符号表部分也相应没那么完整和强大，它只是帮助实现了变量重定义、变量未定义和类型匹配的查错功能。3.4.2数据结构structAinfl//数组表{intlow;intup;TypelCpt;intclen;}structRinfl//结构表{stringID;intoff;TypelTP;}structTypel///////类型表{chartval;Ainfla;Rinfld;}TYPEL[20];intpipei=0;structsymbol//符号总表{stringname;Typeltype;charcat;intaddr;}Symbol[20];4序设计与实现4.1程序流程图yny开始词法扫描出错？输出token序列语法分析出错？报错n4.2程序说明intisLetter(charch)//字母判断intisNumber(charch)//数字判断voidinitKeys()//关键字，分界符初始化intlockupkeys(strings)//查询关键字和分界符voidinsertToken(inta,intb)//token录入voidprintToken()//token输出voidscanner()//一个字符一个字符地扫描voidP();//递归下降子程序voidPp();voidIff();voidCo();voidII();voidDw();voidVt();voidVd();voidIt();voidWt();voidD();输出符号表信息，四元式结束voidE();voidT();voidF();voidI();voidTy();voidaddSymbol(strings,chartval,charcat,intaddr)//添加到符号表sendVall();//输出活动记录表sendSymbol();输出符号表sendConst();输出常数表4.3实验结果:5.结论经过全组人员共同努力，基本实现了编译前端的功能任务，能够实现扫描，进行语法语义分析，并能生成符号表系统，将编译器前端的工作做得比较完善。尽管如此，我们的系统还是有待完善的，诸如函数功能、符号表的进一步细化都是可以继续进行的项目，由于精力和时间有限，我们组暂时只能做到这个地步。整体结果我们自己还是很满意的，毕竟一个编译器前端真真切切地被实现了，我们的辛苦工作没有白费。6.参考文献1、陈火旺.《程序设计语言编译原理》（第3版）.北京：国防工业出版社.2000.2、美AlfredV.AhoRaviSethiJeffreyD.Ullman著.李建中，姜守旭译.《编译原理》.北京：机械工业出版社.2003.3、美KennethC.Louden著.冯博琴等译.《编译原理及实践》.北京：机械工业出版社.2002.4、金成植著.《编译程序构造原理和实现技术》.北京：高等教育出版社.2002.7.收获、体会和建议通过本次开发设计，我们对C语言课程、数据结构、编译原理等一系列的课程的进行回顾学习。在开发基于C语言小型编译器前端中，还是用系统分析、系统设计的思路。一个好的系统分析、设计工作，会使以后的系统实施顺利高效的进行从而达到事半功倍的效果，这也是我的一点心得体会吧。对于系统的可扩展性，在设计前也做了充分的考虑，在设计时预留了一些余地，以便本系统在C语言语法不变的情况下一直都能使用，而不需要再重新开发。同时在设计上使用的是模块化的设计，更为系统以后的扩展提供了良好的条件。同时系统也存在的问题与改进方向,由于本人第一次开发编程语言编译程序，经验不足，所以存在着许多不足之处。由于时间紧，开发任