今天终于开始着手把一年前学的编译原理整理一下啦!打败拖延症 #*#
机器语言:计算机只认识由0和1构成的机器语言,每台机器自己独特的指令系统即机器语言。 机器语言->汇编语言->高级语言 编译程序最初的定义是把一种高级语言设计的源程序(面向人的)翻译成另一种等价的低级程序设计语言(面向硬件的)即机器语言或汇编语言。
区别:是否生成目标程序 共同点:都需进行词法、语法和语义分析 翻译程序按所处理源语言不同分为两种:
Basic、Lisp、Sql解释程序、Unix命令语言解释程序及很多脚本语言Javascript等都解释执行的。C、C++、Pascal等语言是编译执行的 java既有编译又有解释 Java → 编译程序 → Bytecode →解释程序
编译过程可分为下面几个阶段: 1. 词法分析 2. 语法分析 3. 语义分析和中间代码生成 4. 优化 5. 目标代码生成 6. 表格管理和错误处理
1. 词法分析 输入源程序(字符串)根据语言的词法规则对构成源程序的字符串进行扫描和分解识别出一个个的单词 单词内部表示形式: 二元式 (class,value)
单词类别: 1. 保留字(关键字) main,float … 2. 标识符 sum ,first,count … 3. 运算符 *,+,- … 4. 分界符 (,{,[, ],},)… 5. 数值型常量 10,3,…
2. 语法分析 输入单词符号串根据语言的语法规则对单词符号串进行扫描和分解识别出各类语法单位。 程序语言的语法单位:
C语言赋值语句构成规则:
<赋值语句>→<标识符> = <表达式>;
<表达式>→<表达式> + <表达式>
<表达式>→<表达式> * <表达式>
<表达式>→<标识符> 如: X1,Y,Z
<表达式>→<常数> 如:10
“->”意思是“定义为” 语法单位的单词符号:=,+,* ,X1,Y,Z,10 语法单位表达式
语法单位内部表示:语法树
3. 语义分析与中间代码产生 输入各类语法范畴根据语言的语义规则,分析其含义,并进行初步翻译 产生中间代码 中间代码:
4. 优化 输入中间代码进行等价变换 输出更高效的中间代码。
5. 目标代码生成 输入优化后的中间代码变换成特定机器上的低级语言代码,实现最后的翻译,产生目标代码。
6. 表格管理:
* 在完成以上5个过程的同时必须随时对符号表进行管理
* 记录源程序中使用的名字
* 收集每个名字的各种属性信息 如类型、作用域、存储分配信息等
* 例 count 变量 类型 float first 变量 类型 float 地址
7. 出错处理:
* 发现源程序中的错误
* 检查词法、语法和语义中的错误(静态)
* 编译程序的处理能力,如存储空间越界 (动态)
* 报告出错信息和位置
* 处理和恢复
编译程序的结构:
遍 :从头到尾对源程序及其内部表示 扫描一次,并作有关的加工处理
从源程序扫描是第一遍输入每前一遍的输出是后一遍的输入 分遍的原则按实际情况而定 多遍(结构清晰、少占内存、读写次数多,耗时) 一遍(多占内存,速度快)
一个程序语言是一个记号系统 程序语言的定义 语法和语义 语法 形成和产生合适程序的规则集
词法规则 形成单词符号的规则
语法规则 形成语法单位的规则
常用的语法描述方法 :
正规文法——词法规则
上下文无关文法——语法规则
单词——具有语义的最小字符串
“=>”意思是“推导”
符号(元素): 可以相互区别的记号。
* 例 a b 0 1
字母表(语言的基本字符集):非空有穷集
* 例∑={0,1} 二进制数语言的字母表
* A={a,b} 由符号a和b组成的字母表
字母表包含语言中所允许出现的一切符号。 一种程序设计语言的字母表是该语言的基本字符集合。
符号串:由字母表中符号所组成的任何有穷序列。
* 例01,110,001110是字母表∑={0,1}上的符号串。
* 注意符号串中符号的顺序是重要的,110不同于011。
符号串的长度:符号串中符号的个数。
* 例x=001110,则x长度|x|=6。
空串ε:长度为0的符号串,|ε|=0。 符号串集合:集合中的一切元素都是某字母表上的符号串。
* 例 ∑={0,1}是字母表,其中0,1为符号
* 则字符串集合D={0,1} 其中0,1为符号串
* 字符串集合E= {ε, 0,1,00,01,10,11,000, …} 是∑上的符号串集合。
* 特别 空集记为ф ={ },注意与ε、{ε}区别。
符号串集合闭包: 设字母表A={a,b},符号串集合V={a,b}。
V的正闭包V+是V上的所有的非空符号串的集合 语言: 某个字母表∑上的符号串集合,是∑*的一个子集。
例有字母表∑={0,1}
∑ * ={0,1}* ={ε,0,1,00,01,10,11,000,001,…}
则∑*的一个子集{1,11,111,1111,…}是一种语言。
∑*的一个子集{0,1,00,01,10,11,000,001,…} 是二进制语言。 C语言
字母表={所有C语言基本字符}—C语言基本字符集。
{所有C语言基本字符}*是符号串集合。
符合C语言语法规则的符号串集合{所有C语言基本字符}*的子集就是C语言。
规则或产生式: 形式α→β或α::=β α称为产生式的左部 β称为产生式的右部 读作“α定义为β”
举例
A→a 这是关于A的一条规则
<标识符> →<字母>
<字母> →a|b|……|z
文法G的形式定义:(上下文无关文法) G = (VT,VN,S,P)
Chomsky定义文法为一个四元式
VT 非空有穷终结符集
VN 非空有穷非终结符集 VT ∩VN = ф
S∈VN 开始符号
S至少在产生式左部出现一次
P非空有穷产生式集合 α→β
α∈(VT ∪VN)*,且至少含有一个非终结符
β∈(VT ∪VN)*,
令V=VT ∪VN
称V为文法符号,是文法G的字母表
文法描述的约定:
用大写字母A、B、C…或汉语词组<标识符>代表非终结符号
用小写字母a、b、c…代表终结符号
用希腊字母α、β、γ…代表终结符号和非终结符号组成的符号串
若干个左部相同的产生式可以合并为一个
P→α1| α2 |…| αn 每个αi 称为P的一个候选式
“|”意思是“或”.
直接推导(直接归约):
推导(归约): 归约是推导的逆过程。
设G是一个文法
句子 :
合法句子的生成 :
文法:
上下文无关文法: 一组非终结符号,一组终结符号,一个开始符号,以及一组产生式。
每个结点都有一个V中的符号作标记 根结点——开始符S 中间结点——非终结符A∈VN 叶结点——非终结符或终结符(关于句型) 终结符a∈VT (关于句子) 如果结点n标记为A, 其直接子孙从左到右的 标记为A1,A2,…,Ak, 则 A→ A1A2…Ak ∈P 句型的推导过程不同,语法树的生长过程 也不同,但最终生成的语法树结构是完全相同的。
最左(右)推导:
文法的二义性
对运算符规定优先顺序和结合率,将二义性文法变为等价的非二义性文法 。
词法分析: 主要功能 1. 输入源程序、输出单词符号 单词符号种类:
基本字
标识符
常数
运算符
界符
单词符号的输出形式: 二元式(单词种别,属性值)
单词的识别──状态转换图:(有限方向图)
利用状态转换图识别单词:
正规表达式和有限自动机:
单词的形式化描述工具:
LL1文法定义:上下文无关文法 一个上下文无关文法是LL(1)文法的充分必要条件是,对每个非终结符的两个不同的产生式,A→α,A→β,满足: SELECT(A→α)∩SELECT(A→β)= φ