Automata Theory 简明教程

Pushdown Automata & Parsing

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

Parsing is used to derive a string using the production rules of a grammar. It is used to check the acceptability of a string. Compiler is used to check whether or not a string is syntactically correct. A parser takes the inputs and builds a parse tree.

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

A parser can be of two types −

  1. Top-Down Parser − Top-down parsing starts from the top with the start-symbol and derives a string using a parse tree.

  2. Bottom-Up Parser − Bottom-up parsing starts from the bottom with the string and comes to the start symbol using a parse tree.

Design of Top-Down Parser

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

For top-down parsing, a PDA has the following four types of transitions −

  1. Pop the non-terminal on the left hand side of the production at the top of the stack and push its right-hand side string.

  2. If the top symbol of the stack matches with the input symbol being read, pop it.

  3. Push the start symbol ‘S’ into the stack.

  4. If the input string is fully read and the stack is empty, go to the final state ‘F’.

Example

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

Design a top-down parser for the expression "x+y*z" for the grammar G with the following production rules −

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

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

Solution

Solution

如果 PDA 为 (Q, ∑, S, δ, q0, I, F)，则自顶向下的解析如下 -

If the PDA is (Q, ∑, S, δ, q0, I, F), then the top-down parsing is −

(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 具有以下四种类型的转换 -

For bottom-up parsing, a PDA has the following four types of transitions −

  1. Push the current input symbol into the stack.

  2. Replace the right-hand side of a production at the top of the stack with its left-hand side.

  3. If the top of the stack element matches with the current input symbol, pop it.

  4. If the input string is fully read and only if the start symbol ‘S’ remains in the stack, pop it and go to the final state ‘F’.

Example

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

Design a top-down parser for the expression "x+y*z" for the grammar G with the following production rules −

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

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

Solution

Solution

如果 PDA 是 (Q，∑，S，δ，q0，I，F)，则自底向上解析如下所示 −

If the PDA is (Q, ∑, S, δ, q0, I, F), then the bottom-up parsing is −

(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)