程序语言设计
编译的步骤:词法分析,语法分析,语义分析,目标代码生成,目标代码优化
1.词法分析:从字符串中识别一个个的单词
2.语法分析:从符号流中识别出语法单位
3.语义分析:对语法单位进行翻译
4.目标代码生成:中间代码转化为目标代码
常用的三地址指令
三地址指令的四元式
5.优化:对中间代码进行等价变换,使得生成的目标程序效率更高
翻译:将一种语言的程序转换成另一种语言的程序
汇编程序:将汇编语言程序翻译为机器语言程序的程序
编译程序:将高级语言程序翻译为低级语言程序的程序
程序语言的分类:强制式,函数式,逻辑式,对象式
程序语言的变量属性:作用域,生存期,值,类型
数据类型:对存储器中所存储的数据进行的抽象,包含了值的集合和操作1的集合
可分为:内部类型,用户自定义类型,抽象数据类型
数据类型聚合方式和举例
1.笛卡尔积:记录,结构 2.有限映射:数组 3.序列:字符串,顺序文件
4.递归:树 5.判定或:联合,变体记录 6.幂集:集合
类型检查:对数据对象的类型和使用的操作是否匹配的一致性检查
静态检查(编译时):程序是否正确有效
动态检查(运行时):变成方便,影响了可靠性
类型转换:将某种类型的值转换为另一种类型的值
隐式(自动)转换 显式(强制)转换
类型等价:T1和T2是两个类型,T1的任何值都可以赋予T2类型的变量,T1和T2是相容的,或等价的
词法分析
字母表:Σ,一个有穷符号的集合
字母表的乘积:Σ1Σ2={ab|a∈Σ1,b∈2}
字母表的幂运算:Σ的n次幂是n个Σ相乘
字母表的正闭包:Σ的各个正数次幂的并集
字母表的克林闭包:正闭包的基础上增加一个空串
Σ的克林闭包的每一个元素都可以称为Σ上的一个串,串s的长度|s|,是s中符号的个数
串上的运算
x和y的连接,是把y的内容放x的后面 x=dog y=house xy=doghouse
假设x,y,z是三个字符串,如果x=yz,那么y是x的前缀,z是x的后缀
串的幂运算:串的n次方就是n个串相连
文法的定义:文法是描述语言语法结构的形式规则 G=(Vt,Vn,S,P)
Vt:终结符的非空有限集 Vn:非终结符的非空优先集
S:文法的开始符号,S∈Vn P是产生式的非空有限集
终结符:只出现在推到右侧的符号 非终结符:在推导左侧出现过的符号
例子:
约定:在不影响阅读的情况下,可以只写产生式P
产生式的简写:产生式有相同左部的情况下,可将右侧合并,例如:
一般表示:
推导:用产生式的右部替换产生式的左部
规约:用产生式的左部替换产生式的右部
句型:经过推导后得到的产生式就是一个句型
句子:不包含非终结符的句型
语言:文法G包含的所有句子的集合
文法的分类:
正则表达式:描述正则语言的更紧凑的表示方法
例如:
正则的定义:
有穷自动机
转换图
接收:如果给一个输入串x,可以从初始状态到终止状态的方法,x被FA接收
由一个有穷自动机M接收的所有串的集合成为FA定于的语言,记为L(M)
最长子串匹配原则:当输入串的多个前缀与一个或多个模式匹配,总是选择最长的前缀进行匹配
如果是≤,此时都匹配上了,选择3作为终止状态
确定的有穷自动机(DFA)非确定的有穷自动机(NFA)
DFA(S,Σ,δ,s0,F)
S:有穷状态集 Σ:输入字母表(空串不是字母表的元素)
δ:δ(s,a)状态s对应的a的后继状态 s0:初始状态
F:终止状态
NFA(S,Σ,δ,s0,F) 从状态s出发,经过a路径到达的状态可能有多个
从正则表达式到有穷自动机
从NFA到DFA的转化
语法分析
自顶向下的分析(从文法的开始符号S推导出词串w的过程)
推导树:有序的标记树
最左推导,总是从最左非终结符进行替换,得到的句型成为最左句型
最右推导,称为规范推导
文法的二义性:一个句子有两棵不同的推导树
在推导树中:
句型:叶结点自左向右连接 短语:子树便于是相对于根的短语
直接短语:有且仅有两层的子树的边缘时相对于根的直接短语
句柄:位于最左边的直接短语
消除递归的方法
1.公共左因子(提取公共左因子)A⇒aβ1|aβ2
A⇒aβ1|aβ2|aβ3...|aβn|ξ
改写为A⇒aB|ξ
B⇒β1|β2|β3|...|βn
若β1|β2|β3|...|βn中仍含有公共左因子,可以再次提取,直到所有产生式东渡没有公共左因子为止
例子:
2.直接左递归的消除
A⇒Aa1 |Aa2 |Aa3 |... |Aam |β1 |β2| β3 |... |βn
改写为:A⇒β1A` |β2A` | β3A` |... |βnA`
A`⇒a1A` |a2A` |a3A`... |amA`| ε
例子:
3.间接左递归的消除
预测分析法
FIRST集合
FOLLOW集合
SELECT集
LL(1)文法要保证同一非终结符的SELECT集互不相交
预测分析表的构建
对于文法G的每个产生式A⇒a