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.

我见过两种方法:

• 使用一组递归函数的递归下降函数.
• 基于堆栈和表驱动的自动机，如在维基百科上显示.

我对后者更感兴趣，因为它的强大和消除了调用堆栈递归.但是，我不明白如何从隐式解析树构建 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屋！