复习材料，不建议阅读

语法分析

确定的自顶向下分析思想

确定的自顶向下分析方法，是从文法的开始符号出发，考虑如何根据当前的输入符号（单词符号）唯一地确定选用哪个产生式替换相应非终结符以往下推导，或如何构造一棵相应的语法树。

1. 正规情况

文法右部始终由终结符号开始；相同左部时，右部是不同终结符号开始。

就可以直接根据当前输入符号决定产生式。

2. 一般情况

右部不全由终结符开始；相同左部时，右部是不同符号开始；没有空产生式。

问题 A：当输入符号是 $c$ 时，从 $S$ 出发选择 $Ap$ 还是 $Bq$ 能推出 $c$ 开头串？

3. 舍空产生式

有空产生式了。

问题B：如果有一个输入串 $W=abd$，推导过程：$S \Rightarrow aA \Rightarrow abAS \Rightarrow abS \Rightarrow abd$；在 $abAS \Rightarrow abS$ 的时候，$A$ 的产生式右部开始符号集都不包含 $d$ 只有 $ε$ 产生式，就可以认为 $d$ 的匹配实际依赖于 $A$ 后面的符号 $S$。

FIRST 集

FIRST(a) 是符号串 $a$ 可以推导出的所有串的首终结符号集合，称为 $a$ 的开始符号集或首符号集。

$FIRST(a)=\{\alpha |a \overset{*}{\Rightarrow} \alpha \beta,\alpha \in V_T ,\beta \in V^∗ \}$

$a$ 能推导出空的时候，$ε \in FIRST(a)$。

由此解决问题 A，求 $Ap$ 与 $Bq$ 的 $FIRST$ 集（且它们恰好不相交）就可以得出输入符号选择哪个产生式。

FOLLOW 集

$FOLLOW(A)$ 是在所有句型中紧跟在非终结符 $A$ 后面的终结符号集合。# 是输入串的结束符，也称输入串括号。

$FOLLOW(A)=\{a|S \overset{∗}{\Rightarrow} \dots Aa \dots,a \in V_T\}$

$S$ 能推导出 $\dots A$ 的时候，$\# \in FOLLOW(A)$。

结合 $SELECT$ 由此解决问题 B，$A、S$ 不能同时推导出空，替换仍是唯一确定的。

SELECT 集

$SELECT(A \to \alpha)$ 是产生式 $A \to \alpha$ 的选择符号集，表示当遇到这些输入符号时应该选择该产生式进行推导。

• 若 $ε \notin FIRST(\alpha)$，则 $SELECT(A \to \alpha) = FIRST(\alpha)$。
• 若 $ε \in FIRST(\alpha)$，则 $SELECT(A \to \alpha) = (FIRST(\alpha) - \{ε\}) \cup FOLLOW(A)$。

简单来说就是，$FIRST$ 不含空选 $FIRST$，含空就 $FIRST$ 去掉空并 $FOLLOW$。

$LL(1)$ 文法

概念

一个上下文无关文法是 $LL(1)$ 文法的充分必要条件是，对每个非终结符 $A$ 的两个不同产生式 $A \to \alpha$ 和 $A \to \beta$，满足：$SELECT(A \to \alpha) ∩ SELECT(A \to \beta) = ∅$。（同一左部 SELECT 集不相交）

其中 $\alpha$ 和 $\beta$ 不同时能推导出 $ε$。

判别

1. 求能推出 ε 的非终结符

建立标志位数组（“未定”/“是”/“否”），扫描产生式：

• 右部含终结符 → 标记”否”
• 右部为 ε → 标记”是”
• 重复扫描直到标志不再变化

2. 计算 FIRST 集

对每个符号 X：

• 若 $X \in V_T$，则 $FIRST(X) = \{X\}$
• 若 $X \in V_N$ 且 $X \to a\alpha$，则 $a \in FIRST(X)$
• 若 $X \in V_N$ 且 $X \to \varepsilon$，则 $\varepsilon \in FIRST(X)$
• 若 $X \in V_N$ 且 $X \to Y_1...Y_n$，则将 $FIRST(Y_i)$（除 $\varepsilon$）加入 $FIRST(X)$

