自上而下和自下而上解析技术的区别？

Question

我猜两者都应用了相同的逻辑，即用生产规则中提供的相应非终端元素替换匹配的字符串。

他们为什么要分类LL as top down和LR as bottom-up？

Answer 1

Bottom up parsing：

自下而上解析（也称为 移位减少解析）是一种策略 用于分析未知数据 关系试图 找出最基本单位 第一个，然后从中推断出更高阶的 结构。它试图 建立树向上朝着 符号。

Top-down parsing：

自上而下的分析是 通过假设到一般解析树 结构，然后考虑 分析未知的数据关系 战略已知的基本 结构是否与 兼容假设。

Answer 2

自顶向下解析 涉及从第一个非终端生成字符串。 示例：递归下降解析，非递归下降解析，LL解析等。 具有左递归和左分解的语法不起作用。 可能发生回溯。 使用最左推导

Answer 3

事物的兴趣博客 自上而下的分析和自下而上的分析

给出一个正式的语法和由该语法生成​​的字符串，解析之间的差别是找出生产过程为那个字符串。

在上下文无关语法的情况下，生产过程采用分析树的形式。在开始之前，我们总是知道关于分析树的两件事情：根节点（它是字符串最初从其中导出的初始符号）和叶节点（它们是字符串的所有字符）。我们不知道的是它们之间的节点和分支的布局。

例如，如果字符串是acddf，我们知道这已经很多：

S 

/| \

???

| | | | | 一个C d d˚F

示例语法使用本文中

S → xyz | aBC 
B → c | cd 
C → eg | df 

自下而上分析

这种做法是没有什么不同解决拼图。我们从具有单个字符的分析树底部开始。然后，我们使用规则将字符连接成更大的令牌。在字符串的末尾，所有东西都应该合并成一个大S，而S应该是我们剩下的唯一东西。如果不是，则有必要回溯并尝试以不同方式组合令牌。

对于自下而上的解析，我们通常会维护一个堆栈，它是我们迄今为止看到的角色和令牌的列表。在每一步中，我们将一个新字符转移到堆栈上，然后通过将字符组合成较大的标记来尽可能地减少。 示例

字符串是acddf。 步骤

ε can't be reduced 
a can't be reduced 
ac can be reduced, as follows: 
reduce ac to aB 
    aB can't be reduced 
    aBd can't be reduced 
    aBdd can't be reduced 
    aBddf can be reduced, as follows: 
    reduce aBddf to aBdC 
     aBdC can't be reduced 
     End of string. Stack is aBdC, not S. Failure! Must backtrack. 
    aBddf can't be reduced 
ac can't be reduced 
acd can be reduced, as follows: 
reduce acd to aB 
    aB can't be reduced 
    aBd can't be reduced 
    aBdf can be reduced, as follows: 
    reduce aBdf to aBC 
     aBC can be reduced, as follows: 
     reduce aBC to S 
      End of string. Stack is S. Success! 

解析树

| a

| | a c

B | | a c

B | | | a c d

B | | | | a c d d

B | | | | | a c d d f

B C | | | | \ 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

B C 

|/| | \ 一个C d d˚F

S 

/| \ /| | /B C |/| | \ 一个C d d˚F

实施例2

如果所有组合失败，则该字符串不能被解析。

字符串是acdg。 步骤

ε can't be reduced 
a can't be reduced 
ac can be reduced, as follows: 
reduce ac to aB 
    aB can't be reduced 
    aBd can't be reduced 
    aBdg can't be reduced 
    End of string. Stack is aBdg, not S. Failure! Must backtrack. 
ac can't be reduced 
acd can be reduced, as follows: 
reduce acd to aB 
    aB can't be reduced 
    aBg can't be reduced 
    End of string. stack is aBg, not S. Failure! Must backtrack. 
acd can't be reduced 
acdg can't be reduced 
End of string. Stack is is acdg, not S. No backtracking is possible. Failure! 

解析树

| 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

| | | | 一个C d g^

自顶向下解析

对于这种方法，我们假设字符串匹配S和看待这个假设的内在逻辑意义。例如，字符串匹配S的逻辑意味着（1）字符串匹配xyz或（2）字符串匹配aBC。如果我们知道（1）不是真的，那么（2）必须是真的。但（2）有其自己的更深层次的意义。必须对这些进行检查，以证明基本断言。 示例

字符串是acddf。 步骤

Assertion 1: acddf matches S 
    Assertion 2: acddf matches xyz: 
    Assertion is false. Try another. 
    Assertion 2: acddf matches aBC i.e. cddf matches BC: 
     Assertion 3: cddf matches cC i.e. ddf matches C: 
      Assertion 4: ddf matches eg: 
      False. 
      Assertion 4: ddf matches df: 
      False. 
     Assertion 3 is false. Try another. 
     Assertion 3: cddf matches cdC i.e. df matches C: 
      Assertion 4: df matches eg: 
      False. 
      Assertion 4: df matches df: 
      Assertion 4 is true. 
     Assertion 3 is true. 
    Assertion 2 is true. 
Assertion 1 is true. Success! 

解析树

S 
| 

S 

/| \ A B C | |

S 

/| \ A B C | | Ç

S 

/| \ A B C /| | Çd

S 

/| \ A B C /| | \ Çd d˚F

实施例2

如果按照每个逻辑铅后，也不能证明基本假设（“字符串匹配S”），则该字符串不能被解析。

字符串是acdg。 步骤

Assertion 1: acdg matches S: 
    Assertion 2: acdg matches xyz: 
    False. 
    Assertion 2: acdg matches aBC i.e. cdg matches BC: 
     Assertion 3: cdg matches cC i.e. dg matches C: 
      Assertion 4: dg matches eg: 
      False. 
      Assertion 4: dg matches df: 
      False. 
     False. 
     Assertion 3: cdg matches cdC i.e. g matches C: 
      Assertion 4: g matches eg: 
      False. 
      Assertion 4: g matches df: 
      False. 
     False. 
    False. 
Assertion 1 is false. Failure! 

解析树

S 
| 

S 

/| \ A B C | |

S 

/| \ A B C | | Ç

S 

/| \ A B C /| | CD

为什么左递归是自上而下的解析器问题

如果我们的规则是左递归的，例如像这样：

S → Sb 

然后发现我们的算法如何工作： 步骤

Assertion 1: acddf matches S: 
    Assertion 2: acddf matches Sb: 
     Assertion 3: acddf matches Sbb: 
      Assertion 4: acddf matches Sbbb: 
       ...and so on forever 

解析树

S |

S | \ S b |

小号 | \ S B | \ S B |

小号 | \ S B | \ S B | \ S B |

...