自下而上 Bottom-up

从输入串开始，逐步进行归约，直到文法的开始符号。

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

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

算法：算符优先分析法，LR 分析法。

简述概念

基本思想：

• 采用 “移进-规约” 思想进行自下而上分析
• 用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换为（规约）该产生式的左部

核心问题：识别可归约串。

短语：

• 令 G 是一个文法，S 是文法的开始符号，假设 $$\alpha \beta \delta$$ 是文法 G 的一个句型，如果有 $$S \overset{*}{\Rightarrow} \alpha A \delta 且 A \overset{+}{\Rightarrow} \beta$$，则 $$\beta$$ 称是句型 $$\alpha \beta \delta$$ 相对于非终结符 A 的短语。
• 如果有 $$A \Rightarrow \beta$$，则称 $$\beta$$ 是句型 $$\alpha \beta \delta$$ 相对于规则 $$A \rightarrow \beta$$ 的直接短语。
• 一个句型的最左直接短语称为该句型的句柄。

分析过程描述：可以用 步骤、符号栈、输入串、所用产生式 四元组来描述。

算符优先法

定义

优先关系：

• 任何两个可能相继出现的终结符的终结符 a 与 b 可能三种优先关系：
  1. $$a \lessdot b$$，a 的优先级低于 b
  2. $$a \doteq b$$，a 的运算级等于 b
  3. $$a \gtrdot b$$，a 的运算级高于 b
• 算符优先关系与数学上的 < > = 不同：
  • $$+ \lessdot + $$ → 右边的加号比左边的加号优先级高，即算术右结合
  • $$a \lessdot b$$ 并不意味着 $$b \gtrdot a$$

算符文法：

• 如果一个文法的任一产生式的右部都不含两个相继的非终结符，即不含 ...QR... 形式的产生式右部，则我们称该文法为算符文法。
• 假设 G 是一个不含 $$\epsilon$$-产生式的算符文法。对于任何一对终结符 a、b，我们说：
  1. $$a \doteq b$$，当且仅当文法 G 中含有形如 $$P \rightarrow …ab…$$ 或 $$P \rightarrow …aQb…$$ 的产生式
  2. $$a \lessdot b$$，当且仅当 G 中含有形如 $$P \rightarrow …aR…$$ 的产生式，且有 $$R \overset{+}{\Rightarrow} b…$$ 或 $$R \overset{+}{\Rightarrow} Qb…$$
  3. $$a \gtrdot b$$，当且仅当 G 中含有形如 $$P \rightarrow …Rb…$$ 的产生式，且有 $$R \overset{+}{\Rightarrow} …a$$ 或 $$R \overset{+}{\Rightarrow} …aQ$$
• 如果一个算符文法 G 中的任何终结符对 $$(a, b)$$，至多只满足 $$a \doteq b$$、$$a \lessdot b$$ 和 $$a \gtrdot b$$ 这三个关系之一，则称 G 是一个算符优先文法。

构造优先关系表

算法：

1. 确定所有满足 $$\doteq$$ 的所有终结符对：
   • 通过检查 G 的每个产生式的候选式；
2. 确定满足关系 $$\lessdot$$ 和 $$\gtrdot$$ 的所有终结符对：
   • 先构造下面两个集合：
     • $$FIRSTVT(P) = {a | P \overset{+}{\Rightarrow} a… \or P \overset{+}{\Rightarrow} Qa…, a \in V_T \and Q \in V_N}$$
     • $$LASTVT(P) = {a | P \overset{+}{\Rightarrow} …a \or P \overset{+}{\Rightarrow} …aQ, a \in V_T \and Q \in V_N}$$
   • 检查每个产生式的候选式：
     • 假定一个产生式有一个候选式为 $$…aP…$$，那么，对于任何 $$b \in FIRSTVT(P)$$，我们都有 $$a \lessdot b​$$；
     • 假定一个产生式有一个候选式形为 $$…Pb…$$，那么，对于任何 $$a \in LASTVT(P)$$，有 $$a \gtrdot b$$。

构造集合 $$FIRSTVT(P)$$ 的算法：

• 反复使用下面的两条规则构造集合 $$FIRSTVT(P)$$：
  1. 若有产生式 $$P \rightarrow a…$$ 或 $$P \rightarrow Qa…$$，则 $$FIRSTVT(P) += {a}$$
  2. 若 $$\exist P \rightarrow Q…$$，则 $$FIRSTVT(P) += FIRSTVT(Q)$$
