编译原理课程设计报告

程设计报告

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

班级：计算机1308班

组长学号：20134019

组长姓名：刘鑫伟

指导教师：张俐

设计时间：2015年12月

1

设计分工

组长学号及姓名：20134019 刘鑫伟分工：符号表，搭建框架。

组员1学号及姓名：20134010 高八一分工：词法分析，Token。

组员2学号及姓名：20134026 肖辉分工：文法，语法分析。

组员3学号及姓名：20134029 袁宵分工：语义分析及四元式生成。

2

摘要

编译原理是计算机科学与技术专业一门重要的专业课, 它具有很强的理论性与实践性，目的是系统地向学生介绍编译系统的结构、工作原理以及编译程序各组成部分的设计原理和实现技术，在计算机本科教学中占有十分重要的地位。计算机语言之所以能由单一的机器语言发展到现今的数千种高级语言，就是因为有了编译技术。编译技术是计算机科学中发展得最迅速、最成熟的一个分支，它集中体现了计算机发展的成果与精华。本课设是词法分析、语法分析、语义分析的综合，外加上扩展任务中间代码的优化和目标代码的生成，主要是锻炼学生的逻辑思维能力，进一步理解编译原理的方法和步骤。

我们编译课程设计做的是一个简单的编译器的前端。我们用了递归下降子程序法实现这个编译器的前端。

我们参考了了老师提供的简单文法，然后完整的程序生成文法，还有四元式生成文法。在此基础上我们还做了处理赋值语句、if-else 语句、while语句的语法分析和四元式的生成，这样我们就设计完了四元式的生成。然后，我们又设计了符号表。

其中的特色点有：语法分析阶段能够检测出错误，并且能指出错误在哪一行，具体为什么错误；表示式的四元式采用了逆波兰式的方法；同时像if- while, 我们的编译器能判断其中的boolean表达式的真值，从而能采用正确的逻辑得出正确的结果；活动记录表阶段能够指出具体采取了什么动作，具体代码。

关键词：编译原理，前端，递归下降子程序法，四元式，符号表

3

目录

摘要I

1 概述6

2 课程设计任务及要求8 2.1 设计任务8

2.2 设计要求8

3 算法与数据结构9

3.1算法的总体思想（流程）9 3.2 词法扫描模块 9

3.2.1 功能9

3.2.2 数据结构9 3.2.3 算法11 3.3 语法分析模块12 3.3.1功能12

3.3.2 数据结构12 3.3.3算法13 3.3.4算法流程图14

3.4 语义分析四元式分析模块20 3.3.1功能20

3.3.2 数据结构20 3.3.3算法21

3.5 符号表分析模块29

3.3.1功能29

3.3.2 数据结构29 3.3.3算法32

4

4. 程序设计与实现33

4.1 程序流程图33 4.2 程序说明33

4.3 实验结果132

5. 结论134

6. 参考文献。135

7. 收获、体会和建议。135

5

1.概述

编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。编译原理是计算机专业设置的一门重要的专业课程。虽然只有少数人从事编译方面的工作，但是这门课在理论、技术、方法上都对学生提供了系统而有效的训练，有利于提高软件人员的素质和能力。由于时间和同学们的水平有限，故本实验只涉及到了词法分析，语法分析，及中间代码的四元式生成和符号表。具体概述介如下：

1.词法分析：在这个阶段编译器实际阅读源程序（通常以分析程序字符流的形式表示）。扫描程序执行词法分析注释树符号表：它将字符序列收集到称作记号错误处的有意义单元中，记号同自然语言，如英源代码理器语中的字词相似。因此可以认为扫描程序执行与优化程序拼写相似的任务。本实验的词法分析程序用于生成Token序列。

2.语法分析：该程序从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法分析，这与自然语言中句子的语法分析类似。语法分析定义了程序的结构元素及其关系。其任务是识别和处理比单词更大的语法单位。本实验用于指出程序设计语言中的表达式、各种说明和语句乃至全部源程序其中的语法错误；必要时，可生成内部形式，便于下一阶段处理。

3.中间代码：根据中间代码的类型和优化的类型，该代码可以是文本串的数组、临时文本文件或是结构的连接列表。对于进行复杂优化的编译器。由于同学们水平有限，我们只做了四元式的生成。

6

4.语义分析：程序的语义就是它的“意思”，它与语法或结构不同。程序的语义确定程序的运行，但是大多数的程序设计语言都具有在执行之前被确定而不易由语法表示和由分析程序分析的特征。这些特征被称作静态语义，而语义分析程序的任务就是分析这样的语义。一般的程序设计语言的典型静态语义包括声明和类型检查。由于同学们水平有限，我们只做了其中的符号表部分。

