语法分析
语法分析
根据给定的文法，识别输入句子的各个成分，构造出句子的分析树
推导
- 最左推导和最右推导都具有唯一性
最左推导(Left-most Derivation)
- 总是选择每个句型的最左非终结符进行替换
- $S\Rightarrow^*_{lm} \alpha$，称$\alpha$是当前文法的最左句型
- 逆过程称为最右归约
最右推导(Right-most Derivation)
- 总是选择每个句型的最右非终结符进行替换
- $S\Rightarrow^*_{rm} \alpha$，称$\alpha$是当前文法的最右句型
- 逆过程称为最左归约
1 2 3 4 5 6
E =>rm E + E =>rm E + ( E ) =>rm E + ( E + E ) =>rm E + ( E + id ) =>rm E + ( id + id ) =>rm id + ( id + id )
- 在自底向上的分析中，总是采用最左规约的方式，因此把最左规约称为规范归约，而最右推导称为规范推导
自顶向下的分析
Top-Down Parsing
从分析树的顶部向底部方向构造分析树
- 可以看成是从文法开始符号$S$推导出词串$w$的过程
- 推导的每一步，都需要做两个选择
- 替换当前句型中的哪个非终结符
- 用该非终结符的哪个候选式进行替换
采用最左推导方式
递归下降分析
- 由一组过程组成，每个过程对应文法的一个非终结符
- 从文法开始符号$S$对应的过程开始，递归调用文法中其他非终结符对应的过程。
- 如果$S$对应的过程体恰好扫描了整个输入串，则成功完成语法分析
1 2 3 4 5 6 7 8 9 10
void A( ) { 选择一个A产生式， A →X1 X2 … Xk; for (i = 1 to k) { if (Xi是一个非终结符号) 调用过程 Xi ( ) ; else if (Xi 等于当前的输入符号a) 读入下一个输入符号; else /* 发生了一个错误 */ ; } }
- 分类
- 不确定的分析：回溯的分析
- 确定的分析：预测分析
- LL(1)文法可以进行预测分析
存在的问题
- 同一非终结符的多个候选式存在共同前缀，将导致回溯现象
- 左递归文法会使递归下降分析器陷入无限循环
文法转换
左递归
- 存在$A\Rightarrow^+ A\alpha$
- 直接左递归
- 含有$A\rightarrow A\alpha$形式产生式的文法
- 间接左递归
- 经过两步或两步以上推导产生的左递归
消除直接左递归
\[A \rightarrow A\alpha_1|A\alpha_2|...|A\alpha_n|\beta_1|\beta_2|...|\beta_m\] \[\downarrow\] \[A \rightarrow \beta_1 A^{'}|\beta_2 A^{'}|...|\beta_m A^{'}\] \[A^{'} \rightarrow \alpha_1 A^{'}|\alpha_2 A^{'}|...|\alpha_n A^{'}|\varepsilon\]消除间接左递归
将$S$的定义代入$A$-产生式中，得到直接左递归
提取左公因式
通过改写产生式来推迟决定，等读入了足够多的输入，获得足够信心后再做出正确的选择
文法G
1
2
3
S → aAd | aBe
A → c
B → b
文法G’
1
2
3
4
S → a S'
S' → Ad | Be
A → c
B → b
预测分析
不需要回溯，是一种确定的自顶向下分析
从文法开始符号出发，在每一步推导过程中根据当前句型的最左非终结符$A$和当前输入符号$a$，选择正确的$A$-产生式。为保证分析的确定性，选出的候选式必须是唯一的
1. S_文法（简单的确定性文法）
- 每个产生式的右部都以终结符开始
- 同一非终结符的各个候选式的首终结符都不同
- 该文法不含$\varepsilon$产生式
2. q_文法
- 每个产生式的右部或为$\varepsilon$，或以终结符开始
- 具有相同左部的产生式有不相交的可选集
3. LL(1)文法
当且仅当G的任意两个具有相同左部的产生式$A\rightarrow \alpha|\beta$满足下面的条件
- 不存在终结符$a$使得$\alpha$和$\beta$都能够推导出以$a$开头的串
- $\alpha$和$\beta$至多有一个能推导出$\varepsilon$
- 同一非终结符的各个产生式的可选集互不相交
非终结符的后继符号集$FOLLOW$
$FOLLOW(A)$：可能在某个句型中紧跟在$A$后边的终结符$a$的集合
- 若$A$是某个句型的最右符号，则将结束符$\$$添加到$FOLLOW(A)$中
串首终结符集$FIRST$
- 串首终结符：串首第一个符号，并且是终结符
$FIRST(\alpha)$：可以从$\alpha$推导出的所有串首终结符构成的集合
- 若$\alpha \Rightarrow^* \varepsilon$，则$\varepsilon$也在$FIRST(\alpha)$中
产生式的可选集$SELECT$
由$FOLLOW$集和$FIRST$集求得
$SELECT(A\rightarrow \beta)$：可以选用该产生式推导时对应的输入符号的集合
- $SELECT(A\rightarrow a\beta)={a}$
- $SELECT(A\rightarrow \varepsilon)=FOLLOW(A)$
规范计算$SELECT(A\rightarrow \alpha)$
\[SELECT(A\rightarrow \alpha) =\begin{cases} FIRST(\alpha) & if~~\varepsilon \notin FIRST(\alpha) \\ \{FIRST(\alpha)- \{\varepsilon\}\}\cup FOLLOW(A) & if~~\varepsilon \in FIRST(\alpha) \end{cases}\]$FIRST$集和$FOLLOW$集的计算
计算文法符号$X$的$FIRST$集
- 如果$X$是一个终结符，那么$FIRST(X)={X}$
- 如果$X$是一个非终结符，且$X\rightarrow Y_1…Y_k\in P(k\geq 1)$，那么如果对于某个$i$，$a$在$FIRST(Y_i)$中，且$\varepsilon$在所有的$FIRST(Y_1),…,FIRST(Y_{i-1})$中，就把$a$加入到$FIRST(X)$中。
- 如果对于所有的$j=1,2,…,k$，$\varepsilon$在$FIRST(Y_j)$中，那么将$\varepsilon$加入到$FIRST(X)$
- 如果$X\rightarrow \varepsilon \in P$，那么将$\varepsilon$加入到$FIRST(X)$中
计算串$X_1X_2…X_n$的$FIRST$集
- 向$FIRST(X_1X_2…X_n)$加入$FIRST(X_1)$中所有的非$\varepsilon$符号
- 如果$\varepsilon$在$FIRST(X_1)$中，再加入$FIRST(X_2)$中的所有非$\varepsilon$符号；以此类推
- 若对所有的$i$，$\varepsilon$都在$FIRST(X_i)$中，那么将$\varepsilon$加入到$FIRST(X_1X_2…X_n)$中
计算非终结符$A$的$FOLLOW(A)$
- 将\$放入$FOLLOW(S)$中，其中$S$是开始符号，\$是输入右端的结束标记
- 如果存在一个产生式$A\rightarrow \alpha B\beta$，那么$FIRST(\beta)$中除$\varepsilon$之外的所有符号都在$FOLLOW(B)$中
- 如果存在一个产生式$A\rightarrow \alpha B$，或存在产生式$A\rightarrow \alpha B\beta$且$FIRST(\beta)$包含$\varepsilon$，那么$FOLLOW(A)$中的所有符号都在$FOLLOW(B)$中
递归地预测分析
在递归下降分析中，编写每一个非终结符对应的过程时，根据预测分析表进行产生式的选择
- 是对递归下降框架的扩展
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<PROGRAM> → program <DECLIST> :<TYPE> ; <STLIST> end
procedure PROGRAM(TOKEN);
begin
if TOKEN≠’program’ then ERROR;
GETNEXT(TOKEN);
DECLIST(TOKEN);
if TOKEN≠’:’ then ERROR;
GETNEXT(TOKEN);
TYPE(TOKEN)
if TOKEN≠’;’ then ERROR;
GETNEXT(TOKEN);
STLIST(TOKEN);
if TOKEN≠’end’ then ERROR;
GETNEXT(TOKEN);
end
非递归地预测分析
不需要为每个非终结符编写递归下降过程，而是根据预测分析表构造一个自动机，所以该预测分析也叫表驱动的预测分析 （其实就是下推自动机PDA，显示地维护一个栈结构）
- 输入：一个串w和文法G的分析表M
- 输出：如果w在L(G)中，输出w的最左推导；否则给出错误指示
- 输入缓冲区是w，G的开始符号位于栈顶，其下面是\$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
设置ip使它指向w的第一个符号，其中ip是输入指针; 令X=栈顶符号; while (X != $){ if (X == ip所指向的符号a) 执行栈的弹出操作，将ip向后移动一个位置; else if (X是一个终结符) error(); else if (M[X, a]是一个报错条目) error(); else if (M[X, a]=X->Y1Y2...Yk) { 输出产生式 X->Y1Y2...Yk; 弹出栈顶符号; 将Yk, Yk-1..., Y1压入栈中，其中Y1位于栈顶; } 令X=栈顶符号; }
预测分析法实现步骤
- 构造文法
- 改造文法：消除二义性、消除左递归、消除回溯
- 求每个变量的$FIRST$集和$FOLLOW$集，从而求得每个候选式的$SELECT$集
- 检查是不是$LL(1)$文法。若是，构造预测分析表
- 对于递归的预测分析，根据预测分析表为每一个非终结符编写一个过程；对于非递归的预测分析，实现表驱动的预测分析算法
错误检测
- 栈顶的终结符和当前输入符号不匹配
- 栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空
错误恢复
- 恐慌模式
- 忽略输入中的一些符号，直到输入中出现由设计者选定的同步词法单元集合中的某个词法单元
- 其效果依赖于同步集合的选取。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复
- 例如：可以把$FOLLOW(A)$中的所有终结符放入非终结符$A$的同步记号集合
- 其效果依赖于同步集合的选取。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复
- 如果终结符在栈顶而不能匹配，一个简单的办法就是弹出此终结符
- 忽略输入中的一些符号，直到输入中出现由设计者选定的同步词法单元集合中的某个词法单元
自底向上的分析
从分析树的底部向顶部方向构造分析树，可以看成是将输入串w归约为文法开始符号S的过程
- 采用最左归约，反向构造最右推导
- 关键在于正确地识别句柄
移入-归约分析
工作过程
- 在对输入串的一次从左到右扫描过程中，语法分析器将零个或多个输入符号移入到栈的顶端，直到它可以对栈顶的一个文法符号串$\beta$进行归约为止
- 然后，把$\beta$归约为某个产生式的左部
- 语法分析器不断地重复上述过程，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空为止
采取的动作
- 移入
- 归约
- 接收
- 报错
存在的问题
- 归约-归约冲突
- 错误地识别了句柄
- 句柄：句型的最左直接短语
- 移入-归约冲突
- 不确定当前是要进行移入还是归约
LR分析法
LR文法
最大、可以构造出相应移入-归约语法分析器的文法类
- LR(k)分析
- （决定是否归约时）需要向前查看k个输入符号的LR分析
- 句柄是逐步形成的，用“状态”表示句柄识别的进展程度
1 2 3 4
S -> ·bBB 移进状态 S -> b·BB 待约状态 S -> bB·B 待约状态 S -> bBB· 归约状态
LR分析器（自动机）
LR分析算法
输入：串w和LR语法分析表（包含ACTION函数和GOTO函数） 输出：如果w在L(G)中，则输出w的自底向上语法分析过程中的归约步骤；否则给出一个错误指示
1
2
3
4
5
6
7
8
9
10
11
12
13
令a为w$的第一个符号;
while(1) { /* 永远重复 */
令s是栈顶的状态;
if ( ACTION [s，a] = st ) {
将a, t压入各自的栈中;
令a为下一个输入符号;
} else if (ACTION [s，a] = 归约A → β ) {
从栈中弹出│β│个符号;
将GOTO [t，A]压入栈中;
输出产生式 A → β;
} else if (ACTION [s，a] = 接受) break; /* 语法分析完成 */
else 调用错误恢复例程;
}
LR(0)分析
基本概念
LR(0)项目
右部某位置标有圆点的产生式
1
2
3
4
5
对于该产生式S -> bBB
S -> ·bBB 移进项目
S -> b·BB 待约项目
S -> bB·B 待约项目
S -> bBB· 归约项目
- 产生式$A\rightarrow \varepsilon$只生成一个项目$A\rightarrow ·$
- 项目描述了句柄识别的状态
- 后继项目
- 同属于一个产生式的项目，但圆点的位置只相差一个符号，则称后者是前者的后继项目
- $A\rightarrow \alpha ·X\beta$的后继项目是$A\rightarrow \alpha X·\beta$
增广文法
G是一个以S为开始符号的文法，则G的增广文法G’为在G中加上新开始符号S’和产生式$S’\rightarrow S$而得到的文法
- 目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态
项目集合闭包
所有等价的项目组成一个项目集，每个项目集闭包对应着自动机的一个状态
CLOSURE()函数
- 项目集$I$的闭包 $CLOSURE(I) = I \cup {B\rightarrow ·\gamma |A\rightarrow \alpha ·B\beta \in CLOSURE(I), B\rightarrow \gamma \in P}$
GOTO()函数
- 返回项目集$I$对应于文法符号X的后继项目集闭包 $GOTO(I,X)=CLOSURE({A\rightarrow \alpha X·\beta | A\rightarrow \alpha ·X\beta \in I })$
LR(0)分析表构造算法
表中的符号含义
- sn：将符号a、状态n压入栈
- rn：用第n个产生式进行归约
- 构造G’的规范LR(0)项集族$C={I_0,I_1,…,I_n}$
- 令$I_i$对应于状态$i$,
- $if~A\rightarrow \alpha ·a\beta \in I_i ~and~GOTO(I_i, a)=I_j ~then~ ACTION[i, a]=sj$
- $if~A\rightarrow \alpha ·B\beta \in I_i ~and~GOTO(I_i, B)=I_j ~then~ GOTO[i, B]=j$
- $if~A\rightarrow \alpha · \in I_i ~and~ A\neq S’ ~then~ for~ \forall a\in V_T \cup \{\$ \} ~do~ ACTION[i, a]=rj$（$j$是产生式$A\rightarrow \alpha$的编号）
- $if~S’\rightarrow S· \in I_i ~then~ ACTION[i, \$]=acc$
- 没有定义的所有条目都设置为”error”
（这里的$GOTO()$是函数，和$GOTO[]$表是不一样的）
LR(0)自动机的形式化定义
根据给定的文法$G=(V_N, V_T, P, S)$构造LR(0)自动机$M=(C, V_N \cup V_T, GOTO, I_0, F)$
- 状态集：$C$
- 符号表：$V_N \cup V_T$
- 转换函数：$GOTO$
- 初始状态：$I_0=CLOSURE({S’\rightarrow .S})$
- 终止状态：$F={CLOSURE({S’\rightarrow S.})}$
其实这应该是个下推自动机，不应该用有穷自动机的方式定义，应该更加详细一点，包括有穷栈符号集和栈底符号
不是所有CFG都能用LR(0)方法进行分析
问题
存在归约-归约冲突、移入-归约冲突
SLR分析
Simple LR 分析，向前查看1个输入符号
基本思想
查看FOLLOW集，若输入符号在FOLLOW集中，则用对应的产生式进行归约
SLR分析表构造算法
- 构造G’的规范LR(0)项集族$C={I_0,I_1,…,I_n}$
- 令$I_i$对应于状态$i$,
- $if~A\rightarrow \alpha ·a\beta \in I_i ~and~GOTO(I_i, a)=I_j ~then~ ACTION[i, a]=sj$
- $if~A\rightarrow \alpha ·B\beta \in I_i ~and~GOTO(I_i, B)=I_j ~then~ GOTO[i, B]=j$
- $if~A\rightarrow \alpha · \in I_i ~and~ A\neq S’ ~then~ for~ \forall a\in FOLLOW(A) ~do~ ACTION[i, a]=rj$（$j$是产生式$A\rightarrow \alpha$的编号）
- $if~S’\rightarrow S· \in I_i ~then~ ACTION[i, \$]=acc$
- 没有定义的所有条目都设置为”error”
LR(1)分析
基本概念
规范LR(1)项目
$[A\rightarrow \alpha ·\beta, a]$
- 展望符：$a$为一个终结符，它表示在当前状态下，$A$后面必须紧跟的终结符
- 只有在$\beta =\varepsilon$时，展望符$a$才有作用。一个形如$[A\rightarrow \alpha ·,a]$的项只有在下一个输入符号等于$a$时才可以按照$A\rightarrow \alpha$进行归约
- 这样的$a$的集合总是$FOLLOW(A)$的子集，通常是一个真子集
等价LR(1)项目
对于$[A\rightarrow \alpha ·B\beta, a]$，若$B\rightarrow \gamma \in P$，那么其等价项目为$[B\rightarrow ·\gamma,b]$，其中$b\in FIRST(\beta a)$
同心
除展望符外，两个LR(1)项目集是相同的，则称这两个LR(1)项目集是同心的
LR分析表构造算法
- 构造G’的规范LR(0)项集族$C={I_0,I_1,…,I_n}$
- 令$I_i$对应于状态$i$,
- $if~[A\rightarrow \alpha ·a\beta,b] \in I_i ~and~GOTO(I_i, a)=I_j ~then~ ACTION[i, a]=sj$
- $if~[A\rightarrow \alpha ·B\beta, b] \in I_i ~and~GOTO(I_i, B)=I_j ~then~ GOTO[i, B]=j$
- $if~[A\rightarrow \alpha ·,a] \in I_i ~and~ A\neq S’ ~then~ ACTION[i, a]=rj$（$j$是产生式$A\rightarrow \alpha$的编号）
- $if~[S’\rightarrow S·,\$] \in I_i ~then~ ACTION[i, \$]=acc$
- 没有定义的所有条目都设置为”error”
LALR分析
基本思想
- 寻找具有相同核心的LR(1)项目集，并将这些项目集合并成一个项目集。（核心为第一分量的集合）
- 从而减少了自动机的状态个数
问题
- 合并时产生归约-归约冲突
- 推迟错误的发现
特点
- 形式上与LR(1)相同
- 大小上与LR(0)/SLR相当
- 分析能力
- LR(0)<SLR<LALR(1)<LR(1)
二义性文法的LR分析
- 每个二义性文法都不是LR的
- 但某些类型的二义性文法在语言的描述和实现中很有用，更加简短、更加自然
在构造分析表时，若发生冲突时，则根据该文法本身的用途来化解冲突
LR分析中的错误处理
恐慌模式错误恢复
- 丢弃0个或多个输入符号，直到发现一个可能合法地跟在$A$之后的符号$a$为止
- 之后将$s_{i+1}=GOTO(s_i, A)$压入栈中，继续进行正常的语法分析
短语层次错误恢复
- 检查LR分析表中的每一个报错条目，并根据语言的使用方法来决定程序员所犯的何种错误最有可能引起这个语法错误
- 然后构造出适当的恢复过程
This post is licensed under CC BY 4.0 by the author.