下推自动机和解析

---

解析用于使用语法的产生规则派生字符串。它用于检查字符串的可接受性。编译器用于检查字符串语法是否正确。解析器获取输入并构建解析树。

解析器可以有两种类型 -

• 自顶向下解析器- 自顶向下解析从顶部开始符号开始，并使用解析树派生字符串。

• 自下而上的解析器- 自下而上的解析从字符串的底部开始，并使用解析树到达起始符号。

自顶向下解析器的设计

对于自上而下的解析，PDA 有以下四种类型的转换 -

• 将产生式左侧的非终结符弹出到堆栈顶部，并推送其右侧字符串。

• 如果堆栈顶部符号与正在读取的输入符号匹配，则将其弹出。

• 将起始符号“S”推入堆栈。

• 如果输入字符串已完全读取并且堆栈为空，则转到最终状态“F”。

例子

为语法 G 的表达式“x+y*z”设计一个自上而下的解析器，具有以下产生规则 -

P: S → S+X | X, X → X*Y | Y，Y→（S）| ID

解决方案

如果 PDA 为 (Q, Σ, S, δ, q ₀ , I, F)，则自上而下的解析为 -

(x+y*z, I) ⊢(x +y*z, SI) ⊢ (x+y*z, S+XI) ⊢(x+y*z, X+XI)

⊢(x+y*z, Y+XI) ⊢(x+y*z, x+XI) ⊢(+y*z, +XI) ⊢ (y*z, XI)

⊢(y*z, X*YI) ⊢(y*z, y*YI) ⊢(*z,*YI) ⊢(z, YI) ⊢(z, zI) ⊢(ε, I)

自底向上解析器的设计

对于自下而上的解析，PDA 有以下四种类型的转换 -

• 将当前输入符号压入堆栈。

• 将堆栈顶部的产生式的右侧替换为其左侧。

• 如果栈顶元素与当前输入符号匹配，则将其弹出。

• 如果输入字符串已完全读取并且仅当起始符号“S”保留在堆栈中时，将其弹出并进入最终状态“F”。

例子

为语法 G 的表达式“x+y*z”设计一个自上而下的解析器，具有以下产生规则 -

P: S → S+X | X, X → X*Y | Y，Y→（S）| ID

解决方案

如果 PDA 为 (Q, Σ, S, δ, q ₀ , I, F)，则自下而上的解析为 -

(x+y*z, I) ⊢ (+y*z, xI) ⊢ (+y*z, YI) ⊢ (+y*z, XI) ⊢ (+y*z, SI)

⊢(y*z, +SI) ⊢ (*z, y+SI) ⊢ (*z, Y+SI) ⊢ (*z, X+SI) ⊢ (z, *X+SI)

⊢ (ε, z*X+SI) ⊢ (ε, Y*X+SI) ⊢ (ε, X+SI) ⊢ (ε, SI)