• 不断扫描，直到在一整次扫描中没有一个 $$FIRSTVT$$ 集合发生变化。

一个实现的伪代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

GLOBAL:
	STACK stack;
	BOOLEN array[ size(V_N) ][ size(V_T) ];
	
INIT:
	for prod in PROD; do
		a = prod.right.first_V_T()
		p = prod.left
		array[p][a] = true
		stack.push([p, a])
	done
		
MAIN:
	while not stack.empty(); do
		top = stack.pop()
		Q, a = top[0], top[1]
		for prod in PROD; do
			Qc = prod.right.first_symbol()
			P = prod.left
			
			if (Qc is Q) and (array[P][a] is false); then
				array[P][a] = true
				stack.push([P, a])
	        endif
		done
	done

其中 array[P][] 中所有为 true 的列就是 $$FIRSTVT(P)$$ 集合。

同理可以构造 $$LASTVT(P)$$ 集合：

• 反复使用下面的两条规则构造集合 $$LASTVT(P)$$：
  1. 若有产生式 $$P \rightarrow …b$$ 或 $$P \rightarrow …Qb$$，则 $$LASTVT(P) += {b}$$
  2. 若 $$\exist P \rightarrow …Q$$，则 $$LASTVT(P) += LASTVT(Q)$$
• 不断扫描，直到在一整次扫描中没有一个 $$LASTVT$$ 集合发生变化。

同样的也可以写出伪代码实现。

算符优先分析算法

概念：

• 素短语：至少含有一个终结符且不再含任何比它自身更小的素短语。
• 最左素短语：处于句型最左边的那个素短语。

最左素短语定理：

• 算符优先文法句型的一般形式为：

  $$\begin{align}sentence: &#N_1a_1N_2a_2…N_na_nN_{n+1}#,\ where: &\forall i, a_i \in V_T, N_i \in V_N \cap{\epsilon}\end{align}$$

• 则定理：一个满足以下条件的最左边的子串 $$N_ia_i…N_ja_j$$ 是最左素短语：

  1. $$a_{i-1} \lessdot a_i$$
  2. $$\forall s,t \in [i, j], a_s \doteq a_t$$
  3. $$a_j \gtrdot a_{j+1}$$

算符优先分析算法的伪代码描述：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

GLOBAL:
	STACK analysis;
	STACK input;
	
INIT:
	top = 1
	analysis.push('#')
	
MAIN:
	repeat
        a = input.pop()
        j = (analysis[top] in V_T) ? top : top-1
        
        # WHILE:
        # repeat until the precedence of top symbol is greater than the next symbol
        while precedence_greater(S[j], a); do
    
            # REPEAT:
            # find the terminal symbol position in stack where its precedence is less than the continous topper one
            repeat
                Q = analysis[j];
                j = (analysis[j-1] in V_T) ? j-1 : j-2;
            until precedence_less(analysis[j], Q)
    
            # `REDUCT` function is used to reduct list of symbol into a non-terminal symbol.
            N = REDUCT(analysis[j+1], S[top]);
            top = j+1
            analysis[top] = N
        done
        
        # IF:
        # if the next symbol is legal, push it into the stack
        if precedence_less(S[j], a) or precedence_equal(S[j], a); then
        	top++, S[top] = a;
        else ERROR; fi
    until a is '#';

LR 分析法

定义

规范规约：

• 假定 $$\alpha$$ 是文法 G 的一个句子且满足以下的条件，则我们称序列 $$\alpha_n, \alpha_{n-1}, …, \alpha_0$$ 是 $$\alpha$$ 的一个规范规约：
  1. $$\alpha_n = \alpha$$
  2. $$\alpha_0 = S$$
  3. $$\forall i, 0 \lt i \le n$$，$$\alpha_{i-1}$$ 是从 $$\alpha_i$$ 经把句柄替换成相应产生式的左部符号得到的。
• NOTICE：规范规约得到的树是语法树，但是算符优先分析方法得到的树不是语法树（算符优先分析方法不是规范规约）。

规范推导：

• 因为规范规约是最左规约，规范规约的逆过程就是最右推导。最右推导也称规范推导，由规范推导推出的句型又叫规范句型。

LR 文法：

• 对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定的，则这个文法就称为 LR 文法。
• 一个文法，如果能够用一个每步最多向前检查 k 个输入符号的 LR 分析器进行分析，则这个文法就称作 LR(k) 文法。
• LR 文法 $$\subset$$ 无二义文法。

LR 分析表：LR 分析器的核心是一张分析表：