3. 计算 FOLLOW 集

对每个非终结符 A：

• 开始符号 S：$\# \in FOLLOW(S)$
• 产生式 $A \to \alpha B\beta$：$FIRST(\beta)$（非空）加入 $FOLLOW(B)$
• 若 $\varepsilon \in FIRST(\beta)$：$FOLLOW(A)$ 加入 $FOLLOW(B)$

4. 计算 SELECT 集并判别

对每个产生式 $A \to \alpha$：

• 若 $\varepsilon \notin FIRST(\alpha)$，则 $SELECT(A \to \alpha) = FIRST(\alpha)$
• 若 $\varepsilon \in FIRST(\alpha)$，则 $SELECT(A \to \alpha) = (FIRST(\alpha) - \{\varepsilon\}) \cup FOLLOW(A)$

LL(1) 条件：对每个非终结符 A 的不同产生式，SELECT 集的交集为空集。

不确定的自顶向下分析思想

当文法不满足 LL(1) 时，不能用确定的自顶向下分析，但可用不确定的自顶向下分析（带回溯的自顶向下分析）。

引起回溯的原因是：在文法中当关于某个非终结符的产生式有多个候选时，而面临当前的输入符无法确定选用唯一的产生式，从而引起回溯。

回溯分析

1. 由于相同左部的产生式的右部 FIRST 集交集不为空而引起回溯

输入串 xay，先选 A → ab，xa 匹配后当前符 y 与 b 不匹配，回溯改选 A → a，匹配成功。

2. 由于相同左部非终结符的右部存在 ε 的产生式，且该非终结符的 FOLLOW 集中含有其他产生式右部 FIRST 集的元素

输入串 ab#，先选 S → aA，a 匹配后 A 选 A → cA，但 c 与 b 不匹配，回溯改选 A → ε，b 与 S 的 FOLLOW 集中的 b 匹配，匹配成功。

3. 由于文法含有左递归而引起回溯

输入串 baa#，先选 S → b，输入串未分析完，回溯改选 S → Sa，再选 S → b，得到 ba，但输入串还有 a#，继续回溯，最终得到 baa，匹配成功。

带回溯分析代价很高，效率很低，在实用编译程序中几乎不用。

某些非 LL(1)文法到 LL(1)文法的等价变换

左递归消除

文法中含有左递归时不能采用确定的自顶向下分析法。左递归分为直接左递归和间接左递归。

直接左递归消除

形如 $A \to A\alpha$ 的产生式称为直接左递归。

例：文法 $G_5$ 含有直接左递归：

该文法产生的语言 $L = \{ba^n | n \geq 0\}$。输入串 baaa# 应是该语言的句子，但用自顶向下分析时，当输入符为 b 时，为与 S 匹配则应选用 $S \to b$ 推导，但这样就推不出后边部分；而若用 $S \to Sa$ 推导则无法确定到什么时候才用 $S \to b$ 替换。

消除方法：把直接左递归改写为右递归。对文法 $G_5$ 可改写为：

改写后的文法和原文法产生的语言句子集都为 $\{ba^n | n \geq 0\}$，且改写后的文法为 LL(1) 文法。

一般情况下，假定关于 $A$ 的全部产生式是：

其中 $\beta_i$（$1 \leq i \leq m$）不以 $A$ 开头，消除直接左递归后改写为：

间接左递归消除

形如 $A \to B\alpha$，$B \to A\beta$ 等可以形成推导 $A \Rightarrow^+ A$ 的产生式称为间接左递归。

例：文法 $G_6$ 含有间接左递归：

若有输入串为 adbcbcbc#，当分析过程至 $A \Rightarrow aB \Rightarrow aAc \Rightarrow aBbc$ 时，$B$ 若用产生式 $B \to d$ 替换，则分析过程终止，不能推出 adbcbcbc#；而若选用产生式 $B \to Ac$，则会出现无法确定何时终止的情况。

消除方法：先通过产生式非终结符置换，将间接左递归变为直接左递归，然后再按消除直接左递归的方法处理。

以文法 $G_6$ 为例，用产生式 $A \to aB$ 和 $A \to Bb$ 的右部置换产生式 $B \to Ac$ 中的非终结符 $A$，得到左部为 $B$ 的产生式：

