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