我应该如何建立一个简单的LR解析器？ [英] How should I go about building a simple LR parser?

问题描述

我试图为一种类型的模板（配置）文件构建一个简单的LR解析器，用于生成一些其他文件。我已经阅读和阅读关于LR解析器，但我只是似乎不能理解它！我理解有一个解析堆栈，一个状态堆栈和一个解析表。令牌被读取到解析堆栈，并且当匹配规则时，取决于解析表，令牌被移位或缩减。这继续递归，直到所有的令牌都被减少，然后解析完成。

I am trying to build a simple LR parser for a type of template (configuration) file that will be used to generate some other files. I've read and read about LR parsers, but I just can't seem to understand it! I understand that there is a parse stack, a state stack and a parsing table. Tokens are read onto the parse stack, and when a rule is matched then the tokens are shifted or reduced, depending on the parsing table. This continues recursively until all of the tokens are reduced and the parsing is then complete.

问题是我真的不知道如何生成解析表。我已经阅读了不少说明，但语言是技术性的，我只是不明白。

The problem is I don't really know how to generate the parsing table. I've read quite a few descriptions, but the language is technical and I just don't understand it. Can anyone tell me how I would go about this?

还有，我如何存储像语法规则这样的东西？

Also, how would I store things like the rules of my grammar?

http://codepad.org/oRjnKacH 是我尝试的文件示例

我从来没有这样做过，所以我只是在寻找一些建议，谢谢。

I've never done this before, so I'm just looking for some advice, thanks.

推荐答案

在你的解析器理论研究中，你似乎错过了一个更实际的事实：几乎没有人会考虑手写一个表驱动，自下而上的解析器就像你在讨论。对于大多数实际用途，手写解析器使用自顶向下（通常是递归下降）结构。

In your study of parser theory, you seem to have missed a much more practical fact: virtually nobody ever even considers hand writing a table-driven, bottom-up parser like you're discussing. For most practical purposes, hand-written parsers use a top-down (usually recursive descent) structure.

使用表驱动解析器的主要原因是它允许你写一个（相当）少量的代码来操纵表，这样，几乎完全通用（即它适用于任何解析器）。然后你将一个特定语法的所有内容编码成一个计算机很容易操作的形式（例如一些表格）。

The primary reason for using a table-driven parser is that it lets you write a (fairly) small amount of code that manipulates the table and such, that's almost completely generic (i.e. it works for any parser). Then you encode everything about a specific grammar into a form that's easy for a computer to manipulate (i.e. some tables).

显然，这将是完全可能的做手工如果你真的想，但几乎从来没有一个真正的点。

Obviously, it would be entirely possible to do that by hand if you really wanted to, but there's almost never a real point. Generating the tables entirely by hand would be pretty excruciating all by itself.

例如，你通常从构建一个NFA，一个大表 - 通常开始一个每个解析器状态的行，每个可能的一列。在每个单元格，您编码下一个状态进入，当您在该状态开始，然后接收该输入。这些转换大多数基本上是空的（即他们只是说，当你处于这种状态时不允许输入）。

For example, you normally start by constructing an NFA, which is a large table -- normally, one row for each parser state, and one column for each possible. At each cell, you encode the next state to enter when you start in that state, and then receive that input. Most of these transitions are basically empty (i.e. they just say that input isn't allowed when you're in that state).

然后你遍历所有这些，遵循一些相当简单的规则来收集NFA状态集合，以便成为DFA中的状态。规则很简单，很容易将它们编程到计算机中，但是你必须在NFA表中的每个单元格中重复这些规则，并且做一些基本的完善的记事，正确。

You then step through all of those and follow some fairly simple rules to collect sets of NFA states together to become a state in the DFA. The rules are simple enough that it's pretty easy to program them into a computer, but you have to repeat them for every cell in the NFA table, and do essentially perfect book-keeping to produce a DFA that works correctly.

计算机可以并且会做得很好 - 对于NFA状态表中的两万个单元格，应用几个简单的规则一块蛋糕。很难想象，一个人做同样的事情 - 根据联合国的指导，我非常肯定，这将是非法折磨。

A computer can and will do that quite nicely -- for it, applying a couple of simple rules to every one of twenty thousand cells in the NFA state table is a piece of cake. It's hard to imagine subjecting a person to doing the same though -- I'm pretty sure under UN guidelines, that would be illegal torture.

这篇关于我应该如何建立一个简单的LR解析器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！