LL自上而下的解析器，从CST到AST [英] LL top-down parser, from CST to AST

问题描述

我目前正在学习语法分析，尤其是自上而下的解析.

I am currently learning about syntax analysis, and more especially, top-down parsing.

我知道自下而上的LR解析器的术语和区别，并且由于自上而下的LL解析器更易于手工实现，因此我希望自己做.

I know the terminology and the difference with bottom-up LR parsers, and since top-down LL parsers are easier to implement by hand, I am looking forward to make my own.

我看过两种方法:

• 使用递归函数集合的递归下降.
• 基于堆栈的表驱动自动机，如在Wikipedia上显示.

我对后者更感兴趣，因为它的功能和消除了调用堆栈递归的功能.但是，我不明白如何从隐式解析树构建AST.

I am more interested by the latter, for its power and its elimination of call-stack recursion. However, I don't understand how to build the AST from the implicit parse tree.

基于堆栈的有限自动机的此代码示例显示了解析器分析输入缓冲区，只有在接受语法后才给出是/否答案.

This code example of a stack-based finite automaton show the parser analyzing the input buffer, only giving a yes/no answer if the syntax has been accepted.

我听说过用于构建AST的堆栈注释，但我不知道如何实现它们.有人可以提供这种技术的实际实现吗?

I have heard of stack annotations in order to build the AST, but I can't figure out how to implement them. Can someone provide a practical implementation of such technique ?

推荐答案

您需要了解其背后的概念.您需要了解下推自动机的概念.了解了如何使用铅笔在纸上进行计算后，您将能够了解通过递归下降或堆栈进行实现的多种方法.想法是一样的，当您使用递归下降时，您将隐式拥有程序用于执行的堆栈，其中执行数据与解析自动机数据组合在一起.

You need to understand the concept behind. You need to understand the concept of pushdown automaton. After you understand how to make computation on paper with pencil you will be able to understand multiple ways to implement its idea, via recursive descent or with stack. The ideas are the same, when you use recursive descent you implicitly have the stack that the program use for execution, where the execution data is combined with the parsing automaton data.

我建议您从Ullman(自动机)或Dick Grune教授的课程开始，这是最专注于解析的课程. (《 Grune的书是这一个)，请查找第二版.

I suggest you to start with the course taught by Ullman (automata) or Dick Grune, this one is the best focused on parsing. (the book of Grune is this one), look for the 2nd edition.

对于LR解析，本质是理解Earley的想法，Don Knuth从这些想法中创建了LR方法.

For LR parsing the essential is to understand the ideas of Earley, from these ideas Don Knuth created the LR method.

对于LL解析，《 Grune》一书非常出色，Ullman在纸上介绍了计算，解析的数学背景对于知道您是否要实现自己的解析器至关重要.

For LL parsing, the book of Grune is excellent, and Ullman presents the computation on paper, the math background of parsing that is essential to know if you want to implement your own parsers.

关于AST，这是解析的输出.解析器将生成经过AST转换的解析树，或者可以直接生成和输出AST.

Concerning the AST, this is the output of parsing. A parser will generate a parsing tree that is transformed in AST or can generate and output directly the AST.

这篇关于LL自上而下的解析器，从CST到AST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！