语法分析

上下文无关文法

语法描述
- 上下文无关文法 CFG
- BNF
上下文无关文法
- 终结符号
- 非终结符号
- 开始符号
- 产生式
推导： $A\rightarrow\gamma$ $A \to γ$ ，则 $\alpha A\beta\Rightarrow \alpha\gamma\beta$ $α A β \Rightarrow α γ β$
- 最左推导： $\alpha$ 中不包含非终结符 $\overset{*}{\Rightarrow}_{\text{lm}}$
- 零步或多步推导： $\overset{*}{\Rightarrow}$
- 一步或多步推导： $\overset{+}{\Rightarrow}$
- 句型 $\alpha$ ： $S\overset{*}{\Rightarrow} \alpha$
- 句子：不包含非终结符号的句型
- 语言： $L(G)=\{\omega|S\overset{*}{\Rightarrow}\omega\}$

CFG 处理

二义性：如果一个文法可以为某个句子生成多棵语法分析数，则该文法二义
设计文法
- 消除二义性：无较好方法；优先级，结合性消除
- 消除左递归： $A\overset{+}{\Rightarrow} A\alpha$ $A \Rightarrow + A α$
  - 立即左递归： $A\rightarrow A\alpha$
- 提取左公因子
消除左递归
- 立即左递归的消除
  
  如果有 $A\rightarrow A\alpha_1|\cdots|A\alpha_m|\beta_1|\cdots|\beta_n$
  
  变换为 $A\rightarrow \beta_1 A'|\cdots|\beta_n A'$ 和 $A'\rightarrow \alpha_1 A'|\cdots|\alpha_m A'|\epsilon$
- 左递归消除算法
  
  输入：无环和 $\epsilon$ 产生式的文法 $G$ 输出：等价的无左递归的文法算法：非终结符号排序 $A_1,\cdots,A_n$
```
for i = 1 to n do{
  for j = i - 1 do {
    将 Ai -> Aj t 替换为 Ai -> s1 t | s2 t | ... | sk t, 其中 Aj -> s1 | s2 | ... | sk
  }
  消除 Ai 立即左递归
}
```
  问题：很难找到新文法和旧文法之间的对应关系，很难进行语义分析
预测分析法：当两个产生式具有相同前缀时无法预测
- 提取左公因子

自顶向下语法分析器

关键问题：确定对最左边的非终结符号应用哪个产生式
不能处理左递归
递归下降语法分析
- 每个非终结符对应一个过程，描述终结符的结构。程序执行从开始符号对应的过程开始
- 发现错误时，进行回溯
预测分析法
- $\text{FIRST}(\alpha)$ : 可以从 $\alpha$ 推到的首符号的集合
- $\text{FOLLOW}(A)$ : 可能在某些句型中紧跟在 $A$ 右边的终结符号的集合
  - 将结束标记 $ 放入 FOLLOW 中，按以下规则迭代直到不增长
    
    $A\rightarrow \alpha B\beta$ : FIRST( $\beta$ ) 中所有非 $\epsilon$ 符号加入 FOLLOW(B)
    
    如果 $A\rightarrow \alpha B$ 或 $A\rightarrow \alpha B\beta$ 且 FIRST( $\beta$ ) 包含 $\epsilon$ ，则 FOLLOW(A) 中所有符号加入 FOLLOW(B)
LL(1) 文法：从左到右，最左推导，向后看一个符号
- 定义：对文法的任意两个产生式 $A\rightarrow\alpha|\beta$ （保证唯一无二义）
  
  不存在终结符号 $a$ 使得 $\alpha$ 和 $\beta$ 都可以推导出以 $a$ 开头的串
  
  $\alpha$ 和 $\beta$ 最多只有一个可推导出空串
  
  如果 $\beta$ 可推导出空串，则 $\alpha$ 不能推导出以 FOLLOW(A) 中任意终结符号开头的串
- 等价定义： $\text{FIRST}(\alpha)\cap\text{FIRST}(\beta)=\emptyset$ , $\epsilon\in\text{FIRST}(\beta)\Leftrightarrow\text{FIRST}(\alpha)\cap\text{FOLLOW}(A)=\emptyset$
预测分析表

输入：文法 $G$ 输出：预测分析表 $M$ 算法：

对于每个产生式 $A\rightarrow \alpha$ ，将 $A\rightarrow \alpha,a\in \text{FIRST}(\alpha)$ 为终结符号加入 $M[A,a]$ 中；若 $\epsilon\in\text{FIRST}(\alpha)$ 则对 $\text{FOLLOW}(b)$ 中每个符号，将 $A\rightarrow \alpha$ 加入 $M[A,b]$ 中

最后所有空白条目填入 error
预测分析算法
- 输入：串 $\omega$ ，预测分析表 $M$
- 输出：正确输出最左推导，否则报错
- 初始化：输入缓冲区为 $\omega\$$，栈中为$ S$ $，ip 指向$ \omega$ 的第一个符号
  - 不断执行（栈顶符号 $X$ ，ip 指向当前输入符号 $a$ ）
  if $X$ == $a$ : $X$ 出栈，ip 向前移动
  
  else if $X$ 终结符号: error()
  
  else if M[ $X$ , $a$ ] 是报错条目: error()
  
  else if M[ $X$ , $a$ ] = $X\rightarrow Y_1Y_2\cdots Y_k$ : 输出产生式，弹出 $X$ ， $Y_i$ 入栈

自底向上语法分析器

$LR(0)\subset SLR(1)\subset LALR(1)\subset LR(1)$

