我该如何构建一个简单的LR解析器？

Question

我正在尝试为一种模板(配置)文件构建一个简单的LR解析器,该文件将用于生成其他一些文件.我已阅读并阅读有关LR解析器的内容,但我似乎无法理解它!我知道有一个解析堆栈,一个状态堆栈和一个解析表.令牌被读入解析堆栈,当匹配规则时,令牌被移位或减少,具体取决于解析表.这将递归地继续,直到所有令牌都减少并且然后解析完成.

问题是我真的不知道如何生成解析表.我已经阅读了不少描述,但语言是技术性的,我只是不明白.谁能告诉我怎么会这样呢？

另外,我如何存储像语法规则这样的东西？

http://codepad.org/oRjnKacH是我尝试解析的文件示例,我尝试使用其语言的语法.

我以前从未这样做过,所以我只是在寻找一些建议,谢谢.

Answer 1

在你对解析器理论的研究中,你似乎错过了一个更实际的事实:几乎没有人会考虑像你正在讨论的那样用手写自下而上的解析器.对于大多数实际用途,手写解析器使用自上而下(通常是递归下降)结构.

使用表驱动解析器的主要原因是它允许您编写(相当)少量操作表的代码,这几乎完全是通用的(即它适用于任何解析器).然后,您将有关特定语法的所有内容编码为一个易于计算机操作的表单(即某些表).

显然,如果你真的想要,那完全有可能手工完成,但几乎从来没有真正的意义.完全手工生成表格本身就非常令人难以忍受.

例如,您通常首先构建一个NFA,这是一个大表 - 通常,每个解析器状态一行,每个可能一列.在每个单元格中,编码在该状态下启动时要输入的下一个状态,然后接收该输入.大多数这些转换基本上都是空的(即它们只是说当你处于该状态时不允许输入).

然后,您逐步完成所有这些操作,并遵循一些相当简单的规则来收集NFA状态集合,以成为DFA中的状态.规则很简单,很容易将它们编程到计算机中,但是你必须为NFA表中的每个单元重复这些规则,并且基本上完成簿记以生成正常工作的DFA.

计算机可以并且将会很好地完成这项工作 - 因为,对NFA状态表中的每两万个单元应用几个简单的规则是件小事.很难想象让一个人做同样的事情 - 我很确定在联合国的指导下,这将是非法的折磨.

Answer 2

经典的解决方案是 lex/yacc 组合：

http://dinosaur.compilertools.net/yacc/index.html

或者，正如 gnu 所称的 - flex/bison。

编辑：

Perl 有 Parse::RecDescent，它是一个递归下降解析器，但它可能更适合简单的工作。