4.1 语法分析器
4.1.1 语法分析的作用
- 从词法分析器获得一个由词法单元组成的串，并验证这个串可以由源语言的文法生成。
- 对于语法错误的程序，报告错误信息，并恢复继续处理
- 对于语法正确的程序，生成语法分析树 (简称语法树)
语法分析的任务
- 输入：从词法分析器获得一个由词法单元组成的串
- 输出：验证这个串可以由源语言的文法生成。
- 语法规则表示：上下文无关文法
- 识别方法：语法分析树
4.1.2 语法分析器分类
常用语法分析方法：
- 自顶向下语法分析器(通常用于处理LL文法)：从语法分析树的根部开始构造语法分析树
- 自底向上语法分析器(通常用于处理LR文法)：从语法分析树的叶子开始构造语法分析树
这两种方法：总是从左到右、逐个扫描词法单元；只能处理特定类型的文法，但足以描述程序设计语言
4.2 上下文无关文法 CFG
4.2.1 文法
4.2.2 自顶向下语法分析
最左推导方式
总是选择每个句型的最左非终结符进行替换。
根据输入流中的下一个终结符，选择最左非终结符的一个候选式
通用形式——递归下降分析(Recursive-Descent Parsing)
由一组过程组成，每个过程对应一个非终结符
从文法开始符号S对应的过程开始，其中递归调用文法中其它非终结符对应 的过程。如果S对应的过程体恰好扫描了整个输入串，则成功完成语法分析
可能需要回溯(backtracking)， 导致效率较低
预测分析 (Predictive Parsing)
预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数（通常是一个）符号来选择正确的A-产生式。
- 可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也称为LL(k) 文法类
预测分析不需要回溯，是一种确定的自顶向下分析
4.2.3 推导
最左推导/最右推导
每个推导步骤需要做两个选择：
- 替换哪个非终结符号(顺序问题)
- 选择一个以此非终结符号作为头的产生式（选择问题）
最左推导：每次选择最左非终结符号
最右推导：总是选择最右边的非终结符号
最左/最右推导对推导顺序做出了约束
语法分析树
根结点的标号是文法的开始符号
每个叶子结点的标号是非终结符号、终结符号或ε
每个内部结点的标号是非终结符号
每个内部结点表示某个产生式的一次应用
一个语法分析树只对应一个最左推导（或最右推导）
二义性 Ambiguity
如果一个文法可以为某个句子生成多棵语法分析树（同样对应多个最左/右推导），这个文法就是二义的。
二义性文法对同一句子有多个最左推导或多个最右推导。
4.3 文法改造技术
消除二义性
例：考虑句子if E1 then if E2 then S1 else S2
二义性文法：stmt →if expr then stmt
| if expr then stmt else stmt
| other
引入消除二义性的规则：要求在then和else之间出现的语句必须是匹配好的
改写规则：
stmt → matched_stmt | open_stmt
matched_stmt → if expr then matched_stmt else matched_stmt
| other
open_stmt → if expr then stmt
| if expr then matched_stmt else open_stmt
消除左递归
自顶向下的语法分析技术（最左推导）不能处理左递归的情况，因此需要消除左递归。但是自底向上的技术可以处理左递归。
- 输入：没有环和ε产生式的文法G
- 输出：等价的无左递归的文法
提取左公因子
为什么要提取左公因子？
有些产生式具有相同的左公因子
当不清楚应该在两个产生式中如何选择时，可通过改写产生式推后这个决定，等收集足够多的信息再做出正确选择。
如何提取左公因子？
4.4 自顶向下语法分析
每个推导步骤需要做两个选择
- 替换哪个非终结符号(顺序问题)
- 选择一个以此非终结符号作为头的产生式（选择问题）
自顶向下的语法分析：
从分析树的根结点开始，按照先根次序，深度优先地创建各个结点
自顶向下的语法分析采用最左推导方式
总是选择每个句型的最左非终结符进行替换。
根据输入流中的下一个终结符，选择最左非终结符的一个候选式
如何自顶向下地构造语法分析树？
每个非终结符号对应于一个过程，该过程负责扫描此非终结符号对应的结构
程序执行从开始符号对应的过程开始，当扫描整个输入串时宣布分析成功完成
例：考虑利用以下文法自顶向下地构造输入串w=cad的语法分析树
S→cAd
A→ab|a
关键在于确定对最左非终结符号应用哪个产生式
- 随机选择
不一定选择正确的产生式
需要回溯重新选择
对左递归文法进入无限循环
- 预测分析
收集一些信息来判断选择哪个产生式
收集那些信息？如何判断？
LL(1)预测分析
第一个“L”表示从左到右扫描输入。
第二个“L”表示产生最左推导。
“1”表示每一步中只需要向前看一个输入符号来决定语法分析动作。
要求：给定文法，写出FIRST集、FOLLOW集、SELECT集+证明该文法是LL(1)文法→构造预测分析表→对于给定句子的分析（非递归，按照栈的形式来写）
【有时需要先消除左递归，对文法做出初步改造再分析】
FIRST
FIRST(X)
X为任意的文法符号串
可以从X推导得到串的首符号的集合
例如，有两个产生式A→α|β,且FIRST(α)和FIRST(β)不相交，则只需查看下一符号即可判断产生式。
对于
计算FIRST(X)
X是终结符号，那么加入X
X是非终结符号，且X→Y1Y2…Yk是产生式
- 如果a在FIRST(Yi)中，且ε在FIRST(Y1), … , FIRST(Yi-1)中，那么也加入a
- 如果ε在FIRST(Y1), … , FIRST(Yk)中，那么也加入ε
X是非终结符号且X →ε，那么也加入ε
计算FIRST(X1X2…Xn)
加入FIRST(X1)中所有非ε符号
若ε在FIRST(X1)中，加入FIRST(X2)中所有非ε符号 …
若ε在所有FIRST(Xi)中，也加入ε
FIRST集
FOLLOW
FOLLOW(A)
A是非终结符号
可能在某些句型中紧跟在A右边的终结符号的集合
例如：S→αAaβ，终结符号a ∈ FOLLOW(A)
FOLLOW(A)的计算主要是针对空串这种情况
计算所有非终结符号的FOLLOW集
将右端结束标记$加入FOLLOW(S)中
按照下面两个规则不断迭代，直到所有的FOLLOW集合都不再增长为止
- 如果存在产生式A→αBβ，那么FIRST(β)中所有非ε的符号都加入FOLLOW(B)中
- 如果存在一个产生式A→αB，或者A→αBβ且FIRST(β)包含 ε，那么FOLLOW(A)中所有符号都加入FOLLOW(B)中
可选集 SELECT
对于产生式
• 如果 ，那么
• 如果，那么
•
LL(1) 文法
如何判断一个文法是否为LL(1)的？
构造预测分析表
输入：文法G
输出：预测分析表M
方法：对于文法G的每个产生式A→a
- 对于FIRST(a)中的每个终结符号x，将A→a加入到M[A,x]中
- 如果ε在FIRST(a)，那么对于FOLLOW(A)中的每个符号y，将A→a也加入到M[A,y]中
最后在所有的空白条目中填入error
LL(1)预测分析
递归的预测分析
非递归的预测分析
递归/非递归的预测分析
4.5 自底向上语法分析
自底向上的语法分析：
从叶子结点（底部）开始逐渐向上到达根节点（顶部）
对应的最左推导过程：
E => T => T * F => F * F => id * F => id * id
对应的最右推导过程：
E => T => T * F => T * id => F *id => id * id
推导的反向操作称为归约
自底向上语法分析可看作将串w规约为开始符号的过程
归约：一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号
一次归约是一个推导步骤的反向操作。
自底向上语法分析的目标是反向构造一个推导过程。
根据句柄进行归约
句柄：和某个产生式体匹配的子串，代表相应最右推导中的一个反向步骤。
作用：利用句柄进行移入-归约语法分析
4.5.1 移入-归约语法分析技术
移入-归约语法分析是自底向上语法分析的一种形式
用一个栈来保存文法符号
用一个输入缓冲区来存放将要进行语法分析的其余符号
- 开始时刻：栈中只包含$，而输入为w$
- 结束时刻：栈中为S$，而输入为$
- 在分析过程中，不断移入符号，直到识别到句柄时进行归约
- 句柄在被识别之前，总是出现在栈的顶部
移入-归约语法分析器有四种动作：
- 移入：将下一个输入符号移入到栈顶
- 归约：将句柄归约为相应的非终结符号
句柄总是在栈顶
具体操作时弹出句柄，压入被归约到的非终结符号
- 接受：宣布分析过程成功完成
- 报错：发现语法错误，调用错误恢复子程序
示例：
4.5.2 LR语法分析技术
LR语法分析技术介绍
- LR(k)的语法分析概念
L表示最左扫描，R表示反向构造出最右推导
k表示最多向前看k个符号
- 当k增大时，相应的语法分析器的规模急剧增大
k = 2时，程序语言的语法分析器的规模通常非常庞大
当k = 0, 1时，已经可以解决很多语法分析问题，因此 具有实践意义
我们只考虑k <= 1的情况
语法分析器包括：
- 输入、输出
- 栈：栈中存放的是状态序列，可求出相应的符号序列
- 语法分析表：包括ACTION和GOTO两部分
如何利用语法分析表进行LR语法分析？
为什么使用LR语法分析器？
由表格驱动，虽然手工构造表格工作量很大，但 表格可以自动生成
对于几乎所有的程序设计语言，只要写出上下文无关文法，就能够构造出识别该语言的LR语法分析器
最通用的无回溯移入-归约分析技术
能分析的文法比LL(k)文法更多
如何构造语义分析表——LR(0)自动机
考法： 判断是否为LR(0)文法：写出分析表，不存在语义分析动作冲突，因此为LR(0)文法
1.增广文法
G的增广文法G'是在G中增加新开始符号S'，并加入产 生式S'→S而得到的
目的是告诉语法分析器何时停止语法分析并宣称接受输入符号串。
显然G'和G接受相同的语言
如何定义自动机状态：LR(0)项
如何构造LR(0)自动机：CLOSURE和GOTO函数
CLOSURE计算
构造闭包的目的是为了表示LR(0)自动机的状态
所以闭包中每个项应表示处于同样的状态
如果I是文法G的一个项集，CLOSURE(I)就是根据下列两条规则从I构造得到的项集:
将I中的各项加入CLOSURE(I)中
如果A→α·Bβ在CLOSURE(I)中，而B→γ是一个产生式，且项B→·γ不在CLOSURE(I)中，就将该项加入其中，不断应用该规则直到没有新项可加入
GOTO函数
I是一个项集
X是一个文法符号
定义：GOTO(I,X)为I中所有形如[A→α·Xβ]的项所对应的[A→αX·β]的集合的闭包。
GOTO定义了LR(0)自动机的转换，代表转换后的项集
如何构造分析表——SLR语法分析
考法： 写出SLR(1)分析表
如何构造语法分析表：SLR构造方法
如何构造语义分析表——LR(1)语法分析
考法： 写出LR(1)分析表
如何定义自动机状态：LR(1)项
LR(1)分析法的提出
对于产生式 A→α 的归约，在不同的使用位置，A会要求不同的后继符号
在特定位置， A的后继符集合是FOLLOW(A) 的子集
将一般形式为[A→α⋅β,a] 的项称为 LR (1) 项，其中A→αβ 是一个产生式，a是一个终结符 (这里将 $ 视为一个特殊的终结符)， 它表示在当前状态下，A 后面必须紧跟的终结符，称为该项的展望符 (lookahead)
- LR (1) 中的 1 指的是项的第二个分量的长度
- 在形如[A→α⋅β,a] 且 β≠ε 的项中（也就是对于待约项目与移入项目），展望符 a 没有任何作用
- 形如 [A→α⋅,a] 的项（归约项目）在只有在下一个输入符号等于 a 时才可以按照 A→α 进行归约
- 这样的 a 的集合总是 FOLLOW(A) 的子集，而且它通常是一个真子集
等价 LR (1) 项目
如何构造LR(1)自动机：CLOSURE和GOTO函数
CLOSURE计算
GOTO函数
和LR(0)项集的GOTO算法基本相同
利用CLOSURE和GOTO构造自动机
和LR(0)项集族的构造算法相同
如何构造语法分析表：LR(1)构造方法
如何构造语义分析表——LALR语法分析
LALR (lookahead-LR)
每个SLR文法都是LR(1)文法。
SLR语法分析表的分析能力较弱
LR(1)语法分析表的状态数量很大
LALR是实践中常用的方法
- 状态数量和SLR的状态数量相同
- 能够方便地处理大部分常见程序设计语言的构造
·
LALR的思想就是将具有相同核心的LR(1)项集进行合并
不会产生新的移入/归约冲突
因为移入动作仅由核心决定，不考虑向前看符号
可能产生新的归约/归约冲突
所以，LALR的算法可描述为：
- 首先构造LR(1)项集
- 若没有冲突，则将具有相同核心的项集合并
- 根据合并后的项集族构造语法分析表
4.5.3 二义性文法
二义性文法都不是LR的
某些二义性文法是有用的
- 可以简洁地描述某些结构
- 隔离某些语法结构，对其进行特殊处理
对于某些二义性文法
1.构造无二义性文法（见文法改造技术部分）
2.可以在LR分析器中实现优先级和结合性规则
二义性文法的优点
- 容易修改算符的优先级和结合性
- 简洁：如果有多个优先级，那么无二义性文法将引入 太多的非终结符号
- 高效：不需要处理像E→T这样的归约