Parser Generators和Ragel ......制作我自己的D Parser

Question

我是编译器世界的新手,我最近听说过一种称为解析器生成器的东西.从我(我认为)我所理解的,解析器生成器接收语法文件并输出可以使用给定语法解析文件的源代码文件.

几个问题:

1. 我理解正确吗？

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

3. 如果是,Ragel可以将D解析器输出为D源代码吗？

谢谢!

Answer 1

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

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

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

3. 如果您需要快速词法分析器,Ragel会生成D代码.

要完全理解解析器生成器为您做什么,您需要一些正式的语言和解析理论.还有比龙书更糟糕的地方.另请参阅:学习编写编译器.

如果你有勇气,请务必查看使用DMD编译器分发的lexing和解析代码 - /dmd2/src/dmd/ - lexer.c和parse.c.

Answer 2

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

让Ragel与众不同的另一件事是它在线.换句话说,它很容易用于扫描来自异步源的数据,例如非阻塞套接字.它也不使用动态资源,除了对于调用/返回,您可以使用静态,自动或动态内存作为堆栈; 随你怎么便.也没有全球状态.

Ragel非常独特.与大多数(所有？)传统发生器不同,它是为网络编程而制作的.