【编译原理】第四章 语法分析

引言

语法分析的主要任务：根据给定的文法，识别输入句子的各个成分，从而构造出句子的分析树
大部分程序设计语言的语法构造可以用CFG来描述，CFG以token作为终结符
大部分语法分析器都期望文法是无二义性的，否则，就不能为一个句子构造唯一的语法分析树

语法分析的种类

自顶向下分析：从分析树的顶部（根节点）向底部（叶节点）构造分析树；从文法开始符号S推导出串w
自底向上的分析：从分析树的底部（叶节点）向顶部（根节点）构造分析树；将一个串w归约为文法开始符号S
最高效的自顶向下和自底向上方法智能处理某些文法子类，但是其中的某些子类，特别是LL和LR文法，其表达能力足以描述线代程序设计的大部分语法构造

4.1 自顶向下的分析

1、概述

可以看成是从文法开始符号S推导出词串w的过程

推导的每一步，都需要做两个选择：替换当前句型中的哪个非终结符；用该非终结符的哪个候选式进行替换

2、最右推导与最右推导

（1）最左推导

在最左推导中，总是选择每个句型的最左非终结符进行替换

如果S=>*_lmα，则称α是当前文法的最左句型。

（2）最右推导

在最右推导中，总是选择每个句型的最右非终结符进行替换

在自底向上的分析中，总是采用最左规约方式，因此把最左规约成为规范规约，而最右推导相应地称为规范推导

（3）最左推导和最右推导的唯一性

3、自顶下的语法

（1）自顶向下的语法分析采用最左推导方式

总是选择每个句型的最左非终结符进行替换
根据输入流中的下一个终结符，选择最左非终结符的一个候选式

（2）自顶向下语法分析的通用形式

递归下降分析
由一组过程组成，每个过程对应一个非终结符
从文法开始符号S对应的过程开始，其中递归调用文法中其它非终结符对应的过程。如果S对应的过程体恰好扫描了整个输入串，则完成语法分析

（3）自顶向下分析过程中的问题

问题1：同一个非终结符的多个候选式存在共同前缀，将导致回溯现象

问题2：左递归文法会使递归下降分析器陷入无限循环

4、消除左递归

（1）消除直接左递归

一般形式

（2）消除间接左递归

（3）消除左递归算法

5、提取左公因子

6、预测分析

预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数（通常是一个）符号来选择正确的A-产生式，可以以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k)文法类
预测分析不需要回溯，是一种确定的自顶向下分析方法

4.2 预测分析法

1、LL(1)文法

预测分析法的工作过程：从文法开始符号触发，在每一步推导过程中根据当前句型的最左非终结符A和当前输入符号a，选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。
S_文法（简单的确定性文法，Korenjak & Hopcroft ， 1966）

• 每个产生式的右部都以终结符开始
• 同一非终结符的各个候选式的首终结符都不同
• S_文法不含ε产生式
  例：
  

是么时候会用ε产生式

如果当前某非终结符A与当前输入符a不匹配时，则存在A→ε，可以通过检查a是否可以出现A的后面，来决定是否使用产生式A→ε（若文法中无A→ε，则应报错）

非终结符的后继符号集

可能在某个句型中紧跟在A后边的终结符a的集合，记为FOLLOW(A)
FOLLOW(A)={a| S =>* αAaβ, a∈VT，α,β∈(VT∪VN) }
如果A是某个句型的最右符号，则将结束符“$”添加到FOLLOW(A)*中

产生式的可选集

产生式A→β的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为SELECT( A→β )
SELECT( A→aβ ) = { a }
SELECT( A→ε )=FOLLOW( A )
q_文法

• 每个产生式的右部或为ε，或以汇终结符开始
• 具有相同左部的产生式有不相交的可选集
• q_文法不含右部以非终结符打头的产生式

串首终结符集

串首的第一个符号，并且是终结符。简称串首终结符
给定一个文法符号串α，α的串首终结符*FIRST(α)*被定义为可以从α推导出的所有串首终结符构成的集合。如果α=>*ε，那么ε也在FIRST(α)中

计算文法符号X的FIRST(X)

算法
不断应用下列规则，直到没有新的终结符或ε可以被加入到任何FIRST集合中为止

• 如果X是一个终结符，那么FIRST(X) = {X}
• 如果X是一个非终结符，且X→Y₁…Y_k ∈ P(k>=1)，那么如果对于某个i，a在FIRST (Yi ) 中且ε 在所有的 FIRST(Y1) , … , FIRST(Yi-1)中(即Y1…Yi-1=>* ε )，就把a加入 到FIRST( X )中。如果对于所有的 j = 1,2, . . . , k，ε在 FIRST(Yj)中，那么将ε加入到FIRST( X )
• 如果X→ε∈P，那么将ε加入到FIRST( X )中

计算串X1X2 …Xn的FIRST 集合

• 向FIRST(X1X2…Xn)加入FIRST(X1)中所有的非ε符号
• 如果ε在FIRST(X1)中，再加入FIRST(X2)中的所有非ε符号；如果ε在FIRST(X1)和FIRST(X2)中，再加入FIRST(X3)中的所有非ε符号，以此类推
• 最后，如果对所有的i，ε都在FIRST(Xi)中，那么将ε加入到FIRST(X1X2…Xn) 中

产生式A→α的可选集

产生式A→α的可选集SELECT

• 如果 ε∉FIRST(α), 那么SELECT(A→α)= FIRST(α)
• 如果 ε∈FIRST(α), 那么SELECT(A→α)=( FIRST(α)-{ε} )∪FOLLOW(A)

LL(1)文法

文法G是LL(1)的，当且仅当G的任意两个具有相同左部的产生式A → α | β 满足下面的条件：

• 不存在终结符a使得α和β都能够推导出以a开头的串
• α和β至多有一个能推导出ε
• 如果β=>ε，则FIRST (α)∩FOLLOW(A) =Φ；如果 α=> ε，则FIRST (β)∩FOLLOW(A) =Φ；
  同一个非终结符的各个产生式的可选集互不相交
  可以为LL(1)文法构造预测分析器

第一个“L”表示从左向右扫描输入
第二个“L”表示产生最左推导
“1”表示在每一步中只需要向前看一个输入符号来决定语法分析动作

计算非终结符A的FOLLOW(A)

算法
不断应用下列规则，直到没有新的终结符可以被加 入到任何FOLLOW集合中为止

• 将$放入FOLLOW( S )中，其中S是开始符号，$是输入右端的结束标记
• 如果存在一个产生式A→αBβ，那么FIRST ( β )中除ε 之外的所有符号都在FOLLOW( B )中
• 如果存在一个产生式A→αB，或存在产生式A→αBβ且FIRST ( β ) 包含ε，那么 FOLLOW( A )中的所有符号都在FOLLOW( B )

例：表达式文法各产生式的SELECT集

LL(1)文法的分析方法

• 递归的预测分析法
• 非递归的预测分析法

2、递归的预测分析法

3、非递归的预测分析法

4、预测分析中的错误恢复

4.3 自底向上的分析

4.4 LR分析法

4.5 语法分析器自动生成工具

转载：https://blog.csdn.net/Swocky/article/details/104663887