我试图理解LL解析算法上下文中最左边的派生这从生成的角度解释了它。也就是说，它展示了如何遵循最左边的派生来从一组规则生成一个特定的令牌序列。
但我想的是相反的方向给定一个令牌流和一组语法规则，如何通过最左边的派生找到应用一组规则的正确步骤？
让我们继续使用上述链接中的以下语法：
link
给定的令牌序列是：123
一种方法是：
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个之后，找到推导步骤的算法是什么我们必须把最终结果变成一个非终点站吗？
最佳答案
ll解析的一般过程包括重复的：
预测堆栈顶部语法符号的产生（如果该符号是非终结符），并用产生的右侧替换该符号。
将堆栈上的顶部语法符号与下一个输入符号匹配，同时丢弃这两个符号。
匹配操作没有问题，但预测可能需要Oracle。然而，就这一解释而言，作出预测的机制是不相关的，只要它起作用例如，对于一些小整数k，每个可能的k输入符号序列最多只能与一个可能的结果一致，在这种情况下，可以使用查找表。在这种情况下，我们说语法是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结束的派生过程。在本例中，只能使用magic进行预测，因为规则N → N D对于任何k都不是ll（k）；而使用正确的递归规则N → D N将允许ll（2）决策过程（例如，“如果至少有两个未使用的输入标记，则使用N → D N”）。您正在尝试生成的图表，以
N → D开头，以1 2 3结尾，是一个自下而上的分析。使用lr算法的自底向上解析对应于最右边的派生，但是派生需要向后读取，因为它以开始符号结尾。关于algorithm - 说明 token 流上最左边的派生，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41531642/