下推自动机与语法分析

语法分析用于使用文法的产生式规则推导出字符串。它用于检查字符串的可接受性。编译器用于检查字符串在语法上是否正确。解析器接收输入并构建语法树。

解析器可以分为两种类型：

• 自顶向下解析器 - 自顶向下解析从顶部开始符号开始，使用语法树推导出字符串。

• 自底向上解析器 - 自底向上解析从底部的字符串开始，使用语法树到达开始符号。

自顶向下解析器的设计

对于自顶向下解析，PDA 有以下四种类型的转换：

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

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

• 将开始符号“S”压入堆栈。

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

示例

为表达式“x+y*z”设计一个自顶向下解析器，该解析器适用于具有以下产生式规则的文法 G：

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”。

示例

为表达式“x+y*z”设计一个自顶向下解析器，该解析器适用于具有以下产生式规则的文法 G：

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)