超边替换文法的预测自顶向下解析

### 超边替换文法的预测自顶向下解析 #### 1. 解析示例与规则合并 在解析过程中，存在合并规则，它对应解析器中的显式赋值。例如在规则 p3 中，从 A - 配置文件可知，标识符 x1 和 x3 绑定到配置文件节点，x2 和 x4 由相应过程设置。由于 x2 和 x4 之前未被绑定，所以不会产生冲突。 解析图表示 aabbcc 的过程跟踪如下： |行号|动作|标识符到节点的绑定结果| | ---- | ---- | ---- | |2|识别起始节点|...| |3|边匹配 a(n1, n2)，对应 a(1, 2)|n1 绑定到 1，n2 绑定到 2| |4|调用过程 A|部分参数未绑定| |5|选择规则 p2|因为找到边 a(2, 3)| |7|再次调用过程 A|部分参数未绑定| |8|选择规则 p3|因为没有从节点 3 出发的 a - 边| |9|显式赋值|...| |10|边匹配|节点 4 赋值给 x2 和 n3| |12|匹配边 b(4, 5)|...| |13|匹配边 c(6, 7)|...| #### 2. 预测自顶向下可解析性 - **解析过程原理**：PTD 解析器为输入图创建最左推导（如果存在）。在每个时间点，解析器已消耗输入图 H 的子图 H′，表示为终端子句 α（α• = H′）。当前过程调用栈中未展开或未匹配的边对应图子句 x，使得 z L⇒∗αx，x 表示剩余目标，解析将继续构建 αx L⇒∗αβ，使得 (αβ)• = H。 - **边的处理情况** - **非终结边（e 是非终结符）**：解析器调用对应 e 的解析过程，使用配置文件节点 P = ˙α ∩˙e。对于给定的配置文件节点集 P，Rest(e, P, r) 表示所有可能的剩余图集合。解析过程必须选择满足 β• ∈ Rest(e, P, r) 的规则 r。为了实际选择规则，需要满足以下两个条件： - **条件 1**：Rest(e, P, r) ⊆ Sel(e, P, r) 对于每个 e、P 和每个规则 r 成立。 - **条件 2**：Sel(e, P, r) ∩ Sel(e, P, r′) = ∅ 对于每个 e、P 和规则 r ≠ r′ 成立。 - **终结边（e 是终结符）**：解析器选择一个未匹配的边，必须考虑边的标签和 ˙α 已确定的节点。PTD 可解析的 HR 文法必须满足条件 3：对于所有推导 z L⇒∗αey L⇒∗αeβ 和 z L⇒∗αe′y′，存在推导 y′ L⇒∗β′ 使得 H = (αe′β′)•。 #### 3. 定义与性质 - **定义**：如果可以为规则添加条件（可在线性时间内判定），使得规则选择满足条件 1、2 和 3，则 HR 文法称为预测自顶向下（PTD）可解析。 - **引理**：对于每个无无用规则的 PTD 可解析 HR 文法，存在常数 k，使得对于每个句柄子句 h，如果 h L⇒k v，则 v• 至少包含一个不在 h• 中的节点或终结边。这表明具有左递归规则的 HR 文法不是 PTD 可解析的。 - **复杂度定理** - **时间复杂度**：PTD 解析器的时间复杂度为 O(n²)，空间复杂度为 O(n)，其中 n 是输入图的大小。如果可以在常数时间内选择替代规则，时间复杂度实际上是线性的。 - **与