朱航宇-20112878-编译原理合设计
编译原理合设计指导教师：李宏芒
专业班级：信安11-1
姓名：朱航宇
学号：20112878
一．课程设计目的
《编译原理》是计算机专业的一门重要的专业课程，其中包含大量软件设计思想。大家通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要的意义。
二．课程设计内容
（12,13题：12题 DFA 状态最少化的程序实现和13题把NFA确定化为DFA 的算法实现，合并为一题，将NFA确定化为DFA，再将DFA化简即最小化。）我在选择课程设计题目时，只选择了12题DFA的最小化。但由于12题工作量较小同时为了提高我的编程能力我将13题NFA确定化为DFA，将这两题合并为一题，即NFA确定化到最小化的实现。NFA的确定化和DFA的最小化主要是为了更好地使用状态转换图构造词法分析程序和词法分析程序的自动生成。设计并实现将NFA确定化为DFA的子集构造算法以及DFA的最小化，从而更好地理解有限自动机之间的等价性，掌握词法分析器自动产生器的构造技术。
三．设计要求
构造一程序，实现：将给定的NFA M(其状态转换矩阵及初态、终态信息从键盘输入)，确定化为DFA M’。（要先实现ε-CLOSURE函数和Ia函数）。输出DFA M’(其状态转换矩阵及初态、终态信息输出到屏幕上)。然后将由确定化后的的DFA M的有限状态集S划分成若干互不相交的子集，使得：任何不同的两个子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的（要利用Ia 函数，但并不需要构造ε-CLOSURE函数，因这是DFA）。输出化简后的DFA M’(其状态转换矩阵及初态、终态信息输出到屏幕上)。
四．设计思路
4.1 NFA确定化为DFA
1．非确定有限自动机NFA
一个非确定有限自动机（NFA）M是一个五元式M=（S，∑，δ,S0，F）
其中(1)S是一个有限集，它的每一个元素称为一个状态；
(2)∑是一个有穷字母表，它的每一个元素称为一个输入字符；
(3)δ是一个从S×∑*到S的子集映照；
(4)S0属于∑，是一个非空初态集；
(5)F属于S，是一个终态集（可空）。
显然，一个含有m个状态和n个输入字符的NFA可表示成如下的状态转换图：该图含有m个状态结点，每个节点可射出若干条箭弧与别的结点相连接，每
条弧用∑*中的一个字（不一定要相同而且可以是空字）做标记（称为输入字），整张图至少含有一个初态结点以及若干个（可以是0个）终态结点。对于∑*
中的任何一个字a，若存在一条从某一初态结点到某一终态结点的通路，且
这条通路上所有弧的标记字依序连接城的字（忽略那些标记为空字ε的弧）
等于啊，则称a可为NFA M所识别。若M的某些结点既是初态结点又是终态
结点，后者存在一条弧从某个出台节点到某个终态结点的ε通路，则空字ε
可为M所接受。
2．确定有限自动机DFA的最小化
一个确定有限自动机（NFA）M是一个五元式M=（S，∑，δ,s0，F）
其中(1)S是一个有限集，它的每一个元素称为一个状态；
(2)∑是一个有穷字母表，它的每一个元素称为一个输入字符；
(3)δ是一个从S×∑到S的单值部分映射。δ(s,a)意味着：当现行状
态为s、输入字符为a时，将转入下一个状态s’,s’是s的后继状态；
(4)s0∈S，是唯一的初态；
(5)F属于S，是一个终态集（可空）。
显然，一个DFA可用一个状态转换矩阵表示，该矩阵的行表示状态，列表时
输入字符，矩阵元素表示δ(s,a)的值。一个DFA也可以表示成一张状态转换
图，假设DFA M含有m个状态和n个输入字符，那么，该图含有m个状态结
点，每个节点最多有n条箭弧与别的结点相连接，每条弧用∑中的一个字做
标记，整张图含有唯一的一个初态结点和若干个（可以是0个）终态结点。
对于∑中的任何一个字a，若存在一条从某一初态结点到某一终态结点的通
路，且这条通路上所有弧的标记字依序连接城的字等于啊，则称a可为DFA M
所识别。若M的某些结点既是初态结点又是终态结点，后者存在一条弧从某
个出台节点到某个终态结点的ε通路，则空字ε可为M所接受。DFA M所能
识别的字的全体记为L(M)。
3．NFA与DFA的联系
在非确定的有限自动机NFA中，由于某些状态的转移需从若干个可能的后续
状态中进行选择，故一个NFA对符号串的识别必然是一个试探的过程。这种
不确定性识别过程带来的反复，无疑会影响到FA的工作效率。而DFA则是确
定的，将NFA转化为DFA大大提高工作效率，因此将NFA转化为DFA是有其
一定必要的。程序中采用子集法来实现NFA确定化为DFA。
4.2 DFA的最小化
一个有限自动机M的化简是指：寻找一个状态数比M少的DFA M’，使得L(M)=L(M’).假定s和t是M的两个不同状态，如果分别从状态s和t出发能读出同样的某个字w而停于终态，则称s和t是等价的。如果DFA M的两个状态s
和t不等价，则称这两个状态是可区别的。一个DFA M的状态最少化过程旨在将M的状态集分割成一些不相交的子集，使得任何不同的两个字集中的状态是可区别的，而同一子集中的任何两个状态都是等价的。最后，在每个自己中选出一个代表，同时消去其他等价状态。又被删除的状态射出的弧也被删去，但是有保留下来的状态射出的弧是要全部保留的。
五．设计的基本原理
5.1总体方案设计
我的程序总共分三大模块，一是有限自动机状态转换图的结构和有限自动机状态信息的输入输出部分；二是用子集构造算法实现NFA确定化为DFA，这里面又涉及到ε_Closure(I)和转换函数Move(I,a)的实现和新生成的状态的重命名问题以及新的状态转换关系的建立；三是DFA的最小化，这里面包括等价状态的划分，等价状态的划分又涉及到终态结点和非终态结点的区分，划分之后等价状态的重命名和新的状态转换关系的建立。总体模块设计方案如下图所示：
5.2各模块设计
1．有限自动机状态转换结构的定义和状态信息的输入输出
有限状态机的状态结点，边和终结符（即输入字符）均定义为字符串，利用C++标准模板库string中的函数来实现定义和后续操作，以方便实现和简化程序。具体如下程序片段：
string NODE; //结点集合
string CHANGE; //终结符集合
int N; //NFA边数
struct edge
{ //状态图的边，包含一条边的起点，终点和终结符
string first;
string change;
string last;
};
struct chan
{ //状态转换矩阵集合
string ltab; //状态子集I
string jihe[MAXS]; //状态子集Ix
};
有限自动机状态信息是从键盘输入有限自动机的各边信息，包括边的起点初态结点，标记字符即输入字符，终点状态结点；有限自动机状态信息的输出主要是将有限自动机的状态转换矩阵输出到屏幕上，另外还包括一些提示信息，对其空格等。具体见源程序。
2．NFA确定化为DFA，采用子集构造算法
(1) ε_Closure(I)的构造
假定I是NFA M的状态子集,状态集合I的ε闭包的算法ε_Closure(I),
(a)若s∈I，则I∈ε_Closure(I)
(b)若s∈I,那么从s出发经任意条ε弧而能到达的任何状态
s’∈ε_Closure(I)
(2) 转换函数Move(I,a)定义为：a∈∑,定义Ia=ε_Closure(J)，其中J是
那些可从I中的某一状态结点出发经过一条a弧而到达的状态结点的全
体。
(3) 假定∑={ a1 , … , ak },构造一张表，此表的每一行含有k+1列。置该表
的首行首列为ε_Closure(X)。一般而言，如果某一行的第一列的状态子
集已经确定，记为I，那么置该行的i+1列为Iai(i=1, … ,k)。然后检查该
行上的所有状态子集，看它们是否已在表的第一列出现，将未曾出现者
填入到后面空行的第一列，为方便比较，在构造状态子集过程中，可对
子集中的元素进行排序。重复上述过程，直到出现在第i+1(i=1, … ,k)
列上的所有状态子集都已经在第一列上出现。因为M的状态子集的个数
是有限的，所以上述过程必定在有限步内终止。按照构造此表的方法思
想用程序实现有限自动机M状态子集的构造，然后对上表中第一列的个
各状态子集重命名得到一个新的状态转换矩阵，该状态装换矩阵对应一个与NFA M等价的DFA M’。
例如下图为一个非确定有限自动机的状态转换图，终态为Y
对上表中第一列的各状态子集重命名
{X,5,1} = 0；5,3,1} = 1；{5,4,1} = 2；{5,3,1,2,6,Y} = 3；{5,4,1,6,Y} = 4；{5,4,1,2,6,Y} = 5；{5,3,1,6,Y} = 6
则重命名之后上表转化为如下表的状态转换矩阵，该转换矩阵对
该表的状态转换矩阵对映一个与上述NFA M等价的未化简的DFA M’，其中终态为3,4,5,6。其状态转换图如下所示
3．DFA的最小化，采用等价状态划分的方法
对DFA的化简任然要用到上述的Ia函数，对DFA M的状态集S进行划分的步骤是：首先把S的终态和非终态分开，分成两个子集，形成基本划分∏。假定到某个时候∏已含m个子集，记∏={I(1),I(2),…,I(m)},并且属于不同自己的状态是可去别的。检查∏中的每个I(i)看能否进一步划分。对于某个I(i)，令I(i)={q1,q2,…,qk}，若存在一个输入字符a使得Ia(i)不全包含在现行∏的某一子集I(i)中，就将I(i)一分为二。假定状态s1和s2经a弧分别到达状态t1和t2，而t1和t2属于现行∏的两个不同子集，那就将I(i)分成两半，使得一半含有s1，另一半含有s2。由于t1和t2是可区别的，因此字aw将状态s1和s2区别开来。一般地，若Ia(i)落入现行∏中N个不同子集，则应将I(i)划分成N个不相交的组，使得每个组J的Ja都落入现行∏的同一子集，这样形成新的划分。重复上述过程，直至划分中所含的子集数不再增长为止。至此，∏中的每个子集已不可再分，也即每个字集中的状态都是相互等价的，而不同子集的状态则是可以相互区别的。
对于上述划分∏中的子集重命名，然后删除无用状态（即从初态开始永远到达不了的那些状态），则得到最简的DFA M’。上面有NFA M确定化所得的DFA M 形成一个含有四个状态子集的划分∏={{0}，{3,4,5,6}，{1}，{2}}，对∏中的状态进重命名得{0}=A，{3,4,5,6}=B，{1}=C，{2}=D。其中终态为B。
六．程序测试
测试结果如下所示，由于篇幅所限，下面的截图只给出了其中一组数据的测试结果：
七.总结
通过亲自动手编程时出现了子集法地实现了NFA确定化为DFA的过程，然后通过等价状态划分法成功地将所得DFA化简实现了DFA的最小化。同时也明白了，真正的编程需要足够强的逻辑分析能力和耐心，也认识到了自身的不足，还需要加强。
八.程序清单
（见附件）
编译原理课程设计
《编译原理》课程设计大纲 课程编号： 课程名称：编译原理/Compiler Principles 周数/学分：1周/1学分 先修课程：高级程序设计语言、汇编语言、离散数学、数据结构 适用专业：计算机科学与技术专业、软件工程专业 开课学院，系或教研室：计算机科学与技术学院 一、课程设计的目的 课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。 要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写。 设计时间： 开发工具： （1） DOS环境下使用Turbo C； （2） Windows环境下使用Visual C++ 。 （3） 其它熟悉语言。 二、课程设计的内容和要求 设计题一：算术表达式的语法分析及语义分析程序设计。 1.目的
通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词 法检查和分析。 2.设计内容及要求： 算术表达式的文法： 〈无符号整数〉∷＝ 〈数字〉{〈数字〉} 〈标志符〉∷＝ 〈字母〉{〈字母〉｜〈数字〉} 〈表达式〉∷＝ [＋｜－]〈项〉{〈加法运算符〉〈项〉} 〈项〉∷＝ 〈因子〉{〈乘法运算符〉〈因子〉} 〈因子〉∷＝ 〈标志符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’ 〈加法运算符〉∷＝ ＋｜－ 〈乘法运算符〉∷＝ ＊｜／ （1） 分别选择递归下降法、算符优先分析法（或简单优 先法）完成以上任务，中间代码选用逆波兰式。 （2） 分别选择LL（1）、LR法完成以上任务，中间代码选 用四元式。 （3） 写出算术表达式的符合分析方法要求的文法，给出 分析方法的思想，完成分析程序设计。 （4） 编制好分析程序后，设计若干用例，上机测试并通 过所设计的分析程序。 设计题二：简单计算器的设计 1．目的 通过设计、编制、调试一个简单计算器程序，加深对语法及语 义分析原理的理解，并实现词法分析程序对单词序列的词法检 查和分析。 2.设计内容及要求 算术表达式的文法：
编译原理实验指导
编译原理实验指导 实验安排： 上机实践按小组完成实验任务。每小组三人，分别完成TEST语言的词法分析、语法分析、语义分析和中间代码生成三个题目,语法分析部分可任意选择一种语法分析方法。先各自调试运行，然后每小组将程序连接在一起调试，构成一个相对完整的编译器。 实验报告： 上机结束后提交实验报告，报告内容： 1．小组成员； 2．个人完成的任务； 3．分析及设计的过程； 4．程序的连接； 5．设计中遇到的问题及解决方案； 6．总结。
实验一词法分析 一、实验目的 通过设计编制调试TEST语言的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 二、实验预习提示 1．词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示 成以下的二元式(单词种别码，单词符号的属性值)。 2．TEST语言的词法规则
编译原理课程设计报告(一个完整的编译器)
编译原理程序设计报告 一个简单文法的编译器的设计与实现专业班级：计算机1406班 组长姓名：宋世波 组长学号： 20143753 指导教师：肖桐 2016年12月
设计分工 组长学号及姓名：宋世波20143753 分工：文法及数据结构设计 词法分析 语法分析（LL1） 基于DAG的中间代码优化 部分目标代码生成 组员1学号及姓名：黄润华20143740 分工：中间代码生成(LR0) 部分目标代码生成 组员2学号及姓名：孙何奇20143754 分工：符号表组织 部分目标代码生成
摘要 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译是从源代码（通常为高阶语言）到能直接被计算机或虚拟机执行的目标代码（通常为低阶语言或机器语言）的翻译过程。 一．编译器的概述 1.编译器的概念 编译器是将便于人编写，阅读，维护的高级计算机语言翻译为计算机能解读、运行的低阶机器语言的程序。编译器将原始程序作为输入，翻译产生使用目标语言的等价程序。源代码一般为高阶语言如Pascal、C++、Java 等，而目标语言则是汇编语言或目标机器的目标代码，有时也称作机器代码。 2．编译器的种类 编译器可以生成用来在与编译器本身所在的计算机和操作系统（平台）相同的环境下运行的目标代码，这种编译器又叫做“本地”编译器。另外，编译器也可以生成用来在其它平台上运行的目标代码，这种编译器又叫做交叉编译器。交叉编译器在生成新的硬件平台时非常有用。“源码到源码编译器”是指用一种高阶语言作为输入，输出也是高阶语言的编译器。例如: 自动并行化编译器经常采用一种高阶语言作为输入，转换其中的代码，并用并行代码注释对它进行注释（如OpenMP）或者用语
编译原理课程设计
编译原理课程设计报告 课题名称： C-语言编译器设计（scanner和parser） 提交文档学生姓名： 提交文档学生学号： 同组成员名单：无 指导教师姓名：金军 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间： 2011年 6 月 17 日
1.课程设计目标 设计C-Minus编译器分为scanner和parser两个部分。scanner主要作用是对目标代码进行扫描，列出关键字，变量等内容；parser主要对语法进行分析并生成语法树。 2.分析与设计 ●实现方法：代码用C语言编译而成。其中scanner为手工实现，主要采用switch-case结构实现 状态转换；parser部分采用递归下降分析方法实现。 ●扫描器：C-的词法如下： 1、语言的关键字：i f el se i nt return void while 2、专用符号：+ - * /< <= > >= == != =; , ( ) [ ] { } /* */ 3、其他标记是变量（ID）和数字（NUM），通过下列正则表达式定义： ID = letter letter* NUM = di git digi t* letter = a|..|z|A|..|Z digi t = 0|..|9 4、空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM关键字 5. 注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在 标记内)上，且可以超过一行。注释不能嵌套 其DFA图如下：
分析器：以下为C-的语法规则BNF:
编译原理课程设计
编译原理课程设计 实验名称：C-语言词法分析器的手工构造C-语言词法分析器的lex生成 C-语言语法分析器的手工构造 学生姓名：刘恺丽 学生学号： 0943041336 指导教师姓名：于中华
实验一：C-语言词法分析器的手工构造 一、实验目的及意义 1.理解C-语言的词法特点，并能构造各种token的正则表达式； 2.掌握将正则表达式转换为DFA的方法； 3.学会设计C-语言手动生成词法分析器的数据类型和数据结构。 二、实验环境 1.操作系统：Window XP/Windows 7； 2.开发环境：Microsoft Visual C++ 6.0。 三、算法分析与设计 1.C-语言的词法规则 (1)关键字 else if int return void while (2)特殊符号 + - * / <<= >>= == != = ; , ( ) [ ] { } /* */ (3)其它token（区分大小写） ID = letter letter* NUM = digit digit* letter = a|…|z|A|...|Z Digit = 0|…|9 (4)空白符号 空白 \n \t (5)注释 由标记符号/*…*/标记起来的部分。 2.C-语言的词法正则表达式 digit [0-9] number {digit}+ letter [a-zA-Z] identifier {letter}+ newline \n whitespace [" "\t]+
3.C-语言的DFA 4.重要数据类型设计 （1）token类型用枚举量分为以下几个 typedefenum {ENDFILE,ERROR, ELSE,IF,INT,RETURN,VOID,WHILE, ID,NUM, PLUS,MINUS,TIMES,OVER,LT,LTE,RT,RTE,EQ,NE,ASSIGN,SEMI,COMMA,LPAR EN,RPAREN,LZ,RZ,LD,RD,LC,RC }TokenType; （2）DFA9个状态 typedefenum {START,INNE,INEQ,INLT,INRT,INID,INNUM,INOVER,INCOMMENT1,INCOM MENT2,DONE} StateType; 四、代码实现 1.查找保留字 函数TokenTypeS FindResvd (char * s)
编译原理实验指导书
《编译原理》课程实验指导书 计算机学院编 ２００７年９月
实验一 C语言子集编译程序 一、实验目的 用C语言对一个C语言的子集编制一个一遍扫描的编译程序，以加深对编译原理的理解，掌握编译程序的实现方法和技术。 1．设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 2．编制一个递归下降分析程序，并对C语言的简单子集进行分析。 3．通过上机实习，加深对语法制导翻译原理的理解，掌握将语法分析所识别的语法成分变换中间代码的语义翻译方法。 二、实验要求、内容及学时 词法分析部分：2学时 （一）待分析的C语言子集的词法： 1．关键字 main if else int return void while 所有关键字都是小写。 2．专用符号 = + - * / < <= > >= == != ; : , { } [ ] ( ) 3.其他标记ID和NUM 通过以下正规式定义其他标记： ID→letter(letter|digit)*NUM→digit(digit)* letter→a|…|z|A|…|Z digit→0|…|9 4.空格由空白、制表符和换行符组成 空格一般用来分隔ID、NUM、专用符号和关键字，词法分析阶段空格通常被忽略。各种
（二）词法分析程序的功能： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。其中， syn 为单词类别码。 token 为存放的单词自身字符串。 sum 为整型常量。 具体实现时，可以将单词的二元组用结构进行处理。 例如：对源程序 main() { int i=10; while(i) i=i-1; } 的源文件，经词法分析后输出如下序列： (1,main) (26,() (27,)) (30,{) (2,int) (10,i) (21,=) (20,10) (34,;) (7,while) (26,() (10,i) (27,)) (10,i) (21,=) (10,i) (23,-) (20,1) (34,;) (31, }) （三）词法分析程序主要算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 1．主程序示意结构图（如下）： 注：
CMinus词法分析和语法分析设计编译器编译原理课程设计报告书
编译原理课程设计报告 课题名称：C- Minus词法分析和语法分析设计 提交文档学生姓名：X X X 提交文档学生学号：XXXXXXXXXX 同组成员名单：X X X 指导教师姓名：X X 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间：2015年6月10日
1.课程设计目标 实验建立C-编译器。只含有扫描程序（scanner）和语法分析（parser）部分。 2.分析与设计 C-编译器设计的整体框架，本实验实现扫描处理和语法分析程序（图中粗黑部分）。 2.1 、扫描程序scanner部分 2.1.1系统设计思想 设计思想：根据DFA图用switch-case结构实现状态转换。 惯用词法：
①语言的关键字：else if int return void while ②专用符号：+ - * / < <= > >= == != = ; , ( ) [ ] { } /* */ ③其他标记是ID和NUM，通过下列正则表达式定义： ID = letter letter* NUM = digit digit* letter = a|..|z|A|..|Z digit = 0|..|9 大写和小写字母是有区别的 ④空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM 关键字。 ⑤注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套 scanner的DFA
说明：当输入的字符使DFA到达接受状态的时候，则可以确定一个单词了。初始状态设置为START，当需要得到下一个token时，取得次token的第一个字符，并且按照DFA与对此字符的类型分析，转换状态。重复此步骤，直到DONE为止，输出token类型。当字符为“/”时，状态转换为SLAH再判断下一个字符，如果为“*”则继续转到INCOMMENT，最后以“*”时转到ENDCOMMENT状态，表明是注释，如果其他的则是字符停滞于当前字符，并且输出“/”。 2.1.2程序流程图
编译原理课程设计
先简要分析一下语法分析的大致流程： 当有句子要进行处理时，首先要对其进行词法分析来分解出该句子中的每个符号，然后将该句子按照算符优先算法压入归约栈中，如果可以顺利归约，则说明这是一个合法的句子，否则该句子非法。 这里有一个需要考虑的地方，就是如何进行归约。由于文法已经给定，所以我们考虑设计一个文法表，文法表中的内容就是可归约串的种别码的顺序，比如v=E可以表示为9,1,13。这样的话当我们要进行一次归约时，只用按顺序存储最左素短语中符号的种别码，然后拿这个种别码序列与文法表进行匹配，就可知道当前归约需要执行哪些操作。 还有一点需要注意，就是如何对一个表达式进行求值。这里需要我们设计一个二元组的变量名表，这个变量名表可以根据变量的名称来返回变量的数据。变量名表的具体设计见详细设计部分。 由于是简化分析，所以这个程序只考虑整数的处理。 有了上面的分析，可以构造出算符优先分析算法的流程图，如下图所示。
详细设计 （1）词法分析部分 由于词法分析的内容在课程设计1中已经介绍，并且这次的状态转换图与课程设计1中的非常相似，所以这里就不过多介绍。（2）优先关系表 在程序中我们用一个二维数组priTable[][]来存储算符间的优先关系。priTable[a][b]=1表示a>b; 。priTable[a][b]=0表示a=b; 。priTable[a][b]=-1表示a 实验二语法分析 一、实验目的： 设计MiniC的上下文无关文法，利用JavaCC生成调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、语法分析器: 按照MiniC语言的语法规则检查词法分析输出的记号流是否符合这些规则，并根据这些规则所体现出的语言中的各种语法结构的层次性。把规则写入到JavaCC的.jjt文件中，可以生成树状的层次结构。 三、JavaCC: 在JavaCC的文法规范文件中，不仅可以描述语言的语法规范，而且可以描述词法规范，本次实习中，利用JavaCC以MiniC语言构造一个不含语义分析的编译器前端，包括词法分析、语法分析，并要考虑语法分析中的错误恢复问题。通过使用JavaCC, 可以体会LL(k)文法的编写特点，掌握编写JavaCC文法规范文件的方法。 内容：利用JavaCC生成一个MiniC的语法分析器； 要求： 1.用流的形式读入要分析的C语言程序，或者通过命令行输入源程序。 2.具有错误检查的能力，如果有能力可以输出错误所在的行号，并简单提示 3.如果输入的源程序符合MiniC的语法规范，输出该程序的层次结构的语法树本次实习仅完成以下语法范畴的语法分析： 1. 写出一个源程序中仅包含if…else, else语句的语法分析。要求能分析其自身 嵌套. 其他语句可简化处理 2. 写出一个源程序中仅包含for语句的语法分析。要求能分析其自身嵌套， 其他语句可简化处理 3. 写出一个源程序中仅包含while语句的语法分析。要求能分析其自身嵌套。 其他语句可简化处理 4. 写出一个源程序中包含上面的12或者13或者23或者123语句的语法分析。 要求能分析除其自身嵌套外，还包括相互嵌套。其他语句可简化处理 具体实施步骤如下： 1.把MiniC转换为文法如下 <程序〉→ main()〈语句块〉 〈语句块〉→{〈语句串〉} 编译原理课程设计报告 实验名称编译原理课程设计 班级 学号 姓名 指导教师 实验成绩 2013 年06月 一、实验目的 通过设计、编写和调试，将正规式转换为不确定的有穷自动机，再将不确定的有穷自动机转换为与之等价的确定的有穷自动机，最后再将确定有穷自动机进行简化。 通过设计、编写和调试构造LR(0)项目集规范簇和LR分析表、对给定的符号串进行LR分析的程序，了解构造LR(0)分析表的步骤，对文法的要求，能够从文法G出发生成LR(0)分析表，并对给定的符号串进行分析。 二、实验内容 正规式——>NFA——>DFA——>MFA 1.正规式转化为不确定的有穷自动机 （1）目的与要求 通过设计、编写和调试将正规式转换为不确定的有穷自动机的程序，使学生了解Thompson算法，掌握转换过程中的相关概念和方法，NFA的表现形式可以是表格或图形。 （2）问题描述 任意给定一个正规式r（包括连接、或、闭包运算），根据Thompson算法设计一个程序，生成与该正规式等价的NFA N。 （3）算法描述 对于Σ上的每个正规式R，可以构造一个Σ上的NFA M，使得L(M)=L(R)。 步骤1：首先构造基本符号的有穷自动机。 步骤2：其次构造连接、或和闭包运算的有穷自动机。 （4）基本要求 算法实现的基本要求是： (1) 输入一个正规式r； (2) 输出与正规式r等价的NFA。（5）测试数据 输入正规式：(a|b)*(aa|bb)(a|b)* 得到与之等价的NFA N （6）输出结果 2.不确定的有穷自动机的确定化 （1）目的与要求 通过设计、编写和调试将不确定的有穷自动机转换为与之等价的确定的有穷自动机的程序，使学生了解子集法，掌握转换过程中的相关概念和方法。DFA的表现形式可以是表格或图形。（2）问题描述 任意给定一个不确定的有穷自动机N，根据算法设计一个程序，将该NFA N变换为与之等价的DFA D。 （3）算法描述 用子集法将NFA转换成接受同样语言的DFA。 步骤一：对状态图进行改造 (1) 增加状态X,Y,使之成为新的唯一的初态和终态。从X引ε弧到原初态结点, 从原终态结 点引ε弧到Y结点。 (2) 对状态图进一步进行如下形式的改变 编译原理课程设计 自顶向下语法分析器 学院（系）：计算机科学与技术学院学生姓名：xxxxxxxxx 学号：xxxxxxxxx 班级：电计1102 大连理工大学 Dalian University of Technology 目录 1 系统概论 语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位如图1所示： 图1 语法分析器在编译程序中的地位 语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。 自顶向下分析法就是语法分析办法中的一类。顾名思义，自顶向下就是从文法的开始符号出发，向下推导，推出句子。这种方法是带“回溯”的。 自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。 实现这种自顶向下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。 2 需求分析 以前，人们对语法的分析都建立在人工的基础上，人工分析虽然能够做到侧类旁推，但终究人力有限，再精密的分析都会出现或多或少的错误。为减少因人为产生的错误，并加快 摘要 使用过现代计算机的人都知道，多数用户是应用高级语言来实现他们所需要的计算的。现在计算机系统一般都含有不只一个的高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序，供用户按不同需要进行选择。高级语言编译程序是计算机系统软件最主要的组成部分之一，也是用户最直接关系的工具之一。 计算机上执行一个高级语言程序一般分为两步：第一，用一个编译程序把高级语言翻译成机器语言程序；第二，运行所得的机器语言程序求得计算结果。 通常说的翻译程序是指能够把某一种语言程序转换成另一种语言程序（目标语言程序）。如果源语言诸如Fortran，Pascal，C，Ada或java这样的高级语言，而目标程序是诸如汇编语言或者机器语言这类的低级语言，这样的一个翻译程序就是称为编译程序。 一个编译程序的工作过程一般可以划分为五个阶段：词法分析、语法分析、语义分析与中间代码生成、优化、目标代码生成。每个阶段都是从上一个阶段得到结果，对他进行分析，并且根据一些外部环境(例如符号表等)得到最终的输出结果。要构造一个编译程序，可以按照这样的阶段来分别构造，最后来连调。 现在人们已经建立了多种编制部分编译程序或整个编译程序的有效工具。有些能用于自动生成扫描器(如LEX)，有些可以用于自动产生语法分析器(如YACC)，有些甚至可以用来自动产生整个的编译程序。这些构造编译程序的工具成为编译程序－编译程序、编译程序产生器或翻译程序书写系统，他们是按照编译程序和目标语言的形式描述而自动产生编译程序的。 编译程序是一极其庞大而又复杂的系统，掌握它比较苦难。但是一旦对其掌握，对以后的程序语言设计，系统软件分析，系统软件设计，形式语言研究等方面都是非常有好处的。 关键字：C语言、、编译、扫描器、语法分析 编译原理 实 验 指 导 书 前言 编译原理是计算机科学与技术、软件工程等专业的主干课和必修课，由于这门课程相对抽象且内容较复杂，一直是比较难学的一门课程。在编译原理的学习过程中，实验非常重要，只有通过上机实验，才能使学生对比较抽象的课程内容产生一个具体的感性认识。 本书实验环境主要为C环境及一个词法分析器自动生成工具FLEX和一个语法分析器自动生成工具BISON。书中给出的参考源程序也是C源程序，但由于实验者熟悉精通的语言工具不尽相同，因而强求采用统一的编程语言编程是不现实的。实验者在掌握了编译程序各个阶段的功能和原理之后，不难借助使用其他自己熟悉的语言实现相关功能。 实验者在实验过程中应该侧重写出自己在算法分析、设计思路、实现功能或程序代码等方面的特色，写出设计和实现过程中遭遇到的难点和解决办法，可以不拘泥于实验指导给出的参考性设计思路，尽可能在深度和广度上加以拓展。只有这种各具特色的实验报告，才将更有利于体现实验者在创新思维和动手能力上的差异。 通过这些实验，能使学生对这些部份的工作机理有一个详细的了解，达到“知其然，且知其所以然”的目的。并可在C环境下对自动生成工具生成的词法、语法分析器进行编译调试。 由于手工生成词法和语法分析器的工作量太大，在实际中常用自动生成工具来完成之。这些工具中最著名的当属贝尔实验室的词法分析器生成工具LEX和语法分析器生成工具YACC。它们现已成为UNIX的标准应用程序同UNIX一起发行。与此同时GNU推出与LEX完全兼容的FLEX，与YACC完全兼容的BISON。这两个程序都在Internet上以源代码的形式免费发行，所以很容易在其它操作系统下重新编译安装。我们实验采用的就是for dos的FLEX和BISON。本书有关的编译工具及其源程序例子，可到BISON的网站上下载。关于FLEX和BISON的用法简介，参见附录，如需更详细的介绍，请参阅编译工具中帮助文件。 2011-2012学年第二学期 《编译原理》课程设计报告 学院：计算机科学与工程学院 班级： 学生姓名：学号： 成绩： 指导教师： 时间：2012年5 月 目录 一、课程设计的目的 ---------------------------------------------------------------- - 1 - 二、课堂实验及课程设计的内容 -------------------------------------------------- - 1 - 2.1、课堂实验内容-------------------------------------------------------------- - 1 - 2.2、课程设计内容-------------------------------------------------------------- - 1 - 三、visual studio 2008 简介------------------------------------------------------- - 2 - 四、问题分析及相关原理介绍 ----------------------------------------------------- - 3 - 4.1、实验部分问题分析及相关原理介绍 ---------------------------------- - 3 - 4.1.1、词法分析功能介绍及分析------------------------------------- - 3 - 4.1.2、语法分析功能介绍及分析------------------------------------- - 3 - 4.1.3、语义分析功能介绍及分析------------------------------------- - 4 - 4.2、课程设计部分问题分析及相关原理介绍 ---------------------------- - 5 - 4.2.1、编译程序介绍 ----------------------------------------------------- - 5 - 4.2.2、对所写编译程序的源语言的描述（C语言） -------------- - 6 - 4.2.3、各部分的功能介绍及分析 -------------------------------------- - 7 - 4.3、关键算法：单词的识别-------------------------------------------------- - 8 - 4.3.1、算法思想介绍 ----------------------------------------------------- - 8 - 4.3.2、算法功能及分析 -------------------------------------------------- - 8 - 五、设计思路及关键问题的解决方法 ------------------------------------------ - 10 - 5.1、编译系统------------------------------------------------------------------ - 10 - 5.1.1、设计思路 --------------------------------------------------------- - 10 - 5.2、词法分析器总控算法--------------------------------------------------- - 12 - 5.2.1、设计思路 --------------------------------------------------------- - 12 - 5.2.2、关键问题及其解决方法 --------------------------------------- - 13 - 六、结果及测试分析-------------------------------------------------------------- - 14 - 6.1、软件运行环境及限制--------------------------------------------------- - 14 - 6.2、测试数据说明------------------------------------------------------------ - 14 - 6.3、运行结果及功能说明--------------------------------------------------- - 16 - 6.4、测试及分析说明--------------------------------------------------------- - 16 - 七、总结及心得体会 --------------------------------------------------------------- - 17 - 7.1、设计过程------------------------------------------------------------------ - 17 - 7.2、困难与收获 ------------------------------------------------------------- - 17 - 八、参考文献 ------------------------------------------------------------------------ - 18 - 编译原理： 编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。编译原理是计算机专业设置的一门重要的专业课程。编译原理课程是计算机相关专业学生的必修课程和高等学校培养计算机专业人才的基础及核心课程，同时也是计算机专业课程中最难及最挑战学习能力的课程之一。编译原理课程内容主要是原理性质，高度抽象。 编译原理课程设计： 《编译原理课程设计》是2007年11月浙江大学出版社出版的图书，作者是冯雁、鲁东明、李莹。 内容简介： 本书围绕着编译技术的基本原理和方法，以模拟程序设计语言SPL的编译器的设计和实现为主线，结合词法分析、语法分析、语义分析、代码生成、代码优化、错误处理等各个基本模块，对原理和实现方法进行了详细分析。该编译器可接受SPL的程序，并将其翻译成汇编语言程序，最终实现汇编语言到8086/8088机器语言的翻译。本书为编译技术等相关课程的实验提供了参考。在附件中还提供了三类不同类型和难度的实验题，可供课程实验选择。 第1章引论： 1.1本书介绍 1.2SPL语言的特点及实验安排 1.2.1SPL语言的特点 1.2.2SPL语言编译器的主要结构1.2.3实验安排 1.3平台的选择和介绍 1.3.1LEX简介 1.3.2YACC简介 第2章词法分析： 2.1词法分析器的基本框架 2.2词法分析器的基本原理 2.2.1DFA的构造和实现 2.2.2词法分析的预处理 2.2.3实现词法分析器的注意要点2.3词法分析器的实现 2.3.1SPL语言单词属性字 2.3.2SPL词法分析器的输入和输出2.3.3SPL词法分析器的分析识别第3章语法分析： 3.1语法分析的基本框架 3.1.1上下文无关文法 3.1.2语法分析过程 3.1.3语法分析过程中的数据结构3.2语法分析的基本方法 编译原理课程设计报告 实验1：用Lex设计词法分析器1 实验目的：学会用lex设计一个词法分析器。 实验内容：使用lex为下述文法语言写一个词法分析器。 实验要求： 输入为用该语言所写的源程序文件；输出为记号序列，每个记号显示为二元组(记号名，记号属性值)的形式。输出可以在屏幕上，也可以输出到文件中。不要求建立符号表。 在cygwin下用flex和gcc工具将实验调试通过，并能通过例子parser0中testcases目录下的测试例的测试。 实验参考：和。 语言文法： <程序>? PROGRAM <标识符> ; <分程序> <分程序>? <变量说明> BEGIN <语句表> END. <变量说明> ? VAR <变量说明表>; <变量说明表>?<变量表>: <类型> | <变量表>: <类型>; <变量说明表> <类型>? INTEGER | REAL <变量表>? <变量> | <变量>, <变量表> <语句表>? <语句> | <语句>; <语句表> <语句>? <赋值语句> | <条件语句> | 5. 目标代码生成 本章实验为实验四，是最后一次实验，其任务是在词法分析、语法分析、语义分析和中间代码生成程序的基础上，将C 源代码翻译为MIPS32指令序列（可以包含伪指令），并在SPIM Simulator上运行。当你完成实验四之后，你就拥有了一个自己独立编写、可以实际运行的编译器。 选择MIPS作为目标体系结构是因为它属于RISC范畴，与x86等体系结构相比形式简单便于我们处理。如果你对于MIPS体系结构或汇编语言不熟悉并不要紧，我们会提供详细的参考资料。 需要注意的是，由于本次实验的代码会与之前实验中你已经写好的代码进行对接，因此保持一个良好的代码风格、系统地设计代码结构和各模块之间的接口对于整个实验来讲相当重要。 5.1 实验内容 5.1.1 实验要求 为了完成实验四，我们建议你首先下载并安装SPIM Simulator用于对生成的目标代码进行检查和调试，SPIM Simulator的官方下载地址为：https://www.wendangku.net/doc/161507642.html,/~larus/spim.html。这是由原Wisconsin-Madison的Jame Larus教授（现在在微软）领导编写的一个功能强大的MIPS32汇编语言的汇编器和模拟器，其最新的图形界面版本QtSPIM由于使用了Qt组件因而可以在各大操作系统平台如Windows、Linux、Mac等上运行，推荐安装。我们会在后面介绍有关SPIM Simulator的使用方法。 你需要做的就是将实验三中得到的中间代码经过与具体体系结构相关的指令选择、寄存器选择以及栈管理之后，转换为MIPS32汇编代码。我们要求你的程序能输出正确的汇编代码。“正确”是指该汇编代码在SPIM Simulator（命令行或Qt版本均可）上运行结果正确。因此，以下几个方面不属于检查范围： 1)寄存器的使用与指派可以不必遵循MIPS32的约定。只要不影响在SPIM Simulator中的 正常运行，你可以随意分配MIPS体系结构中的32个通用寄存器，而不必在意哪些寄存器应该存放参数、哪些存放返回值、哪些由调用者负责保存、哪些由被调用者负责保存，等等。 2)栈的管理（包括栈帧中的内容及存放顺序）也不必遵循MIPS32的约定。你甚至可以使 用栈以外的方式对过程调用间各种数据的传递进行管理，前提是你输出的目标代码（即MIPS32汇编代码）能运行正确。 实验时间：200 年月日实验小组：第组 组长：组员： 组员： 指导教师签名：实验情况评定： 实验二编写一个简单的FLEX脚本并编译运行 实验目的: 通过实验掌握下列知识: 1、进一步熟悉Visual C++的基本操作； 2、进一步熟悉Visual C++ 6.0里Win32 Console Application工程的建立和相应的编程知识； 3、了解如何建立和编译Flex脚本文件； 5、了解如何通过Visual C++ 6.0编译Flex程序； 内容及步骤: 一、输入一个Flex脚本，编译并运行: 1、按实验一介绍的方法，建立一个Win32 Console Application并选择“An empty project”； 2、从选课系统里下载“Flex源代码及编译系统”； 3、将下载的RAR文件解压到D盘的某个文件夹，然后将解压的所有文件复制到D盘的文件夹“D:\Flex”里； 4、打开“附件->记事本”，输入以下代码，并以文件名“DEMO1.L”保存到文件夹“D:\Flex”里： %{ #include return 0; } 5、点击桌面左下角并运行“开始->程序->附件->命令提示符”； 6、在DOS窗口中输入命令(1)D: (2)cd \Flex(与你存储Flex文件的文件夹名有关) (3)flex DEMO1.L； 7、将D:Flex文件夹下的文件“emalloc.c”、“hash.c”、“LEXYY.C”、“libyywra.c”、“hash.h”、“types.h”和“DEMO1.L”全部复制到你的工程文件夹下； 8、运行VC并调入你建立的工程文件，然后点击左边的FileView，分别用鼠标右键点击Source Files和Header Files，并选择“Add Files to Folder”添加7步复制的c文件和h文件： 图1 9、在第8步添加的文件如下： 图2 10、点击“编译”菜单里的“重建全部”,或者点工具栏上的“!”运行； 注：Flex程序在DOS窗口里运行，词法分析程序是通过键盘输入文本信息，文本信息输入结束时，先按回车，再按Ctrl+Z即可结束文本输入； 实验报告要求: 1、记录错误信息、错误数量和警告数量，以及运行结果； 2、记录Flex脚本文件； 第一章 1、将编译程序分成若干个“遍”是为了。 a．提高程序的执行效率 b．使程序的结构更加清晰 c．利用有限的机器内存并提高机器的执行效率 d．利用有限的机器内存但降低了机器的执行效率 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法d．以上三项都是 3、变量应当。 a．持有左值b．持有右值 c．既持有左值又持有右值d．既不持有左值也不持有右值 4、编译程序绝大多数时间花在上。 a．出错处理b．词法分析 c．目标代码生成d．管理表格 5、不可能是目标代码。 a．汇编指令代码b．可重定位指令代码 c．绝对指令代码d．中间代码 6、使用可以定义一个程序的意义。 a．语义规则b．语法规则 c．产生规则d．词法规则 7、词法分析器的输入是。 a．单词符号串b．源程序 c．语法单位d．目标程序 8、中间代码生成时所遵循的是- 。 a．语法规则b．词法规则 c．语义规则d．等价变换规则 9、编译程序是对。 a．汇编程序的翻译b．高级语言程序的解释执行 c．机器语言的执行d．高级语言的翻译 10、语法分析应遵循。 a．语义规则b．语法规则 c．构词规则d．等价变换规则 二、多项选择题 1、编译程序各阶段的工作都涉及到。 a．语法分析b．表格管理c．出错处理 d．语义分析e．词法分析 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成 d．语义检查e．目标代码生成 三、填空题 1、解释程序和编译程序的区别在于。 2、编译过程通常可分为5个阶段，分别是、语法分析、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是，最后阶段的输出为程序。编译原理实验二
(重庆理工大学计算机学院)编译原理课程设计报告
编译原理课程设计
编译原理课程设计一个简单编译器的设计与分析
编译原理实验指导书(图)
编译原理课程设计报告
编译原理课程设计
编译原理课程设计报告
编译原理实验：目标代码的生成
编译原理实验2-编写一个简单的FLEX脚本并编译运行
(完整版)编译原理习题及答案(整理后)