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

1、 课 程 设 计 报 告 设计题目：一个简单文法的编译器前端的设计与实现班 级：计算机1208班组长学号：20124016组长姓名： 樊荣指导教师： 张俐 设计时间：2014年12月设计分工组长学号及姓名： 20124016 樊荣分工： 四元式生成、语义分析(未定义、重定义等)、整体设计组员1学号及姓名： 20124020 李鑫分工： 符号表建立及其输入输出设计组员2学号及姓名： 20124032 杨学良分工： 词法分析组员3学号及姓名： 20124018 焦 通 分工： 语法分析组员4学号及姓名： 201240 陈 凤分工： 简单C语言文法设计及部分简单函数编写 摘 要 编译器是程序员使用的

2、关键工具，程序员每天都在使用编译器，并且非常依赖于其正确性和可靠性。编译器作为广大IT从业者必须接触的系统软件，它的设计本身又是一个极其庞大的工程。编译器相关的各项技术经过近几十年的发展，已经日臻成熟，然而编译器构造原理和技术依然是计算机科学中理论与实践相结合的最好典范。本文重点介绍了编译器前端的详细开发过程，分为四个部分分别阐述：文法设计，词法分析器的设计，语法分析器的设计，语义分析部分。每个部分又分别从功能，数据结构和算法三个方面进行详尽阐述，。由于C语言本身的复杂性，很难面面俱到实现所有标准定义，所以本次设计只象征性的选择部分具有代表性的功能。在本文的第四章详细给出了此次设计所实现的功能

3、和语法规范，同时也给出了编译器的运行方式。关键词：编译原理，编译器前端，C源程序 目 录摘要 ······························ 1 1 概述···········

4、·················· 22 课程设计任务及要求·······················3 2.1 设计任务·····&

5、#183;····················3 2.2 设计要求··························3 3 算法与数据

6、结构··························4 3.1算法的总体思想（流程）···················4 3.2词法分析模块&

7、#183;······················5 3.2.1 功能························73.2.2 数据

8、结构······················8 3.2.3 算法························9 3.3 语法分析模块

9、·······················10 3.3.1功能························113.3.2

10、数据结构······················12 3.3.3算法························13 3.4 符号表

11、模块························13 3.4.1功能·······················13 3.4

12、.2 数据结构·····················14 4序设计与实现··························1

13、4 4.1 程序流程图······················14 4.2 程序说明······················15 4.3 实验结果

14、83;·····················155. 结论···························&#

15、183;·166. 参考文献。··························177. 收获、体会和建议。··················&#

16、183;···17 1.概述 经过一段时间的学习，我们在初步掌握了编译器的基本原理以后，设计了一个具有基本编译功能的编译器前端。该编译器前端接受类C语言语法的源代码输入，输出结果是四元式组。本编译器实现了基本高级语言所必须的语法要素，包括简单变量声明、条件判断语句和循环语句及跳转语句、基本代数运算、赋值等。由于编译程序本身涉及到词法分析、语法分析、中间代码生成等诸多模块，要在实验中做到面面俱到不太可能，所以本编译器不可避免的会存在各种问题，但作为一个具有基本功能的、可扩充的系统，完全达到了巩固编译原理的理论知识，并将其运用于实践的目的。2. 课程设计任务及要求 2

17、.1设计任务 在下列内容中任选其一： 1、一个简单文法的编译器前端的设计与实现。 2、基本块的划分及中间代码优化程序设计与实现。 3、LL（1）、LR分析表的自动生成算法的设计实现。 4、自选一个感兴趣的与编译原理有关的问题加以实现，要求难度相当。 我们组由于人数较多，且综合代码编写能力不强，经多方面考虑选择了简单类C文法的编译前端设计与实现任务。 2.2设计要求 1.给出一个源程序文件，作为编译器前端的输入 2.输出相关编译阶段的运行结果 词法分析阶段： Token序列； 关键字表、界符表、符号表系统。 中间代码生成阶段： 四元式序列； 符号表系统。 3. 算法及数据结构 3.1算法的总体思

18、想（流程）输入文件 输入文件 开 始错误检查 词法分析语法树语法分析建立符号表 符号表类型检查输出信息 程序整体上遵从上图所示流程图，源代码通过词法分析器，录入token序列，并纠察词法错误，接下来根据token序列进行语法分析，采用递归下降法对程序语法进行验证检查，在这过程中，建立和完善符号表，并进行语义差错（主要是类型检查、未定义和重定义），通过前面过程后，才能生成中间代码，并输出有关信息。 3.2词法分析模块 3.2.1功能 词法分析程序又称扫描器，它是编译过程的第一个阶段。其主要任务是从左到右依次描描字符串形式的源程序的各个字符，逐个识别出其中的单词，并将其转换成为内部编码形式的单词符

