shesl-meow
博客 标签 分类 笔记
游戏
2048
shesl-meow

自上而下分析 Top-down

从文法的开始符号开始，反复使用各种产生式，寻找 “匹配” 的推导。

  • 推导：根据文法的产生式规则，把串中出现的产生式的左部符号替换成右部

从树的根节点开始，构造语法树。

算法：递归下降法，预测分析程序。

基本问题

面临的两个基本问题

  • 当面临多个候选式时的回溯问题。
  • 文法的左递归问题。

左递归的消除

一个文法消除左递归的条件：

  • 不含以 $$\epsilon$$ 为右部的左产生式
  • 不含回路，即不含推导 $$P \Rightarrow P$$

直接左递归的消除：

  • 产生式的直接左递归：$$P \rightarrow P\alpha | \beta, \beta 不以 \beta 开头$$
  • 转变成右递归文法：
    • $$P \rightarrow \beta P’$$
    • $$P’ \rightarrow \alpha P’ | \epsilon$$
  • 推广：$$P \rightarrow P\alpha_1 | P\alpha_2 | …| P\alpha_m| \beta_1 | \beta_2 | … | \beta_n$$（每个 $$\alpha$$ 都不等于 $$\epsilon$$，每个 $$\beta$$ 都不以 P 开头）
    • $$P \rightarrow \beta_1 P’ | \beta_2 P‘ |…|\beta_n P’$$
    • $$P’ \rightarrow P’ \alpha_1 | P’ \alpha_2 | … | P’ \alpha_m$$

间接左递归的消除：

  • 算法：
    1. 把文法 G 中的所有非终结符按任意一种顺序排列 $$P_1, P_2, …, P_n$$；按此顺序执行：
    2. 把 $$P_i$$ 的规则改造 成 $$P_i \rightarrow a…|P_{i+1}…|P_{i+2}…|…|P_{i+k}…$$，即 $$P_i$$ 的推导式，只能以下标大于 $$i$$ 的开头。并消除 $$P_i$$ 的直接左递归。
    3. 化简 2 所得到的文法，去除从开始符号出发无法到达的非终结符的产生规则。

回溯的消除

回溯消除的结果：

  • 对于文法的任何非终结符，当他要去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应该是确信无疑的。

引入概念：

  • FIRST 集合：
    • 令 G 是一个不含左递归的文法，对于 G 中的每个非终结符 $$\alpha$$ 定义它的终结首符号集 $$FIRST(\alpha)$$ 为：
      • $$FISRT(\alpha) = {a | \alpha \Rightarrow a…, a \in V_T}$$
      • 特别的，若 $$\alpha \Rightarrow \epsilon$$，则规定 $$\epsilon \in FIRST(\alpha)$$
    • 则：没有回溯 $$\Leftrightarrow$$ $$ A \rightarrow \alpha_i|\alpha_j, FIRST(\alpha_i) \cap FIRST(\alpha_j) = \varnothing $$
  • FOLLOW 集合：
    • 假定 S 是文法的开始符号，对于 G 的任何非终结符 A，我们定义 A 的 FOLLOW 集合：
      • $$FOLLOW(A) = {a | S \Rightarrow …Aa…., a \in V_T}$$
      • 特别的，若 $$S \Rightarrow …A$$，则规定 $$ $ \in FOLLOW(A) $$

算法：

  • 提取左公共因子：
    • 假定 A 的规则是：$$A \rightarrow \delta \beta_1 | \delta \beta_2 | … | \delta \beta_n | \gamma_1 | \gamma_2 | … | \gamma_m$$（其中每个 $$\gamma$$ 都不以 $$\delta$$ 开头）
    • 那么可以将这些规则改写成：
      • $$A \rightarrow \delta A’ | \gamma_1 | \gamma_2 | … | \gamma_m $$
      • $$A’ \rightarrow \beta_1 | \beta_2 | … | \beta_n$$

LL(1) 文法

