英文原文：The difference between top-down parsing and bottom-up parsing

给出一个形式语法（formal grammar） 和 一个通过语法创建的字符串， 解析 是指产生这个字符串的处理过程。

在这种情况下，它是上下文无关的语法， 产生的处理过程采用了一个解析树的形式。我们在开始之前，我们应该知道关于解析树的两样东西：根节点， 它是字符串被原生派生出来的一个初始符号， 叶子节点， 它是序列化字符串的所有字符。 我们不知道节点的层数和分支之间是什么？

举例来说，如果一个字符串是 acddf，我们只知道这样：

    S/|

   ???

| | | | |
a c d d f

在本文中使用的示例语法

• S→ xyz | aBC

• B→ c | cd

• C→ eg | df

其它翻译版本 (1) 加载中

自下而上解析

这种解析方法特像玩智力拼图玩具。我们从解析树底层的一个个字符开始，然后使用规则把这些字符联系到一起形成较大的我们常用的语法标记。到字符串结尾，我们已经把字符串中的所有东西化合成一个大S,一个仅剩的东西。如果不是这样，我们有必要回去重新以不同的方式结合那些语法标记。

使用自下而上的解析方法，一件经典又有特色的事情是我们维护了一个栈，这个栈是那些字符和语法标记的列表。在解析的每一步中，我们首先将新字符入栈，然后在字符可以组合成大的语法标记的时候讲字符出栈。

例子：

给定字符串acddf

步骤：

• ε不能出栈

• a不能出栈

• ac可以出栈，如下：

• ac出栈形成aB,再入栈

• aB不能出栈

• aBd不能出栈

• aBdd不能出栈

• aBddf可以出栈，如下：

• 出栈aBddf形成aBdC，再入栈

• aBdc不能出栈

• 字符串结尾。栈中是aBdC，不是S。失败！重来。

• aBddf不能出栈

• ac不能出栈

• acd可以出栈，如下：

• acd出栈形成aB，再入栈

• aB不能出栈

• aBd不能出栈

• aBdf可以出栈，如下：

• 出栈aBdf形成aBC，再入栈

• aBC可以出栈

• aBC出栈形成S

• 字符串结尾。栈中是S。成功！

解析树：

|
a

| |
a c

  B| |
a c

  B| | |
a c d

  B| | | |
a c d d

  B| | | | |
a c d d f

  BC| | | |
a c d d f

| |
a c

| | |
a c d

    B|  /|
a c d

    B|  /| |
a c d d

    B|  /| | |
a c d d f

    BC|  /| |
a c d d f

    S/|
  / | |
 /BC|  /| |
a c d d f

例2

如果所有结合方式都失败，那么这个字符串将不能被解析。

给定字符串abcdg

步骤：

• ε不能出栈

• a不能出栈

• ac可以出栈，如下：

• ac出栈形成aB,再入栈

• aB不能出栈

• aBd不能出栈

• aBdg不能出栈

• 字符串结尾。栈中是aBdC，不是S。失败！重来。

• ac不能出栈

• acd可以出栈，如下：

• acd出栈形成aB，再入栈

• aB不能出栈

• aBg不能出栈

• 字符串结尾。栈中是aBg，不是S。失败！重来。
  

• acd不能出栈

• acdg不能出栈

• 字符串结尾。栈中是aBg，不是S。没有重来方式了。失败！

解析树：

|
a

| |
a c

  B| |
a c

  B| | |
a c d

  B| | | |
a c d g

| |
a c

| | |
a c d

    B|  /|
a c d

    B|  /| |
a c d g

| | |
a c d

| | | |
a c d g

自上而下解析

对于这种方法，我们假定字符串可以转化为S的，然后着眼于字符串内部关于这个假定的逻辑暗示。例如，字符串可以转化为S的事实在逻辑上暗示这个字符串要么可以转化为xyz，要么可以转化为aBC。如果不是xyz那么一定是aBC。而aBC有进一步的逻辑暗示。以此类推所有这些都有必要去检查来验证最初的假定。

例子

假定字符串acddf.

步骤

• 断言（假定）1: acddf可以转化为S

• 断言2：acddf可以转化为xyz;

• 断言错误。再试。

• 断言2：acddf可以转化为aBC，即cddf可以转化为BC;

• 断言3: cddf可以转化为cC即ddf可以转化为C

• 断言4：ddf可以转化为eg;

• 不能

• 断言4：ddf可以转化为df;

• 不能

• 断言3错误。再试。

• 断言3：cddf可以转化cdC，即df可以转化为C;

• 断言4：df可以转化为eg;

• 不能。

• 断言4：df可以转化df;

• 断言4正确。

• 断言3正确。

• 断言2正确。

• 断言1正确，成功。

解析树

    S|

    S/|
  aBC| |

    S/|
  aBC| |
    c

    S/|
  aBC/| |
  c d

    S/|
  aBC/| |
  c d d f

例2

如果，随着每一步逻辑导向，最终我仍然不能证明最初的假设（给定字符串可以转化成S），那么这个字符串不能被解析。

给定字符串acdg.

步骤

• 断言（假定）1: acdg可以转化为S

• 断言2：acdg可以转化为xyz;

• 断言错误。再试。

• 断言2：acdg可以转化为aBC，即cdg可以转化为BC;

• 断言3: cdg可以转化为cC即dg可以转化为C

• 断言4：dg可以转化为eg;

• 不能

• 断言4：dg可以转化为df;

• 不能

• 断言3错误。再试。

• 断言3：cdg可以转化cdC，即g可以转化为C;

• 断言4：g可以转化为eg;

• 不能。

• 断言4：g可以转化df;

• 不能。

• 不能。

• 不能。

• 断言1错误，失败。

解析树

    S|

    S/|
  aBC| |

    S/|
  aBC| |
    c

    S/|
  aBC/| |
  c d

自上而下解析为什么不能从左边迭代

如果我们的规则是从左边迭代的，就像这样：

• S→Sb

那么注意算法是怎样运作的:

步骤

• 断言1：acddf可以转换为S；

• 断言2：acddf可以转化为Sb；

• 断言3：acddf可以转化为Sbb；

• 断言4：acddf可以转化为Sbbb；

• 子子孙孙无穷尽也。。。。。。

解析树

  S|

  S|Sb
  |

  S|Sb
  |Sb
  |

  S|Sb
  |Sb
  |Sb
  |

...

本文中的所有译文仅用于学习和交流目的，转载请务必注明文章译者、出处、和本文链接。 2KB翻译工作遵照 CC 协议，如果我们的工作有侵犯到您的权益，请及时联系我们。

2KB项目（www.2kb.com，源码交易平台）,提供担保交易、源码交易、虚拟商品、在家创业、在线创业、任务交易、网站设计、软件设计、网络兼职、站长交易、域名交易、链接买卖、网站交易、广告买卖、站长培训、建站美工等服务