编译原理
2018-06-24 08:36:57 28 举报AI智能生成
编译原理是计算机科学的一门重要分支，主要研究如何将高级语言编写的源程序转换为目标程序。这个过程包括词法分析、语法分析、语义分析、优化和代码生成等阶段。编译原理的目标是构建一个编译器或解释器，使得用户可以使用高级语言编写复杂的程序，而不需要关心底层的机器指令。编译原理不仅在软件开发中起着关键作用，也是理解计算机系统工作原理的重要途径。
作者其他创作
大纲/内容
前言
语法描述
上下文无关文法
定义
文法
上下文无关
限制
不含P->P
每个非终必有用处
概念
句型
句子
语言
推导
最左推导
最右推导（规范推导）
元语言符号
->
|
=>
扩充的巴斯德范式
语法树
二义性
文法的二义性
语言的二义性
叶节点
短语
素短语
最左素短语
直接短语
句柄
句型
Chomsky文法分类
0型（短语文法）
1型（上下文有关文法）
2型（上下文无关文法）
3型（正规文法）
右线性文法
左线性文法
出错处理
语法错误
语义错误
符号表
编译程序与解释程序
遍与阶段
编译前端与后端
编译程序的生成（高级语言）
T型图
工作过程
词法分析
状态转换图
状态
输入字符
单词符号的种类
正规集
证明正规式等价
找正规集，从复杂的下手
变换常用手段
用正规式表示
有限自动机（FAM）
NFA
DFA（NFA的特例）
DFA的化简
1、基本划分Π
2、划分子集
3、重复至子集数目不再增加
正规式、DFA与NFA的等价性
正规集
消结规则
加结规则
1、正规式->NFA
2、确定化NFA->DFA
ε-closure(I)和Ia
步骤
1、设字母表只包含两个a和b，构造一张表列为I、Ia、Ib
2、置第1行第1列为ε-closure({开始符号})求出这一行的I、Ia，Ib
3、检查这两个Ia，Ib，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第1列上，求出每行第2，3列上的集合
4、重复3到所有2、3列子集出现在第1列
5、标号，相同集合的标一样的号，生成一个状态转换矩阵
6、根据表画出DFA
识别（接收）
L(M)
相关概念
Σ
符号
符号串（字）
字的连接（积）
闭包
字的长度
ε-空字
Σ*
Φ-空集
语法分析
自上而下
LL(1)分析法
1、消除左递归，提取公共左因子
2、求FIRST和FOLLOW
3、构造分析表
4、判断是否LL(1)文法
5、分析字符串
1、栈顶符号X，X=‘#’，成功
2、X终且≠‘#’，出栈（识别成功一个字符）
3、X是非终，根据输入字符，查分析表，有产生式则X出栈，产生式右部符号（除ε）串逆序进栈
递归下降分析法
程序构造
几个全局过程和变量
构造方法
利用扩充的巴斯德范式构造
自下而上
规范归约
规范归约是规范推导的逆过程
规范句型
算符优先分析
条件
算符文法
非终结符对关系数量
算法步骤
1、求FIRSTVT、LARTVT
子主题
子主题
2、画优先关系表（优先函数）
子主题
子主题
3、判断是否是算符优先文法
4、分析输入串
1、移进直到最左素短语
2、归约为形状相似的产生式的左部符号
优先关系
a与b相等
a高于b
a低于b
LR分析法
分析表
动作ACTION[s,a]
移进
归约
接受
报错
状态转换（GOTO）
LR(k)文法
LR(0)文法
前缀
活前缀
识别活前缀的NFA
识别活前缀的DFA
LR(0)分析表构造
1、初态
2、ACTION子表
3、GOTO子表
4、是否LR(0)文法
分析步骤
1、写出所有项目
2、DFA（CLOSURE）
3、分析表
4、是否LR(0)
5、根据分析表分析输入串
LR(0)项目集规范族
归约项目
接受项目
移进项目
待约项目
项目
CLOUSER(I)
1、I的任何项目都属于CLOSURE(I)
2、A->α·Bβ也属于该闭包，则扩展
3、重复1，2直到不再增大
In是某个状态集
SLR(1)分析表构造
1、拓广文法
2、求LR(0)项目集规范簇|构造DFA
3、求所有FOLLOW，由此解决移进-归约冲突
4、构造分析表
5、分析输入串
符号栈
语义分析与中间代码生成
中间语言
三地址代码
三元式
四元式
间接三元式
后缀式
图表示
DAG（有向无环图）
抽象语法树
控制语句的翻译
属性文法
综合属性
S-属性文法
继承属性
优化
三大原则
常用优化技术
删除公共子表达式
复写传播
删除无用代码
代码外提
强度削弱
删除归纳变量
三个级别
局部优化
基本块
入口语句
循环优化
全局优化
目标代码生成
0 条评论
下一页
