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

Question

我猜在它们中应用了相同的逻辑，即用产生式规则中提供的相应非终止元素替换匹配的字符串。

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

Answer 1

Bottom up parsing

自底向上解析(也称为shift-reduce解析)是一种分析未知数据关系的策略，它试图首先确定最基本的单元，然后从它们推断出更高阶的结构。它试图朝开始符号向上构建树。

Top-down parsing

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

Answer 2

自顶向下解析涉及从第一个非终端生成字符串。例如:递归下降解析，非递归下降解析，LL解析等。左递归和左因子分解的语法不起作用。可能会发生回溯。使用最左边的派生法

Answer 3

感兴趣的事情博客自上而下解析和自下而上解析之间的区别

给定一个形式语法和由该语法生成的字符串，解析就是找出该字符串的生成过程。

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

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

S

/|\

?？?

|||a 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

| /| |\ a c d d f

S

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

|||a 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||c

S

/|\ a B C /| |c d

S

/|\ a B C /| |\ 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||c

S

/|\ a B C /| |c d

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

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

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 |\ S b |\ S b

S |\ S b |\ S b |\ S b

..。