我目前正在学习语法分析，尤其是自上而下的解析。
我知道术语和自下而上的LR解析器的区别，并且由于自上而下的LL解析器更容易手工实现，我期待着自己创建。
我见过两种方法：
我对后者更感兴趣，因为它的功能和消除了调用栈递归。但是，我不明白如何从隐式解析树构建AST。
基于堆栈的有限自动机的This code example显示解析器分析输入缓冲区，如果语法已被接受，则仅给出是/否答案。
我听说过堆栈注释以构建AST，但我无法弄清楚如何实现它们。有人可以提供这种技术的实际实现吗？
你需要了解背后的概念。您需要了解下推自动机的概念。在您了解如何使用铅笔在纸上进行计算之后，您将能够通过递归下降或使用堆栈了解实现其想法的多种方法。这些想法是相同的，当您使用递归下降时，您隐式地拥有程序用于执行的堆栈，其中执行数据与解析自动机数据相结合。
我建议你从Ullman（自动机）或Dick Grune教授的课程开始，这是最专注于解析的课程。 （Grune的书是this one），寻找第2版。
对于LR解析，必要的是理解Earley的想法，从这些想法Don Knuth创建了LR方法。
对于LL解析，Grune的书非常出色，Ullman提出了纸上计算，解析的数学背景对于了解是否要实现自己的解析器至关重要。
关于AST，这是解析的输出。解析器将生成一个在AST中转换的解析树，或者可以生成并直接输出AST。
“自上而下”和“自下而上”是对两种解析策略的出色描述，因为它们精确地描述了如何构造语法树。 （您也可以将其视为隐式解析树的遍历顺序，但在这里我们实际上对真正的解析树感兴趣。）
很明显，自下而上的树构造有一个优势。当需要向树中添加节点时，您已经知道它的子节点是什么。您可以在一个（功能）操作中构造完全形成的节点。所有子信息都在那里等着您，因此您可以根据子节点的语义信息向节点添加语义信息，甚至可以按照从左到右的顺序使用子节点。
相比之下，自上而下的解析器构造没有任何子节点的节点，然后需要将每个子节点依次添加到已构造的节点。这当然是可能的，但它有点难看。此外，节点构造函数的增量性质意味着附加到节点的语义信息也需要以递增方式计算，或者推迟到节点完全构造之前。
在许多方面，这类似于用反向波兰表示法（RPN）编写的表达式与用（正向）波兰表示法[注1]编写的表达式之间的区别。 RPN的发明正是为了简化评估，这可以通过简单的价值堆栈实现。显然可以评估前向波兰语表达式：最简单的方法是使用递归求值器，但是在不能依赖调用堆栈的环境中，可以使用运算符堆栈来实现它，这有效地将表达式转换为RPN飞。
所以这可能是从自上而下的解析器构建语法树的首选机制。我们在每个右侧的末尾添加一个“缩小”标记。由于标记位于右侧的末端，因此首先按下它。
我们还需要一个值栈来记录正在构造的AST节点（或语义值）。
在基本算法中，我们现在还有一个案例。我们首先弹出解析器堆栈的顶部，然后检查此对象：
S' -> S $的标记操作会导致接受解析，将值堆栈中的（唯一）值作为AST返回。）