下推自动机和解析
解析用于使用语法的生成规则来派生字符串。它用于检查字符串的可接受性。编译器用于检查字符串在语法上是否正确。解析器获取输入并构建解析树。
解析器可以有两种类型 −
自上而下的解析器 − 自上而下的解析从顶部的起始符号开始，并使用解析树派生字符串。
自下而上的解析器 −自下而上的解析从底部开始，使用解析树从字符串开始，然后到达起始符号。
自上而下的解析器设计
对于自上而下的解析，PDA 具有以下四种类型的转换 −
弹出堆栈顶部产生式左侧的非终结符，并将其右侧字符串推送。
如果堆栈顶部符号与正在读取的输入符号匹配，则将其弹出。
将起始符号"S"推送到堆栈。
如果输入字符串已完全读取且堆栈为空，则转到最终状态"F"。
示例
为表达式设计一个自上而下的解析器对于语法 G，其生成规则如下 −
的"x+y*z"为 −P: S → S+X | X, X → X*Y | Y, Y → (S) | id
解决方案
如果 PDA 为 (Q, ∑, S, δ, q0, I, F)，则自上而下的解析为 −
(x+y*z, I) ⊢(x +y*z, SI) ⊢ (x+y*z, S+XI) ⊢(x+y*z, X+XI)
⊢(x+y*z, Y+X I) ⊢(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, δ, q0, 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）