• ACTION[s, a]：当前状态 s 面临输入符号 a 时，应该采取什么动作。比如：
  • s5：表示 shift，表示把当前文法符号移进入栈，并且将状态 5 压栈。
  • r4：表示 reduce，表示用第 4 个产生式规约，把产生式右部和状态弹出栈，把 GOTO[栈顶状态, 产生式左部] 和 产生式左部 非终结符移入栈。
• GOTO[s, X]：状态 s 面对文法符号 X 时，下一个状态是什么。
• acc：宣布分析成功，停止分析器工作。
• 空白：不允许出现的情况，出现了需要报错。

活前缀

字的前缀、活前缀：

• 字的前缀：字的任意首部。
• 活前缀：指规范句型的一个前缀，这种前缀不含句柄之后的任意符号。
  • 即：如果 $$\beta$$ 是 $$\alpha \beta \delta$$ 的句柄，如果 $$\alpha \beta = u_1 u_2 … u_r$$，则符号串 $$u_1 u_2 … u_i (1 \le i \le r)$$ 是 $$\alpha \beta \delta$$ 的一个活前缀。

拓广文法：

• 构造文法 G’，它包含了整个 G，并且引进不出现在 G 中的新的开始符号非终结符 S’、以及产生式 $$S’ \rightarrow S$$。

$$LR(0)$$ 项目：

• 在每个产生式右部添加一个圆点，表示我们在分析过程中看到了产生式的多大部分。
• $$A \rightarrow \alpha \cdot$$ 称为 “规约项目”
• $$S’ \rightarrow \alpha \cdot$$ 称为 “接受项目”（“接受项目” $$\subset$$ “规约项目”）
• $$A \rightarrow \alpha \cdot a \beta$$ 称为 “移进项目”
• $$A \rightarrow \alpha \cdot B \beta$$ 称为 “待约项目”

构造识别活前缀的 DFA：

• 构造识别文法所有活前缀的 NFA：

  1. ${\displaystyle State(i): X \rightarrow X_1 X_2 … X_{i-1} \cdot X_i…X_n}$

     ${\displaystyle State(j):X \rightarrow X_1 X_2…X_i \cdot X_{i+1} … X_n}$

     ${\displaystyle \Rightarrow f(State(i), X_i) = State(j) }$

  2. ${\displaystyle State(i): X \rightarrow \alpha \cdot A \beta}$

     $ State(j): A \rightarrow \cdot \gamma $

     $\Rightarrow f(State(i), \epsilon) = State(j) $

• 把该识别文法所有活前缀的 NFA 确定化为 DFA。

• PS：构成识别一个文法活前缀的 DFA 的项目集（状态）的全体称为文法的 LR(0) 项目集规范族。

构造的另一种方法（通过有效项目集）：

• 有效项目：项目 $$A \rightarrow \beta_1 \cdot \beta_2$$ 对活前缀 $$\alpha \beta_1$$ 是有效的，如果存在规范推导：$$S’ \overset{*}{\Rightarrow}_R \alpha A \omega \Rightarrow_R \alpha \beta_1 \beta_2 \omega $$

• 定理：若项目 $$A \rightarrow \alpha \cdot B \beta$$ 对于活前缀 $$\eta = \delta \alpha$$ 是有效的且 $$B \rightarrow \gamma$$ 是一个产生式，则项目 $$B \rightarrow \cdot \gamma$$ 对 $$\eta = \delta \alpha$$ 也是有效的。

• 构造项目集 I 的闭包 $$CLOSURE(I)$$：

  1. I 的任何项目都属于 $$CLOSURE(I)$$；
  2. 若 $$A \rightarrow \alpha \cdot B \beta$$ 属于，任意关于 B 的产生式 $$B \rightarrow \gamma$$，项目 $$B \rightarrow \cdot \gamma$$ 也属于 $$CLOSURE(I)$$；
  3. 重复执行上述两步直至 $$CLOSURE(I)$$ 不再增大为止。

• 状态转换函数 GO：对于 I 是一个项目集，X 是一个文法符号，则：

  $$\begin{align} GO(I, X) &= CLOSURE(J) \where\ J &= {A \rightarrow \alpha X \cdot \beta \mid (A \rightarrow \alpha \cdot X \beta) \in I} \end{align}$$

• 构造方法：

  1. $$State := {CLOSURE({S’ \rightarrow \cdot S})}$$

  2. 对于 State 中的每个项目集 I 和 G’ 中的每个文法符号 X：

     $$State += GO(I, X), where\ GO(I, X) \neq \varnothing \and GO(I, X) \notin State $$

  3. 重复第二步直到 State 不再增大。