消除左递归后得：

再把原来其余的产生式 $A \to aB$ 和 $A \to Bb$ 加入，最终文法为：

该文法与 $G_6$ 等价，即它们产生相同的句子集。

消除一切左递归的算法

对文法中一切左递归的消除要求文法中不含回路，即无 $A \overset{+}{\Rightarrow} A$ 的推导。满足这个要求的充分条件是，文法中不包含形如 $A \to A$ 的有害规则和 $A$ 的空产生式。

算法步骤如下：

1. 把文法的所有非终结符按某一顺序排序，例如：$A_1, A_2, \dots, A_n$
2. FOR i = 1 TO n DO
   • FOR j = 1 TO i-1 DO
     • 若 $A_i$ 的所有产生式为 $A_i \to \delta_1 | \delta_2 | \dots | \delta_k$
     • 将其替换形如 $A_i \to A_j\gamma$ 的产生式得到 $A_i \to \delta_1' | \delta_2' | \dots | \delta_m'$
   • 消除 $A_i$ 中的一切直接左递归
3. 去掉无用产生式

例：按上述方法消除如下文法的一切左递归：

若非终结符排序为 $S, Q, R$：

• 左部为 $S$ 的产生式 $S \to Qc$ 无直接左递归
• 左部为 $Q$ 的产生式 $Q \to Rb | b$ 中右部不含 $S$
• 把产生式 $S \to Qc$ 的右部代入产生式 $R \to Sa$ 得：$R \to Qca | a$
• 再将产生式 $Q \to Rb | b$ 的右部代入得：$R \to Rbca | bca | a$
• 对产生式消除直接左递归得：

最终文法变为：

若非终结符的排序为 $R, Q, S$，则把产生式 $R \to Sa | a$ 代入产生式 $Q \to Rb | b$ 得：$Q \to Sab | ab | b$，再将此代入产生式 $S \to Qc$ 得：$S \to Sabc | abc | bc$。消除该产生式的左递归后，文法变为：

由于 $Q, R$ 为不可到达的非终结符，所以以 $Q, R$ 为左部及包含 $Q, R$ 的产生式应删除。

当非终结符的排序不同时，最后结果的产生式形式不同，但它们是等价的。

提取左公因子

若文法中含有形如 $A \to \alpha\beta_1 | \alpha\beta_2$ 的产生式，会导致相同左部产生式的 FIRST 集相交，不满足 LL(1) 条件。

可将产生式等价变换为：

写成一般形式：$A \to \alpha\beta_1 | \alpha\beta_2 | \dots | \alpha\beta_n | \gamma$（其中 $\gamma$ 不以 $\alpha$ 开头）

提取左公共因子后变为：

若 $\beta_i$ 中仍含有左公共因子，可再次提取，直到无左公共因子为止。

例 1：文法 $G_1$ 的产生式为

对产生式(1)、(2)提取左公共因子后得：

进一步变换为：

例 2：文法 $G_2$ 的产生式为

产生式(2)的右部以非终结符 $B$ 开始，左公共因子可能是隐式的。用产生式(3)、(4)的右部替换产生式(2)中的 $B$，可得：

提取产生式(1)、(2)的左公共因子得：

引进新非终结符 $A'$ 后得 $G_2$ 为：

注意事项：

1. 提取左公共因子后，可能使某些产生式变成无用产生式，需要对文法重新压缩。

2. 某些文法不能在有限步骤内提取完左公共因子。例如文法 $G_4$：

用产生式(2)、(3)的右部替换产生式(1)中的 $A$、$B$，再提取左公共因子，只能使文法的产生式越来越多，无限增加下去，而不能得到提取左公共因子的预期结果。

3. 一个文法提取了左公共因子后，只解决了相同左部产生式右部的 FIRST 集不相交的问题。当改写后的文法不含空产生式，且无左递归时，则改写后的文法是 LL(1) 文法；若还有空产生式时，则还需用 LL(1) 文法的判别方式进行判断才能确定是否为 LL(1) 文法。

LL(1) 分析的实现

递归下降分析

