解析器生成器和Ragel…制作我自己的D解析器
-
12-10-2019 - |
题
我是编译器世界的新手,最近我听说了一种叫做解析器的东西。据我所知,解析器生成器接收语法文件并输出可以用给定语法解析文件的源代码文件。
几个问题:
我正确理解吗?
如果是这样,Ragel是这样的工具吗?
如果是这样,Ragel可以将D解析器输出到D源代码中吗?
谢谢!
解决方案
基本上就是这样。解析器发生器将语法转换为源文件,该文件可用于识别作为该字符串 语 由语法定义。通常但并非总是如此,解析器需要一个词汇分析仪才能在其工作之前将文本分解为代币。 Lex和Yacc 是配对词汇分析仪和解析器发生器的经典示例。
现代解析器发电机提供其他功能。例如, antlr 可以生成用于词汇分析,语法分析甚至行走生成的抽象语法树的代码。 Elkhound 生成一个使用的解析器 Glr 解析算法。这使其能够识别比非普通解析算法更广泛的语言。 钉解析器 不需要单独的词汇分析仪。
Ragel实际上以有限状态机的形式生成词汇分析仪。它可以识别 常规语言 但不是 无上下文 语。这意味着它无法识别包括D在内的大多数编程语言。
如果您需要快速的词汇分析仪,Ragel确实会生成D代码。
为了充分了解解析器生成器为您所做的事情,您将需要一些正式的语言和解析理论。有比 龙书. 。也可以看看: 学会编写编译器.
如果您感到勇敢,请务必查看使用DMD编译器 - /dmd2/src/dmd/-lexer.c和parse.c分发的Lexing和解析代码。
其他提示
虽然拉格尔是基于正则表达式的,但不是 只是 REGEX FSM发电机。它允许使用附加的呼叫/返回语法以及其他允许解析非规范语言的功能进行递归。因此,尽管Ragel确实会生成FSM,但它允许生成多个不同的FSM,并提供了在任意点或使用特殊机器过渡语法之间跳跃的机制。它还允许在状态过渡时执行任意代码。
使Ragel与众不同的另一件事是它在线。换句话说,很容易用于从异步源扫描数据,例如非阻滞插座。它也没有动态资源,除了用于呼叫/返回外,您可以为堆栈使用静态,自动或动态内存;随你怎么便。也没有全球状态。
Ragel非常独特。与大多数(全部?)传统发电机不同,它是用于网络编程的。
可能:
mySourcecode->(scanner) - > myScannerdatafile myScannerdatafile->(Parser) - > myparserdatafile myparserdatafile->(codegenerator) - > myExeCutableFile
或者:
mySourcecode->(ScannerandParser) - > myScannerandparserDatafile myScannerandparserdatafile->(codegenerator) - > myExecutableFile