Automata Theory 简明教程

Pushdown Automata & Parsing

解析用于根据语法的产生式导出一串字符。它用于检查一串字符的可接受性。编译器用于检查一串字符在语法上是否正确。解析器获取输入并构建一个解析树。

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

  1. Top-Down Parser - 自顶向下解析从顶部开始，以起始符号为起始，并使用解析树导出一个字符串。

  2. Bottom-Up Parser - 自底向上解析从底部开始，以字符串为起始，并使用解析树得到起始符号。

Design of Top-Down Parser

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

  1. 弹出栈顶中产生式左侧的非终结符，并压入其右侧的字符串。

  2. 如果栈顶符号与正读取的输入符号匹配，则弹出该符号。

  3. 将起始符号“S”压入栈中。

  4. 如果输入字符串已完全读取，且栈已清空，则转至最终状态“F”。

Example

设计一个自顶向下的解析器来解析表达式“x+y*z”，针对具有以下产生式的语法 G -

P: S → S+X | X, X → X*Y | Y, Y → (S) | id

Solution

如果 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)

Design of a Bottom-Up Parser

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

  1. 将当前输入符号压入栈中。

  2. 将堆栈顶部的某个产生式的右侧用其左侧替换。

  3. 如果堆栈元素的栈顶与当前输入符号匹配，则弹出该元素。

  4. 如果输入字符串被完全读入，并且只有开始符号“S”仍然保留在堆栈中，则弹出该开始符号，并转到最终状态“F”。

Example

设计一个自顶向下的解析器来解析表达式“x+y*z”，针对具有以下产生式的语法 G -

P：S → S+X | X，X → X*Y | Y，Y →（S）| id

Solution

如果 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)