编译原理讲义.docx
- 文档编号:15967413
- 上传时间:2023-07-09
- 格式:DOCX
- 页数:31
- 大小:715.95KB
编译原理讲义.docx
《编译原理讲义.docx》由会员分享,可在线阅读,更多相关《编译原理讲义.docx(31页珍藏版)》请在冰点文库上搜索。
编译原理讲义
编译原理讲义
一、导入课
1.编译原理这门课,旨在介绍编译程序构造的一般原理和基本方法,首先我们需要了解下述几个问题
a)“编译程序是什么?
”
我们学过C语言,用C语言进行编程的时候,我们用到了开发环境VC,这个VC就是一个编译程序
b)“编译程序如何工作的?
”
如果把c语言比喻成英语,机器语言比喻成汉语,那么编译程序就是翻译员。
我们有个相类似的例子:
“翻译员是如何翻译的?
”
举例子:
IamChinese.IlikeChina.Ihaveafriend.HisnameisJim.
我们的理解和翻译是这样的:
一段一段的理解
一句一句的翻译,翻译时候要考虑上下文
每一个词的翻译都根据上下文翻译比如his
2.为什么要学习编译原理,你知道哪些编译程序?
a)为什么要学习编译原理?
有科学家这么说:
“编译原理是计算机科学中的皇冠”
学会了编译程序的构造,没有任何其他程序在理论上、算法上能够难住你,因为编译程序的构造用到了最复杂的一些算法
b)“有哪些编译程序”:
i.c语言的vc6.0visualstudio2010linux下面的:
gcc
ii.Java语言的编译程序eclipse
......iii.每种语言都有对应的编译程序
3.编译程序的发展历程:
机器语言——汇编语言——高级语言
在1954年至1957年期间,IBM的JohnBackus带领的一个研究小组对FORTRAN语言及其编译器的开发,使得上面的担忧不必要了。
但是,由于当时处理中所涉及到的大多数程序设计语言的翻译并不为人所掌握,所以这个项目的成功也伴随着巨大的辛劳。
几乎与此同时,人们也在开发着第一个编译器,NoamChomsky开始了他的自然语言结构的研究。
他的发现最终使得编译器结构异常简单,甚至还带有了一些自动化。
为了将人们易懂易使用的高级语言转化为机器能够执行的低级语言,我们制作了编译器。
4.编译程序的定义(概念):
编译器就是将“高级语言”翻译为“机器语言(低级语言)”的程序,其它程序则为系统程序和应用程序。
通常包含两种:
编译器和解释器
a)编译器主要做哪些工作:
i.检查变量是否正确定义,正如翻译过程首先检查每个单词是否拼写正确。
ii.检查语句是否正确,正如翻译过程看每个句子的语法是否正确
iii.检查变量使用时的类型是否匹配,正如看每个句子的但是使用含义是否符合逻辑
iv.根据上下文翻译语句,正如根据上下文翻译语句
v.。
。
。
b)现代编译器的主要工作流程
源代码 (sourcecode)→ 预处理器 (preprocessor)→ 编译器 (compiler)→ 目标代码 (objectcode)→ 链接器 (Linker)→可执行程序
解释器的主要工作流程:
源代码 (sourcecode)→ 预处理器 (preprocessor)→ 解释器 (compiler)→直接执行
5.我们这门课的主要目标:
构建一个解释程序,解释执行我们写好的代码
大体流程如下:
源代码 (sourcecode)→ 语法分析器 (preprocessor)→ 语义分析器 (compiler)→直接执行
2、预备知识
1.我们的语言:
KDXF
我们语言有哪些基本关键词,有哪些语句?
a)变量定义:
三种变量:
布尔型bool数字型num字符串型str
bool变量名
num变量名
str变量名
b)赋值语句变量名=布尔值或数值或字符串
c)输入输出语句:
打印语句pt(变量名)
输入语句sc(变量名)
c)判断语句:
两种
if语句
if(布尔值)
{
语句
}
ifelse语句
if(布尔值)
{
语句
}
else
{
语句
}
d)循环语句
while(数值变量<或<=或>或>=数字常量或数值变量)
{
语句
}
2.教科书上经常提到的理论知识:
a,词法规则
有穷自动机
语言的字母表为:
∑={a---z、A—Z、0—9、(、)、[、]、、.、!
、~、+、-、*、/、&、%、<、>、=、^、|、?
、,、;}
变量名的构成规则:
字母打头的字母、数字和下划线构成的符号串。
如:
a1、av_e、day5
类比c语言的定义
b,语法规则
语法规则规定了如何从单词符号形成更大的结构(即语法单位),换言之,语法规则是语法单位的形成规则
一般的程序设计语言的语法单位有:
表达式、语句、分程序、函授、过程和程序等
KDXF语言包括:
表达式、语句、分程序
计算表达式的分析
表达式:
E→E+T
E→E-T
E→T
T→T*F
T→T/F
T→F
F→(E)
F→id
布尔表达式:
B→BorB
B→BandB
B→notB
B→(E)
B→idrelopid
B→true
B→false
三、词法分析
1.什么是词法分析?
类似问题:
“判断一个词是不是英文词汇,是什么样的词汇,动词还是名词,等等?
”
a)
如果把c语言比喻成英语,机器语言比喻成汉语,那么编译程序就是翻译员。
分析提问:
i.如何判断一个词是不是可能的合适的英文单词?
比如:
do,what,so,2liu,林j,...
其中哪些是英文单词,哪些不是?
b)判断一个词是不是合适的语言中的词汇,是哪种词汇,这个就是词法分析的过程
2.编译器实现过程中的词法分析是怎么样进行的?
i.扫描每行代码,确定提取该行中的某个单词
ii.判断该单词是不是语言的关键字
iii.如果是关键字,返回一个设定值,如果不是关键词,判断是常量还是变量
iv.如果是数字常量,返回一个设定值;如果是合适变量名,返回一个设定值;
v.。
。
。
有穷自动机的概念:
判断一个变量名是否是符合要求的词汇,这个时候会用到有穷自动机的概念
......
设定我们的编译程序进行词法分析,需要的函数:
1)我们需要从需要编译的代码文件中读取一行,需要readline函数
2)我们需要从一行中读取一个词,需要readword函数
3)判断我们当前单词是否是关键词,还是其他,比如变量,或者数字,等,需要wordanalysis函数
4)如果不是关键字,判断是否是一个合适的数字常量,需要isnum函数
5)如果不是关键字和数字,判断是否是一个合适的变量名,需要isviable函数
3.理论依据:
有穷自动机
第二章已略有介绍
4.readline函数的关键点
5.readword函数关键点
6.wordanalysis函数关键点
7.isnum函数关键点
8.isviable函数关键点
四、语法分析
1.“如何判断一个句子是不是符合语法?
”
a)以英语为例
i.如何判断一个词是不是可能的合适的句子?
举例子:
Iloveapples.
Hehitme.
Ilaughather.
Imakedo.
Appleeatme.(符合语法,但不符合语义)
答案:
英文的句子类型有几种,只要符合这几种规则中的一种,就是一个合法的句子
比如常见的句子类型——主语加谓语加宾语
满足这样的规则就是符合语法的句子
2.语法分析的目的:
判断一个语句段的所有句子是否符合语法规则
3.编译器实现过程中的语法分析是怎么样进行的?
a)
i.扫描第一行代码,根据关键字确定是否是符合语法的句子,如果是,确定是何种类型,下面行与之有无关系,是否包含子语句段,接着判断剩余语句段是否符合语法
ii.具体实现 kdxf语言一共包括如下几种句型:
变量定义语句,变量赋值语句,打印输出语句,输入语句,变量计算赋值语句,条件语句,循环语句
iii.如果是变量定义语句,是否符合变量定义的语法
iv.如果是变量赋值语句,是否符合变量赋值的语法
v.如果是变量计算赋值语句,是否符合变量计算赋值的语法
Ⅵ.如果是条件语句,是否符合条件语句的语法,并且判断子语句段是否符合语法
Ⅶ如果是循环语句,是否符合循环语句的语法,并且判断子语句段是否符合语法
...
......
4.我们的编译程序进行语法分析,需要的函数:
1)判断是否符合语法,需要isgoodsyntax函数
2)判断当前句子是何种句子,需要sentense_analysis函数
3)取当前语句段的子段,需要subsegment函数
4)取当前语句段的剩余段,需要restsegment函数
5)统计本行语句有几个词,需要howmanywords函数
6)统计本段语句有多少个左大括号,需要howmanyleftbraces函数
7)统计本段语句有多少右大括号,需要howmanyrightbraces函数
5.动手设计isgoodsyntax函数,该函数的关键点
6.设计sentense_analysis函数,其关键点
7.设计subsegment函数,其关键点
如果segment字符串如下
ifa>10
{
a=22
}
else
{
a=23
}
那么subsegment(segment,0)为
a=22
subsegment(segment,1)为
a=23
8.设计restsegment函数,其关键点
如果segment字符串如下
numa
ifa>10
{
a=22
}
else
{
a=23
}
numb
那么restsegment(segment)为
ifa>10
{
a=22
}
else
{
a=23
}
numb
restsegment(segment)为
numb
9.howmanywords函数的关键点
10.howmanyleftbraces函数的关键点
11.Howmanyrightbraces函数的关键点
五、语义分析
1.问题“什么是语义?
”“如何才是符合语义的句子?
”
a)案例(推荐):
分析提问:
i.如何判断一个词是不是可能的合适的句子?
举例子:
Iloveapples.(符合语法和语义)
Appleeatme.(符合语法,但不符合语义)
b)语法和语义的差别:
语法关注的是语句的构成规则,语义关注的是语句的含义,含义要合理
比如说名词分为好多种,人物、动物、植物、非生物等等,人能做的动作,动物不一定可以做,动物能做的动作,植物不一定可以做,植物能做的动作,非生物不一定能够做
2.编译器实现过程中的语义分析目的是什么,是怎么样进行的?
a)目的:
让编译器实现更好的类型匹配,变量的使用能够更加的合理、可靠
比如一个变量必须先定义后使用,使用时要注意上下文场合,布尔变量、数字变量、字符串变量要分别对待,分别处理
b)那么是怎样进行的呢?
i.判断当前是什么语句,如果是变量定义语句作如下判断
1)如果是布尔变量,布尔变量是否重定义
2)如果是数字变量,数字变量是否重定义
3)如果是字符串变量,字符串变量是否重定义
ii.判断当前是什么语句,如果是变量赋值语句作如下判断
1)如果是布尔变量,布尔变量是否已定义,是否定义在适用范围内,“=”右边是否是布尔变量或者布尔常量,或者布尔变量与常量的计算
2)如果是数字变量,数字变量是否已定义,是否定义在适用范围内,“=”右边是否是数字变量或者数字常量,或者数字变量与常量的计算
3)如果是字符串变量,字符串变量是否已定义,是否定义在适用范围内,“=”右边是否是字符串变量或者字符串常量,或者是字符串变量与常量的计算
iii.如果是变量计算赋值语句,变量是否与相应的常量计算,计算符号是否相应
iv.如果是条件语句,是否符合比较的条件
v.如果是循环语句,是否符合循环条件
...
......
9.设定我们的编译程序进行语义分析,需要的函数,提问,让学生回答:
老师从旁提醒:
1)判断是否符合语义,需要函数semantics函数
2)判断变量是否定义,需要worddefined函数
3)判断变量是否重定义,需要wordredefined函数
4)判断变量是何种类型,需要definetype函数
5)判断变量是在哪一行定义,,需要defineline函数
6)判断变量是否正确定义,需要wordrightdefined函数
10.让学生动手设计semantics函数,老师在旁指出该函数的关键点
5,让同学设计worddefined函数,老师在旁指出关键点
6,让同学设计wordredefined函数,老师在旁指出关键点
7,让同学设计definetype函数,老师指出关键点
8,让同学设计defineline函数,老师指出关键点
9,让同学设计wordrightdefined函数,老师指出关键点
判断是否在子段中定义,如果是,返回false
六、解释执行
1.“如何解释执行一个语句?
”
a)以英语为例,学生学过英语,已有一定的认识,给学生5-8分钟时间
b)和学生一起分析上述的答案,取其中比较合适的答案进行讨论,如果答案都不太合理,采用教师备选案例(推荐):
分析提问:
i.解释执行一个语句?
举例子:
Goandtakeanapple.(符合语法和语义)
Givehimapen.
正确的答案:
语句的解释执行,要求完成语句含义的动作.
2.编译器如何实现语句翻译?
目的:
对待不同的语句,不同的处理
a)那么是怎样进行的呢?
i.判断当前是什么语句,如果是变量定义语句作如下处理
定义三个数组二维数组,分别表示这个变量的名称和值,比如定义一个数组charboolviable[100][2][20],boolviable[1][0]boolviable[1][1]分别存储第一个bool变量的名称和值
1)如果是布尔变量,加入数组boolviable[100][2],如果是第i个bool变量,则在bool[i][0]处记录它的名称
2)如果是数字变量,加入数组numviable[100][2],记录它的名称
3)如果是字符串变量,加入数组strviable[100][2],记录它的名称
ii.判断当前是什么语句,如果是变量赋值语句作如下判断
1)循环判断是否是bool变量,如果是第i个bool变量,则在bool[i][1]处记录这个变量的值
2)循环判断是否是bool变量,如果是第i个bool变量,则在bool[i][1]处记录这个变量的值
3)循环判断是否是bool变量,如果是第i个bool变量,则在bool[i][1]处记录这个变量的值
iii.如果是变量计算赋值语句,变量是否与相应的常量计算,计算符号是否相应
1)循环判断是否是bool变量,如果是第i个bool变量,则在bool[i][1]处记录这个变量的值
2)循环判断是否是bool变量,如果是第i个bool变量,则在bool[i][1]处记录这个变量的值
3)循环判断是否是bool变量,如果是第i个bool变量,则在bool[i][1]处记录这个变量的值
iv.如果是条件语句,
判断if后面是不是合理的bool表达式,如果是,算出这个bool表达式的值
1)如果值为true,解释执行第0个子段
2)如果值为false,如果有else,则执行第1个字段
3)如果值为false,并且没有else,则执行后面的过程
v.如果是循环语句,
判断循环的步长是多少,判断循环的上限或者下限是多少
1)如果是”>”,判断下限是多少
2)如果是“<”,判断上限是多少
然后如果while(a>10)
{
Subsegment
(其中包括a=a-1这句)
}
翻译成while(a>10)
{执行子段
a=a-1;
}
...
......
3.设定我们的编译程序进行语句执行,需要的函数,提问,让学生回答:
老师从旁提醒:
1)解释执行,需要函数translateandcommit;
2)对于布尔表达式和数字计算表达式,需要计算函数boolcompute,numcompute
3)取当前表达式的剩余表达式,需要restexpression函数
4)取当前语句行的剩余行,需要restline函数
5)取当前语句行的反剩余行,需要restlinereverse函数
6)取当前表达式的子表达式,需要subexpression函数
7)判断当前表达式是否是正确的表达式,需要isgoodexpression函数
4.让学生动手设计tanslateandcommit函数,老师在旁指出该函数的关键点
5.让同学设计numcompute函数,老师在旁指出关键点
6.
6.让同学设计subexpression函数,老师在旁指出关键点
如果expre字符串如下
a+(a/9)(b*3+8)
那么subexpression(expre,0)为b*3+8
subexpression(segment,1)为a/9
7.让同学设计restexpression函数,老师指出关键点
如果expre字符串如下
a+2*c+b
那么restexpression(expre)为
a+2*c
8.让同学设计restline函数,老师指出关键点
9.让同学设计restlinereverse函数,老师指出关键点
10,让同学设计isgoodexpression函数,老师指出关键点
参考资料
1.《编译原理》(龙书),机械工业出版社,赵建华等,译
2.《编译器设计之路》机械工业出版社,裘巍
3.《编译原理》,国防科技出版社,陈火旺等著,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 讲义
![提示](https://static.bingdoc.com/images/bang_tan.gif)