编译原理课程兼有很强的理论性和实践性，是计算机专业的一门非常重要的专业基础课程，在系统软件中占有十分重要的地位。编译原理课程设计是本课程重要的综合实践教学环节，是对平时实验的一个补充。通过编译器相关子系统的设计，使学生能够更好地掌握编译原理的基本理论和编译程序构造的基本方法和技巧，融会贯通本课程所学专业理论知识；培养学生独立分析问题、解决问题的能力，以及系统软件设计的能力；培养学生的创新能力及团队协作精神。

7

2.课程设计任务及要求

2.1 设计任务

在下列内容中任选其一：

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

2、一个简单文法的编译器后端的设计与实现。

3、一个简单文法的编译器的设计与实现。。

4、自选一个感兴趣的与编译原理有关的问题加以实现，要求难度相当。

2.2 设计要求

1、在深入理解编译原理基本原理的基础上，对于选定的题目，以小组为单位，先确定设计方案；

2、设计系统的数据结构和程序结构，设计每个模块的处理流程。要求设计合理；

3、编程序实现系统，要求实现可视化的运行界面，界面应清楚地反映出系统的运行结果；

4、确定测试方案，选择测试用例，对系统进行测试；

5、运行系统并要通过验收，讲解运行结果，说明系统的特色和创新之处，并回答指导教师的提问；

6、提交课程设计报告。

8

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<>();

// 常数表

9

10 private Map constantMap = new HashMap<>();

//栈

privateStack 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所示：

11

12

图3-2-3-2

3.3递归下降子程序设计语法

3.3.1 功能

语法扫描器的功能主要有三：

（1） 识别一般源程序——检查源程序中是否符合语法规范；

（2） 实现if while 语句的识别——对于特殊语句如if while 的识别。

（3） 程序的纠错----对于源程序中出现的语法规范错误进行纠错改正并且提示。

3.3.2 数据结构

publicclassRecursiveWay

{

String current;//当前词.

String kind;//当前词属性，k关键字,i标识符,c常数，界符p.

String word;//用于词分析所用的变量.

String single = "";//用于词分析所用的的单个字母所用变量

staticint tures = 0;// 说明多少个错误。

int type2 = 0;// 类型说明，如果是整形为1，实数型为2，字符型为3

WordScanner scanner = new WordScanner()

}

3.3.3程序生成文法：

//程序定义

<1程序program> -> program <2ID 标识符后有读取><3分程序deputyProgram>

<3 分程序deputyProgram> -><10 变量说明VD><4 复合语句compoundStatement>

//语句定义变量说明VD：Variable description

<10变量说明VD> -> var<5 标识符表IDTable>: <6 类型type>;

<5 标识符表IDTable> -><2 标识符ID>{,<2 标识符ID>}

<4 复合语句compoundStatement> -> begin {!end while if <7 语句表statementTable>}

<8 compoundStatement1> -> begin<7 语句表statementTable>end;|<9 赋值语句assignmentStatement>;

<7 语句表statementTable> -><9 赋值语句

assignmentStatement>{;<9 赋值语句assignmentStatement>}

13

<9 赋值语句assignmentStatement> -><2 标识符ID> := <18 算术表达式AE>

<11 while>-><12 or> do <8 compoundStatement1>

<13 if> -><12 or>then<8 compoundStatement1>else<8 compoundStatement1>

<12 or>-><14 and>{or<14 and>}

<14 and>-><15 not>{and<15 not>}

<15 not>->not<16 booleans>|<16 booleans>

<16 booleans>-><17 boolTerm>|(<12 or>) 前后换顺序

<17 boolTerm>-><18 算术表达式AE>w2<18 算术表达式AE>

//算术表达式定义。AE: Arithmetic expression

<18 算术表达式AE> -><19 项term>{w0<19 项term>}

<19 项term> -><20 因子factor>{w1<20 因子factor>}

<20 因子factor> -><21 算术量quantity>|(<18 算术表达式AE>) 前后换顺序

<21 算术量quantity> -><2 标识符ID>|<22 常数constant>

//上面的英文为程序中的函数名或标识符，汉字为注释

其中

w0: +,-

w1: *,/

w2: >|<|==|<=|>=

3.3.4算法流程图：

14

16

18

19

并给其他同学负责的部分提供语法是否规范信息

3.4 语义分析及四元式生成

3.4 .1功能

采用递归下降语法制导翻译法,对算术表达式、赋值语句进行语义分析并生成四元式序列。

3.4 .2数据结构

四元式结构

public class Quat {

private String first = " ";

private String second = " ";

private String third = " ";

private String fourth = " ";

}

四元式组：用于增删查改四元式

20

Quats={ Quat1, Quat2, Quat3, Quat4....}

3.4.3算法

图3-4-3-1

说明：scanner是用来读取程序代码；forfour在原来语法分析的基础上插入相应的语义动作：将输入串翻译成四元式序列。在实验中我们只对表达式、赋值语句简单的条件语句if和while进行翻译。

21

本文来源：https://www.bwwdw.com/article/f28q.html