目录

• 1. 自顶向下分析（Top-Down Parsing）
  • 最左推导(Left-most Derivation)
  • 最右推导(Right-most Derivation)
  • 最左推导和最右推导的唯一性
  • 自顶向下语法分析的通用形式
  • 预测分析(Predictive Parsing)
  • 1.1. 文法转换
    • 问题1---回溯
    • 问题2---左递归导致无限循环
    • 消除直接左递归
    • 消除直接左递归的一般形式
    • 消除间接左递归
    • 消除左递归算法
    • 提取左公因子(Left Factoring)
    • 提取左公因式算法
  • 1.2. LL(1)文法
    • S_文法
    • 非终结符的后继符号集(FOLLOW)
    • 串首终结符集(FIRST)
    • 产生式的可选集(SELECT)
    • LL(1)文法概念
    • FIRST集计算
    • FOLLOW集计算
    • SELECT集计算
    • 预测分析表
  • 1.3. LL(1)文法的分析方法
    • 递归的预测分析法
    • 非递归的预测分析法(表驱动)
    • 递归的预测分析法vs.非递归的预测分析法
    • 预测分析法实现步骤
    • 预测分析法中的错误检测
    • 预测分析法中的错误恢复
• 2. 自底向上分析: 移入规约分析(Shift-Reduce Parsing)
  • 移入-归约分析的工作过程
  • 移入-归约分析器可采取的4中动作
  • 移入-归约分析中存在的问题
  • (句型的)短语
  • 2.1. LR分析法
    • LR分析法的基本原理
    • LR分析器(自动机)的总体结构
    • LR分析表的结构 及 分析过程
    • LR分析器的工作过程
    • LR分析算法
    • 如何构造给定文法的LR分析表
  • 2.2. LR(0)分析
    • LR(0)项目
    • 增广文法(Augmented Grammar)
    • LR(0)分析表的构造算法
      • CLOSURE()函数
      • GOTO()函数
      • 构造LR(0)自动机的状态集
      • LR(0)分析表构造算法
    • LR(0)自动机的形式化定义
    • LR(0)分析过程中的冲突
  • 2.3. SLR分析
    • SLR条件
    • 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分析表
  • 2.7. LR分析中的错误处理
    • 恐慌模式错误恢复
    • 短语层次错误恢复

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)

串首终结符集(FIRST)

产生式的可选集(SELECT)

LL(1)文法概念

FIRST集计算

算法:

计算串X₁X₂…X_n的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分析表构造算法

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分析表

**应该保守地使用二义性文法, 并且必须在严格控制之下使用, 英文稍有不慎就会导致语法分析器所识别的语言出现偏差. **

2.7. LR分析中的错误处理

恐慌模式错误恢复

短语层次错误恢复