编译原理课程设计报告.docx

程 设 计 报 告设计题目：一个简单文法的编译器前端的设计与实现班 级： 计算机1308班组长学号：20134019组长姓名：刘鑫伟指导教师：张俐设计时间：2015年12月设计分工组长学号及姓名：20134019 刘鑫伟分工：符号表，搭建框架。组员1学号及姓名：20134010 高八一分工：词法分析，Token。组员2学号及姓名：20134026 肖辉分工：文法，语法分析。组员3学号及姓名：20134029 袁宵分工：语义分析及四元式生成。摘 要编译原理是计算机科学与技术专业一门重要的专业课, 它具有很强的理论性与实践性，目的是系统地向学生介绍编译系统的结构、工作原理以及编译程序各组成部分的设计原理和实现技术，在计算机本科教学中占有十分重要的地位。计算机语言之所以能由单一的机器语言发展到现今的数千种高级语言，就是因为有了编译技术。编译技术是计算机科学中发展得最迅速、最成熟的一个分支，它集中体现了计算机发展的成果与精华。本课设是词法分析、语法分析、语义分析的综合，外加上扩展任务中间代码的优化和目标代码的生成，主要是锻炼学生的逻辑思维能力，进一步理解编译原理的方法和步骤。我们编译课程设计做的是一个简单的编译器的前端。我们用了递归下降子程序法实现这个编译器的前端。我们参考了了老师提供的简单文法，然后完整的程序生成文法，还有四元式生成文法。在此基础上我们还做了处理赋值语句、if-else语句、while语句的语法分析和四元式的生成，这样我们就设计完了四元式的生成。然后，我们又设计了符号表。其中的特色点有：语法分析阶段能够检测出错误，并且能指出错误在哪一行，具体为什么错误；表示式的四元式采用了逆波兰式的方法；同时像if- while, 我们的编译器能判断其中的boolean表达式的真值，从而能采用正确的逻辑得出正确的结果；活动记录表阶段能够指出具体采取了什么动作，具体代码。关键词：编译原理，前端，递归下降子程序法，四元式，符号表目 录摘要 I1 概述 62 课程设计任务及要求 8 2.1 设计任务 8 2.2 设计要求 83 算法与数据结构 9 3.1算法的总体思想（流程） 9 3.2 词法扫描模块 9 3.2.1 功能93.2.2 数据结构9 3.2.3 算法11 3.3 语法分析模块12 3.3.1功能123.3.2 数据结构12 3.3.3算法13 3.3.4算法流程图 143.4 语义分析四元式分析模块20 3.3.1功能203.3.2 数据结构20 3.3.3算法213.5 符号表分析模块 29 3.3.1功能293.3.2 数据结构29 3.3.3算法324. 程序设计与实现33 4.1 程序流程图33 4.2 程序说明33 4.3 实验结果1325. 结论 1346. 参考文献。1357. 收获、体会和建议。1351. 概述编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。编译原理是计算机专业设置的一门重要的专业课程。虽然只有少数人从事编译方面的工作，但是这门课在理论、技术、方法上都对学生提供了系统而有效的训练，有利于提高软件人员的素质和能力。由于时间和同学们的水平有限，故本实验只涉及到了词法分析，语法分析，及中间代码的四元式生成和符号表。具体概述介如下： 1.词法分析：在这个阶段编译器实际阅读源程序（通常以分析程序字符流的形式表示）。扫描程序执行词法分析注释树符号表：它将字符序列收集到称作记号错误处的有意义单元中，记号同自然语言，如英源代码理器语中的字词相似。因此可以认为扫描程序执行与优化程序拼写相似的任务。本实验的词法分析程序用于生成Token序列。 2.语法分析：该程序从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法分析，这与自然语言中句子的语法分析类似。语法分析定义了程序的结构元素及其关系。其任务是识别和处理比单词更大的语法单位。本实验用于指出程序设计语言中的表达式、各种说明和语句乃至全部源程序其中的语法错误；必要时，可生成内部形式，便于下一阶段处理。 3.中间代码：根据中间代码的类型和优化的类型，该代码可以是文本串的数组、临时文本文件或是结构的连接列表。对于进行复杂优化的编译器。由于同学们水平有限，我们只做了四元式的生成。 4.语义分析：程序的语义就是它的“意思”，它与语法或结构不同。程序的语义确定程序的运行，但是大多数的程序设计语言都具有在执行之前被确定而不易由语法表示和由分析程序分析的特征。这些特征被称作静态语义，而语义分析程序的任务就是分析这样的语义。一般的程序设计语言的典型静态语义包括声明和类型检查。由于同学们水平有限，我们只做了其中的符号表部分。编译原理课程兼有很强的理论性和实践性，是计算机专业的一门非常重要的专业基础课程，在系统软件中占有十分重要的地位。编译原理课程设计是本课程重要的综合实践教学环节，是对平时实验的一个补充。通过编译器相关子系统的设计，使学生能够更好地掌握编译原理的基本理论和编译程序构造的基本方法和技巧，融会贯通本课程所学专业理论知识；培养学生独立分析问题、解决问题的能力，以及系统软件设计的能力；培养学生的创新能力及团队协作精神。2.课程设计任务及要求2.1 设计任务在下列内容中任选其一：1、一个简单文法的编译器前端的设计与实现。2、一个简单文法的编译器后端的设计与实现。3、一个简单文法的编译器的设计与实现。4、自选一个感兴趣的与编译原理有关的问题加以实现，要求难度相当。2.2 设计要求1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小组为单位，先确定设计方案；2、设计系统的数据结构和程序结构，设计每个模块的处理流程。要求设计合理；3、编程序实现系统，要求实现可视化的运行界面，界面应清楚地反映出系统的运行结果；4、确定测试方案，选择测试用例，对系统进行测试；5、运行系统并要通过验收，讲解运行结果，说明系统的特色和创新之处，并回答指导教师的提问；6、提交课程设计报告。3 算法与数据结构3.1算法的总体思想我的课程设计实验基于词法扫描，采用递归下降子程序法的语法分析的方法实现编译器前端。主要部分有词法扫描、语法分析、四元生成、符号表建立等。3.2 词法分析3.2.1 功能词法分析程序又称扫描器，任务有二：（1） 识别单词从用户的源程序中把单词分离出来；（2） 翻译单词把单词转换成机内表示，便于后续处理。词法分析是编译的第一步，其目的是对程序进行扫描，并生成token序列，以便后面进行语法分析。3.2.2 数据结构词法分析中用到的数据结构如下所示：/关键字表private Map keyWordMap = new HashMap();/ 界符表private Map borderMap = new HashMap();/ 标识符表private Map idSignMap = new HashMap();/ 常数表private Map constantMap = new HashMap();/栈private Stack pastword = new Stack(在程序中用哈希表存储关键字表，界符表，常数表，标识符表，其中标示符表和常数表在分析单词过程中生成，关键字表和界符表根据语法规则写成，其中用哈希表中的key来存储单词，用val存储标号，如下图： （a） （b）图3-2-2：关键字表（a）和界符表（b）；3.2.3算法词法分析主要是通过自动机来写的，设计如下：一个简单识别器（有限自动机）的设计，如图3-2-3-2所示:图3-2-3-1 A|B|C|Z|a|b|c|z 0|1|2|3|4|5|6|7|8|9其中 (1)（字母），d（数字），#（源程序结束符）； (2)？（空格，回车，换行），需要过滤掉； ()（泛指单词的后继符）； () .(表示省略了其他界符的处理)。一个简单词法分析器设计，如图3-2-3-2所示： 图 3-2-3-23.3递归下降子程序设计语法3.3.1 功能语法扫描器的功能主要有三：（1） 识别一般源程序检查源程序中是否符合语法规范；（2） 实现if while语句的识别对于特殊语句如if while的识别。（3） 程序的纠错-对于源程序中出现的语法规范错误进行纠错改正并且提示。3.3.2 数据结构public class RecursiveWay String current;/当前词.String kind;/当前词属性，k关键字,i标识符,c常数，界符p.String word;/用于词分析所用的变量.String single = ;/用于词分析所用的的单个字母所用变量static int tures = 0;/ 说明多少个错误。int type2 = 0;/ 类型说明，如果是整形为1，实数型为2，字符型为3WordScanner scanner = new WordScanner();3.3.3程序生成文法：/程序定义 - program - /语句定义 变量说明VD：Variable description - var: ; - , - begin !end while if - beginend;|; - ; - := - do - thenelse-or-and-not|-|() 前后换顺序-w2/算术表达式定义。AE: Arithmetic expression - w0 - w1 -|() 前后换顺序 - |/上面的英文为程序中的函数名或标识符，汉字为注释其中w0: +,-w1: *,/w2: |=|= 3.3.4算法流程图：调用词法分析中的read().得到要分析的词和属性报错并给出正确答案纠错提示不符合语法语法中检查符合语法报错并给出正确答案报错并给出正确答案报错并给出正确答案报错并给出正确答案报错并给出正确答案报错并给出正确答案报错并给出正确答案报错并给出正确答案报错并给出正确答案一直分析到源程序的末尾：并给其他同学负责的部分提供语法是否规范信息报错并给出正确答案报错并给出正确答案报错并给出正确答案报错并给出正确答案报错并给出正确答案报错并给出正确答案报错并给出正确答案3.4 语义分析及四元式生成3.4 .1功能采用递归下降语法制导翻译法,对算术表达式、赋值语句进行语义分析并生成四元式序列。3.4 .2数据结构四元式结构public class Quat private String first = ;private String second = ;private String third = ;private String fourth = ;四元式组：用于增删查改四元式Quats= Quat1, Quat2, Quat3, Quat算法图3-4-3-1说明：scanner是用来读取程序代码；forfour在原来语法分析的基础上插入相应的语义动作：将输入串翻译成四元式序列。在实验中我们只对表达式、赋值语句简单的条件语句if和while进行翻译。语义规则（属性文法）重点是算术表达式，赋值语句和条件语句产生式语 义 规 则i:=E Gen(:=, E.PLACE , ，entry(i) EE1+E2 E.PLACE = Newtemp; Gen(+ , E1.PLACE, E2.PLACE , E.PLACE ) EE1*E2 E.PLACE = Newtemp; Gen(* , E1.PLACE, E2.PLACE , E.PLACE ) E E1 E.PLACE = Newtemp; Gen( , E1.PLACE, , E.PLACE ) E (E1) E.PLACE = E1.PLACE Ei E.PLACE = Entry(i) 产生式语 义 规 则Sif E then M S1 backpatch(E.truelist, M.quad );S.nextlist:=merge(E.falselist, S1.nextlist) M M.quad := nextquad ; N N.nextlist:=makelist(nextquad);Gen( j , , , 0 ) Sif E then M1 S1 N else M2 S2 backpatch(E.truelist, M1.quad );backpatch(E.falselist, M2.quad );S.nextlist:=merge(S1.nextlist, N.nextlist, S2.nextlist) Swhile M1 E do M2 S1 backpatch(S1.nextlist, M1.quad ); Gen( j , , , M1.quad ); backpatch(E.truelist, M2.quad ); S.nextlist:= E.falselist S begin L end S.nextlist:=L.nextlist S A S.nextlist:= makelist() /*空链*/ L S L.nextlist:=S.nextlist LL1； M S backpatch(L1.nextlist, M.quad );L.nextlist:=S.nextlist 这里着重说明对算数表达式的四元分析：这里我们用到了四元式转化为逆波兰式算法： (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。(2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串储存并输出。(4)如果不是数字，该字符则是运算符，此时需比较优先关系。做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。(5) 重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。其中的优先关系我们用一个数组保存char pre = /* 运算符之间的优先级制作成一张表格 */ , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 0, , , , , , , 1这样的并产生四元式根据词法分析的词法三元式判断关键字，这里的关键字是指when，if和while，并产生四元式2布尔表达式规约1判断关键字 这里说明下词法、语法和语义分析的衔接1、词法分析是分析输入代码产生词法三元式的程序。读入代码，并将代码中的单词分解成词法三元式。2、语法分析读入词法三元式，并根据词法三元式对句子进行语法分析。3、语义分析嵌入在语法分析中。根据语法分析中得到的句子类型和语义四元式产生规则，产生四元式。关键代码（由组长刘鑫伟与我一起书写)说明：本人写此编译器代码时对Java知之甚少，所以主要是在组长帮助下，边学边写。3.5符号表3.5.1功能符号表是标识符的动态语义词典，属于编译中语义分析的知识库，符号表可以存储标识符的各种信息，以便以后做处理。3.5.2数据结构1.符号表集合。 /符号表总表。private HashMap synbTable = new HashMap();/ 数组表。private List arrayTable = new ArrayList();/ 结构表。private List strutsTable = new ArrayList();/ 函数表。private List functionTable = new ArrayList();/ 活动记录表。private StackArrayList vallStack = new Stack();private ArrayList globalList = new ArrayList();2.符号表总表元素实体类。public class Synb / 名字，标识符源码。private String name;/ 值(新增项)。private String value;/* * 类型，指针，指向类型表相应项。:i(整型)，r(实型)，c(字符型)，b(布尔型)， a(数组型)， * d(结构型)f(函数)，c(常量)，t(类型)，d(域名)，v,vn,vf(变量，换名形参，赋值形参)。 */private Type type;/ 数据长度。private int length;3.数组表实体类。public class Array / 数组的下界。private String low;/ 数组的上界。private String up;/ 成分类型指针，指向该维数组成分类型(在类型表中的信息)。private String ctp;/ 成分类型的长度，成分类型的数据所值单元的个数。private String clen;4.结构体表实体类。public class Struts / 结构的域名。private String id;/ 区距。private String off;/ 域成分类型指针，指向idk域成分类型(在类型表中的信息)。private String tp;5.函数表。public class Function / 层次号，该过函静态层次嵌套号。private String level;/ 区距，该过函自身数据区起始单元相对该过函值区区头位置。private String off;/ 参数个数，该过函的形式参数的个数。private String fn;/ 参数表，指向形参表。private String entry;/ 入口地址，该函数目标程序首地址(运行时填写)。private String param;6.活动记录表实体类。public class Vall / 从属于哪个活动记录块。private String belongs;/ 局部数据区：用来存放局部变量、内情向量、临时单元。private String name;/ 形式单元：用来存放实参的值或地址。(值)private String value;/ 执行动作。private String action;3.5.3算法符号表的建立是在程序的声明部分，或者说是在函数的声明部分，因此我们只要对声明部分进行处理就可以了。我们发现，声明部分一般都在begin前面，我们利用这个特点，在begin前面进行符号表的建立，在begin和end之间进行四元式的生成。在进行符号表的建立过程中，我们又分了两种情况，一种是含有function的语句，即函数的声明语句，还有一种是普通的语句，即普通的变量和常量的声明语句。具体的实现可以参照void estable() 这个函数。4 程序设计与实现4.1程序流程图图4-14.2程序说明4.2.1程序说明说明：a. 按照功能，分不同功能，分为5个package,分别为piler(编译器入口包)、com.wordScanner(词法扫描器包)，com.syntaxAnalysis(语法分析包)、com.middleCode(中间代码包)、com.signTable(符号表包)。b. 每个package中可能包含若干个Class,实现具体的功能,组织结构如图4-2-1所示。 图 4-2-1c. import包省去，仅显示package部分，以显示组织结构。4.2.2程序源代码package piler;/* * 编译器前端。 * author 刘鑫伟 * */public class Compiler WordScanner wordScanner = new WordScanner();RecursiveWay recursiveWay = new RecursiveWay();public void excute() recursiveWay.recursive();if (recursiveWay.getTures() = 0) ForFour forFour = new ForFour();SignTable signTable = new SignTable();forFour.forreadWord();signTable.display();package com.wordScanner;/* * 词法扫描器 * * author Gao, Bayi; Liu, Xinwei */public class WordScanner / 词表路径。public static final String TABLE_PATH = resource/table.txt;/ 代码路径。public static final String CODE_PATH = resource/code.txt;/ 待扫描代码。private String code = ;/ token。private String token = ;/ 关键字表。private Map keyWordMap = new HashMap();/ 界符表。private Map borderMap = new HashMap();/ 标示符表。private Map idSignMap = new HashMap();/ 常数表。private Map constantMap = new HashMap();private Stack pastword = new Stack();readCodeFromFile();writeToMap();scan(code);/* * 从文本中读取代码。 */public void readCodeFromFile() try File myFile = new File(CODE_PATH);FileReader fileReader = new FileReader(myFile);BufferedReader reader = new BufferedReader(fileReader);String line = null;while (line = reader.readLine() != null) code = code + line + ;reader.close(); catch (Exception ex) ex.printStackTrace();/* * 将词表写入Map。 */public void writeToMap() try File myFile = new File(TABLE_PATH);FileReader fileReader = new FileReader(myFile);BufferedReader reader = new BufferedReader(fileReader);String line = null;String kind = null;while (line = reader.readLine() != null) if (KeyWord.equals(line) | Border.equals(line) kind = line; else if (KeyWord.equals(kind) String splits = line.split( );keyWordMap.put(splits0, splits1); else if (Border.equals(kind) String splits = line.split( );borderMap.put(splits0, splits1);reader.close(); catch (Exception ex) ex.printStackTrace();/* * 扫描代码。 * param code * 代码字符串。 */public void scan(String code) String word; / 当前单词。char start; / 开始字符。char ch; / 当前字符。while (!.equals(code) int i = 0;while (code.indexOf( ) = 0) code = code.substring(1);if (.equals(code) break;start = code.charAt(0);if (start = A & start = a & start = a & ch = A & ch = code.length() break;ch = code.charAt(i);word = code.substring(0, i); / 截取字符串/ 判断当前单词在哪个表中if (keyWordMap.containsKey(word) token = token + ; else if (idSignMap.containsKey(word) token = token + ; else idSignMap.put(word, 0 + (idSignMap.size() + 1);token = token + ; else if (Character.isDigit(start) int pointerTimes = 0;ch = code.charAt(0);while (Character.isDigit(ch)| (ch = .) & pointerTimes = 0) if (ch = .) pointerTimes+;i = i + 1;if (i = code.length() break;ch = code.charAt(i);word = code.substring(0, i);if (constantMap.containsKey(word) token = token + ; else constantMap.put(word, 0 + (constantMap.size() + 1);token = token + ; else start = code.charAt(0);if (start = | start = =| start = :) ch = code.charAt(1);String signAdd = + start + ch;if (borderMap.containsKey(signAdd) i = i + 2;token = token + ; else i = i + 1;token = token + ; else i = i + 1;token = token + ;code = code.substring(i);token = token + ;/* * 读单词，给语法分析提供使用。 * * param code * 待识别的程序。 * return 当前单词。 */public String readWord() String word = ; / 当前单词。char start; / 开始字符。char ch; / 当前字符。int i = 0;while (code.indexOf( ) = 0) code = code.substring(1);if (.equals(code) return ;start = code.charAt(0);if (start = A & start = a & start = a & ch = A & ch = code.length() break;ch = code.charAt(i);word = code.substring(0, i); else if (Character.isDigit(start) int pointerTimes = 0;ch = code.charAt(0);while (Character.isDigit(ch) | (ch = .) & pointerTimes