核心思想：把每个非终结符编写为一个递归函数，右部作为函数体。函数内根据当前输入符号查 SELECT 集选择产生式，递归调用对应函数。

构造方法：

1. 为每个非终结符 $A$ 编写函数 A()
2. 函数体结构：
   • 根据当前输入符号 lookahead 选择产生式
   • 对产生式右部的每个符号：
     • 终结符：匹配并读入下一符号
     • 非终结符：调用对应函数

示例：文法 $E \to E+T \mid T$，$T \to T*F \mid F$，$F \to (E) \mid \text{id}$

消除左递归后：$E \to TE'$，$E' \to +TE' \mid \varepsilon$，$T \to FT'$，$T' \to *FT' \mid \varepsilon$，$F \to (E) \mid \text{id}$

def E():
    T()
    E_prime()

def E_prime():
    if lookahead == '+':
        match('+')
        T()
        E_prime()
    # else: ε 产生式，什么都不做

def T():
    F()
    T_prime()

def T_prime():
    if lookahead == '*':
        match('*')
        F()
        T_prime()

def F():
    if lookahead == '(':
        match('(')
        E()
        match(')')
    elif lookahead == 'id':
        match('id')
    else:
        error()

def match(expected):
    global lookahead
    if lookahead == expected:
        lookahead = next_token()  # 读入下一符号
    else:
        error()

优点：代码结构清晰,易于理解和调试,可手工编写。

缺点：每个文法需单独编程,修改文法需重写代码。

表驱动分析（预测分析）

核心思想：构建预测分析表 $M[A, a]$ 存储”非终结符 $A$ 遇到输入符号 $a$ 时选择哪个产生式”,用栈模拟推导过程。

分析表构造：对每个产生式 $A \to \alpha$，对 $SELECT(A \to \alpha)$ 中的每个终结符 $a$，令 $M[A, a] = A \to \alpha$。

分析过程：

