编译原理
2019-11-12 14:01:48 50 举报AI智能生成
编译原理知识点
作者其他创作
大纲/内容
词法分析
词法单元（标识符）
词素
词素模式
正则表达式
不确定有穷自动机
确定有穷自动机
转换方式
正则表达式转换成不确定有穷自动机，再转换成确定有穷自动机
保留词
关键字
预设的固定词法单元
操作符
属性
类型
类型标号
类型名
值
功能
解析词法单元
过滤注释和空白
关联错误信息与代码位置
通过词法单元的行号
扫描过程
词法错误
错误恢复动作
恐慌模式
缓冲（预读当前匹配的字符个数）
哨兵标记
lexemeBegin
前词素开始处
forward
当前模式匹配前读入的位置
有穷自动机
状态转换图
在不同的状态节点，尝试各个词法单元的状态转换
多个模式匹配冲突解决规则
选择最长匹配前缀
按照顺序匹配
向前看一个节点，匹配后需要回退输出
自动机类别
不确定有穷自动机 NFA
每个状态可以有多个边，同一个输入可以有多条变，并且边可以是 ε（可以直接到达）
确定有穷自动机 DFA
每个状态只有一个后继状态
NFA 特例，没有输入 ε 上的转换动作
NFA 转换成 DFA
子集构造法
DFA 的每个状态对应 NFA 的一个状态集合（当前状态及通过 ε 到达的状态）
ε-closure(T) 闭包
在下一个输入可以到达的状态及 ε 间接到达的状态
正则表达式转换 NFA
基本规则
子表达式不包含运算符
归纳规则
连接表达式的直接子表达式NFA
N(r)=L(s)∪L(t)
分解正则表达式的子表达式，构造每个子表达式的NFA，连接各子NFA的起始状态
正则表达式转化 DFA
构造抽象语法树
重要状态对应预算分量（叶子节点），连接符为运算符（内部结点）
相关函数
nullable(n)
判断是否生成空串
firstpos(n)
子节点子表达式字符串起始位置集合
lastpos(n)
子节点子表达式字符串结束位置集合
followpos(n)
当前位置所有后继节点位置，所有后继节点集合对应下一状态集
转换表
每个状态在不同的输入下，所能到达的后继状态节点集合
语法及语义分析
上下文无关文法（文法）
文法
产生式 production
终结符号（字符串、词法单元） terminal
关键字
名字
属性
数值
指向符号表的指针
非终结符号（字符串形式、语法变量）nonterminal
通过下标区分不同位置相同非终结符
二义性
消除二义性
添加附加规则
运算符结合性
运算符优先级
设置文法分段
因子（不可拆分） factor
就近匹配原则，优先匹配成分量表达式
项（可拆分） term
合并公因子，改写产生式，推后推导匹配
语法分析方法
分析模式
自顶向下
从左往右扫描，选择最左端节点产生式进行扩展，直到找到最小匹配终结符，不符合则回溯
预测分析法
通过向前看符号 lookahead 解决二义性
左递归
可能出现循环扩展
消除左递归
立即左递归
左递归的结束必然是使用终结符产生式，所以可以将之转换成以该终结符为开头的产生式
间接左递归
先消除对上级非终结符的循环推导（产生式首部为上级符号），在消除自身的直接左递归
提取左公因子
改写产生式，合并公因子（FIRST无交集），推后推导匹配
LL(1)文法
文法要求
同一左部的不同产生体不能相交
非空产生式的 FIRST 集合不能与 空产生式的 FOLLOW 集合相交，保证 LL 文法向前看时能够分清使用哪个产生式
保证文法分支树不能有交集，必须是分叉的，预测分析时能够分辨出使用哪种产生式
文法状态转换图
文法需要先先出左递归，再抽取公因式
每个非终结符都有单独的转换图
边（输入）可以是终结符或者非终结符号
如果是非终结符，则该边可以替换成对应的转换图
每个非终结符转换对应一个过程调用
预测分析
向前看符号集 FIRST(α)
定义
出文法符号α推导出的首字符集合，如果该文法符号可以推导出 ε，则可递推后续符号的首字符
作用
用作 FOLLOW 集合的依据
注意事项
同一个左部的多个产生式的 FIRST(α) 不能相交，否则需要调整产生式文法
FOLLOW
定义
在当前文法符号后边的“终结符号”集合，包括后边文法符号的 FIRST 集合等等
如果在末端（包括后一文法符号可以推导出 ε 的情况）则向前（左部）兼容，如果在中间则为后一文法符号的 FIRST 集合
作用
作为预测分析向前看的符号集合，根据不同的 FOLLOW 选择不通过的产生式
在恐慌模式中作为同步词法单元
可以通过表格改进性能
二维表：非终结符号、输入终结符，标识不同的文法符号在不同输入情况下的产生式选择方式
预测分析表
M[A，a]
FIRST、FOLLOW
算法
非终结符号遇到产生式对应的的 FIRST 集合，则选择该产生式
如果产生式的 FIRST 集合中包含 ε，则如果遇到 FOLLOW 集合中的元素，也可以使用该产生式，该产生式推导为 ε
最左推导
自底向上
从左往右扫描
最右推导（规范推导）
状态集（移入、规约）
归约体的选择依据
句柄（句型组成部分）
归约时当前输入必须是归约非终结符的“句柄”
句柄只会出现在栈顶
根据状态集判断会否可以进行归约
相关行为
移入
归约
接受
报错
冲突
移入/归约冲突
向前看，LR(k)文法
归约/归约冲突
LR语法分析技术
常见种类
SLR
LR(k)
LALR
项集簇（状态集）
当前推导进度处于产生式的位置
项：当经过某个前缀路径后所处的状态
状态类型
移入状态
项集位置还未到达末尾，并且在预读输入符上有对应的转换，那么可以做移入操作
规约状态
项集位置已到达末尾，并且在预读输入符上没有对应的转换，则做归约操作
遇到 FOLLOW 集合
增广文法
CLOSURE（项集的闭包）
加入当前位置右端文法服务的所有推导项（包括右端推导符号的所有子表达式），用于推导输入不同非终结符\终结符所能到达的路径
内核项
LR(0)项
非内核项
GOTO
在当前项目接收到终结符/非终结符时，转移到后一项状态
SLR
如果向前看输入符在 FOLLOW 集合中则可以做归约操作
存在移入/归约冲突
本质原因是归约的 FOLLOW 集是可行前缀的超集
归约后需要考虑当前归约后，栈中的句型是否是上一层的归约的最右句型，如果不是则不是可行前缀
是否需要一直向上校验
一般只要向前看一个符号就可以了，需要在文法上进行控制，使其分析分析数尽可能不想交（提取左公因）
是否存在归约的时候也只有一种选择，和 LL(1) 类似
LR(1)
在 SLR 项集遇到 FOLLOW 集合进行归约时，向前看一个符号判断前缀+移入符号+向前看符号是否是上一推导的最右句型
向前看符号是否在规约后的后一符号的 FIRST 集合中
在生成 CLOESUER 集合时，从上往下带入可用的向前看符号（这样就不需要从下往上查找了），只要满足该可用向前看符号，才能进行归约
LALR
合并LR(1)相同核心项（第一分量）
由于合并后第二分量也会合并，此时会将错误的发现推迟，会有一步所处的项的预期输入符与当前输入符不匹配的情况
存在归约/归约冲突
项 [A → α.Bβ, a] 中的 FIRST(β a) 仍有多余部分
构造方式
A、先生成LR(1)项，在合并同心项
B、使用“传播和自发生”生成向前看符号
1、先生成LR(0)核心项
核心思想
通过输入不同的终结符到达不同的状态集，最后只状态集只包一个状态（归约状态），状态集的离开边不能相交
LR语法分析表
ACTION
根据预读的终结符进行相关操作
相关参数
项状态标识 i
终结符号 a&$
相关操作
移入
归约
接受
报错
GOTO
如果做了归约操作，那边还需要根据规约后非终结符号转移到合适的状态集
执行过程
遍历语法树各节点，分析出符号匹配的表达式时，执行文法符号包含语义动作
遍历方式
前序遍历
后序遍历
求值顺序
执行位置
额外节点
分析过程中，不断将信息以节点的方式附属到对应节点上
分析结果
抽象语法树（语法树）
数据结构
自身节点（运算符号）
子节点（运算分量）
语法分析树（具体语法树）
数据结构
节点 node（文法代表的程序构造）
标号 label
两者结合
语法分析树同时包含文法符号构造函数节点及运算符节点，运算符节点包含运算分量节点，运算分量节点依赖文法符号构造节点的计算结果
错误恢复
恢复策略
恐慌模式
同步词法单元
界限符（分好、}）
短语层次恢复
局部纠错
字符替换、插入字符
错误产生式
对预期错误设置产生式，生成适当的错误诊断信息
不同层次错误
词法错误
语法错误
语义错误
逻辑错误
语法制导翻译
产生式附加程序片段（语义动作），顺序执行
语法制导定义
文法符号关联属性集合
继承属性
由父节点确定
综合属性
由子节点和自身共同确定
求值顺序
产生式关联语义规则，语义规则用于计算属性值
“递归下降”语法分析
手动编写分析代码，每个文法都有对应的构造程序
符号表
作用
区分同一标识符在不同位置的声明
实现方式
每个程序块都有对应作用域的符号表，嵌套程序块继承父程序块的符号表
最近嵌套规则
嵌套程序块作用域符号表链
放在语义动作中实现
语义分析
左部和右部
静态类型检查
不同语言语法检查
是否符合不通语言语法规范，例如关键词的使用方式等
中间代码生成
中间代码形式
抽象语法树（语法树）
三地址码
计算
比较
跳转
机器无关代码优化
目标机器代码生成
目标机器代码优化
0 条评论
下一页