一个文法 G 满足下面条件，称作该文法 G 为 LL(1) 文法。

  1. 文法不含左递归
  2. 对于文法中每一个非终结符 A 的各个产生式的候选首符集两两不相交。
    • 即：$$ A \rightarrow \alpha_i|\alpha_j, FIRST(\alpha_i) \cap FIRST(\alpha_j) = \varnothing $$
  3. 对文法中的每一个非终结符，若存在某个候选首符集包含 $$\epsilon$$，则：$$FIRST(\alpha_i) \cup FOLLOW(A) = \varnothing, i=1,2,…,n$$

其中第一个 L 表示从左到右扫描输入串，第二个 L 表示分析过程是一个最左推导，1 表示每次只需前进一个符号。

LL(1) 分析法

对于LL(1) 文法，可以对其输入串进行有效的无回溯自上而下分析：

  • 假设要用非终结符 A 进行匹配，面临的输入符号为 a，A 的所有产生式为：$$A \rightarrow \alpha_1 | \alpha_2 | … | \alpha_n$$
    1. 若 $$a \in FIRST(\alpha_i)$$，则指派 $$\alpha_i$$ 执行匹配任务；
    2. 若 $$\forall i, a \notin FIRST(\alpha_i). \exist i, \epsilon \in FIRST(\alpha_i) 且 a \in FOLLOW(\alpha_i)$$，则让 A 与 $$\epsilon$$ 自动匹配。
    3. 否则，a 的出现是一种语法错误。

FIRST 和 FOLLOW 集

$$FISRT(\alpha) = {a | \alpha \Rightarrow a…, a \in V_T}$$

构造 $$FIRST(\alpha)$$：

  1. 对于 $$\alpha = X, X \in V_T \cup V_N$$
    • 对于每一个 $$X \in V_T \cup V_N$$，连续使用下面规则，直至 FIRST 集合不再增大为止：
      1. 若 $$X \in V_T$$，则 $$FIRST(X) = {X}$$
      2. 若 $$X \in V_N, \exist X \rightarrow a…, a \in V_T$$，则 $$FIRST(X) += {a}$$
      3. 若 $$ \exist X \rightarrow Y_1Y_2..Yi…Y_k $$，其中 $$Y_1, Y_2,…, Y_{i-1}$$ 都是非终结符
        • 若 $$\forall j, 1 \le j \le i-1, \epsilon \in FIRST(Y_j)$$，则 $$FIRST(X) += FIRST(Y_i) - {\epsilon}$$
        • 若 $$\forall j, 1 \le j \le k, \epsilon \in FIRST(Y_j)$$，则 $$FIRST(X) += {\epsilon}$$
    • NOTICE：任何一个符号的 FIRST 集合发生了变化，都要重新开始扫描。直到一次扫描过程中，FIRST 集合没有任何发生变化。
  2. 对于 $$\alpha = X_1 X_2 … X_n$$
    1. 置 $$FIRST(\alpha) = FIRST(X_1) - {\epsilon}$$
    2. 若 $$\forall j, 1 \le j \le i-1, \epsilon \in FIRST(X_j)$$，则 $$FIRST(X) += FIRST(X_i) - {\epsilon}$$
    3. 若 $$\forall j, 1 \le j \le k, \epsilon \in FIRST(X_j)$$，则 $$FIRST(X) += {\epsilon}$$

$$FOLLOW(A) = {a | S \Rightarrow …Aa…., a \in V_T}$$

构造 $$FOLLOW(\alpha)$$ ：

  • 连续使用下面的规则，直到 FOLLOW 不再增大为止：
    1. 对于文法的开始符号，置 $$ $ $$ 于 FOLLOW(S) 中；
    2. 若 $$\exist A \rightarrow \alpha B \beta, FOLLOW(B) += FIRST(\beta)-{\epsilon}$$
    3. 若 $$(\exist A \rightarrow \alpha B) \or (\exist A \rightarrow \alpha B \beta \and \epsilon \in FIRST(\beta))$$，则 $$FOLLOW(B) += FOLLOW(A)$$

递归下降分析器

分析程序由一组子程序组成，对每一个语法单位构造一个相应的子程序，识别对应的语法单位。通过子程序间的相互调用实现对输入串的识别。

定义全局过程和变量：

  • ADVANCE：把输入串指示器 IP，指向下一个输入符号，即读入一个单词符号
  • ERROR：出错处理子程序
  • SYM：IP 当前所指向的输入符号

子程序设计：每个非终结符都有对应的子程序定义，在分析的过程中，当需要从某个非终结符出发进行展开（推导）时，就调用这个非终结符对应的子程序。

以 $$A \rightarrow TE | BC | \epsilon $$ 为例，其递归下降子程序为：

1
2
3
4
5
6
7
8
9

PROCEDURE A;
BEGIN
	if SYM in FIRST(TE) then
		BEGIN T; E; END
    else if SYM in FIRST(BC) then
    	BEGIN B; C; END
    else if SYM not in FOLLOW(A) then
    	ERROR
END;

PostScript: 扩充巴科斯范式。

在元符号 $$\rightarrow$$ 或 ::= 和 | 的基础上，扩充以下几个元语言符号：

  • 用 $${\alpha}$$ 表示闭包运算 $$a^*$$；
  • 用 $${\alpha}_0^n$$ 表示可任意重复 0 次到 n 次；
  • $$[\alpha] \Leftrightarrow {\alpha}_0^1 \Leftrightarrow \alpha | \epsilon$$

JavaCC 工作流程入下：

D:/program/git/Note/%E5%AD%A6%E6%A0%A1%E8%AF%BE%E7%A8%8B/%E7%BC%96%E8%AF%91%E5%8E%9F%E7%90%86/2.%E8%AF%AD%E6%B3%95%E5%88%86%E6%9E%90/javacc-flow.svg

预测分析程序

分析流程

预测分析程序的构成：

  • 总控程序：根据现行栈顶符号和当前输入符号，执行动作
  • 分析表 $$M[A, a]$$ 矩阵：$$A \in V_N, a \in V_T \cap {end}$$
  • 分析栈 STACK：用于存放文法符号

预测分析过程：总控程序根据当前栈顶符号 X 和输入符号 a，执行下列三个动作之一：

  1. 若 $$X = a = end ​$$，则宣布分析成功，停止分析；
  2. 若 $$X = a \neq end $$，则把 X 从 STACK 栈顶取出，让 a 指向下一个输入符号；
  3. 若 $$X \neq a $$ 且 X 是一个非终结符，则查看分析表 M：
    • 若 $$M[X, a]$$ 中存放着关于 X 的一个产生式，把 X 出栈，把产生式的右部符号串按反序推进 STACK 栈中；
    • 若 $$M[X, a]$$ 中未存放任何标记或 “出错标志” 的话，则调用出发诊察程序 ERROR。
  4. 若 $$X \neq a$$ 且 X 是一个终结符，则调用错误诊察程序 ERROR。

分析表的构造

首先需要计算每个非终结符 X 的 $$FIRST(X)$$ 和 $$FOLLOW(X)$$ 集合。

构造 G 的分析表 $$M[A, a]$$，即确定每个产生式 $$A \rightarrow \alpha$$ 在表中的位置：

  1. 对文法 G 的每个产生式执行第 2 步和第 3 步：
  2. $$\forall a \in FIRST(\alpha), M[A,a] = “A \rightarrow \alpha”$$
  3. 若 $$\epsilon \in FIRST(\alpha)$$，则 $$\forall b \in FOLLOW(A), M[A,b] = A \rightarrow \alpha$$

可以证明：一个文法 G 的预测分析表 M 不含多重定义入口 $$\Leftrightarrow$$ 该文法为 LL(1) 的 $$\Leftrightarrow$$ 该文法无二义性。

PostScript：尽管构造的文法可能是二义的，但是可以通过手动消除的方式取消二义性，比如：if stat else if stat else stat