LR(0) 分析表

假若一个文法 G 的拓展文法 G’ 的活前缀识别自动机中的每个状态（项目集）不存在以下的情况，则称 G 是一个 LR(0) 文法。

• 既含移进项目又含规约项目；
• 含有多个规约项目。

构造 LR(0) 分析表的算法：

1. 令每个项目集 $$I_k$$ 的下标 k 作为分析器的状态，包含项目 $$S’ \rightarrow \cdot S$$ 的集合 $$I_k$$ 的下标 k 为分析器的初始状态。
2. 构造分析表的 ACTION 子表：
   1. 若项目 $$A \rightarrow \alpha \cdot a \beta$$ 属于 $$I_k$$ 且 $$GO(I_k, a) = I_j$$，a 为终结符，则置 $$ACTION[k, a] = “sj”$$（动作移进，进入状态j）
   2. 若项目 $$A \rightarrow \alpha \cdot$$ 属于 $$I_k$$，那么，$$\forall a \in V_N, a \in FOLLOW(A)$$，置 $$ACTION[k, a] = “rj”$$（动作规约，使用第 j 个产生式 $$A \rightarrow \alpha$$）
   3. 若项目 $$S’ \rightarrow S \cdot$$ 属于 $$I_k$$，则置 $$ACTION[k, $] = “acc”$$（动作接受）
3. 构造分析表的 GOTO 子表：
   • 若 $$GO(I_k, A) = I_j$$，其中 A 为非终结符，则置 $$GOTO[k, A] = j$$（在第 k 个状态，栈顶是 A 符时，下一个状态是 j）
4. 分析表中凡不能用规则上述规则填入信息的空白格均填入 “报错标志”。

SLR(1) 分析法

LR(0) 中，一个项目集可能会包含多个规约项目，因为规约使用的规则必须向前看一个单词才可以选择规则进行规约，因此引入了 SLR(1) 分析法。其中 S 指 Simple，1 指最多向前看一个单词。

LR(0) 冲突解决办法：

• 假定一个 $$LR(0)$$ 规范族中含有如下的项目集 $$I = {X \rightarrow a \cdot b \beta, A \rightarrow \alpha \cdot, B \rightarrow \alpha \cdot}$$，其中：$$I \in S, FOLLOW(A) \cap FOLLOW(B) = \varnothing, b \notin FOLLOW(A) \cup FOLLOW(B)$$
• 当状态 I 面临输入符号 a 时，可以：
  1. 若 $$a = b$$，则移进
  2. 若 $$a \in FOLLOW(A)$$，用产生式 $$A \rightarrow \alpha$$ 进行规约；
  3. 若 $$a \in FOLLOW(B)$$，用产生式 $$B \rightarrow \alpha$$ 进行规约；
  4. 此外，报错。

更一般的：

• 假定一个 $$LR(0)$$ 规范族中含有如下的项目集 $$I = {A_1 \rightarrow \alpha \cdot a_1 \beta_1, A_2 \rightarrow \alpha \cdot a_2 \beta_2, …, A_m \rightarrow \alpha \cdot a_m \beta_m, B_1 \rightarrow \alpha \cdot, B_2 \rightarrow \alpha \cdot, …, B_n \rightarrow \alpha \cdot }$$，其中：$$I \in S; \forall k \le m, i,j \le n, FOLLOW(B_i) \cap FOLLOW(B_j) = \varnothing, b_k \notin FOLLOW(B_i) \cup FOLLOW(B_j)$$
• 当状态 I 面临输入符号 a 时，可以：
  1. 若 $$a \in {a_i \mid 0 < i \le m }$$，则移进
  2. 若 $$a \in FOLLOW(B_i), 0 < i \le n$$，用产生式 $$B_i \rightarrow \alpha$$ 进行规约；
  3. 此外，报错。

LASR(1) 分析法

可以构造一个比规范 LR 分析表更小的分析表。其中 LA 指 lookhead。

同心项目集：（没看懂）

对于一个拓广文法 G’，构造 LASR(1) 的分析表方法如下：

1. 构造 LR(1) 项目集规范族 $$C = {I_0, I_1, …, I_n}$$
2. 将同心集合并
3. 令 $$C’ = {J_0, …, J_m}$$ 为合并后项目集，构造 action 子表，如果有冲突则合并失败；
4. 。。。

LR 分析产生器 YACC

YACC (Yet Another Compiler Compiler)

LR 的变种：SALR(1)