第一篇:编译原理设计题目
编译原理设计题目
设计原则:
1.使用了《编译原理》中的某些内容,如原理、概念等;
2.具有完整性,表现或演示了某种完整的功能;
3.实用性,有一定的应用价值。
设计目的:花了足够的时间,做了一定量的工作,从而使得水平提高。设计语言:任意熟悉的开发环境。
设计步骤:
1.选好题目
2.思考你将要把软件编成什么模样?
3.写出需求分析
4.开始设计
5.测试
第一大类:充分利用《编译原理》
1.与表达式有关的内容:
表达式计算器:这是一款算术表达式计算程序,用户通过输入表达式达到计算的目的,可代替目前普遍使用的计算器。使用了编译原理中的词法分析、算符优先分析等。根据功能的不同可分为:
无符号整数表达式计算器:输入无符号整数表达式,输出结果。难度:较难。工作量:中等。
整数表达式计算器:考虑负数。难度:较难。工作量:中等。
定点实数表达式计算器:难度:较难。工作量:中等。
通用表达式计算器:考虑1.23e-2的形式输入。难度:难。工作量:中等。 函数表达式计算程序:这是一款能计算函数值的实用程序,用户输入含有自变量x的函数表达式被电脑接受后,可接着输入自变量x的值,电脑输出函数值y的值。用户可以是数学、物理等教师,他们可以在上课教授与函数有关的课程时进行课堂演算,也可以在备课时验证数据;用户也可以是工程技术人员和学生。使用了词法分析、算符优先分析。根据功能的不同可以分为:
多项式函数计算程序:只处理多项式函数,如f(x)=x^3+x^2+5等。难度:较难。也可设计成其他专用函数计算程序,如幂函数计算、三角函数计算等。但要避免出现不同用,如不要设计成仅能处理f(x)=2^x的幂函数,因为这样的函数利用普通编程就能实现,无法体现编译原理。工作量:中等。
通用初等函数计算程序:能处理所有的初等函数的计算。如f(x)=3*sin(x/2+3.1415)+x^2等。难度:难(因为涉及到函数名称和参数的识别问题)。工作量:较大。
二元或多元函数的计算:请参考立体解析几何中相关方程。如f(x,y)=x^2+y^2等。难度和工作量同一元函数的计算。
逻辑运算分析:可对关系表达式进行分析,并得出结果。这个设计结果可改变后用于电路分析、谓词演算等。难度:较难。
2.与字符搜索、匹配有关的内容:
字符串搜索程序:用户输入要查找的字符串的正则表达式,软件可在大量文本中找
到符合描述的字符串。这个设计可参考微软.NET的正则表达式的功能。使用到正规式、词法分析等,还需要有较大的设计技巧。根据功能的不同可以分为:
名称查找程序(类似于文件名、词典等):存有大量的名称,如abc,123,a1,ab1245
等,输入要查找的规则,找出符合规则的名称。
方案1:通配符,把“*、?”当作通配符:如输入“a*”,显示“abc,a1,ab1245”;
输入“a?”,输出“a1”。
方案2:正规式,把“*”当作“闭包”,把“|”当作“或”:如输入“(a|b)1”,输出“a1”;输入“(a|b)*c”,输出“abc”。
方案3:只要包含正规式即可,当名称中包含该正规式,就输出来:如输
入“(a|b)1”,输出“a1,ab1245(含有b1)”;输入“(a|b)*”,输出
“abc,a1,ab1245”。
方案4:含有通配符的正规式,设“@”表示任意字母,“$”表示任意数
字(其他可再设多一点,如表示符号等,但会减少名称中的符号种数):
如输入“a@*” 输出“abc”;输入“a(@|$)*”,输出“abc,a1,ab1245”。
(以上涉及到正规式的方案难度较大,其他难度一般。注:以上的@$等
符号是随便设定的,与.NET中通用的符号不同且有冲突的,请在实际编
程时修改之。)
文本搜索程序:在一连串文本中搜索所需的字符串。同“名称查找程序”中的有关正则式的方案,难度较大,具体正规式包含哪些符号和通配符可另定。
(关于正则表达式的介绍参见另一文档,详细信息见.NET框架联机文档)
转义符的识别:C语言的字符串常量书写时使用了大量的转移符,如“”表示单
斜杠,而“n”表示换行(同“u000A”),“x20”表示十六进制表示形式(恰好两位)与 ASCII 字符匹配(这里代表值为32的ASCII字符,即空格)。请参照C语言教材,编制一个软件,输入包含转义符的字符串,输出没有转义符的真实字符串。难度:一般。工作量:一般。
源程序中特定信息的提取:可以提取全局变量列表、所有变量列表、所有函数列表、所有名称列表、注解信息等。主要利用词法分析的原理,有时用到有限自动机的运行。难度:一般,实用性强。
3.纯粹的编译原理的实现
迷你编译器的设计:利用Lex/Yacc等实用工具,开发一个编译器。通过自学有关的编译器生成工具,定义小型C语言,设计相应的文法,利用编译器生成工具生成一个自己的编译器。难度高,需要自学大量的东西,实用性强。
CPU仿真:自己定义一个CPU指令,指令若干条、寄存器若干个、内存若干,用
软件模拟汇编代码的执行。难度高,实用性高,可扩展性强。
有限自动机的确定化和最小化:输入一个不确定的优先自动机,输出它的确定化、最小化后的确定的优先自动机。难度:较难。
正规文法转化为有限自动机:输入正规文法,自动转化为不确定的优先自动机。为
了实用,可以考虑加点其他功能(参考有限自动机的确定化和最小化)。难度:一般。
正则表达式转化为有限自动机:输入正则表达式,转化为不确定的有限自动机(参
考相关题目)。难度:较难。
万能有限自动机的运行:以状态转移表驱动的万能有限自动机的运行,输入不同的状态表(也可以以状态转换函数的形式输入),可以使程序识别不同的字符串,从而达到万能的运行效果。难度:较难。
第二大类:利用《编译原理》的有关概念
1.词频分析程序:分析一篇文章中词的出现频率,从而得出有意义的结果。如果仅使用字符串匹配的概念,则和编译原理搭不上边了,可以加点正则表达式匹配的概念(参考.Net关于正则表达式的例子和说明),这样实用性会更强一点。难度一般,实用性强。
2.在应用软件中添加正则表达式的校验(或搜索)功能:这是一类程序,这类程序完成某个实际的应用,但是在某个环节需要对数据进行校验,或从一大片文本中搜索特定的子串,那么,在校验和搜索时可利用正则表达式。而正则表达式是很多开发语言和运行库都提供的,你只需要调用其中的功能就能达到校验或搜索的目的。如用户注册时的密码的字符组成校验,用户手机号码的校验,用户名的组成校验、日期校验等;搜索,如在一篇文章中搜索并提取出所有货币表示的内容、人的姓名、数字、日期、单词、手机。其中一个实用的例子就是:分析web网页,提取其中的文本,即滤掉html标记,获取有用的文本信息;也可以差找到网页中游多少个超级链接,从而得到网页内的超链接列表;也可以搜索到网页内的邮箱地址列表。
3.查找替换:你能否在你的某个应用程序中设立查找替换功能,支持通配符的查找,然后在文本中标出,或显示出,或替换之。难度:一般。实用性强。
第二篇:编译原理课程设计
课 程 设 计 报 告
设计题目:一个简单文法的编译器前端的设计与实现
班
级: 计算机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画图的能力。此外,对于文档的编写和美化自己也获得了许多有用的经验。[
第三篇:编译原理 学习心得
国际学院 0802 杨良燕 200819100227
《编译原理》课程学习心得
《编译原理》是计算机专业的一门重要课程,正如教材
第一章的引论所述,“编译程序是现代计算机系统的基本组成部分之一”。“一个编译程序就是一个语言翻译程序,语言翻译程序把一种语言(源语言)书写的程序翻译成另一种语言(目标语言)的等价程序”。
通过这一学期的学习,我觉得编译原理是一门理论性很强的课程,从文法和语言的概念到LL(1)文法和LR(0)文法的分析,几乎都是对具体问题的抽象。因而,我们需要更多的时间来理解、掌握相关的知识,当然在这一过程中也存在很多问题,比如我们后期学习具体文法的分析方法时,对于文法的概念不够清晰,影响了上课的效率,知道老师再次给我们讲解了文法等基础的知识点,我们才慢慢掌握后面所学的LL(1)文法等,也发现了知识点之间的关联。此外,这门课程的课时被安排得很少,一周只有一次,这样很不利于我们对这门重要课程的理解和掌握。但是我觉得我们很幸运,因为老师在有限的课程中尽量将知识点以比较容易接受的方式给我们讲解,教我们用简单的方法理解记忆不同的知识,对于我们提出的问题,无论课上或是课外,老师一直是不厌其烦,甚至利用课余时间为我们讲解重要的难题。
编译原理这门课程不仅仅在于其本身的理论价值,更在于为我们解决问题提供的思维方式和方法。从LL(1)到LR(0),问题不断被解决的同时,又有一个个新的问题提了出来。对计算机语言世界的知识积累,像滚雪球一样越滚越大。这个逐渐递进,逐渐解决问题的过程对我来说是收获很大的。整个过程好像踏着前人研究编译理论的路线,不断感觉他们遇到的问题,更重要的是他们解决问题的思路。编译原理的课程带给我的不只是如何去编译程序这样的理论知识,相信更重要的是一种如何“自动计算”的思路。通过对相关编译问题的具体分析,让我体会最深的是一种“自动计算”的思想,同时完成编译试验后,更是感到了一种“自动计算”的快乐。”然而我明白自己虽然对编译有了一定的了解,我懂得了文法的分析,学会了构造确定和非确定有限自动机,学会了LL(1)文法和LR(0)文法等,但是并没有完全掌握,对于这些知识点的实质性和其他方面,更是认识不深。作为一名学习计算机科学与技术的学生,我明白编译原理是软件工程的基础,课程的结束并不意味着学习的结束,只有通过以后的学习,才能更深入地了解编译原理。
第四篇:编译原理论文
编译原理心得体会
编译原理是计算机专业的一门重要专业课,旨在介绍编译程序构造的一般原理和基本方法,在计算机本科教学中占有十分重要的地位。
该课程理论性与实践性都很强,我们在学习是普遍感到内容非常抽象,不易理解,内容多且繁琐,难以完整、全面地掌握编译原理的有关知识,更不用说灵活运用编译原理知识从事相关设计或应用于其他领域。虽然只有少数人从事编译方面的工作,但是这门课在理论、技术、方法上都对我们提供了系统而有效的训练,有利于提高软件人员的素质和能力。
在我们学习编译原理以前,都认为编译原理只能应用在写程序语言的编译器上,觉得用处不大,学习兴趣不高。而在后来的学习中,我们逐渐认识到计算机专业的学生,除了要会编写程序语言之外,还应该了解它是如何被计算机所识别,这才是真正并且透彻地学习软件。另外,编译器中每一个模块的编写,都能对我们的编程能力的提高有很大帮助。在今后若从事软件工程,这门课程也能够对编写程序有所帮助。
为了能够系统掌握这门专业课,我们把编译原理分为以下几个模块:①语言和文法;②词法分析;③语法分析;④语义分析和中间代码生成;⑤代码优化和目标代码生成。
在学习的开始,我们需要掌握什么是编译,编译分为哪些阶段,编译程序和解释程序的区别等等。在做好了这些方面的准备后,开始了系统的学习。
语言和文法部分的知识包括文法基本概念及文法的二义性。基本概念有文法定义、推导、句型、句子等等。二义性文法是通过画语法树的方法来证明。
词法分析中的重点是有穷自动机DFA的生成以及DFA和正规式与正规文法的关系。还要熟练掌握NFA转换为DFA的方法及DFA的化简。
语法分析包括自上而下和自下而上分析。自上而下分析着重掌握LL(1)文法,自下而上分析重点掌握算符优先文法和LR(0)、SLR(1)文法。
语义分析重点是其功能,中间代码生成和语法制导翻译定义与方法。
最后,优化分为局部优化和循环优化,重点理解一些关键词,如基本块、流图等,要学会自己画出程序流图。用DAG图进行局部优化是重点。
在学习文法时,对文法的组成,用法都较为明了,而在真正做题时却感到十分吃力。例如给出了一个语言,要求写出它的上下文无关文法,就感到十分棘手,所以今后在这方面要加大练习量,以熟练掌握。
而在之后的词法分析和语法分析中,我感到在看基本原理时十分困难,通常要长时间钻研才能够有所了解,而一旦掌握了基本原理,做题时就感到十分顺畅了。例如,在刚接触到LR(0)文法时,我用了大量的时间去学习它的原理,掌握之后,在列LR(0)分析表和写分析过程时,只要思路清晰,就会比较顺畅,而且不会犯错。
下面是我认为的比较有效的学习编译原理的步骤:
1.先利用ANTLR之类的编译器生成工具,做一个小程序(如上面提到的HTML文件转化成纯文本文件的程序),所需知识只是正则表达式的基本知识和生成工具本身的使用方法(可以看联机帮助和网上教程(tutorial)来掌握).这样做的好处是:
1)可以体会到编译原理的实用性,提高学习兴趣
2)入门容易,消除编译原理学习的畏难情绪.3)获得词法分析器和语法分析器的感性认识,有利于加深对理论的理解.4)获得编译器自动生成工具(compiler compiler)的使用经验,提高解决实际问题的能力.(实际工作很多都不是手编而是利用工具的)
2.象ANTLR之类的工具是开源(open source)的,可研究其源码,以便必要时自己手编分析程序.3.回过头来看编译原理教材.这时大概会发现,很多理论很容易懂,剩下的只有上面说的几个难点,多看几遍,重点突破.4.结合教材所附源码,进一步加深对教材的理解。以上就是我对这门课的心得体会。
第五篇:编译原理实验报告
编译原理实验报告
报告完成日期 2018.5.30
一. 组内分工与贡献介绍
二. 系统功能概述;
我们使用了自动生成系统来完成我们的实验内容。我们设计的系统在完成了实验基本要求的前提下,进行了一部分的扩展。增加了声明变量类型、类型赋值判定和声明的变量被引用时作用域的判断。从而使得我们的实验结果呈现的更加清晰和易懂。
三. 分系统报告;
一、词法分析子系统
词法的正规式:
标识符
<字母>(<字母>|<数字字符>)* 十进制整数
0 |(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* 八进制整数 0(1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)* 十六进制整数 0x(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)* 运算符和分隔符 +| * | / | > | < | = |(|)| <=|>=|==; 对于标识符和关键字: A5—〉 B5C5 B5—〉a | b |⋯⋯| y | z C5—〉(a | b |⋯⋯| y | z |0|1|2|3|4|5|6|7|8|9)C5|ε 综上正规文法为: S—〉I1|I2|I3|A4|A5 I1—〉0|A1 A1—〉B1C1|ε C1—〉E1D1|ε D1—〉E1C1|ε
E1—〉0|1|2|3|4|5|6|7|8|9 B1—〉1|2|3|4|5|6|7|8|9 I2—〉0A2 A2—〉0|B2 B2—〉C2D2 D2—〉F2E2|ε E2—〉F2D2|ε
C2—〉1|2|3|4|5|6|7 F2—〉0|1|2|3|4|5|6|7 I3—〉0xA3 A3—〉B3C3 B3—〉0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f C3—〉(0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f)|C3|ε
A4—〉+ |-| * | / | > | < | = |(|)| <=|>=|==; A5—〉 B5C5 B5—〉a | b |⋯⋯| y | z C5—〉(a | b |⋯⋯| y | z |0|1|2|3|4|5|6|7|8|9)C5|ε
状态图
流程图:
词法分析程序的主要数据结构与算法
考虑到报告的整洁性和整体观感,此处我们仅展示主要的程序代码和算法,具体的全部代码将在整体的压缩包中一并呈现
另外我们考虑到后续实验中,如果在bison语法树生成的时候推不出目标的产生式时,我们设计了报错提示,在这个词的位置出现错误提示,将记录切割出来的词在code.txt中保存,并记录他们的位置。
以下是我们的主要代码:
进制的识别:
结果展示:
二、语法分析子系统
根据选择的语法分析方法进行描述
我们使用了递归子程序发,并且对原有的产生式进行了改写,改写后的结果如下: P→LP1|L L→S
S→id=E|{P}|if C then S | if C then S
1else S2 | while C do S1 C→E1C’
C’→>E2| E→int8E’| int10E’| int16E’| idE’|T E’→+T|-T||+TE’|-TE’ T→int8T’| int10T’| int16T’| idT’|F T’→*F|/F|*FT’|/FT’ F→(E)|int8|int10|int16|id 简化的语法图: S的语法图: C的语法图: E的语法图: T的语法图: F的语法图: 流程图: 语法分析子系统的主要数据结构与算法 我们采用了自动生成技术,同样在这里也是展示主要的核心功能代码,全部的代码展示在压缩包中: 我们在设计时,实现了产生式对应的字符串同时标识产生式定义的int值 辅助程序: 生成语法树的程序: 1.树节点: 2.创建新节点 3.创建实数类型新节点 4.创建标识符类型新节点 5.输出语法树 三、三地址码生成器 算法的基本思想: 我们增加了声明变量类型、类型赋值判定和声明的变量被引用时作用域的判断。从而使得我们的实验结果呈现的更加清晰和易懂。 在报错的时候,我们会呈现类型、作用域和赋值三种的问题的报错信息。 流程图: 算法展示: 四、实验体会 这次实验其实总的来说是让我们更加清晰的理解到了我们所学的内容。有时候我们上课听讲,课下复习写作业的时候,其实看似掌握了所学内容,但实际上并没有亲身体会的操作很难让我们深刻的理解其中的相关意义。通过这次实验,我们能够从根源处了解到了我们所学的内容,并且基于我们理解之后的输出。比如词法分析不能采用空格来区分单词,因为存在加减乘除等运算符和分隔符,使用空格来区分可能会造成错误的分解。又比如我们再在程序设计中,常常体会到效率的重要性。影响词法分析的效率的主要因素是各个状态的分支如何规划。如果每个进来的单词都能在最短的时间和最少的匹配次数内找到其入口,则效率将得到很大程度上的提高。所以由此我们产生了声明变量类型、赋值和作用域的想法,将其放在最后来进行判断,这样可以提高整体的执行效率。 另外,这次小组成员彼此不在一个班级,这样从某一方面来说,也加强了我们互相快速熟识并团结协作的能力,有了这种体验,我想我们在今后的生活中,面对这种情况的时候,将会变得更加有经验。 五、源程序 词法分析器: 输入结果: 输出结果: 语义分析结果: 输入: 第二组数据的输入: 输出: 三地址码的输入: 第二组数据的输入: 输出: