第三章 语法分析

本章阐述编译器采用的典型语法分析方法。首先提出有关上下文无关文法的基本概念，然后介绍适合于手工实现的预测分析技术，最后给出自动工具采用的LR分析算法。

3.1上下文无关文法

3.1.1 上下文无关文法的定义

• 正规式能定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复
  例：a (ba)⁵, a (ba)^*

• 正规式不能用于描述配对或嵌套的结构
  例1：配对括号串的集合
  例2：{wcw | w是a和b的串}

• 上下文无关文法是四元组（V_T , V_N , S, P）
  V_T : 终结符集合
  V_N: 非终结符集合
  S : 开始符号
  P : 产生式集合， 产生式形式 : A → α
  例 ( {id, +, * ，-， (, )}, {expr, op}, expr, P )
  expr → expr op expr expr → (expr)
  expr → - expr expr → id
  op → + op → *

3.1.2 推导

• 把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替
  例: E E + E | E * E | (E ) | - E | id
  E => -E => -(E) => -(E + E) => -(id + E)=> -(id + id)
• 概念
  • 上下文无关语言、等价的文法、句型
  • 记号
    S =>^*α 、S =>⁺ w
  • 最左推导
    E =>_lm -E =>_lm-(E) =>_lm -(E + E)=>_lm-(id + E) =>_lm -(id + id)
  • 最右推导（规范推导）
    E =>_rm -E =>_rm -(E) =>_rm-(E + E)=>_rm-(E + id)=>_rm-(id + id)

3.1.3 分析树

3.1.4 二义性

3.2 语言和文法

• 文法的优点

  • 文法给出了精确的，易于理解的语法说明
  • 自动产生高效的分析器
  • 可以给语言定义出层次结构
  • 以文法为基础的语言的实现便于语言的修改

• 文法的问题

  • 文法只能描述编程语言的大部分语法

    3.2.1 正规式和上下文无关文法的比较

• 正规式

• 文法

3.2.2 分离词法分析器理由

• 为什么要用正规式定义词法
  • 词法规则非常简单，不必用上下文无关文法
  • 对于词法记号，正规式描述简洁且易于理解
  • 从正规式构造出的词法分析器效率高
• 从软件工程角度看，词法分析和语法分析的分离有如下好处
  • 简化设计
  • 编译器的效率会改进
  • 编译器的可移植性加强
  • 便于编译器前端的模块划分

3.2.3 验证文法产生的语言

G : S → (S ) S | ε L(G) = 配对的括号串的集合

• 按推导步数进行归纳：推出的是配对括号串
  • 归纳基础： S => ε
  • 归纳假设：少于n步的推导都产生配对的括号串
  • 归纳步骤：n步的最左推导如下：
    S => (S)S => (x) S => (x) y
• 按串长进行归纳：配对括号串可由S推出
  • 归纳基础： S => ε
  • 归纳假设：长度小于2n的都可以从S推导出来
  • 归纳步骤：考虑长度为2n(n ≥ 1)的w = (x) y
    S => (S )S => (x) S => (x) y

    3.2.4 适当的表达式文法

    3.2.5 消除二义性

    3.2.6 消除左递归

    3.2.7 提左因子

    3.2.8 非上下文无关的语言结构

    3.2.9 形式语言鸟瞰

• 文法 G = (VT , VN, S, P)
• 0型文法：α → β，α , β ∈ (V_N ∪V_T)^*, | α | ≥ 1
• 1型文法：| α | ≤ | β |，但S → ε可以例外
• 2型文法：A → β，A∈V_N , β ∈ (V_N ∪V_T)^*
• 3型文法：A → αB或A → α，A, B∈V_N , α ∈V_T
• 短语文法、上下文有关文法、上下文无关文法、正规文法

3.3 自上而下分析

3.3.1 自上而下分析的一般方法

3.3.2 LL(1)文法

• LL(1)文法
• LL(1)文法有一些明显的性质
  • 没有公共左因子
  • 不是二义的
  • 不含左递归

    3.3.3 递归下降的预测分析

    3.3.4 非递归的预测分析

    3.3.5 构造预测分析表

    （1）对文法的每个产生式A   ，执行(2)和(3)
    （2）对FIRST()的每个终结符a，把A   加入M[A, a]
    （3）如果在FIRST()中，对FOLLOW(A)的每个终结符b（包括$）, 把A  加入M[A, b]
    （4）M的其它没有定义的条目都是error

    3.3.6 预测分析的错误恢复

