说明令牌流上的最左边的推导
Ilustrate the left-most derivation on a token stream
我试图在 LL 解析算法的上下文中理解最左边的推导。这个link从生成的角度解释了它。即它展示了如何遵循最左推导从一组规则中生成特定的标记序列。
但我正在考虑相反的方向。给定一个标记流和一组语法规则，如何通过最左推导找到 应用一组规则的正确步骤？
让我们继续使用上述link中的以下语法：
并且给定的令牌序列是：1 2 3
一种方法是这样的：
1 2 3
-> D D D
-> N D D (rewrite the *left-most* D to N according to the rule N->D.)
-> N D (rewrite the *left-most* N D to N according to the rule N->N D.)
-> N (same as above.)
但是还有其他方法可以应用语法规则：
1 2 3 -> D D D -> N D D -> N N D -> N N N
或
1 2 3 -> D D D -> N D D -> N N D -> N N
但只有第一个推导以单个非终结符结束。
随着令牌序列长度的增加，可以有更多的方式。我认为要推断出正确的推导步骤，需要 2 个先决条件：
- 一个starting/root规则
- 令牌序列
给出这2个后，求导步骤的算法是什么？我们是否必须使最终结果成为 单个 非终结符？
LL解析的一般过程包括重复：
预测栈顶文法符号的产生式，如果该符号是非终结符，则用右手替换该符号生产方面。
将栈顶语法符号与下一个输入符号匹配，同时丢弃它们。
匹配操作没有问题，但预测可能需要 oracle。但是，出于此解释的目的，只要预测有效，预测的机制就无关紧要了。例如，对于某个小整数 k，每个可能的 k 输入符号序列可能只与最多一个可能的产生式一致，在这种情况下，您可以使用查找 table。在那种情况下，我们说文法是LL(k)。但是你可以使用任何机制，包括魔法。只需要预测总是准确的。
在此算法的任何步骤中，部分派生的字符串都是附加在堆栈上的消耗输入。最初没有消耗的输入，堆栈仅由开始符号组成，因此部分派生的字符串（应用了 0 次派生）。由于消耗的输入仅由终端组成，并且算法仅修改堆栈的顶部（第一个）元素，因此很明显，部分派生的字符串系列构成了最左边的派生。
如果解析成功，整个输入将被消耗，堆栈将为空，因此解析结果是从起始符号开始对输入进行最左边的推导。
这是您示例的完整解析：
Consumed Unconsumed Partial Production
Input Stack input derivation or other action
-------- ----- ---------- ---------- ---------------
N 1 2 3 N N → N D
N D 1 2 3 N D N → N D
N D D 1 2 3 N D D N → D
D D D 1 2 3 D D D D → 1
1 D D 1 2 3 1 D D -- match --
1 D D 2 3 1 D D D → 2
1 2 D 2 3 1 2 D -- match --
1 2 D 3 1 2 D D → 3
1 2 3 3 1 2 3 -- match --
1 2 3 -- -- 1 2 3 -- success --
如果你阅读了最后两栏，你可以看到从N开始到1 2 3结束的推导过程。在此示例中，只能使用魔术进行预测，因为规则 N → N D 不是 LL(k) 对于任何 k；使用右递归规则 N → D N 将允许 LL(2) 决策过程（例如，"use N → D N if there are at least two unconsumed input tokens; otherwise N → D"。）
您尝试生成的图表以 1 2 3 开头并以 N 结尾，是一个 自下而上 解析。使用LR算法自下而上解析对应最右推导，但推导需要倒着读，因为它以开始符号结束。
我试图在 LL 解析算法的上下文中理解最左边的推导。这个link从生成的角度解释了它。即它展示了如何遵循最左推导从一组规则中生成特定的标记序列。
但我正在考虑相反的方向。给定一个标记流和一组语法规则，如何通过最左推导找到 应用一组规则的正确步骤？
让我们继续使用上述link中的以下语法：
并且给定的令牌序列是：1 2 3
一种方法是这样的：
1 2 3
-> D D D
-> N D D (rewrite the *left-most* D to N according to the rule N->D.)
-> N D (rewrite the *left-most* N D to N according to the rule N->N D.)
-> N (same as above.)
但是还有其他方法可以应用语法规则：
1 2 3 -> D D D -> N D D -> N N D -> N N N
或
1 2 3 -> D D D -> N D D -> N N D -> N N
但只有第一个推导以单个非终结符结束。
随着令牌序列长度的增加，可以有更多的方式。我认为要推断出正确的推导步骤，需要 2 个先决条件：
- 一个starting/root规则
- 令牌序列
给出这2个后，求导步骤的算法是什么？我们是否必须使最终结果成为 单个 非终结符？
LL解析的一般过程包括重复：
预测栈顶文法符号的产生式，如果该符号是非终结符，则用右手替换该符号生产方面。
将栈顶语法符号与下一个输入符号匹配，同时丢弃它们。
匹配操作没有问题，但预测可能需要 oracle。但是，出于此解释的目的，只要预测有效，预测的机制就无关紧要了。例如，对于某个小整数 k，每个可能的 k 输入符号序列可能只与最多一个可能的产生式一致，在这种情况下，您可以使用查找 table。在那种情况下，我们说文法是LL(k)。但是你可以使用任何机制，包括魔法。只需要预测总是准确的。
在此算法的任何步骤中，部分派生的字符串都是附加在堆栈上的消耗输入。最初没有消耗的输入，堆栈仅由开始符号组成，因此部分派生的字符串（应用了 0 次派生）。由于消耗的输入仅由终端组成，并且算法仅修改堆栈的顶部（第一个）元素，因此很明显，部分派生的字符串系列构成了最左边的派生。
如果解析成功，整个输入将被消耗，堆栈将为空，因此解析结果是从起始符号开始对输入进行最左边的推导。
这是您示例的完整解析：
Consumed Unconsumed Partial Production
Input Stack input derivation or other action
-------- ----- ---------- ---------- ---------------
N 1 2 3 N N → N D
N D 1 2 3 N D N → N D
N D D 1 2 3 N D D N → D
D D D 1 2 3 D D D D → 1
1 D D 1 2 3 1 D D -- match --
1 D D 2 3 1 D D D → 2
1 2 D 2 3 1 2 D -- match --
1 2 D 3 1 2 D D → 3
1 2 3 3 1 2 3 -- match --
1 2 3 -- -- 1 2 3 -- success --
如果你阅读了最后两栏，你可以看到从N开始到1 2 3结束的推导过程。在此示例中，只能使用魔术进行预测，因为规则 N → N D 不是 LL(k) 对于任何 k；使用右递归规则 N → D N 将允许 LL(2) 决策过程（例如，"use N → D N if there are at least two unconsumed input tokens; otherwise N → D"。）
您尝试生成的图表以 1 2 3 开头并以 N 结尾，是一个 自下而上 解析。使用LR算法自下而上解析对应最右推导，但推导需要倒着读，因为它以开始符号结束。