1

如果这个问题对某些人来说很明显，请原谅我，但我正在尝试自学如何编写解释器。我在 python 中执行此操作，我已经编写了 Lexer。

我已经创建了我的令牌列表，我被困在哪里是构建解析树。我对从这里去哪里有了某种想法，但我不确定我的想法是否正确。

这是我在语法中为使用正则表达式的简单算术表达式定义的语法。

<a_expression> = <identifier | number> <operator> <identifier | number>

但是，如果我的解析器从我的词法分析器接收到与此模式匹配的标记流：

<identifier | number> <operator> <identifier | number> <operator> <identifier | number>

我该如何解析它，因为它有两个运算符和三个操作数，而不仅仅是两个操作数？

此外，如何处理 n 个操作数和 n-1 个运算符？我觉得这应该递归地完成，但我不确定是否需要为不同类型的表达式定义更多解析器或从这里开始。我可以将 n 个操作数和 n-1 个运算符的模式与正则表达式匹配吗？

4

3 回答 3

3

虽然今天的“正则”表达式并未严格归入正则语言领域，但您会发现您需要一个更强大的工具来完成您想要做的事情。

上下文无关语法是你想要的，有一些工具可以用 Python 编写 CFG。最值得注意的是pyparsing，但是您也可以查看 Haskell 的 Parsec 库的一个端口，称为 Pysec。

于 2013-09-12T20:47:23.210 回答
2

正则表达式是否易于解析您的语法，取决于您的语法（即您的语法）是否也是正则的，或者是另一个 Chomsky 类的。

对于 0 型（无限制）语法，您需要一台图灵机。

对于类型 1（上下文相关），您将需要一个线性有界自动机（或上述任何一种）。

对于类型 2（无上下文），您将需要一个下推自动机（或上述任何一种）。

并且只有 type-3 (regular) 可以被正则表达式（或上述任何一个）读取。

您可以在 wikipedia 等处找到更多阅读材料。

于 2013-09-12T20:47:12.407 回答
2

具有优先权的中缀算术不是常规语言。正则表达式只适用于解析正则语言。（现代正则表达式实现不仅仅是正则表达式，它们实际上可以解析大多数上下文无关语言……但其中一些语言会花费指数级的时间，而且预测哪些语言并非易事。）

但它是一种上下文无关的语言。请参阅有关上下文无关语法的 Wikipedia 文章以获取简要说明。上下文无关文法适用于解析常规语言和上下文无关语言。

但是，许多非常规语言不需要 CFG 的全部功能。

两个重要的类是LL - 或LR -可解析的（在线性时间内）。（这些变体，尤其是 LALR 和 SLR，也很重要。）例如，Python 可以（并且至少在参考实现中）由 LL(1) 解析器解析。

您的语言适合 LR(1), OP的一个更具限制性的子集。事实上，顾名思义（“OP”是“Operator Precedence”的缩写），它就是范例。并且 OP 解析器比更通用的解析器更容易手工编写。因此，如果您要从头开始构建自定义解析器，那么您可能希望在这里使用它。

于 2013-09-12T20:54:49.953 回答