第一篇：编译原理课程设计2011级
2011级《编译原理课程设计》任务书
一、课程设计的性质和目的编译原理课程设计是计算机专业课程，通过课程设计使学生进一步巩固课堂所学知识，全面熟悉、掌握编译程序编写的基本设计方法和技巧，进一步提高分析问题、解决问题及上机操作能力，为将来从事高层次的计算机软件开发工作打下一定的专业基础。
二、设计课题
课题一：应用编译原理的方法实现带括号的四则混合运算
给定条件：
1、词法符号定义如下：
INTC D+
FLOATC (D+.D+)|(D+.)|(.D+)
FLOATC ((D+.D+)|(D+.)|(.D+)|(D+))(E | e)(+ | − | λ)D+
OPADD +
OPSUB −
OPMUL *
OPDIV /
LPAREN ‘(’
RPAREN ‘)’
LINE ‘n’
ASSIGN =
2、表达式文法定义如下：
01.S E
02.E T
03.E EOPADDT
04.E EOPSUBT
05.T P
06.T TOPMULP
07.T TOPDIVP
08.P INTC
09.P FLOATC
10.P LPARENERPAREN
基本要求：
1、以ASSIGN作为文法结束符号；
2、应用词法分析技术识别单词；
3、应用SLR(1)分析技术判别表达式的合法性；
4、应用尾动作文法技术计算表达式的类型与值；
5、要求表达式的类型与值严格一致。
课题二：Micro语言词法语法分析
给定条件：
1、词法符号定义如下：
ID L(L|D)*
INTC D+
REALC D+ D+
PLUS +
MULT *
LPAREN （RPAREN )
COLON ：
ASSIGN ：＝
SEMI ；
LINE ’n’
STOP
FEOF EOF2、表达式文法定义如下：
01.PROG BEGINDECLBODYENDSTOP
02.DECL DECLVARIDCOLONTYPESEMI
03.DECL VARIDCOLONTYPESEMI
04.TYPE REAL
05.TYPE INTEGER
06.BODY BODYSEMISTM
07.BODY STM
08.STM IDASSIGNEXP
09.STM WRITELPARENEXPRPAREN
10.STM READLPARENIDRPAREN
11.EXP EXPPLUSFACT
12.EXP FACT
13.FACT FACTMULTPRIM
14.FACT PRIM
15.PRIM ID
16.PRIM INTC
17.PRIM REALC
18.PRIM LPARENEXPRPAREN
基本要求：
1、以FEOF作为文法结束符号；
2、应用词法分析技术识别单词；
3、应用SLR(1)分析方法进行语法分析；
4、报错要指明所在行。
三、课程设计报告要求
1、课程设计报告必须按本系规定的格式要求打印成册；
2、课程设计报告每人一份，正文必须包含如下几个方面的内容：
1)基本设计思想；
2)主要数据结构；
3)总结与体会。
3、课程设计报告装订顺序：封面、任务书、目录、正文、源程序清单。
四、选题及考核办法
1、一人一组，学号为奇数者做课题一，学号为偶数者做课题二。
2、成绩考核按个人课题完成情况、设计报告质量及对课程设计的态度等综合评定。
五、设计进度安排
1、讲课时间安排：
待定
2、上机调试时间安排：
待定
3、答辩时间安排：
待定
4、其余时间：查阅资料，确定方案，设计课题相关程序。
第二篇：编译原理课程设计
课 程 设 计 报 告
设计题目：一个简单文法的编译器前端的设计与实现
班
级： 计算机1206 组长学号：201239 组长姓名：闫智宣 指导教师：李晓华 设计时间：2014年12月
[在此处键入]
设计分工
组长学号及姓名： 20123974
闫智宣
分工：
语法分析，四元式生成，目标代码优化及生成 组员1学号及姓名：20123977
廖峭 分工：
词法分析，错误处理 组员2学号及姓名：20123959
郭天龙
分工：
符号表生成，语义动作插入，操作界面[在此处键入]
摘要
编译原理课程设计是通过C语言编译器相关子系统的设计，进一步加深对编译器构造的理解；第一部分词法分析，设计各单词的状态转换图，并为不同的单词设计种别码，制作扫描器识别一个个单词，返回值为识别码的序号，返回Token序列。将词法分析器设计成供语法分析器调用的子程序。词法分析器具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；第二部分，语法分析，用递归下降法，实现对表达式、各种说明语句、控制语句进行语法分析。若语法正确，则用语法制导翻译法进行语义翻译；生成并打印出语法树；若语法错误，要求指出出错性质和出错位置（行号）。
我们还做了附加功能，即编译后端，有中间代码优化，生成目标代码汇编语言。通过此次课程设计，提高了我们的独立分析问题、解决问题的能力，以及系统软件设计的能力； 提高程序设计能力、程序调试能力，团结协作能力
关键词：词法分析，语法分析，四元式生成，错误处理，符号表生成，语义动作插入，中间代码优化，生成目标代码 [在此处键入]
目录
摘要
1.概述
2.课程设计任务及要求
2.1 设计任务
2.2 设计要求
3.算法及数据结构
3.1算法的总体思想（流程）
3.2 词法分析模块
3.2.1 功能
3.2.2 数据结构
3.2.3 算法
3.3 语法分析模块
3.3.1功能
3.3.2 数据结构
3.3.3算法
3.4 符号表模块
3.4.1功能
3.4.2 数据结构
3.4.3算法
3.5 四元式模块
3.5.1功能
[在此处键入]
3.5.2 数据结构
3.5.3算法
3.6 语义动作分析模块
3.6.1功能 3.6.2 数据结构
3.6.3算法
3.7 错误处理模块
3.7.1功能
3.7.2 数据结构
3.7.3算法
3.8 目标代码模块
3.8.1功能
3.8.2 数据结构
3.8.3算法
4.程序设计与实现
4.1 程序流程图
4.2 程序说明
4.3 实验结果
5.结论 6.参考文献。7.收获、体会和建议。
[在此处键入]
1.概述
编译器是将C语言翻译为汇编语言代码的计算机程序。编译器将源程序（source language）编写的程序作为输入，翻译产生目标语言（target language）机器代码的等价程序。通常地，源程序为高级语言（high-level language），C语言程序，而目标则是 机器语言的目标代码（object code），也就是可以在计算机硬件中运行的机器代码软件程序。这一过程可以表示为：
源程序→编译器 →目标机器代码程序
2.课程设计任务及要求
2.1设计任务
学生在学习《编译原理》课程过程中，结合各章节的构造编译程序的基本理论，要求用C#语言描述及上机调试，实现一个 C编译程序（包括词法分析，语法分析等重要子程序），使学生将理论与实际应用结合起来，受到软件设计等开发过程的全面训练，从而提高学生软件开发的能力。
2.2设计要求 要求：
（1）设计词法分析器
设计各单词的状态转换图，并为不同的单词设计种别码。将词法分析器设计成供语法分析器调用的子程序。功能包括：
a.具备预处理功能。将不翻译的注释等符号先滤掉，只保留要翻译的符号串，即要求设计一个供词法分析调用的预处理子程序；
b.能够拼出语言中的各个单词； [在此处键入]
c.返回（种别码，属性值，行号）。
（2）语法分析
要求用学习过的自底向上或自顶向下的分析方法等，实现对表达式、各种说明语句、控制语句进行语法分析。若语法正确，则用语法制导翻译法进行语义翻译；生成并打印出语法树；若语法错误，要求指出出错性质和出错位置（行号）。
3.算法及数据结构
3.1算法的总体思想（流程）
本节主要分析程序的代码结构和代码工程文件的划分。（程序由几个类组成: Token类和Variable类SymbolTable类ObjectCode类Lexical类Grammar类Four_Yuan类Action类ErrorItem类，分别为词法分析和语法分析类。工程分为几个文件：Form1.cs,Token.cs,Variable.cs,SymbolTable.cs,ObjectCode.cs,Lexical.cs,Grammar.cs,Four_Yuan,cs,Action.cs,ErrorItem.cs分别对应Token类和Variable类SymbolTable类ObjectCode类Lexical类Grammar类Four_Yuan类Action类ErrorItem类的声明和实现文件）。本程序采用C#语言以面向对象的思想编写，程序分为几部分：词法分析（Lexical），语法分析（Grammer），目标代码生成（ObjectCode）。Lexical类主要的工作是词法分析获取Token。Grammer类的主要工作是根据Lexical类词法分析之后的Token进行语法分析，生成语法树，最后并输出语法树。在处理过程中，Token类的对象作为Lexical类的一个成员变量，配合Grammer类进行语法分析。
工程文件总体上是按照九个类的格局分为十个文件，分别是九个类的声明文件和实现文件。十个文件为Form1.cs,Token.cs,Variable.cs,SymbolTable.cs,ObjectCode.cs,Lexical.cs,Grammar.cs,Four_Yuan,cs,Action.cs,ErrorItem.cs，他们分别是Lexical类声明文件、Lexical类实现文件、Grammer类声明文件、Grammer类实现文件。[在此处键入]
程序流程
在程序中，Lexical类的对象(Token)作为Grammer类中的一个成员变量，配合Grammer类进行语法分析。它们的关系是这样的：Grammer类的一个成员变量temp首先对源程序删除注释，然后进行词法分析获取所有Token，并将获取的Token存储在Token对象的tokenList（List类型）中。然后Grammer类的语法分析程序就根据tokenList中的Token进行语法分析，生成语法树，最后打印语法树。同时，这也是程序的流程。[在此处键入]
3.2 词法分析模块 3.2.1功能
Lexical类主要的工作是词法分析获取Token序列。
3.2.2数据结构
词法分析阶段的代码被封装成一个类——Lexical，Token中主要是Lexical类的声明代码，Lexical.cs中主要是Lexical类的实现代码。Lexical类对外提供的函数主要有：
static public int RecogId(string str, int i)，static public int RecogDig(string str,int i)，static public int RecogOperator(string str, int i)，static public int RecogBound(string str, int i)，以上几个函数构成了词法分析的骨架，在Lexical类中还有其他成员变量和函数，主要作为这三个函数处理过程的中间步骤，为这三个函数服务。Lexical类的代码结构和主要的成员变量和函数及其含义如下图所示：
3.2.3算法
算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是[在此处键入]
根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。
主程序示意图：
主程序示意图如图3-1所示。
⑴ 关键字表的初值。
关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。
（2）程序中需要用到的主要变量为type和number 扫描子程序的算法思想：
首先设置3个变量： [在此处键入]
①token用来存放构成单词符号的字符串； ②number用来整型单词；
③type用来存放单词符号的种别码。
Token定义
Token定义:
Token类型（TokenType）:
3.3 语法分析模块
3.3.1功能
语法分析是编译过程的一个逻辑阶段。语法分析的功能是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.3.3.2 数据结构
下图为实现语法分析的类Grammar，属性与方法的作用都已说明 在此处键入]
3.3.3算法
1.文法
下面终结符与非终结符意义
B程序开始
Z 数据类型，如int,char,float等
V 标识符
S 语句
P 语句块
E 加减算术表达式
D 逗号表达式
T 乘除算术表达式
C 关系表达式
L 逻辑表达式
Q 标识符或圆括号
e 表示空
i 表示标识符 a)函数文法
B----ZV()S
[
[在此处键入]
b)语句块文法
P----SP|e
S----{P} c)语句文法
表达式语句文法
S----V=E
goto语句文法
S----i:S
S----goto i
if语句文法
S----if(E)S[else S]
while语句文法
S----while(E)S
声明语句文法
S----ZVD
D----,VD|=ED|e d)表达式文法
E----T|E+T|E-T
T----F|T*F|T/F
C----C|C
L----Q|L&&Q|L||Q
Q----i|(E)|!Q
2.递归下降程序流程图
对应于每个文法编写如下递归下降子程序
主程序（B）[在此处键入] [在此处键入]
3.4 符号表模块
3.4.1功能
进行符号表的储存，添加，更新，查找，保存标识符活跃信息以及输出。3.4.2 数据结构
在此处键入]
3.4.3算法
3.5 四元式模块
3.5.1功能
四元式为中间代码，编译程序进行完语义分析后，先生成中间代码作为过渡，此时中间代码与目标代码已经比较相似
3.5.2 数据结构
[ 在此处键入]
3.5.3算法
3.6语义动作分析模块
3.6.1功能
在语法分析中嵌入相应的语义动作，生成四元式 3.6.2 数据结构
[
[在此处键入]
3.6.3算法 GEQ(+)(-)(*)(/)
(+,i1,i2,t)PUSH(i)ASSI(=)
(=,t,_,POP)LABER(i)
(lb,_,_,i)GOTO(i)
(gt,_,_,i)IF(if)
(if,a,_,_)EL(el)
(el,_,_,_)IE(ie)
(ie,_,_,_)WH()
(wh,_,_,_)DO()
(do,a,_,_)WE(we)
(we,_,_,_)
3.7 错误处理模块
3.7.1功能 保存运行时发现的错误，储存行号已经详细信息并输出。
3.7.2 数据结构
3.7.3算法 [在此处键入]
public static void AddErrorMessage(int lineno,string content)函数用作在发现错误时保存错误信息以及行号。
public static string PrintErrorList()把所有发现的错误格式化后统一输出。
错误信息在语法分析，语义分析，符号表检错中添加。3.8 目标代码模块
3.8.1功能
目标代码生成把优化后的中间代码变换成目标代码，此处的目标代码为汇编代码，采用单寄存器生成目标代码 3.8.2 数据结构[在此处键入]
3.8.3算法
对于一个基本块有如下流程图
W：操作符，B：第一操作数，C：第二操作数，R：寄存器
5.结论
网上找一段话抄上 [在此处键入]
6.测试
测试打开文件
测试保存文件
如果没打开文件，直接敲代码，点保存时会弹出另存为窗口[在此处键入]
测试错误检测，程序缺少main函数的类型，错误列表中显示第一行函数缺少错误类型。
测试错误检测，程序缺少分号，错误列表中显示该行缺少语句结束标志';' 单击错误列表，会自动选定错误行
编译成功，生成并显示token串、符号表、四元式与目标代码 [在此处键入]
测试if与while语句，而且while嵌套在if当中
测试goto语句，结果正确。[在此处键入]
测试优化，输入课件中的代码，结果与课件一样
6.参考文献。
1、陈火旺.《程序设计语言编译原理》（第3版）.北京：国防工业出版社.2000.2、美 Alfred V.Aho Ravi Sethi Jeffrey D.Ullman著.李建中，姜守旭译.《编译原理》.24 [在此处键入]
北京：机械工业出版社.2003.3、美 Kenneth C.Louden著.冯博琴等译.《编译原理及实践》.北京：机械工业出版社.2002.4、金成植著.《编译程序构造原理和实现技术》.北京：高等教育出版社.2002.7.收获、体会和建议。
直接拷贝好歹也检查一下错误
对于编译原理的这次课程设计，自己经历了从刚开始的不懂明白任务的要求和内容理论知识的了解开始着手写代码完成基本功能根据DFA及自顶向下等理论修改完善代码等这些过程。
自己着手写词法分析的时候还不清楚词法分析的任务内容，还不知道词法分析的结果是什么，词法分析出错的情况和类型有哪些，也总是将词法分析和语法分析混在一起，不明白哪些错误在词法分析中报，哪些错误在语法分析中判断，后来经过查书、网上资料、请教同学等途径逐步清晰了词法分析的工作内容是从源代码文件中获取出Token，供语法分析使用。在充分了解了语法分析需要哪些信息时，我才真正了解了词法分析的工作内容和目标，才知道词法分析需要完成哪些任务获取到哪些信息。充分了解了词法分析的任务之后，就开始理论知识的学习。经过揣摩书上的例子，自己理解和掌握了怎么设计过滤注释和分析程序中Token的DFA，于是开始根据设计好的DFA进行编码，最后经过调试已经可以正确地完成词法阶段的任务了。这只是词法分析的原始代码，在之后还进行了两次彻底的改动。虽然之前写的词法分析的代码已经完成了词法分析的需求，也是根据DFA的原理编写的，但是在代码结构上却难以体现，在对书上的根据已知DFA写代码的例子进行了详细的研究之后，发现自己的代码并没有像书上那样完全按照所依据的DFA各状态转移的关系进行编写，所以对代码进行了重写，像书上一样严格按照状态之间转移的方式进行编写，将状态划分成11个状态，状态分别按1~11进行标注，程序也按照DFA来编写，也实现了词法分析的功能。再后来写报告的时候，发现分析出Token的那个DFA并不是最简的，有很多多余的状态，完全可以用一个flag标志来标识，从而简化代码结构，于是又重写了一次词法分析函数scan()的代码，将状态缩减为5个，且不再用1-5来表示，而是像书上那样分别取了名字（START、INNUM、INID、INDBSYM、DONE），同时为了简化代码将输出Token到文件的部分从scan()中剥离开来，而在Lexical类中加了一个printToken()的函数，使scan()函数逻辑更加清晰，使读者能够容易地将代码与DFA进行查看比照。
在写语法分析的时候，已经对编译器的语法分析的内容有了一定的了解，所以直接进行了理论的学习。首先自己对递归向下分析法进行了学习，将书上的几个递归向下分析的伪代码看过之后，自己对递归向下的分析方法的原理有了初步的认识，大概知道了根据文法怎么分析，但是对于如何编写代码却还在此处键入]
是难以下手，于是就对照TINY语言的文法看了几遍书后面的TINY语言的递归向下分析的语法分析程序，这样就基本知道了C-语言的语法分析程序怎么写。由于C-语言给出的文法有左递归存在，于是自己将存在左递归的文法改写成EBNF的形式，并据此进行代码编写。由于在编写代码的过程中需要确定分析是否正确或选择多个文法中的某一个文法进行分析，有时必须探测需要的或下一个Token的类型，在这种情况下需要求First集合，在推导中若存在empty，又需要求Follow集合，所以这样又需要我了解First集合和Follow集合，自己在程序中也根据求出的First集合和Follow集合进行判断，以确定程序的走向。在编写过程中，还有一类问题，就是存在公共左因子，如文法expression→ var = expression | simple-expression，左因子为ID，在分析过程中，由于已经取出了一个ID的Token，且生成了一个IdK的节点，但是在当前状态无法确定是哪一个推导，然而IdK节点已经生成，又无法回退，并且是使用自顶向下的分析方法，已经生成的IdK在程序上方无法使用，自己通过查阅资料等途径的学习确定了在这种情形下的处理方式：将已经生成的IdK节点传到下方的处理程序，所以TreeNode * simple_expression(TreeNode * k)、TreeNode * additive_expression(TreeNode * k)等函数都被设计成有节点类型参数的函数，目的就是将已经生成的节点传到下面的分析函数中去。
通过这次的编译原理课程的学习和实践，自己获益良多。首先最基本的成果是完成了课程设计的任务，实现了编译器的词法分析和语法分析阶段的功能，词法分析主要能过滤注释、分析出语法分析阶段需要的Token并满足语法阶段的所有要求，能够判别词法分析阶段是否出错和出错类型和位置。语法分析主要能根据递归向下的分析思想和C-文法对词法分析获取的Token进行语法分析，能够构造出语法树，能够判别语法分析过程中是否出错以及出错位置和错误类型。
由于在编写程序过程中，涉及到了正则表达式、DFA、提取公共左因子、消除左递归、EBNF、求First集合和Follow集合、递归向下分析方法以及编程语言方面的知识，所以，通过本次的课程设计的实践，使得自己对编译原理这门课的许多知识点有了更加深刻和具体的理解，而不再只限制于做题。此外，对以前那些已掌握的知识有了温习和动手锻炼的机会。如：以前在编译原理课上虽然知道First集合和Follow集合怎么求的，却不知道First集合和Follow集合到底是干什么的，通过编写程序自己明白了他们的实际作用，使得自己不仅知其然还知其所以然，从而使得自己加深了对知识点的理解和掌握。由于以前编写代码都是使用JAVA语言，所以C/C++很多内容都忘记了，通过本次的实践，自己又重新拾起了以前的知识。此外，由于在做报告的时候，需要描绘DFA和程序流程图，使得自己初步掌握了使用visio和word画图的能力。此外，对于文档的编写和美化自己也获得了许多有用的经验。[
第三篇：编译原理课程设计简介
编译原理实践课程
编译原理课程是计算机专业必修的一门重要的专业基础课程，也是计算机系统软件中非常重要的一个分支，经过多年建设取得了丰硕的教学成果：2003年被评为“吉林大学百门精品课程”之一，2004年被评为吉林省精品课程，2006年被评为教育部—微软精品课程。编译原理实践课程建设作为新世纪教学改革重点项目和编译原理精品课程建设的一个重要组成部分，在教材建设、教学内容和教学方法的改革等方面也取得了较突出的成绩，并发表了多篇学术论文。
一、实验课程目的
编译原理课程是计算机科学与技术专业学生的专业骨干课之一。通过学习这门课程，使学生掌握编译程序的基本原理、方法和实现技术，使学生更好的理解程序语言的内部机制，培养学生初步掌握设计大型系统软件的方法、技术以及设计大型软件的能力。
编译原理实践性教学的设计思想是使学生透彻的理解编译程序的原理和思想，系统全面的掌握编译技术，使学生通过课堂学习，理解编译原理的同时，注重学生实践能力的培养，进一步巩固对知识的理解，通过实际的锻炼，掌握编译技术，进而能够独立的进行编译器的设计。
二、实验内容及要求
编译程序不同于一般的应用程序，是一个十分庞大和复杂的系统软件。一般的应用程序是以数据作为操作对象，而编译程序则是以程序作为操作对象，是一个元级处理程序，它所包含的算法和思想比较特殊，理论性较强，抽象度也较高，因而编译原理课程一直以来都是计算机专业学生比较难于理解和掌握的一门课程。为此我们开设编译原理实践课程。编译原理实践课程的主要实践题目有：
实验一： 词法分析程序开发
实验要求： 1.掌握词法分析程序自动生成工具LEX的使用。
2.掌握各类单词的形式描述。
3.学会用数据中心法实现有限自动机。4.学会用直接转向法实现有限自动机。5.独立完成SNL语言的词法分析器。
实验二： 递归下降语法分析
实验要求： 1.理解递归下降语法分析方法的主要原理。
2.理解递归下降分析法对文法的要求。
3.熟练掌握Predict集合的求法。
4.熟练掌握文法变换算法（消除左递归和消除公共前缀）。实验三： LL(1)语法分析
实验要求： 1.理解LL(1)分析法的主要原理。
2.理解LL(1)分析法对文法的要求。
3.熟练掌握Predict集合的求法。
4.通过编程熟练掌握LL(1)分析法的工作过程。实验四： 符号表管理
实验要求： 1.了解符号表在编译过程中的重要作用。
2.掌握符号表应包含的符号的属性信息。3.了解符号表的组织原则。4.掌握符号表的操作。
5.掌握符号表的可见性问题。
实验五： 语义检查
实验要求： 1.了解语义检查是语义分析的一个重要内容。
2.掌握语义检查的一般内容。
3.学会在语法分析的同时进行语义检查。4.学会将语义分析作为一遍独立的扫描。
实验六： 中间代码生成
实验要求： 1.了解中间代码生成是为优化和移植而进行的。
2.了解几种常见中间代码表示形式掌握符号表应包含的符号的属性信息。
3.会用简单的程序实现中缀式到后缀式的转换。4.会用栈实现复杂表达式的求值。
5.掌握常见程序结构的中间代码结构。
6.掌握由语法树到四元式中间代码的转换方法。
实验七： 中间代码优化
实验要求： 1.能够对中间代码正确划分基本块。
2.理解常量表达式局部优化算法。
3.理解公共表达式局部优化算法。
4.理解循环不变式外提优化算法。实验八： 目标程序生成
实验要求： 1.熟练掌握虚拟机的指令系统。
2.理解并掌握指令选择的方法。
3.理解多寄存器分配的原则和方法。
4.熟练掌握基本语句从四元式中间代码形式到目标代码的翻译原理和方法。
5.独立完成目标代码生成程序。
三、实验教学过程及教学手段
教学过程：
经过近三年的研究、探索与实践，我们在编译原理实践课程的建设方面取得了一定成效。在吉林大学计算机学院首次开设了编译原理实践课程，该课程以学生实际上机实习为主，教师指导为辅，强调启发式教学，注重学生自学能力的培养。学生在实践课程中，通过实际动手编程，将抽象的编译理论知识具体化和形象化，加深了对基本概念和方法的理解和运用，从而全面系统地掌握了编译器的构造过程。
该课程采用教研室自编实践教材《编译程序设计与实现》（高等教育出版社）作为辅导教材，通过对教材中提供的编译实例的透彻解析，加深了学生对编译程序的直观认识，提高了学生对源程序的分析和设计能力。同时，对学生学习、理解和掌握编译原理理论课程也有很大的促进作用。在课程中，学生通过亲自动手实践，把原理性的抽象理论知识具体化和形象化，消化了课堂上、书本中难于理解的概念和方法，全面系统的掌握了编译器的构造过程，激发了学生的学习兴趣，培养了学生进行更深入学习的主动性。在教学方法上，结合多媒体课件，强调启发式教学，培养学生的创新能力和动手实践能力。实践证明，这些教学方式的尝试在实际教学中取得了良好的教学效果。
教学环境：
拥有良好的实践教学环境，已建成3个大型网络化、多媒体微机实验室，共有800台奔IV微机，32台服务器，实验室面积为2040平方米，完全能够满足教学实践要求，通过开放式的实践教学，收到了良好的教学效果。除实践课程中规定的实验之外，还设计了一些难度较大的选作实验题目，激发学生的能动性，提高学生分析问题、解决问题的能力。教学手段：
1.多媒体辅助教学软件－PCMCAI（Principle of Compile Multimedia CAI）在教学过程中，我们发现由于编译原理理论性强，抽象度高，学生不易于理解。针对这一情况，我们研制了编译原理多媒体辅助教学软件－PCMCAI（Principle of Compile Multimedia CAI），该软件以多媒体动画的形式生动形象地描述了编译器的各个阶段的工作过程。借助现代化的教学手段和工具，将抽象的知识具体化，便于学生理解复杂的原理，极大地调动了学生的学习积极性，学习效果有了明显的提高；
2.编译实例库
我们完成了编译实例库的构建，建立实例库的目的是使学生通过编译实例库，可以了解和掌握不同类型语言的编译原理和构造技术，培养学生的主动参与、自主思考和创新能力，扩大学生的知识面。通过实践课程，我们总结和综合了学生中优秀的设计实例，同时，广泛的收集当前国内外最新的素材资料，对编译实例库不断地进行完善。目前，实例库已经初具规模并投入使用，为学生提供了广泛的实践素材和范例，在教学过程中作为一种辅助教学手段，效果良好。
3.网络教学平台：http://softlab.jlu.edu.cn 针对目前学生人数增多，教学资源不足，学生质量参差不齐，教学质量和效率得不到保证的情况，我们充分利用Internet，建立和实施网络课程体系，利用Internet在信息制造、贮存和递送方面的优势，克服资源不足的缺点，同时也为学生提供了完全个性化的学习环境，发挥网络教学优势。目前我们已经开始了这方面的建设，完成了编译原理实例库、课件、习题库等方面的建设，构建了网络课程的框架体系，目前正着手网络课程的进一步完善工作。
四、教材及课件
教材建设：
1.校内教材：《一个教学语言TINY的编译程序教学实例分析教材》（2001年6月）。2.校内教材：《编译程序构造原理与实例分析》（2003年2月）。3.编译原理实践教材：《编译程序的设计与实现》（高等教育出版社，2004年7月）。
教学软件：
1.多媒体辅助教学软件－PCMCAI（Principle of Compile Multimedia CAI）。2.SNL（Small Nested Language）语言实例设计及其编译器构造。3.编译原理实例库（C语言版本）。4.编译原理实例库（Java语言版本）。
五、相关成果
发表论文：
1.《编译原理实践课程设计的探索》，刘磊等，吉林大学新世纪教学改革项目研究成果----创新、改革与实践 第一集 吉林大学出版社。2.《用递归下降方法实现自底向上的分析》，刘磊等，吉林大学学报（信息科学版），2004（3）。
3.《编译原理多媒体辅助教学软件的设计与实现》，刘磊等，吉林大学自然科学学报，2002(2)。
4.《测试语言ATLAS的实现技术》，刘磊等，仪器仪表学报，2004(4)。5.《ATLAS_MPS的设计与实现》，刘磊等，吉林大学学报，2004(4)。6.《编译原理实践课程教学方法研究》，张晶等，全国首届计算机程序设计类课程教学研讨会，2005(9)。7.《“编译原理”课程建设研究》，刘磊等，计算机教育，2006(6)。获得奖励：
1.2004年，《编译原理实践课程建设》，吉林大学教学成果二等奖。2.2006年，《编译程序的设计与实现》一书获吉林大学本科优秀教材。3.2002年，编译原理CAI课件－PCMCAI获被吉林省教育厅评为二等奖，并在第六届全国多媒体教育软件大奖赛上获得优秀奖。
4.《编译原理》课程先后被评为吉林大学精品课程、吉林省精品课程及教育部-微软精品课程。
总之，经过多年的研究、探索与实践，我们在编译原理实践课程的建设方面取得了一定成效。在吉林大学计算机学院首次开设了编译原理实践课程，该课程以学生实际上机实习为主，教师指导为辅，强调启发式教学，注重学生自学能力的培养。学生在实践课程中，通过实际动手编程，将抽象的编译理论知识具体化和形象化，加深了对基本概念和方法的理解和运用，从而全面系统地掌握了编译器的构造过程。该课程采用我们自编实践教材《编译程序设计与实现》作为辅导教材，通过对教材中提供的编译实例的透彻解析，加深了学生对编译程序的直观认识，提高了学生对源程序的分析和设计能力。同时，对学生学习、理解和掌握编译原理理论课程也有很大的促进作用。在教学方法上，结合多媒体课件，强调启发式教学，培养学生的创新能力和动手实践能力。实践证明，这些教学方式的尝试在实际教学中取得了良好的教学效果。
附件（获得奖励证书）
第四篇：《编译原理课程设计》教学大纲
《编译原理课程设计》教学大纲
课程名称： 课程编号： 适用专业： 总 学 分： 总 周 时： 主 撰 人： 撰写日期：
一、目的与任务
通过程序设计上机调试程序实现算法，学习编译程序调试技巧和设计编译程序的一般原则，加深对词法分析、语法分析、语义分析和中间代码生成等编译阶段及实用编译系统的认识，初步掌握编译程序构造的基本原理与技术, 从形式语言理论的角度, 进一步认识与理解程序设计语言。通过编译程序的编写和调试能力的训练，激发学生进一步思考问题，培养学生的学习兴趣和创新能力。并进一步培养学生的抽象思维能力，进一步巩固《编译原理》课程所学知识。
本次课程设计的时间为2周，目的是通过实际的题目如：词法分析、语法分析、代码优化等，使学生了解和掌握编译程序的工作原理，同时培养学生用相关的程序设计语言进行程序设计，实现编译的功能，从而提高学生的综合能力。
二、教学基本要求
1．设计和调试过程要规范化
需求分析：将题目中要求的功能进行叙述分析，并且设计解决此问题的数据存储结构，（有些题目已经指定了数据存储的，按照指定的设计），设计或叙述解决此问题的算法，描述算法可以使用自然语言、伪代码、或函数的方式。
给出实现功能的一组或多组测试数据（测试文法），程序调试后，将按照此测试数据进行测试的结果列出来。
如果程序不能正常运行或运行过程中出现了不满足算法思想的情况，写出出现这一情况的原因或改进行的方法。
源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。
程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环。2．课程设计实习报告的书写格式
编译原理 436105 软件工程 2W 2012．6
审 核 人：
① 设计题目
②运行环境（软、硬件环境）③算法设计的思想 ④算法设计分析 ⑤主要函数 ⑥源代码 ⑦运行结果分析 ⑧收获及体会 3．实施方式
本次课程设计分成9个题目，都有一定的工作量，涵盖本课程内容和实际应用相关的主要技术，学生可以自由组队选择其中一个实现。课程设计题目见“主要内容”。
根据老师给定的9个题目进行分析设计，本次课程设计采取分组的办法进行，3-4人为一组，要求每组学生在规定时间内独立完成。4．答辩：课题的论述、测试及问题回答
三、课程设计内容
1、词法分析器的构造：
人们理解一个程序，起码是在单词级别上来思考。同样，在编绎一个程序时，也是在单词级别上来分析和翻译源程序。词法分析是编绎的基础，执行词法分析的程序即为词法分析器，它的任务是对输入或给定的源程序，从左至右逐个字符进行扫描，产生一个个单词符号，把作为字符串的源程序改造成单词符号串的中间程序。设计目的与任务：
通过本课程设计教学所要求达到的目的是：对词法分析工作流程进行总体设计和详细设计，最终用C语言来设计一个简单词法分析器，实现对源程序的词法分析功能，对输入程序去除注释，并以二元式形式输出程序中所有单词。
2、正则表达式到NFA 在编译系统中，词法分析阶段是整个编译系统的基础。对于单词的识别，有限自动机FA是一种十分有效的工具。有限自动机由其映射f是否为单值而分为确定的有限自动机DFA和非确定的有限自动机NFA。在非确定的有限自动机NFA中，由于某些状态的转移需从若干个可能的后续状态中进行选择，故一个NFA对符号串的识别就必然是一个试探的过程。这种不确定性给识别过程带来的反复，无疑会影响到FA的工作效率。而DFA引擎在任意时刻必定处于某个确定的状态，它搜索是无需象NFA一样必须记录所有的可能路径（trace multiple possible routes through the NFA），这也是DFA运行效率高于NFA的原因。而已经证明DFA是NFA的一个特例，即对于每一个NFA M存在一个DFA M’’，使得L(M)=L(M’’)。
设计目的与任务
通过本课程设计教学所要求达到的目的是：充分理解和掌握NFA，DFA以及NFA确定化过程的相关概念和知识，编程实现对输入的任意正规式转换成NFA的形式输出。
3、NFA的确定化
有限自动机理论是描述词法规则的基本理论。一条词法规则表示一个正规表达式(又叫正规式)，而一个正规式又可化为一个DFA(确定有穷自动机)，这个有限自动机可用来识别词法规则所定义的所有单词符号。把程序设计语言的所有词法规则都构造出相应的有限自动机,就得到一个词法分析器。然后,再转换为计算机可识别的程序就能自动实现词法的分析和检查。在实际应用中，用NFA(不确定有穷自动机)识别词法存在不确定和状态的冗余,因而,就要将NFA(不确定有穷自动机)转换为DFA(确定有穷自动机),消除了不可到达和不确定。设计目的与任务
通过本课程设计教学所要求达到的目的是：掌握从NFA到DFA的转换，以及用子集法把NFA转换成DFA理论，编程实现将NFA(不确定有穷自动机)转换为DFA(确定有穷自动机)。
4、DFA的最小化
确定性有限自动机(DFA ,Deterministic Finite Automata)的最小化仍是有限自动机应用及实现方面的重要问题之一。DFA的最小化可以揭示状态之间的内在联系，便于其存储实现，便于建立用DFA描述的任务模型，一些理论问题也与最小化思想有关。DFA的最小化是指,构造一个与之等价且状态数最小的DFA,即等价最小DFA。许多文献给出了一个最小化算法，算法的思想是，构造状态集的一个划分，再将这个划分中的每个子集作为新的状态，从而得到等价最小DFA。
DFA的最小化可以揭示状态之间的内在联系，便于其存储实现,便于建立用DFA描述的任务模型，一些理论问题也与最小化思想有关。
5、语法分析之LL(1)文法
通过该课程设计了解了程序语言的自上而下的语法分析过程,提高了编程能力,能使我们了解编程语言更多的细节 设计目的与任务（1）读入文法（2）求出first(), follow()（3）判断是否为LL(1)文法
（4）若是，构造分析表；
（5）输入一个字符串看是否是文法的一个句子。
6、算符优先文法
一个文法，如果它的任一产生式的右边都不含有两个相继（并列）的非终结符，即不 含有如下形式的产生式的右部：
„QR„
则我们称该文法为算符文法。
假设文法中的任意两个终结符之间最多只有一个优先关系，则该文法称为算符优先文法。
该课程设计按照求,(P),(P)各两条规则，求出各非终结符的集。然后按照算符优先算法求出各终结符的算符优先关系，填写算符优先表，并将其输出。
7、LR(0)分析表的构造
LR分析技术是一种有效的自下而上分析技术，是一种规范归约，其中L表示从左到右扫描输入串，R表示构造一个最右推导的逆过程。这种方法可以适用于很大一类上下无关文法的语法分析。LR方法的基本思想是：在规范归约过程中，一方面记住已经移进和归约出的整个符号串，即记住“历史”；另一方面根据所用的产生式推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶端时，我们希望能够根据所记载的“历史”和“展望”以及“现实”的输入符号等三方面的材料，来确定栈顶的符号传是否构成相对某一产生式的句柄。
LR分析器的核心部分是一张分析表。这张分析表包括两部分，一是“动作”(ACTION)表，另一是“状态转换”(GOTO)表。对于一个文法，如果能用一个每步顶多向前检查K个输入符号的LR分析器进行分析，则这个文法就称为LR(K)文法。本文研究的LR(0)文法即K=0时的文法。
设计目的与任务
本课程设计所设计目的与任务是：通过C语言程序实现LR(0)分析表的构造，熟练掌握LR(0)分析表的构造方法，即利用拓广文法和构造项目集规范族的方法。了解LR(0)分析器的工作原理，并能利用LR(0)分析表对输入串进行分析。
8、逆波兰表达式生成算法
虽然源程序可以直接翻译为目标语言代码，但许多编译程序采用了独立于机器的、复杂性介于源语言和机器翻译语言之间的中间语言：后缀式（逆波兰表达式）等。这样做的好处是：
（1）便于进行与机器无关的代码优化工作；（2）使编译程序改变目标机更容易；
（3）使编译程序的结构在逻辑上更为简单明确。以中间语言为界面，编译前端和后端的接口更清晰。设计目的与任务
将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并能运行查看结果。
9、表达式的中间代码生成
源程序可以直接翻译为目标语言代码，但是许多编译程序却采用了独立于机器的、复杂性介于源语言和机器语言之间的中间语言。这样我们可以做下面工作：
（1）：便于进行与机器无关的代码优化工作；（2）：使编译程序以改变目标机更容易；（3）：使编译程序的结构在逻辑上更为简单明确；
而以中间语言为界面，编译前端和后端的接口更清晰，表达式可以用四个域分别称为OP、ORG1、ORG2及RESULT来表示。
四、时间安排
《编译原理课程设计》安排在第三学期进行，时间2周（17-18周）。
五、组织管理
1．由院、系指派经验丰富的专业教师担任指导教师。
2．课程设计实行指导教师负责制，由指导教师全面负责课程设计的指导与管理工作。
六、成绩考核与评定
学生课程设计结束后写出总结报告，对设计的内容和效果进行总结，按照学生在设计期间的表现，指导老师对每位学生写出评语和鉴定，系课程设计领导小组组织答辩，最后确定每位学生课程设计成绩，课程设计成绩分为优、良、中、及格和不及格五个等级。课程设计成绩为平时表现30%、设计报告50%、答辩20%。评分标准：
① 优秀：目的明确，态度端正，模范遵守学校的各项纪律。工作认真，积极 主动，吃苦耐劳，能出色的完成设计任务。撰写了高质量的总结报告。答辩准确流利。
② 良好：目的明确，态度端正，能遵守学校的各项纪律，工作比较积极主动。能较好地完成设计任务，成绩较突出，表现良好；撰写了质量比较高的实习报告。答辩较准确流利。
③ 及格：目的明确，态度基本端正，能遵守学校纪律，在督促下能开展工作 并完成一定的设计任务，无大的违纪违规现象；撰写了实习报告。通过了答辩。
④ 不及格：实习态度端正，不能遵守实习单位的纪律，不服从领导，自由散漫，工作消极被动，不能完成实习任务，实习期间有失职、旷工、打架、酗酒等大的过失。或无实习报告，没有通过答辩。
2．成绩评定
依据上述考核内容，最后采用优（>90分）、良（80～89分）、中（70～79分）及格（60～69分）、不及格（<60分）五级记分制评定学生课程设计成绩。
七、主要参考资料
教材：
《编译原理及实践》冯博琴等译，机械工业出版社 教学参考书
1、《程序设计语言与编译》龚天富、侯文永编，电子工业出版社。
2、《编译原理》吕映芝、张素琴、蒋维杜主编，清华大学出版社，1998年
3、《编译原理》胡伦骏、徐兰芳、刘建农编，电子工业出版社2002年
4、《编译原理》（第二版）蒋立源、康慕宁主编，西北工业大学出版社，2002年
5、《编译原理习题精选》陈意云、张昱著，中国科技大学出版社，2002年
6、《编译原理习题与解析》 伍春香著，清华大学出版社，2001年
7、《编译原理实验指导书》自编
第五篇：合肥工业大学编译原理课程设计
关于《编译原理》课程设计的有关说明
《编译原理》是计算机专业的一门重要的专业课程，其中包含大量软件设计思想。大家通过课程设计，实现一些重要的算法，或设计一个完整的编译程序模型，能够进一步加深理解和掌握所学知识，对提高自己的软件设计水平具有十分重要的意义。大家在进行课程设计时，可从所学内容中选择某个主题，抽象成一个模型，可适当进行简化。也可按提供给大家的一些参考选题进行设计。软件开发选择C/C++语言（也可以是你熟悉的任何语言）。最后每位同学都要认真撰写设计报告，格式要规范，内容要详尽，包括：设计题目，设计目的，设计内容，设计要求，问题的描述及解决的方法、原理、思想、算法（流程图），设计的输入和输出形式，测试、模拟的结果（屏幕拷贝、生成结果的打印输出），总结（体会），源程序清单，等等。
大家应把该门课的课程设计当成对自己学习效果的一次检验，当成是为在大四能够顺利完成毕业设计的一次基本功训练。希望每个同学尽可能不要都选择完全一样的题目。大家可以自主选题，或选择我提供的题目，也可以把几个题目合起来做（如开发一个小的编译器）。鼓励选择有一定技术难度、有一定工作量、综合性较强的题目，在评定成绩时将会给予好的成绩。
编译原理课程设计部分参考选题： 1． 题目： FORTRAN语言实型常数识别程序设计
设计内容及要求： 将教材P.41的图3.2(d)识别FORTRAN实型常数的状态转换图用程序实现。程序能够从用户输入的任意一个字符串中识别出FORTRAN实型常数，显示输出。
2． 题目： 简化的FORTRAN语言词法分析程序设计
设计内容及要求：将教材P.42上的表3.1的词法分析器构造出来，限制条件如教材所述。保留字的识别按标识符一样识别，通过查找保留字表区分是保留字还是标识符。程序能够从用户输入的源程序中，识别出的单词符号，并用二元式表示，显示输出或输出到文件中。
3． 题目： ε-CLOSURE(I)构造算法的程序实现
设计内容及要求：将ε-CLOSURE(I)构造算法用程序实现。要求：对任意
第1页 给定的一个NFA M(其状态转换矩阵及初态、终态信息保存在指定文件中)的某一个状态子集I，显示输出构造出的ε-CLOSURE(I)。
4． 题目： 从右线性文法构造与之等价的有限自动机的程序实现
设计内容及要求：构造一转换程序，实现将用户任意给定的右线性文法，转换为与之等价的有限自动机FA M，输出其状态转换矩阵（显示输出或输出到文件中）。
5． 题目： 从有限自动机构造与之等价的右线性文法的程序实现
设计内容及要求：构造一转换程序，实现将用户任意给定的有限自动机FA M，转换为与之等价的右线性文法，显示输出或输出到文件中。6． 题目： 有限自动机的状态转换图显示程序的实现
设计内容及要求：构造一程序，实现：将任一给定的有限自动机M(其状态转换矩阵及初态、终态信息保存在指定文件中)，在屏幕上显示输出M的状态转换图。程序应具有通用性，状态节点在屏幕上的分布应合理、美观。7． 题目： 从NFA构造与之等价的正规式r的程序实现
设计内容及要求：对给定的任意NFA M(其状态转换矩阵及初态、终态信息分别保存在指定文件中)。构造一程序，从NFA构造与之等价的正规式r，并显示输出。
8． 题目： 构造正规式r1|r2（或运算）的NFA的程序实现
设计内容及要求：对给定的正规式r1、r2，已知它们的NFA分别为M1、M2(其状态转换矩阵及初态、终态信息分别保存在指定文件中)。构造一程序，由此程序构造正规式r1|r2（或运算）的NFA(将其状态转换矩阵及初态、终态信息保存在指定文件中)。
9． 题目： 构造正规式r1r2（连接运算）的NFA的程序实现
设计内容及要求：对给定的正规式r1、r2，已知它们的NFA分别为M1、M2(其状态转换矩阵及初态、终态信息分别保存在指定文件中)。构造一程序，由此程序构造正规式r1r2（连接运算）的NFA(将其状态转换矩阵及初态、终态信息保存在指定文件中)。10． 题目： 构造正规式r*（闭包运算）的NFA的程序实现
设计内容及要求：对给定的正规式r，已知其NFA为M(其状态转换矩阵及初态、终态信息保存在指定文件中)。构造一程序，由此程序构造正规式r*（闭包运算）的NFA(将其状态转换矩阵及初态、终态信息保存在指定文件中)。11．
题目： 基于语法制导构造正规式的NFA
第2页 设计内容及要求：首先构造一个语法分析程序，实现对任意正规式的语法分析。语法分析方法采用自下而上的分析方法（如算符优先分析，或LR分析）。在此语法分析器的基础上，按照语法制导的思想，增加构造NFA的功能。生成的NFA将其状态转换矩阵及初态、终态信息保存在指定文件中。进一步实现把NFA确定化为DFA 的算法(其状态转换矩阵及初态、终态信息保存在指定文件中)。12． 题目： DFA M状态最少化的程序实现
设计内容及要求：构造一程序，实现：将给定的DFA M(其状态转换矩阵及初态、终态信息保存在指定文件中)的有限状态集S划分成若干互不相交的子集，使得：任何不同的两个子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的（要利用Ia函数，但并不需要构造ε-CLOSURE函数，因这是DFA）。输出化简后的DFA M’(其状态转换矩阵及初态、终态信息保存在指定文件中)。13． 题目： 把NFA确定化为DFA 的算法实现
设计内容及要求：构造一程序，实现：将给定的NFA M(其状态转换矩阵及初态、终态信息保存在指定文件中)，确定化为DFA M’。（要先实现ε-CLOSURE函数和Ia函数）。输出DFA M’(其状态转换矩阵及初态、终态信息保存在指定文件中)。14． 题目： 基于贪心算法的DFA 的程序实现
设计内容及要求：采用贪心算法实现教材P.62表3.5的DFA，要求从输入串中匹配最长的子串。输出所有识别出的符号串及其词形。15． 题目： 根据句型的推导构造其语法分析树的程序实现
设计内容及要求：构造一程序，实现：接受用户任意输入的一个句型的推导序列，生成该句型的语法分析树并显示输出。程序应具有通用性，语法分析树的节点在屏幕上的分布要合理、美观。16． 题目： 从语法分析树构造句型所有的推导的程序实现
设计内容及要求：构造一程序，实现：接受用户任意输入的一个句型的语法分析树（其表示存于指定文件中），生成该语法分析树中包含的该句型的所有推导（显示输出）。17． 题目： 递归下降分析程序的实现 设计内容及要求：
对文法 G: E→E+T|T 构造出G的递归下降分析程序。程序显示输出
T→T*F|F 匹配过程（即自上而下生成语法分析树的步骤，F→（E）|i 输出各匹配产生式序号即可）。
18．题目： 集合FIRST(X)构造算法的程序实现
第3页 设计内容及要求：构造一程序，实现教材P.78的FIRST(X)集合的构造算法。对任一给定的文法G，程序输出所有非终结符P的FIRST(P)。19． 题目： 集合FOLLOW(A)构造算法的程序实现
设计内容及要求：首先，构造一程序，实现教材P.78的FIRST(X)集合的构造算法。对任一给定的文法G，程序输出所有非终结符P的FIRST(P)。在此基础上，构造一程序，实现教材P.79的FOLLOW(A)集合的构造算法。对任一给定的文法G，程序输出所有非终结符A的FOLLOW(A)。20． 题目： 预测分析表构造算法的程序实现
设计内容及要求：对于给定的一个LL(1)文法，假定所有非终结符号P的集合FIRST(P)和集合FOLLOW(P)都已知，构造其预测分析表（实现教材P.79给出的预测分析表构造算法）。对教材P.79给出的例4.7构造出预测分析表。程序显示输出预测分析表或输出到指定文件中。21． 题目： 预测分析表自动构造程序的实现
设计内容及要求：对于任意输入的一个LL(1)文法，构造其预测分析表。要求：首先实现集合FIRST(X)构造算法和集合FOLLOW(A)构造算法，再实现教材P.79给出的预测分析表构造算法。程序显示输出预测分析表或输出到指定文件中。22． 题目： 预测分析程序的实现 设计内容及要求：
对文法 G: E→E+T|T 按教材P.76表4.1构造出G的预测分析程序，T→T*F|F 程序显示输出如P.78那样的匹配过程。
F→（E）|i 23． 题目： 集合FIRSTVT(P)构造算法的程序实现
设计内容及要求：构造一程序，实现教材P.91的FIRSTVT(P)集合的构造算法。对任一给定的算符文法G，程序输出所有非终结符P的FIRSTVT(P)。24． 题目： 集合LASTVT(P)构造算法的程序实现
设计内容及要求：构造一程序，实现教材P.91的LASTVT(P)集合的构造算法。对任一给定的算符文法G，程序输出所有非终结符P的LASTVT(P)。25． 题目： 算符优先分析算法的程序实现 设计内容及要求：
对文法 G: E→E+T|T 采用教材P.90表5.1，实现P.93描述的算符优先
T→T*F|F 分析算法。程序显示输出“移进-归约”的步骤。F→P↑F|P
第4页 P→（E）|i 26． 题目： 带出错处理的算符优先分析算法的程序实现 设计内容及要求：
对文法 G: E→E+T|T 采用教材P.98表5.3，实现P.93描述的算符优先
T→T*F|F 分析算法。程序显示输出“移进-归约”的步骤。
F→(E)|i 要编制各出错处理子程序。
27． 题目： 优先表构造算法的程序实现
设计内容及要求： 实现教材P.92优先表构造算法。对任一给定的算符优先文法G，假定所有非终结符P的FIRSTVT(P)、LASTVT(P)均已知。以教材P.90例5.4文法为例，程序生成表5.1优先表。28． 题目： 优先表自动构造程序的实现
设计内容及要求：对任一给定的算符优先文法G，构造其优先表。要求：首先实现对于非终结符P的FIRSTVT(P)构造算法和LASTVT(P)构造算法，再实现教材P.92给出的优先表构造算法。以教材P.90例5.4文法为例，程序生成表5.1优先表。29． 题目： 优先函数构造程序的实现
设计内容及要求：构造一程序，实现：根据优先关系表构造优先函数。输入的优先表假定保存在指定文件中，构造出的优先函数可显示输出，或输出到指定文件中。30． 题目： 消除左递归算法的程序实现
设计内容及要求：构造一程序，实现教材P.70消除左递归算法。对于用户任意输入的文法G，输出一个无左递归的等价文法，可显示输出，或输出到指定文件中。31． 题目： 消除回溯算法的程序实现
设计内容及要求：构造一程序，实现：消除文法每一条产生式候选式的公共左因子。对于用户任意输入的文法G，输出一个无回溯的等价文法，可显示输出，或输出到指定文件中。32． 题目： LR分析器总控程序的实现
设计内容及要求：对P.101中的文法，按图5.5LR分析表构造LR分析器。要求程序按P.102例5.7那样，对于输入串i*i+i，输出LR分析器的工作过程。33． 题目： 识别文法活前缀的NFA构造程序的实现
设计内容及要求：构造一程序，对任意给定的文法G：①构造并输出G的所有LR(0)项目；②用这些LR(0)项目构造并输出识别文法活前缀的NFA(输出其
第5页 状态转换矩阵)。34． 题目： LR(0)项目集规范族构造程序的实现
设计内容及要求：构造一程序，对任意给定的文法G，构造识别文法活前缀的DFA，输出DFA的状态转化矩阵及LR(0)项目集规范族。要求按教材P.107所给的ITEMSETS(G’)构造，要实现CLOSURE(I)、GO(I,X)函数。按P.105例5.8给出测试结果，可输出到指定文件中。35． 题目： LR(0)分析表构造算法的程序实现
设计内容及要求： 构造一程序，实现LR(0)分析表构造算法。根据教材P.106图5.7的识别文法活前缀的DFA，输出如P.109表5.4的LR(0)分析表，可输出到指定文件中。36． 题目： LR(0)分析器自动构造程序的实现
设计内容及要求：对任意给定的文法G，构造识别文法活前缀的DFA，输出DFA的状态转化矩阵及LR(0)项目集规范族；实现LR(0)分析表构造算法；实现LR分析器总控程序。程序输出一个完整的LR(0)分析器源程序，可输出到指定文件中。37． 题目： SLR(1)分析表构造算法的程序实现
设计内容及要求：构造一程序，实现SLR(1)分析表构造算法(假定所给文法识别文法活前缀的DFA、LR(0)项目集族、所有非终结符FOLLOW集合均已构造出来了)。根据教材P.111例5.11文法为输入，构造其SLR(1)分析表。38． 题目： LR(1)项目集规范族构造程序的实现
设计内容及要求：构造一程序，对任意给定的文法G构造LR(1)项目集规范族（按教材P.115所述方法构造，要实现CLOSURE(I)、GO(I,X)，集合FIRST的构造方法参见教材P.78）。39． 题目： LR(1)分析表构造算法的程序实现
设计内容及要求：构造一程序，实现LR(1)分析表构造算法(假定所给文法识别文法活前缀的DFA、LR(1)项目集族已构造出来了)。根据教材P.116图5.10的LR(1)项目集族和GO函数为输入，构造并输出其LR(1)分析表5.5。40． 题目： LR(1)分析表自动构造程序的实现
设计内容及要求：对任意给定的文法G构造LR(1)项目集规范族（按教材P.115所述方法构造，要求实现CLOSURE(I)、GO(I,X)、FIRST（集合FIRST的构造方法参见教材P.78）；然后实现LR(1)分析表构造算法。以教材P.115例5.13为输入，构造并输出其LR(1)分析表5.5。
第6页 41． 题目： LALR(1)项目集规范族构造程序的实现
设计内容及要求：假设对于给定文法，识别文法活前缀的DFA、LR(1)项目集族已构造出来了。构造一程序，检查两个LR(1)项目集是否为同心集（可任意输入），若是，则输出合并后的同心集，并检查合并后的集合是否含有冲突项目（指出存在何种冲突），输出合并同心集后的识别文法活前缀的DFA，及LALR(1)项目集规范族。42． 题目： LALR(1)分析表自动构造程序的实现
设计内容及要求：对任意给定的文法G构造LR(1)项目集规范族（按教材P.115所述方法构造，要求实现CLOSURE(I)、GO(I,X)、FIRST（集合FIRST的构造方法参见教材P.78）；然后构造LALR(1)项目集规范族；再实现LALR(1)分析表构造算法。以教材P.115例5.13为输入，构造并输出其LALR(1)分析表5.6。43． 题目： 带出错处理的LR分析器总控程序的实现
设计内容及要求：按教材P.127表5.9分析表构造一LR分析器，输出语法分析过程（如P.128所述），要构造各出错处理子程序。44． 题目： 算术表达式从中缀式翻译成后缀式的程序实现
设计内容及要求：设计一个语法制导翻译器，将算术表达式从中缀式翻译成后缀式。要求：先确定一个定义算术表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的算术表达式，程序将其转换成后缀式输出。45． 题目：将算术表达式转换成抽象语法树的程序实现
设计内容及要求：设计一个语法制导翻译器，将算术表达式转换成抽象语法树。要求：先确定一个定义算术表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的算术表达式，程序将其转换成抽象语法树输出(可按一定格式输出到指定文件中)。46． 题目：将算术表达式转换成DAG的程序实现
设计内容及要求：设计一个语法制导翻译器，将算术表达式转换成DAG。要求：先确定一个定义算术表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的算术表达式，程序将其转换成DAG输出(可按一定格式输出到指定文件中)。
第7页 47． 题目：将算术表达式转换成三元式的程序实现
设计内容及要求：设计一个语法制导翻译器，将算术表达式翻译成三元式。要求：先确定一个定义算术表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的算术表达式，程序将其转换成三元式输出(可按一定格式输出到指定文件中)。48． 题目：将算术表达式转换成间接三元式的程序实现
设计内容及要求：设计一个语法制导翻译器，将算术表达式翻译成间接三元式。要求：先确定一个定义算术表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的算术表达式，程序将其转换成间接三元式输出(可按一定格式输出到指定文件中)。49． 题目：将算术表达式转换成四元式的程序实现
设计内容及要求：设计一个语法制导翻译器，将算术表达式翻译成四元式。要求：先确定一个定义算术表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的算术表达式，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。50． 题目：将布尔表达式转换成四元式的程序实现
设计内容及要求：设计一个语法制导翻译器，将布尔表达式翻译成四元式。要求：先确定一个定义布尔表达式的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的布尔表达式，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。51． 题目：将条件语句转换成四元式的程序实现
设计内容及要求：设计一个语法制导翻译器，将条件语句翻译成四元式。要求：先确定一个定义条件语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的条件语句，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。52． 题目：将WHILE语句转换成四元式的程序实现
设计内容及要求：设计一个语法制导翻译器，将WHILE语句翻译成四元式。
第8页 要求：先确定一个定义WHILE语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的WHILE语句，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。53． 题目：将FOR语句转换成四元式的程序实现
设计内容及要求：设计一个语法制导翻译器，将FOR语句翻译成四元式。要求：先确定一个定义FOR语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的FOR语句，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。54． 题目：将SWITCH语句转换成四元式的程序实现
设计内容及要求：设计一个语法制导翻译器，将SWITCH语句翻译成四元式。要求：先确定一个定义SWITCH语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的SWITCH语句，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。55． 题目：将包含数组引用的赋值语句转换成四元式的程序实现
设计内容及要求：设计一个语法制导翻译器，将包含数组引用的赋值语句翻译成四元式。要求：先确定一个定义包含数组引用的赋值语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的包含数组引用的赋值语句，程序将其转换成四元式输出(可按一定格式输出到指定文件中)。56． 题目：嵌套过程中的说明语句翻译的程序实现
设计内容及要求：设计一个语法制导翻译器，完成对说明语句的翻译，即构造每个过程的符号表，填写所有名字在符号表中的有关信息。要求：先确定一个定义允许嵌套过程的说明语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一组正确的说明语句，程序将输出相应的符号表(可按一定格式输出到指定文件中)。57． 题目：基本块划分算法的程序实现
设计内容及要求：根据基本块划分算法，构造一个基本块划分程序，实现：对于任意输入的一个四元式程序，将其划分为基本块，输出各基本块，并输出程
第9页 序流图。以P.279例10.1为输入，输出P.281图10.8.58． 题目：将基本块转换成DAG的算法的程序实现
设计内容及要求：根据将基本块转换成DAG的算法，实现：对于任意输入的一个基本块（四元式程序），将其转换成DAG并输出(可按一定格式输出到指定文件中)。以P.283例10.4为输入，输出P.284图10.10构造过程。59． 题目：由DAG重构基本块的程序实现
设计内容及要求：按照DAG节点构造顺序，重构基本块四元式代码。输入的DAG按一定格式存于指定文件中，输出的基本块四元式代码按一定格式输出到指定文件中。以P.284图10.10为输入，输出基本块四元式代码。60． 题目：局部优化程序的实现
设计内容及要求：根据将基本块转换成DAG的算法，实现：对于任意输入的一个基本块（四元式程序），将其转换成DAG；然后按照DAG节点构造顺序，重构基本块四元式代码。以P.283例10.4为输入，完成并输出局部优化。
（待续）
。。。(大家也可以自行设计一个设计题目)
第10页
点击咨询 