规范归约#

最右推导的逆过程：每步归约句型的句柄，得到规范归约序列 αₙ⇒αₙ₋₁⇒…⇒α₁=S。

🧮 例题（务必练熟，5 项都写）#

文法 E→E+T|T，T→T*F|F，F→(E)|i，句型 T+T*F：

• 短语：T、T*F、T+T*F
• 直接短语：T*F（也可含 T 由 T→…）
• 句柄：最左直接短语
• 素短语：T*F、i（含终结符且不含其他素短语）
• 最左素短语：T*F

补充例：句型 F↑P+T*(E+T) 中 —— 短语含 F↑P、T*(E+T) 等；直接短语 F↑P、E+T；句柄 F↑P；素短语 F↑P、E+T；最左素短语 F↑P。

算符文法 OG（Operator Grammar）#

文法 G 中没有形如 U→…VW…（两个非终结符相邻）的规则，则 G 是算符文法。

• 性质 1：任何句型都不含两个相邻的非终结符。
• 性质 2：若 Ab 或 bA 出现在句型中，则含 b 的短语必含 A。

算符优先关系（只看终结符之间，有次序）#

• a = b：存在规则 A→…ab… 或 A→…aBb…。
• a < b：存在规则 A→…aB…，且 B⇒⁺b… 或 B⇒⁺Cb…（a 优先级低于 b）。
• a > b：存在规则 A→…Bb…，且 B⇒⁺…a 或 B⇒⁺…aC（a 优先级高于 b）。

⚠️ <、=、> 表示归约的先后，与数学大小无关，且有方向（a<b 与 b<a 不同）。

算符优先文法 OPG（Operator Precedence Grammar）#

一个不含 ε 规则的 OG，若任意两个终结符间至多只有一种优先关系，则 G 是算符优先文法。

结论：OPG 是无二义的。

FIRSTVT / LASTVT#

• FIRSTVT(A) = { b | A⇒⁺b… 或 A⇒⁺Bb…, b∈V_T, B∈V_N } —— A 往下推导能露出的**第一个算符（终结符）**集合。
• LASTVT(A) = { a | A⇒⁺…a 或 A⇒⁺…aB, a∈V_T, B∈V_N } —— A 往下推导能露出的**最后一个算符（终结符）**集合。

构造关系表的规则#

1. 先算每个非终结符的 FIRSTVT、LASTVT。
2. 填优先关系：
   • A→…aB…：对 FIRSTVT(B) 中每个 b，置 a < b。
   • A→…Ba…：对 LASTVT(B) 中每个 b，置 b > a。
   • A→…ab… 或 A→…aBb…：置 a = b。
3. 补界符：
   • 对 FIRSTVT(S) 中每个 b，置 # < b；
   • 对 LASTVT(S) 中每个 a，置 a > #；
   • 置 # = #。

🧮 例（表达式文法）#

E→E+T|T，T→T*F|F，F→(E)|i

由此可填出 +<*、*>+、(=)、#<+/*/(/i、+/*/)/i># 等关系。

最左素短语的识别#

算符优先文法的句型可写成 # N₁a₁N₂a₂…NₙaₙNₙ₊₁ #。最左素短语是满足下式的最左子串：

1
aᵢ₋₁ < aᵢ ≐ aᵢ₊₁ ≐ … ≐ aⱼ₋₁ ≐ aⱼ > aⱼ₊₁

（即被 < 开头、> 结尾夹住的一段，中间是 =）。

分析算法（移进-归约）#

1. 栈初始化为 #。
2. 栈顶终结符与当前输入符比较：
   • < 或 =：移进输入符。
   • >：说明找到最左素短语的尾，向栈内找到相同优先关系的串归约（非终结符不影响识别，可用任意 N 代替）。
3. 两终结符间无优先关系 → 出错。
4. 读到 # 且栈中只剩 #N 时，接受。

🧮 分析 i+i# 过程#

目的#

用两个整数函数 f、g 代替优先矩阵，把存储从 (n+1)² 降到 2(n+1)。

定义#

• a=b ⟹ f(a)=g(b)
• a<b ⟹ f(a)<g(b)
• a>b ⟹ f(a)>g(b)

构造（Floyd 算法）#

1. 对每个终结符 a（含 #），令 f(a)=g(a)=1。
2. 逐行扫描优先矩阵，反复执行：
   • a>b 且 f(a)≤g(b) ⟹ f(a)=g(b)+1；
   • a<b 且 f(a)≥g(b) ⟹ g(b)=f(a)+1；
   • a=b 且 f(a)≠g(b) ⟹ 令二者取 max（相等）。
3. 迭代到收敛；若出现 >2n 的值，说明不存在优先函数。

性质#

• 优先函数不唯一（各值同加常数关系不变）。
• 存在优先关系的矩阵不一定存在优先函数。
• 缺点：无优先关系的空格（出错位置）用函数无法体现，而矩阵可置出错标记。