10

我是编译器领域的新手，最近听说了一种叫做解析器生成器的东西。根据我（认为）我的理解，解析器生成器接收一个语法文件并输出一个源代码文件，该文件可以解析具有给定语法的文件。

几个问题：

  1. 我理解正确吗？

  2. 如果是这样，Ragel 是这样的工具吗？

  3. 如果是，Ragel 能否将 D 解析器输出为 D 源代码？

谢谢！

4

3 回答 3

19

  1. 基本上就是这样。解析器生成器将语法转换为源文件，该源文件可用于识别作为语法定义的语言成员的字符串。通常，但并非总是如此，解析器生成器需要词法分析器在其工作之前将文本分解为标记。Lex 和 Yacc是成对的词法分析器和解析器生成器的经典示例。

    现代解析器生成器提供了额外的功能。例如，ANTLR可以生成用于词法分析、语法分析的代码，甚至可以遍历生成的抽象语法树。Elkhound生成一个使用GLR解析算法的解析器。这使它能够识别比非通用解析算法更广泛的语言。PEG 解析器不需要单独的词法分析器。

  2. Ragel 实际上以有限状态机的形式生成了一个词法分析器。它可以识别常规语言，但不能识别上下文无关语言。这意味着它无法识别大多数编程语言，包括 D。

  3. 如果你需要一个快速的词法分析器，Ragel 确实会生成 D 代码。

要完全理解解析器生成器为您做了什么，您需要一些正式的语言和解析理论。有比《龙之书》更糟糕的起点。另请参阅：学习编写编译器。

如果您有勇气，请务必查看随 DMD 编译器分发的词法分析和解析代码 - /dmd2/src/dmd/ - lexer.c 和 parse.c。

于 2011-01-18T05:31:28.993 回答
13

虽然 Ragel 基于正则表达式，但它不仅仅是一个正则表达式 FSM 生成器。它允许使用额外的调用/返回语法以及允许解析非常规语言的其他功能进行递归。因此，虽然 Ragel 确实生成了 FSM，但它允许生成多个不同的 FSM，并提供在任意点之间跳转的机制，或者使用特殊的机器转换语法。它还允许在状态转换时执行任意代码。

使 Ragel 与众不同的另一件事是它是在线的。换句话说，它很容易用于从异步源（例如非阻塞套接字）扫描数据。它也不使用动态资源，除了调用/返回可以使用堆栈的静态、自动或动态内存；随你怎么便。也没有全局状态。

拉格尔非常独特。与大多数（全部？）传统生成器不同，它是为网络编程而设计的。

于 2011-03-27T03:52:37.287 回答
1

可能：

MySourceCode --> (Scanner) --> MyScannerDataFile MyScannerDataFile --> (Parser) --> MyParserDataFile MyParserDataFile --> (CodeGenerator) --> MyExecutableFile

或者：

MySourceCode --> (ScannerAndParser) --> MyScannerAndParserDataFile MyScannerAndParserDataFile --> (CodeGenerator) --> MyExecutableFile

于 2011-04-08T15:14:33.780 回答