我目前正在学习语法分析，尤其是自上而下的解析。
我知道术语以及与自下而上的 LR 解析器的区别，并且由于自上而下的 LL 解析器更容易手动实现，所以我期待着制作自己的解析器。
我见过两种方法：
- 递归下降使用一组递归函数。
- 基于堆栈和表驱动的自动机为在维基百科上显示 https://en.wikipedia.org/wiki/LL_parser#Parser_implementation_in_C++.
我对后者更感兴趣，因为它的强大功能以及它消除了调用堆栈递归。但是，我不明白如何从隐式解析树构建 AST。
这段代码示例 https://gist.github.com/DmitrySoshnikov/29f7a9425cdab69ea68f基于堆栈的有限自动机显示解析器分析输入缓冲区，仅在语法被接受时给出是/否答案。
我听说过使用堆栈注释来构建 AST，但我不知道如何实现它们。有人可以提供这种技术的实际实现吗？
“自上而下”和“自下而上”是对两种解析策略的极好描述，因为它们精确地描述了语法树如果被构造的话将如何构造。 （您也可以将其视为隐式解析树的遍历顺序，但这里我们实际上对真正的解析树感兴趣。）
显然，自下而上的树构建有一个优势。当需要向树中添加节点时，您已经知道它的子节点是什么。您可以通过一个（功能性）操作构建完整的节点。所有子节点信息都在那里等着您，因此您可以根据子节点的语义信息向节点添加语义信息，甚至可以按照从左到右以外的顺序使用子节点。
相比之下，自上而下的解析器构造没有任何子节点的节点，然后需要将每个子节点依次添加到已经构造的节点中。这当然是可能的，但有点难看。此外，节点构造函数的增量性质意味着附加到节点的语义信息也需要增量计算，或者推迟到节点完全构造完成为止。
在许多方面，这类似于计算用逆波兰表示法 (RPN) 编写的表达式与用（正向）波兰表示法编写的表达式之间的差异 [注 1]。 RPN 的发明正是为了简化评估，这可以通过简单的值堆栈实现。显然，正向波兰表达式可以求值：最简单的方法是使用递归求值器，但在不能依赖调用堆栈的环境中，可以使用运算符堆栈来实现，这可以有效地将表达式转换为 RPN飞。
因此，这也可能是从自顶向下解析器构建语法树的选择机制。我们在每个右侧的末尾添加一个“减少”标记。由于标记位于右侧末端，因此它被先推入。
我们还需要一个值堆栈，来记录正在构造的 AST 节点（或语义值）。
在基本算法中，我们现在还有一种情况。我们首先弹出解析器堆栈的顶部，然后检查该对象：
解析器堆栈的顶部是一个终端。如果当前输入符号是相同的终端，我们从输入中删除输入符号，并将其（或其语义值）压入值堆栈。
解析器堆栈的顶部是一个标记。关联的归约操作被触发，该操作将通过从值堆栈中弹出适当数量的值并将它们组合成一个新的 AST 节点来创建新的 AST 节点，然后将该新的 AST 节点推送到值堆栈上。 （作为一种特殊情况，增强开始符号的独特制作的标记动作S' -> S $导致解析被接受，返回值堆栈中的（唯一）值作为 AST。）
解析器堆栈的顶部是非终端。然后，我们使用当前输入符号识别适当的右侧，并将该右侧（从右到左）推送到解析器堆栈上。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
