一、绪论
编译程序
- 功能：高级pro转低级目标pro
- 形式
- 编译执行
- 转obj在执行，效率高
- 跨平台性差
- 解释执行
- 逐行解释，效率低
- 跨平台性好
- 编译执行
编译过程/结构
- 词、语法、语义...
- 结构：各种分析器+表格、错误管理
编译程序实现
- 自编译
- 交叉~
- 自展
- 移植
解释&编译程序区别
0、不生成obj & 生成~
1、边解释边执行 & 转目标程序再执行
2、速度慢，效率低 & 快，高
3、跨平台性好 & ~差
4、可动态修改 & 修改不方便
相关细节
- 编译过程分模块是为了使pro结构清晰
- 编译pro时间大多花在表格管理上
2、词法分析
功能：
- 输入源pro，输出可识别单词
- 字符扫描器
分析形式
- 单独做主pro
- 作语法分析pro的子pro
输出形式
- 二元式
- （单词种别,单词值）
识别单词形式
- 状态转换图
- 识别单词的有限有向图
- 状态转换图组成
1、结点
- 圆圈表示
- 代表状态
- 必有初态、终态
- 每个状态对应一小段程序
- 结点数有限
2、有向边
- 连接结点
- 边上标记字符
状态矩阵：转换图的一种实现形式
1、行表示状态
2、列表示输入符
3、矩阵元素表示f(s,a)值-
正规表达式
- 形式化表示法
- 表示单词符号的结构
- 定义单词符号集
- 形式化表示法
-
有限自动机
- 实现状态转移的自动机
- 一般化的状态转换图
- 类别
- 确定-DFA
- 非确定-NFA
题型
- 构造简化DFA
- 根据正规式—>NFA->DFA->简化DFA
- 比较正规式是否等价
- 求两个正规式的状态转换矩阵，相等则等价
相关细节
- DFA/NFA区别
- 一个/若干个初始态
- 单/多值函数
- 即同一状态，同一输入字符，对应一/多个输出状态
3、语法分析
功能
根据语法规则，输出分析树（短语、句子）
概念
- 文法
1、proLang的生成系统
2、精确定义一个语言
-
四元组
- 终结符集
- 非终结符集
- 开始符
一般为S - 产生式的非空有限集
产生式：语法实体书写规则
S——>Ta
-
类别
- 0型文法
（1）短文法
（2）α至少有一个非终结符
（3）例：A—>ab - 1型文法
（1）上下文有关文法
（2）α->β，且|β|>=|α|
（3）正例：A->Ba
（4）例：aA->a - 2型文法
（1）上下文无关文法
（2）α->β，|β|>=|α|，且α为非终结符
（3）正例：AB->abc
（4）错例：aB->abc - 3型文法
（1）正规文法
（2）2型文法基础上，满足左线性或右线性
（3）左线性：A->a|Ba
（4）右线性：A->a|aB
- 0型文法
-
四类文法
- 联系
（1）0到3，逐渐增加限制
（2）1到3，均属0
（3）2、3，不属1 - 区别
1不许"A->ε, 2、3允许
- 联系
-
文法二义性
- 二义性影响pro执行
- 二义性消除
方法一：加进一些语法的非形式规定
如运算符的优先规则
方法二：构造等价无二义性文法 - 二义文法
定义: 文法中某个句子存在一棵以上的语法树
无法判定
无算法
-
相关细节
- 错误：文法限制越大，语言越小
- 3型文法：描述高级pro的词法
- 2型文法：描述高级pro的语法
- NFA/DFA:识别高级pro的的词法
- 下推PDA：识别高级pro的语法
- 正规文法&表达式
前：描述、定义一个语言
后：识别是否符合某个语言 - 文法唯一对应一种语言
- 语言可对应多个文法
- 推导
- 例：αAβ=>αiβ
- =>直接推导 & ->产生式定义符号
- 句型
- 终结符U非终结符
- E+E、E+E*i
- 句子
- 终结符
- i+i*i
- 推导形式
- 最右推导
- 最左推导
- 语法树
- 定义
- 图示化形式分解句子
各组成部分描述句子语法结构 - 语法树与文法相一致
- 满足的条件
（1）结点用终或非终标记
（2）根结点用S标记
（3）子结点一定是非终结符
- 图示化形式分解句子
- 短语
- 子树末端节点形成的符号串
- 子树根的短语
- 直接短语
- 简单子树末端节点形成的符号串
- 简单子树根的直接短语
- 句柄
- 最左简单子树的末端节点形成的符号串
- 素短语
- 子树
- 有终结符
- 无更小子树
- 定义
形式
（1）自顶向下
- 文法 推 句子
文法开始符 推 输入串 - 分析方法
-
递归下降分析法
- 定义
A. 根节点出发
B. 自顶向下匹配输入串
C. 建立语法树 - 自顶向下分析的不确定性
坏处
A. 穷举法
B. 效率低-
改进：确定的自顶向下分析
A. 消除左递归左递归 改 右递归 A->Aa|β A->βA' A'->αA'|εB. 消除回溯
发生回溯原因: 存在公共左因子
- 定义
-
LL(1)分析法
-
定义
- 又称预测分析法
- 不回溯、非递归
- 1L：自左向右；2L：最左推导；(1):向右查看一个符号
-
核心
- 构造文法的LL(1)分析表
-
LL(1)文法
- 无二义
- 分析表无多重定义入口
- 途径：消除左递归
- 无回溯
- 无二义
-
构造过程
1、求First集X->a...,将a置入First(X) X->Y...,First(Y)置入First(X) X->Y1Y2Y3..Yk,First(Y1Y2Y3..YI)置入First(X)2、求Follow集
置#于Follow(S) 若A->aBT,置Frist(T)-空于Follow(B) 若Ａ®αB,或Ａ®αBβ,而β=>*e，置FOLLOW（A）于FOLLOW（B）中．3、构造分析表
出现多重入口，遵从相应匹配原则（题意会给出）
-
-
疑问
- 构造LL(1)分析表的过程即是消除二义性的过程？
- 构造过程中，求完First集，直接画分析表，对形如"A->ε"进行Follow集，可否？
-
First和Follow集含义
- First(α)是α的所有可能推导的开头终结符或可能的ε
- Follow(A)是所有句型中出现在紧随A之后的终结符或“#”
-
（2）自底向上
句子 推 文法
输入串 推 文法开始符-
定义
- 自左向右
- 循环查找句柄
- 归到开始符号，停止
-
过程
- 移进，形成句柄，就规约
- 重复上述过程，遇开始符号，成功
- PS：规约的中心问题寻找一个句型的句柄
-
分析方法
- 算符优先文法
- 特点
- 简单直观
- 擅分析各类表达式
- 宜手工实现
- 关键
- 预先规定运算法之间的优先关系
- 相继两个终结符的优先关系
- 找最左素短语
- 至少含一个终结符
- 最小性
自身不得再含素短语 - 最左性
- 定义与构造过程
-
优先关系定义
a≡b
A→…ab…或A→…aBb…a≮b
A→…aB…,且B=>b…或B=>Cb…a≯b
A→…Bb…，且B…a或B…aC FIRSTVT集构造
A->b... 或A->Bb...
b∈FIRSTVT(A)
A->B…
FIRSTVT(B)∈FIRSTVT(A)LASTVT集构造
A->...b 或A->...bB
b∈LASTVT(A)
A->…B
LASTVT(B)∈LASTVT(A)-
优先关系表构造
- 改进：构造优先函数
- 好处
- 节省空间
- 便于比较运算
- 方法
- 关系图法
若a.>b，fa 至gb画一条弧
若a <.b，fa至gb画一条弧；
该结点所能到达的所有结点
包括下级结点所能到达的结点 - 定义法（Floyd法）
-
步骤
1、令f(x) = g(x) = 1
2、比较x <. y，如果f(x)≥g(y)，则令g(y) = f(x) + 1 x .> y，如果f(x)≤g(y)，则令f(x) = g(y) + 1 x = y，如果f(x)≠g(y)，则令f(x) = g(y) = max(f(A)3、大于2n，非算符优先文法
-
- 关系图法
- 好处
- 改进：构造优先函数
-
- 特点
- 算符优先文法
-
规范规约方法（找句柄）
- LR分析法
- 定义
- 1L：自左向右
- 2R：逆最右推导（规范规约）
- 特点：局限大，基础
- 原理
- 自左向右
- 循环查找句柄
活前缀 - 归到开始符号，停止
- 项目类别
- 归约项目: A->α·
- 移进项目: A->α·aβ
- 待约项目: A->α·Bβ
- 接受项目: S’->S ·
- 构造步骤
1、拓广
2、求CLOSURE({S’->·S}),得到初态项目集
3、重复2，知道无新项目
4、GO函数构造文法DFA
5、生成LR(0)分析表
PS:生成LR（0）表时，归约r1，r2..决定于归约项目所对应的编号
- 定义
- SLR(1)分析法
- 简单LR表
- 易实现，有使用价值
- 过渡
- LR(1)分析法
- 规范LR表
- 适用大多数DFG
- 体积庞大
- 理论过渡
- LALR(1)分析法
- 实用
- 能力在SLR(1)和LR(1)之间
- LR分析法
题型
- 判断产生式文法类别：例3.3
- 正规式，求正规文法：例3.4
- 画DFA，再推正规文法
- 上下文无关文法描述正规表达式：例3.5
- 构造LL(1)分析表
- 证明文法是LL(1)文法
- 构造算符优先关系表、优先函数
- 构造LR(0)分析表
相关细节
- 文法相关定义
- 大写字母：非终结符
- 小写字母：终结符
- 希腊字母：文法符号串