栈初始化: [#, S]  (# 是栈底, S 是开始符号)
输入指针: 指向输入串首符号

循环:
  X = 栈顶符号
  a = 当前输入符号

  if X == a == #:
      分析成功
  elif X == a:
      弹栈, 输入指针前移
  elif X 是终结符:
      报错 (栈顶终结符与输入不匹配)
  elif M[X, a] 为空:
      报错 (无对应产生式)
  else:  # M[X, a] = X → Y₁Y₂...Yₖ
      弹出 X
      将 Yₖ...Y₂Y₁ 逆序压栈 (若 Yᵢ = ε 则不压栈)

示例：文法 $E \to TE'$，$E' \to +TE' \mid \varepsilon$，$T \to FT'$，$T' \to *FT' \mid \varepsilon$，$F \to (E) \mid \text{id}$

分析表（部分）：

分析 id+id 的过程：

栈              输入          动作
[#, E]          id+id#       M[E,id]=E→TE', 弹E压E'T
[#, E', T]      id+id#       M[T,id]=T→FT', 弹T压T'F
[#, E', T', F]  id+id#       M[F,id]=F→id, 弹F压id
[#, E', T', id] id+id#       匹配id, 弹栈前移
[#, E', T']     +id#         M[T',+]=T'→ε, 弹T'
[#, E']         +id#         M[E',+]=E'→+TE', 弹E'压E'T+
[#, E', T, +]   +id#         匹配+, 弹栈前移
[#, E', T]      id#          M[T,id]=T→FT', 弹T压T'F
[#, E', T', F]  id#          M[F,id]=F→id, 弹F压id
[#, E', T', id] id#          匹配id, 弹栈前移
[#, E', T']     #            M[T',#]=T'→ε, 弹T'
[#, E']         #            M[E',#]=E'→ε, 弹E'
[#]             #            接受

伪代码实现：

def LL1_parse(input_string, parse_table):
    stack = ['#', start_symbol]
    input_ptr = 0
    input_string += '#'

    while True:
        X = stack[-1]  # 栈顶
        a = input_string[input_ptr]  # 当前输入

        if X == a == '#':
            return "接受"
        elif X == a:
            stack.pop()
            input_ptr += 1
        elif X in terminals:
            return f"错误: 期望 {X}, 得到 {a}"
        elif parse_table[X][a] is None:
            return f"错误: 无产生式 M[{X}, {a}]"
        else:
            production = parse_table[X][a]  # X → Y₁Y₂...Yₖ
            stack.pop()
            if production != 'ε':
                for symbol in reversed(production):
                    stack.append(symbol)

优点：通用性强,修改文法只需重新生成分析表,适合自动化工具生成。

缺点：需要预先构造分析表,不如递归下降直观。

LL(1) 分析中的错误处理

错误处理包含两个任务：报错（指出错误位置和类型）和错误恢复（使分析继续进行）。

错误发生的情况

LL(1) 分析中有两种错误情况：

1. 栈顶终结符与当前输入不匹配
2. 栈顶非终结符 $A$ 面临输入符号 $a$，但 $M[A, a]$ 为空

应急恢复 (Panic Mode)

核心思想：跳过输入符号直到遇到”同步符号”，使分析能继续。

同步符号选择：将 $FIRST(A)$ 或 $FOLLOW(A)$ 中的符号作为非终结符 $A$ 的同步符号。

恢复策略：

• 遇到 $FOLLOW(A)$ 中的符号：弹出栈顶的 $A$，继续分析
• 遇到 $FIRST(A)$ 中的符号：保留 $A$ 在栈顶，根据 $A$ 恢复分析

示例：若 $E$ 在栈顶，当前输入是 )，但 $M[E, )]$ 为空：

FOLLOW(E) = {), #}
策略: 跳过输入直到遇到 ) 或 #，弹出 E，继续分析

短语层恢复 (Phrase-Level)

核心思想：根据当前语法单位的上下文进行更精确的恢复。

流程：

1. 进入语法单位时：

   • 检查当前符号是否属于 $BeginSym$（通常取 $FIRST$ 集）
   • 若不属于，报错并跳过 $BeginSym \cup EndSym$ 之外的符号
   • 遇到 $BeginSym$ 中符号：重新分析该单位
   • 遇到 $EndSym$ 中符号：退出该单位

2. 离开语法单位时：

   • 检查当前符号是否属于 $EndSym$（基于 $FOLLOW$ 集）
   • 若不属于，报错并跳过 $BeginSym \cup EndSym$ 之外的符号

递归下降中的实现示例：

文法：$B \to [A] \mid (A)$，$A \to a$

def ParseB(EndSym):
    BeginSym = {'[', '('}  # FIRST(B)

    # 进入时检查
    if sym not in BeginSym:
        error("期望 [ 或 (")
        skip_until(BeginSym | EndSym)

    if sym == '[':
        match('[')
        ParseA(EndSym | {']'})  # 传入上下文相关的 EndSym
        match(']')
    else:
        match('(')
        ParseA(EndSym | {')'})  # 不同上下文使用不同参数
        match(')')

    # 离开时检查
    if sym not in EndSym:
        error("意外的符号")
        skip_until(BeginSym | EndSym)

关键点：不同上下文传入不同的 $EndSym$ 参数，体现”短语层”的含义。例如方括号内调用 ParseA 时传入 EndSym ∪ {]}，圆括号内传入 EndSym ∪ {)}。

两种方法对比

实际编译器（如 PL/0）通常采用短语层恢复，在进入和退出语法单位时调用检查函数，根据 $FIRST$ 和 $FOLLOW$ 集合进行错误检测和恢复。

自底向上优先分析

自底向上分析（也称 移进-归约分析）的基本思想是：对输入符号串自左向右扫描，将输入符逐个移入一个后进先出栈中，边移入边分析；一旦栈顶符号串形成某个句型的句柄或其他可归约串（对应某产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号串，称为一步归约。重复这一过程，直到栈中只剩文法的开始符号时分析成功，确认输入串是文法的句子。

自底向上分析是规范推导（最右推导）的逆过程，因此规范归约也称为最左归约。

例 5.1

设文法 $G[S]$ 为：

对输入串 $abbcde\#$ 进行分析：

该串的最右推导为：

归约过程（构造语法树的逆过程）如下表所示：

上述分析过程也是自底向上构造语法树的过程，每步归约对应构造一棵子树，最后当输入串结束时刚好构造出整个语法树（见图 5.1）。

关键问题

在上述移进-归约过程中，不能简单地在栈顶出现某产生式右部时就立即归约。例如表中第 (5) 步，栈顶符号串 $b$ 和 $Ab$ 分别是产生式 (2)、(3) 的右部，此时必须依据句柄来确定归约。

• 句柄：当前句型的某产生式的右部，且该右部在规范推导中最后被推出。
• 文法无二义性时，一个句子的规范推导唯一，规范归约也唯一。
• 因此，自底向上分析的关键问题是：在分析过程中如何确定句柄（或其他可归约串）。

本章和第 6 章分别介绍优先分析和 LR 类分析。本章介绍的优先分析技术，其可归约串是最左简单短语。

优先分析分类

优先分析法可分为简单优先分析法和算符优先分析法。

简单优先分析法

简单优先分析法按照文法符号之间的优先关系确定句柄，因此先给出任意两个文法符号之间的优先关系定义。

优先关系定义

文法中任意两个文法符号 $X$ 和 $Y$：

1. 相等（$X \doteq Y$）：$X$ 与 $Y$ 的优先性相等。

   $$X \doteq Y \text{ 当且仅当 } G \text{ 中存在产生式 } A \to \alpha X Y \beta$$

2. 小于（$X \lessdot Y$）：$X$ 的优先性比 $Y$ 小。

   $$X \lessdot Y \text{ 当且仅当 } G \text{ 中存在产生式 } A \to \alpha X B \beta \text{ 且 } B \Rightarrow^+ Y \gamma$$

3. 大于（$X \gtrdot Y$）：$X$ 的优先性比 $Y$ 大。

   $$X \gtrdot Y \text{ 当且仅当 } G \text{ 中存在产生式 } A \to \alpha B Y \beta \text{ 且 } B \Rightarrow^+ \gamma X$$

注意：这里的 $\lessdot$、$\gtrdot$ 与数学中的 $<$、$>$ 含义不同。

优先关系也可通过语法树的结构直观理解。当某两个符号同时出现在句柄中时，它们具有 $\doteq$ 关系；当左边的符号不在句柄中而右边的在句柄中时，左边 $\lessdot$ 右边；当左边的在句柄中而右边的不在时，左边 $\gtrdot$ 右边。

例 5.2

设有文法 $G[S]$：

求优先关系：

1. 相等关系 ($\doteq$)：由 $S \to bAb$、$A \to (B)$、$B \to Aa$ 可得：

   $$b \doteq A,\quad A \doteq b,\quad ( \doteq B,\quad A \doteq a$$

2. 小于关系 ($\lessdot$)：

   • 由 $S \to bAb$，且 $A$ 可推出以 $($ 或 $a$ 开头的串，可得：$b \lessdot ($、$b \lessdot a$
   • 由 $A \to (B$，且 $B$ 可推出以 $A$ 开头的串（$B \Rightarrow Aa$），可得：$( \lessdot A$

3. 大于关系 ($\gtrdot$)：

   • 由 $S \to bAb$，且 $A$ 可推出以 $a$ 结尾的串（$A \Rightarrow a$），可得：$a \gtrdot b$
   • 由 $B \to Aa$，且 $A$ 可推出以 $($ 开头的串…（依此类推）

上述关系可用优先关系矩阵表示。矩阵中元素为空时，表示该文法中任何句型都不会出现该符号对的相邻关系，在分析过程中若遇到则为出错，可断定输入串不是该文法的句子。

$\#$ 为句子括号符：$\# \lessdot X$ 且 $X \gtrdot \#$ 对所有与 $\#$ 相邻的符号 $X$ 成立。

例 5.2 文法的简单优先关系矩阵（表 5.2）：

简单优先文法的定义

若一个文法是简单优先文法，必须满足以下条件：

1. 唯一性：文法符号集中，任意两个符号之间最多只有一种优先关系成立。
2. 无二义性：文法中任意两个产生式没有相同的右部。

简单优先分析法的操作步骤

1. 移进：将输入符号串 $a_1 a_2 \dots a_n \#$ 依次存入符号栈，直到栈顶符号的优先性大于下一个待输入符号时为止。
2. 找句柄：以当前栈顶符号为句柄尾，由此向左在栈中找句柄的头符号。
3. 归约：由句柄在文法的产生式中查找右部为句柄的产生式。若找到，则用相应产生式的左部代替句柄；若找不到，则为出错，断定输入串不是该文法的句子。
4. 重复：重复上述 (1)、(2)、(3) 步，直到归约完输入符号串，栈中只剩文法的开始符号为止。

直观算符优先分析法

在处理表达式求值过程中，运算次序是先乘除后加减，即乘除运算的优先级高于加减运算的优先级，且同级运算服从左结合（或右结合，如幂运算）。这说明运算的次序只与运算符有关，而与运算对象无关。

因此，直观算符优先分析法的关键只涉及优先级问题和同一优先级的结合性质。算符间的优先关系表示法与简单优先关系类似，规定如下：

• $X \lessdot Y$：$X$ 的优先性低于 $Y$
• $X \doteq Y$：$X$ 的优先性等于 $Y$
• $X \gtrdot Y$：$X$ 的优先性高于 $Y$

注意：这三个关系与数学中的 $<$、$=$、$>$ 不同，它们是有序的。若有 $a \lessdot b$，不一定有 $b \gtrdot a$ 成立；若有 $a \doteq b$，也不一定具有对称性。例如，通常表达式中运算符的优先关系有 $+ \gtrdot +$（左结合），但没有 $+ \lessdot +$；有 $( \doteq )$，但没有 $) \doteq ($。

表达式的二义性文法

该文法是二义的，但可以用算符优先分析法进行分析。运算对象（终结符 $i$）的优先级最高。其他运算符按计算顺序规定优先级和结合性如下：

1. 幂运算符 $\uparrow$：优先级最高，遵循右结合。相当于 $\lessdot$ 关系。 例如 $i \uparrow i \uparrow i$ 等价于 $i \uparrow (i \uparrow i)$，归约时从右向左进行。

2. 乘除运算符 $*$ 和 $/$：优先级低于 $\uparrow$，服从左结合。 优先关系为：$* \gtrdot *$、$* \gtrdot /$、$/ \gtrdot *$、$/ \gtrdot /$、$* \lessdot \uparrow$、$/ \lessdot \uparrow$。

3. 加减运算符 $+$ 和 $-$：优先级最低，服从左结合。 优先关系为：$+ \gtrdot +$、$+ \gtrdot -$、$- \gtrdot +$、$- \gtrdot -$，且 $+ \lessdot *$、$+ \lessdot /$、$- \lessdot *$、$- \lessdot /$。

4. 括号 $($ 和 $)$：

   • 左括号 $($ 的优先性小于括号内的运算符，大于括号外的运算符
   • 右括号 $)$ 的优先性大于括号外的运算符，小于括号内的运算符
   • 内括号的优先性大于外括号

5. 句子括号 $\#$：与它相邻的任何运算符的优先性都比它大，即 $\# \lessdot X$ 且 $X \gtrdot \#$ 对所有与 $\#$ 相邻的算符 $X$ 成立。

算符优先分析法的理论基础

算符文法

定义 5.1 设有文法 $G$，如果 $G$ 中没有形如 $A \to \alpha B C \beta$ 的产生式，其中 $B$、$C$ 为非终结符，则称 $G$ 为算符文法（Operator Grammar），也称 OG 文法。

算符文法的特点是：任何产生式的右部都不包含两个相邻的非终结符。

性质 1 在算符文法中，任何句型都不包含两个相邻的非终结符。

性质 2 如果 $bA$（或 $Ab$）出现在算符文法的句型 $\gamma$ 中，其中 $A \in V_N$，$b \in V_T$，则任何包含 $b$（或 $A$）的短语必含有 $A$（或 $b$）。

算符优先关系定义

定义 5.2 设 $G$ 是一个不含 $\varepsilon$ 产生式的算符文法，$a$、$b$ 是任意两个终结符，$A$、$B$、$C$ 是非终结符。算符优先关系 $\doteq$、$\lessdot$、$\gtrdot$ 定义如下：

1. 相等（$a \doteq b$）：当且仅当 $G$ 中含有形如 $A \to \alpha a B b \beta$ 或 $A \to \alpha a b \beta$ 的产生式。

   即 $a$ 与 $b$ 在同一句柄中同时归约。

2. 小于（$a \lessdot b$）：当且仅当 $G$ 中含有形如 $A \to \alpha a B \beta$ 的产生式，且 $B \Rightarrow^+ b \gamma$。

   即 $a$ 不在句柄中而 $b$ 在句柄中，$a$ 先归约。

3. 大于（$a \gtrdot b$）：当且仅当 $G$ 中含有形如 $A \to \alpha B b \beta$ 的产生式，且 $B \Rightarrow^+ \gamma a$。

   即 $a$ 在句柄中而 $b$ 不在，$a$ 后归约。

这三种优先关系也可由语法树的结构直观说明：

• $\doteq$：如图 5.3(a)，$a$ 和 $b$ 在同一句柄中同时归约，优先级相同。
• $\lessdot$：如图 5.3(b)，$a$ 不在句柄中而 $b$ 在句柄中，$a$ 的优先级低于 $b$。
• $\gtrdot$：如图 5.3(c)，$a$ 在句柄中而 $b$ 不在，$a$ 的优先级高于 $b$。

注意：算符之间的优先关系是有序的，允许 $a \lessdot b$ 和 $b \gtrdot a$ 同时存在，但不允许同一对终结符之间同时存在两种不同的关系（如不允许 $a \lessdot b$ 和 $a \gtrdot b$ 同时成立）。

算符优先文法的定义

定义 5.3 设 $G$ 是一个不含 $\varepsilon$ 产生式的算符文法。如果对于任意一对终结符 $(a, b)$ 之间至多只有 $\doteq$、$\lessdot$、$\gtrdot$ 三种关系中的一种成立，则称 $G$ 是一个算符优先文法（Operator Precedence Grammar），即 OPG 文法。

算符优先文法一定是算符文法，但算符文法不一定是算符优先文法。

算符优先关系表的构造

FIRSTVT 和 LASTVT 集合

定义：

• $FIRSTVT(B) = \{a \mid B \Rightarrow^+ a\alpha, a \in V_T, \alpha \in V^*\}$（取头）

• $LASTVT(B) = \{a \mid B \Rightarrow^+ \alpha a, a \in V_T, \alpha \in V^*\}$（取尾）

优先关系的计算方法

1. $\doteq$ 关系：直接查看产生式的右部，对如下形式的产生式，有 $a \doteq b$ 成立：
   • $A \to \alpha a B b \beta$
   • $A \to \alpha a b \beta$

2. $\lessdot$ 关系：求出每个非终结符 $B$ 的 $FIRSTVT(B)$，观察如下形式的产生式：

   • $A \to \alpha a B \beta$

   对每一 $b \in FIRSTVT(B)$，有 $a \lessdot b$ 成立。

3. $\gtrdot$ 关系：求出每个非终结符 $B$ 的 $LASTVT(B)$，观察如下形式的产生式：

   • $A \to \alpha B b \beta$

   对每一 $a \in LASTVT(B)$，有 $a \gtrdot b$ 成立。

例 5.3

表达式文法如下：

计算 FIRSTVT 和 LASTVT 集合：

计算优先关系：

1. $\doteq$ 关系：由产生式 (0) 和 (6) 可得 $\# \doteq \#$、$i \doteq i$
2. $\lessdot$ 关系：
   • 由 $\# E$，$\# \lessdot FIRSTVT(E)$
   • 由 $E + T$，$+ \lessdot FIRSTVT(T)$
   • 由 $T * F$，$* \lessdot FIRSTVT(F)$
   • 由 $F \uparrow F$，$\uparrow \lessdot FIRSTVT(F)$
   • 由 $P (E$，$( \lessdot FIRSTVT(E)$
3. $\gtrdot$ 关系：
   • 由 $E \#$，$LASTVT(E) \gtrdot \#$
   • 由 $E +$，$LASTVT(E) \gtrdot +$
   • 由 $T *$，$LASTVT(T) \gtrdot *$
   • 由 $F \uparrow$，$LASTVT(F) \gtrdot \uparrow$
   • 由 $E)$，$LASTVT(E) \gtrdot )$