-
1. 自顶向下分析（Top-Down Parsing）
- 最左推导(Left-most Derivation)
- 最右推导(Right-most Derivation)
- 最左推导和最右推导的唯一性
- 自顶向下语法分析的通用形式
- 预测分析(Predictive Parsing)
- 2. 自底向上分析: 移入规约分析(Shift-Reduce Parsing)
1. 自顶向下分析（Top-Down Parsing）
-
从分析树的顶部（根节点）向底部（叶节点）方向构造分析树
-
可以看成是从文法开始符号S推导出词串w的过程
-
每一步推导中，都需要做两个选择
- 替换当前句型中的哪个非终结符
- 用该非终结符的哪个候选式进行替换
最左推导(Left-most Derivation)
自顶向下的语法分析采用最左推导方式.
最右推导(Right-most Derivation)
最左推导和最右推导的唯一性
自顶向下语法分析的通用形式
预测分析(Predictive Parsing)
1.1. 文法转换
问题1---回溯
问题2---左递归导致无限循环
消除直接左递归
消除直接左递归的一般形式
消除间接左递归
合并产生式, 将间接左递归变成直接左递归再消除
消除左递归算法
在每个终结符的循环内:
- 先将所有比该终结符小的(标号小)终结符替换为产生式
- 然后消除改终结符产生式之间的立即左递归
提取左公因子(Left Factoring)
推迟进入候选式的选择, 减少回溯长度
提取左公因式算法
1.2. LL(1)文法
S_文法
如果S_文法包含ε产生式,那么它就成为了LL文法
非终结符的后继符号集(FOLLOW)
产生式的可选集(SELECT)
串首终结符集(FIRST)
LL(1)文法概念
FIRST集计算
算法:
计算串X1X2…Xn的FIRST集合:
FOLLOW集计算
SELECT集计算
预测分析表
1.3. LL(1)文法的分析方法
递归的预测分析法
非递归的预测分析法(表驱动)
递归的预测分析法vs.非递归的预测分析法
预测分析法实现步骤
预测分析法中的错误检测
预测分析法中的错误恢复
2. 自底向上分析: 移入规约分析(Shift-Reduce Parsing)
移入-归约分析的工作过程
移入-归约分析器可采取的4中动作
移入-归约分析中存在的问题
句柄: 句型的最左直接短语
(句型的)短语
2.1. LR分析法
LR分析法的基本原理
LR分析器(自动机)的总体结构
LR分析表的结构 及 分析过程
LR分析器的工作过程
LR分析算法
如何构造给定文法的LR分析表
- LR(0)分析
- SLR分析
- LR(1)分析
- LALR分析
2.2. LR(0)分析
LR(0)项目
句柄? 含义? 直接短语?
增广文法(Augmented Grammar)
LR(0)分析表的构造算法
CLOSURE()函数
GOTO()函数
构造LR(0)自动机的状态集
LR(0)分析表构造算法
LR(0)自动机的形式化定义
LR(0)分析过程中的冲突
可能存在:
-
移进 - 归约 冲突
-
归约 - 归约 冲突
- 如果LR(0)分析表中没有语法分析动作冲突,那么给定的文法就称为LR(0)文法
- 不是所有CFG都能用LR(0)方法进行分析, 也就是说, CFG不总是LR(0)文法
2.3. SLR分析
S: simple
用FOLLOW集来判断是归约还是移入
- 解决了一些 移入 - 归约 冲突
- 解决了 归约 - 归约 冲突 (每个产生式左部的FOLLOW集交集为∅)
LR分析的产生式满足LL分析产生式的条件吗??
SLR分析表构造算法
SLR分析中的冲突
2.4. LR(1)分析
LR(1)的提出
规范LR(1)项目
等价LR(1)项目
赋值语句文法的LR(1)分析表
LR(1)项目集闭包
GOTO函数
为文法 G' 构造LR(1)项集族
LR(1)自动机的形式化定义
LR分析表构造算法
2.5. LALR分析(lookahead-LR)
基本思想
合并同心项集
合并同心项集时产生 归约-归约冲突的例子
合并同心项集后, 虽然不产生冲突, 但可能会推迟错误的发现
LALR(1)的特点
2.6. 二义性文法的LR分析
二义性文法分析
二义性算术表达式文法的LR(0)分析器
二义性算术表达式文法的SLR分析表
二义性if语句文法的SLR分析表
**应该保守地使用二义性文法, 并且必须在严格控制之下使用, 英文稍有不慎就会导致语法分析器所识别的语言出现偏差. **