19、号串输出，用于进行语法分析。概括的说语法分析器在工作中完成以下几项任务： （1）识别出源程序中的各个单词符号，并将其转换成内部编码形式； （2）删除无用的空白字符、回车字符以及其他非实质性字符； （3）进行词法检查，报告所发现的错误； （4）填写符号表。 3.2.2 数据结构 struct TokenType int code,value;token100;/token序列 string bsfwords20;/标示符数组，code = 0 int bsf = 0; char zifwords20;/字符数组，code = 1 int zif = 0; string zfcwords20;/字

20、符串数组,code = 2 int zfc = 0; float numwords30;/数字常量数组,code = 3 int num =0; 3.2.3 算法 识别器算法流程图设计： 总体算法流程图设计： 开始关联文件，读文件生成标示符token，存储字符串，填写符号表；生成关键字token fin.get(ch)# ?字符？ 有获取字符串，查关键字表 y y 结束 y n数字？ 获取数字常量，生成数字常量token，填写符号表y n查界符表，生成界符token 界符？nyerror3.3 语法分析模块 3.3.1功能 语法分析程序又称分析器，它以单词串形式的源程序作为输入或分析的对象，其

21、基本任务是：根据程序设计语言的语法规则（即定义该语言的前后无关文法），分析源程序的语法结构，即分析如何由这些单词组成该源程序的各种语法成分（如下标变量、函数、各种表达式、各种程序语句等），并在分析过程中进行语法正确性检查，产生内部形式的中间代码，供编译程序后续阶段处理。 3.3.2数据结构 int sem20;模拟语义栈，存储单词token码 3.3.3 算法 扩展文法：增设一个产生式，作为主程序：Z->Z ， 入出口约定： 子程序入口时，其首符号已经读来！子程序出口时，其后继符应该读来！ 子程序内容设计：遇终结符，判定之 ，确认后读下一单词；遇非终结符,调用之,返回后不读下一单词； 遇

22、空串 ( e ) ，直接出口；根据定义的文法和算法编写部分递归下降程序框图如下： 入口 入口 P: Void？ N errory NEXT（W）Main？nErroryNEXT（W） ？nerror y 结束 ？ NEXT（W）nErroryIT： 入口 标示符？nErroryNEXT（w） =？nyNEXT（w） E ，？ 出口 ny NEXT（w）诸如上面框图，实现文法内容，在相应的地方加入语法动作，可生成四元式，调用符号表系统，可以填写符号表和语义查错。3.4 符号表模块 3.4.1功能 符号表是标识符的动态语义词典，属于编译中语义分析的知识 库；主要内容： 名字 标识符源码，用作查询关

23、键字； 类型 - 该标识符的数据类型及其相关信息； 种类 - 该标识符在源程序中的语义角色； 地址 - 与值单元相关的一些信息； 由于文法比较简单，只是实现一部分功能，所以符号表部分也相应没那么完整和强大，它只是帮助实现了变量重定义、变量未定义和类型匹配的查错功能。3.4.2数据结构struct Ainfl / 数组表 int low; int up; Typel Cpt; int clen;struct Rinfl / 结构表 string ID; int off; Typel TP;struct Typel /类型表 char tval; Ainfl a; Rinfl d;TYPEL20;

24、int pipei=0;struct symbol / 符号总表 string name; Typel type; char cat; int addr;Symbol20;4序设计与实现4.1 程序流程图 开始 词法扫描出错？ 报 错 y输出token序列n语法分析出错？yn输出符号表信息，四元式 结束4.2程序说明 int isLetter(char ch)/字母判断 int isNumber(char ch) /数字判断void initKeys() /关键字，分界符初始化 int lockupkeys(string s) /查询关键字和分界符 void insertToken(int a

25、,int b) /token录入 void printToken() /token 输出 void scanner()/一个字符一个字符地扫描void P();/递归下降子程序void Pp();void Iff();void Co();void II();void Dw();void Vt();void Vd();void It();void Wt();void D();void E();void T();void F();void I();void Ty();void addSymbol(string s,char tval,char cat,int addr)/添加到符号表sendVall();/输出活动记录表 sendSymbol();输出符号表 sendConst();输出常数表4.3实验结果: 5. 结论经过全组人员共同努力，基本实现了编译前端的功能任务，能够实现扫描，进行语法语义分析，并能生成符号表系统，将编译器前端的工作做得比较完善。尽管如此，我们的系统还是有待完善的，诸如函数功能、符号表的进