2.编译的基础知识
2021-05-26 21:57:01 0 举报AI智能生成
B站东南大学 廖力 的编译原理 -自制笔记
作者其他创作
大纲/内容
1.引入
语义
对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义
离开语义，语言只是一堆符号的集合
各种语言中有形式上完全相同的语法单位，含义却不尽相同。
对某种语言，可以定义一个程序的意义的一组规则称为语义规则
目前，大多数编译程序使用基于属性文法的语法制导翻译方法来分析语义
语法
1、单词符号
语言中具有独立意义的最基本结构
词法规则
词法规则规定了字母表中那些字符串是单词符号
单词符号一般包括：常数、标识符、基本字、算符、界限符等
我们用正规式和有限自动机理论来描述词法结构和进行词法分析
2、语法单位
表达式、子句、语句、函数、过程、程序
语法规则
规定了如何从单词符号来形成语法单位
现在多数程序语言使用上下文无关文法来描述语法规则
语言的词法规则和语法规则定义了程序的形式结构，是判断输入字符串是否构成一个形式上正确的程序的依据
高级语言
程序语言是一个记号系统
语法
任何语言程序都可以看成是一定字符集（字母表）上的字符串
语法＝词法规则＋语法规则
语义
语法使得这串字符形成一个形式上正确的程序
例如：0.5*x1+c
0.5、x1、c、*、+是语言的单词符号
看是否符合词法规则
0.5*x1+c是语言的语法单位
看是否符合语法规则
2.字母表和符号串
一、相关概念
字母表
这门语言里头的每一个字目都出自于这个字母表当中
- 是符号的非空有穷集合
- 用Σ、V表示
符号
是语言中最基本的不可再分的单位
符号串
符号串是字母表中符号组成的有穷序列
空串
不含有任何符号的串称作空串，记作ε
句子
符合词法规则
构成词
按照语法规则把单词组合在一起构成的串
构成了语句
语言
字母表上句子的集合
注：
约定用a,b,c…表示符号
用α,β,γ…表示符号串
用A,B,C…表示其集合
二、符号串集合的运算
符号→符号串→句子→语言
1、连接（乘积）运算
如果...那么...
都是符合语法要求的
- 定义：若串集A={α1， α2， …}，串集B={β1，β2， …}，则乘积AB={α β| α ∈ A and β ∈ B}
注：
1）串集的自身乘积称作串集的方幂
3）字母表A的n次方幂是字母表A上所有长度为n的串集
例子
例如：A={a,b}; B={c,e,d}
则AB={ac,ae,ad,bc,be,bd}
AB是有顺序的
A一定在前面，B一定在后面
例如：串集A＝{a}的各次方幂定义为
三、字母表的闭包与正闭包
1）字母表A的闭包（A*）
即
由A上符号组成的所有串的集合（包括空串ε ）
2）字母表A的正闭包（A+）
即
由A上符号组成的所有串的集合（不包括空串ε ）
3）语言
是字母表上符合某种规则的语句组成的
字母表上语言
是字母表上正闭包的子集
3文法与语言的关系
一、文法的概念
1、文法
文法是描述语言的语法结构的形式规则
eg
我们写这样一个句子
Young men like pop music
其语法规则如下
相关概念
(1)非终结符
(2)终结符
(3)开始符号
(4)产生式
（5）推导
（6）归约
(7)句型、句子和语言
句型
推导过程的那些就是句型
句子
是仅含终结符的句型
eg
例如：根据英语的语法规则，看能否用最左推导得出“Young men like pop music”是个语法正确的句子；
在推导过程中有哪些句型。
在推导过程中有哪些句型。
最左推导
因为由句子推导出来的，和我们要验证的句子一样，所以是语法正确的句子
最右归约
子主题
用图示化方式表示
最左归约
语言
语言是由S开始通过1步或1步以上推导所得的句子的集合
(8)文法规则的递归定义
非终结符的定义中包含了非终结符自身
一定要有终止符，这样才能停止，不然构不成句子，没有句子就构不成语言，没有语言就没有文法之说
使用文法的递归定义要谨慎
扩充表示
(9)元语言符号
用来说明文法符号之间关系的符号，如，“→”和“|”称为元语言符号
“→”
产生/由......组成
“|”
或者
二、文法与语言的形式定义
1、Chomsky对文法的定义
Vn表示非终结符集合
Vt表示终结符集合
P ——表示规定
S ——表示开始符号是什么
2、Chomsky对文法的分类
根据对产生式施加的限制，可分为
0型文法
1型文法
上下文有关
如果bB→b，那么为0型文法
如果长度至少都是相同的话，那么就是1型文法
⭐2型文法
⭐上下文无关文法
上下文无关文法包含正规文法
产生式的左部一定是非终结符
产生式的左部是一个非终结符
产生式的右部可能是非终结符，终结符，空串
右部是任意的
要求产生式左边只有一个非终结符存在
⭐判断句子是否正确的一个标准
⭐3型文法
第一种就是右线性文法
第二种是左线性文法
也成为⭐正规文法
非终结符要么是全部在最右边，要么是全部在最左边
如果是左右参杂的话就不是正规文法了
举例
产生式的左边全是单个的非终结符
⭐判断单词是否正确的一个标准
i型语言
某一种文法的语言，由开始符号开始经过一步或者一步以上的推导所得到的句子的集合
⭐
4.文法构造与文法简化
一、如何由语言构造文法
先找出它最一般的情况
再去找它的规律
二、文法与语言的形式定义
三、文法的简化
例题
四、构造无ε产生式的上下文无关文法
例题
5.语法树与文法的二义性
一、语法树
例题
3、语法树中的概念
子树
句型
S的短语是ba
B的短语是bba
bba也是它的简单短语
bS也是
根据书的概念
bbA也是
简单短语
bS
此B的短语是abbab
简单短语
子树根一步推导的得到的它的孩子结点，它的孩子结点通通都是叶子结点。这样合起来的短语叫做简单短语
要求末端符号从左到右连成串
二、文法的二义性
例题
两种推导方法
例题2
else和离它最近的if进行匹配
第二种更符合我们的平时的规则
加上一个规则就变成一个非二义性的文法
0 条评论
下一页