• 先对编译器的错误处理做一个概述
  • 词法错误，如标识符、关键字或算符的拼写错
  • 语法错误，如算术表达式的括号不配对
  • 语义错误，如算符作用于不相容的运算对象
  • 逻辑错误，如无穷的递归调用
• 分析器对错误处理的基本目标
  • 清楚而准确地报告错误的出现
  • 迅速地从每个错误中恢复过来，以便诊断后面的错误，并尽量少出现伪错误
  • 它不应该使正确程序的处理速度降低太多
• 非递归预测分析在什么场合下发现错误
  • 栈顶的终结符和下一个输入符号不匹配
  • 栈顶是非终结符A，输入符号是a，而M[A , a]是空白
• 非递归预测分析：采用紧急方式的错误恢复
  • 发现错误时，分析器每次抛弃一个输入记号，直到输入记号属于某个指定的同步记号集合为止
• 同步
  • 词法分析器当前提供的记号流能构成的语法结构，正是语法分析器所期望的

    3.4 自下而上分析

    3.4.1 归约

    3.4.2 句柄

• 句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步
• 句柄的右边仅含终结符，如果文法二义，那么句柄可能不唯一

  3.4.3 用栈实现移进-归约分析

  先通过移进-归约分析器在分析输入串id₁ * id₂ + id₃时的动作序列来了解移进-归约分析的工作方式

  3.4.4 移进-归约分析的冲突

  3.5 LR分析器

• 特点
  • 适用于一大类上下文无关文法
  • 效率高
• 主要介绍构造LR分析表的三种技术
  • 简单的LR方法（简称SLR）
  • 规范的LR方法
  • 向前看的LR方法（简称LALR）

    3.5.1 LR分析算法

    3.5.2 LR文法和LR分析方法的特点

• 活前缀：右句型的前缀，该前缀不超过最右句柄的右端
• LR文法：我们能为之构造出所有条目都唯一的LR分析表
• LR分析方法的特点
  • 栈中的文法符号总是形成一个活前缀
  • 分析表的转移函数本质上是识别活前缀的DFA
  • 栈顶的状态符号包含了确定句柄所需要的一切信息
  • 是已知的最一般的无回溯的移进归约方法
  • 能分析的文法类是预测分析法能分析的文法类的真超集
  • 能及时发现语法错误
  • 手工构造分析表的工作量太大

    3.5.3 构造SLR分析表

    3.5.4 构造规范的LR分析表

    3.5.5 构造LALR分析表

• 合并同心项目集可能会引起冲突
  • 同心集的合并不会引起新的移进归约冲突
  • 同心集的合并有可能产生新的归约归约冲突

    3.5.6 非LR的上下文无关结构

• 若自左向右扫描的移进-归约分析器能及时识别出现在栈顶的句柄，那么相应的文法就是LR的

  3.6 二义文法的应用

  二义文法的特点：
• 二义文法决不是LR文法
• 简洁、自然
• 可以用文法以外的信息来消除二义
• 语法分析的效率高（基于消除二义后得到的分析表）

  3.6.1 使用文法以外信息来解决分析动作冲突

-二义文法：E → E + E | E * E | (E) | id
规定： *优先级高于+，两者都是左结合

3.6.2 特殊情况产生式引起的二义性

3.6.3 LR分析的错误恢复

• LR分析器在什么情况下发现错误
  • 访问动作表时若遇到出错条目
  • 访问转移表时它决不会遇到出错条目
  • 决不会把不正确的后继移进栈
  • 规范的LR分析器甚至在报告错误之前决不做任何无效归约

    3.7 分析器的生成器

    3.7.1 分析器的生成器Yacc

    3.7.2 用Yacc处理二义文法

    3.7.3 Yacc的错误恢复

• 编译器设计者的工作
  • 决定哪些“主要的”非终结符将有错误恢复与它们相关联
  • 加入A → error α的错误产生式，其中A是主要非终结符，α是文法符号串
  • 为这样的产生式配上语义动作
• Yacc把错误产生式当作普通产生式处理
• 遇到语法错误时
  • 从栈中弹出状态，直到发现栈顶状态的项目集包含形为A →·error α的项目为止
  • 把虚构的终结符error“移进”栈
  • 忽略若干输入符号，直至找到α，把α移进栈
  • 把error α归约为A，恢复正常分析