移入（shift）：将下一个输入符号移入栈顶
归约（reduce）：将句柄归约为相应的非终结符
- 何时归约
- 归约到哪个非终结符
句柄：如果 $S\overset{*}{\Rightarrow}_{rm}\alpha A\omega\Rightarrow_{rm}\alpha\beta\omega$ ，则紧跟在 $\alpha$ 之后的 $\beta$ 是 $A\rightarrow\beta$ 的一个句柄
移入归约冲突
归约归约冲突
LR(k) 语法分析：最左扫描，反向构造最右推导， $k\leq 1$ ，表格驱动
LR(0) 项：文法的一个产生式加上在其中某处的一个点
- 增广文法：增加新开始符号 $S'$ ，产生式 $S'\rightarrow S$
- 项集闭包 CLOSURE：如果 $I$ $I$ 是文法 $G$ $G$ 的一个项集
  - $I$ 中各项加入 CLOSURE(I)
  - $A\rightarrow\alpha\cdot B\beta$ 在 CLOSURE(I) 中且 $B\rightarrow\gamma$ 是一个产生式， $B\rightarrow\cdot\gamma$ 不在 CLOSURE(I) 中，则迭代加入
- GOTO 函数：I 是项集，X 是文法符号，GOTO(I,X) 为 I 中所有形如 $[A\rightarrow\alpha\cdot X\beta]$ 的项所对应的 $[A\rightarrow\alpha X\cdot\beta]$ 项的闭包
计算 LR(0) 项集规范组的算法：从初始项集闭包开始，不算计算各种可能的后继，直到生成所有的项集
LR(0) 自动机
LR(0) 语法分析器
- ACTION: 状态，终结符号
- GOTO: GOTO[ $I_i$ ,A]= $I_j$ , 则 GOTO[ $i$ ,A]= $j$
- 格局: $(s_0s_1\cdots s_m,a_ia_{i+1}\cdots a_n\$ ) $，查询 ACTION[$ s_m $,$ a_i$]
LR(0) 分析表
- SLR(1) 语法分析表
  - $[A\rightarrow\alpha\cdot a\beta]$ 在 $I_i$ ，且 GOTO $(I_i,a)=I_j$ ，则 ACTION $[i,a]$ = $s_j$ （移入 j）
  - $[A\rightarrow\alpha\cdot]$ 在 $I_i$ 中，那么对 FOLLOW( $A$ ) 中所有 $a$ ，ACTION $[i,a]$ =按 $A\rightarrow\alpha$ 规约
  - 如果 $[S'\rightarrow S\cdot]$ 在 $I_i$ 中，则 ACTION[$i,$$] 设为接受
  - GOTO( $I_i,A$ )= $I_j$ , GOTO[i,A]=j
  - 如果 SLR 分析表没有冲突，则该文法为 SLR
- LR 方法：将期望向前看符号加入项中（LR(1)项集，状态太多）
- LALR 方法
LR(1) 项： $[A\rightarrow\alpha\cdot\beta,a]$ $[A \to α \cdot β, a]$ ， $a$ $a$ 为向前看符号
- 增广文法： $[S'\rightarrow S,\$ ]$
- 闭包：存在 $[A\rightarrow\alpha\cdot B\beta,a]$ ，则 $[B\rightarrow\cdot \theta,b],b=$ FIRST( $\beta a$ )
- GOTO: $[A\rightarrow\alpha\cdot X\beta,a]$ ，则 $[A\rightarrow\alpha X\cdot\beta,a]$
LR(1) GOTO 图
LR(1) 语法分析表
- $[A\rightarrow\alpha\cdot a\beta,b]$ 在项集中，且 GOTO( $I_i$ ,a)= $I_j$ ，那么 ACTION[ $i,a$ ]=移入 $j$
- $[A\rightarrow\alpha\cdot,a]$ 在项集中，ACTION[i,a]=按 $A\rightarrow\alpha$ 规约
- $[S'\rightarrow S,\$ ] $在项集中，ACTION[i,\$ ]=接受
LALR(1) 语法分析
- 原 LR(1) 中无冲突，则合并后只有归约冲突
- LALR(1) 分析表构造算法：对于 LR 每个核心，合并具有该核心的项集
- 处理正确输入时，LR 与 LALR 处理一样
- 处理错误输入时，LALR 会多处理一些归约

语法错误处理

LL 语法错误的处理：恐慌模式，短语层次恢复
- 恐慌模式：忽略输入中的一些符号直到出现由设计者选定的某个同步词法单元
  - 非终结符：FOLLOW(A) 中所有符号放入 A 的同步集合；高层次非终结符号加入较底层；FIRST(A) 加入 A 的同步集合；A 可以推导空串，将该产生式当做默认值
  - 终结符：栈顶终结符号匹配错误，可以直接弹出该符号，并且发出消息称已经插入
- 短语层次恢复：空白条目中插入错误处理例程
LR 语法错误处理
- 恐慌模式：假定当前试图规约到 A 但碰到了语法错误，因此设法扫描完包含语法错误的 A 的子串，假装找到了 A 的一个实例
- 短语层次的恢复

语法分析器生成工具

YACC/Bison
YACC 中的冲突处理
- 缺省处理方法
  - 规约/移入冲突：总是移入
  - 规约/规约冲突：选择列在前面的产生式
- 确定终结符号优先级
YACC 的错误恢复：error
bison: LALR(1)
bison + %glr-parser: LR(1)
ANTLR: LL(*)

Table of Contents

Table of Contents

上下文无关文法

CFG 处理

自顶向下语法分析器

自底向上语法分析器

语法错误处理

语法分析器生成工具