简单的解析器，但不是计算器

Question

我正在尝试编写一个非常简单的解析器。我在 SO 和互联网上阅读了类似的问题，但我能找到的仅限于 "arithmetic like" 东西。

我有一个非常简单的DSL，例如：

ELEMENT TYPE<TYPE> elemName {
    TYPE<TYPE> memberName;
}

其中 <TYPE> 部分是可选的并且仅对某些类型有效。

根据我的阅读，我尝试在 Python 中编写一个递归下降解析器，但有几件事我似乎无法理解：

如何查找超过 1 个字符的标记？
如何将文本拆分成不同的部分？例如，在 TYPE 之后我可以有一个空格或一个 < 或一个空格后跟一个 <。我该如何解决？

Answer 1

简答

您所有的问题都归结为您在解析字符串之前没有对其进行标记。

长答案

解析过程实际上分为两个不同的部分：词法和解析。

乐行

您对解析的思考方式中似乎缺少的东西称为标记化或词法分析。这是将字符串转换为标记流（即单词）的过程。这就是您在询问 如何将文本拆分成不同部分时要查找的内容？

您可以通过使用 re 根据正则表达式列表检查您的字符串来自行完成，或者您可以使用一些知名的库，例如 PLY. Although if you are using Python3, I will be biased toward a lexing-parsing librairy that I wrote, which is ComPyl.

所以继续使用 ComPyl，您正在寻找的语法如下所示。

from compyl.lexer import Lexer

rules = [
    (r'\s+', None),
    (r'\w+', 'ID'),
    (r'< *\w+ *>', 'TYPE'), # Will match your <TYPE> token with inner whitespaces
    (r'{', 'L_BRACKET'),
    (r'}', 'R_BRACKET'),
]

lexer = Lexer(rules=rules, line_rule='\n')
# See ComPyl doc to figure how to proceed from here

请注意，第一条规则 (r'\s+', None) 实际上解决了您关于空格的问题。它基本上告诉词法分析器匹配任何空白字符并忽略它们。当然，如果你不想使用词法分析工具，你可以简单地在你自己的 re 实现中添加一个类似的规则。

正在解析

您似乎想编写自己的 LL(1) 解析器，因此我将简要介绍这部分内容。只要知道有很多工具可以为你做这件事（PLY 和 ComPyl 库提供 LR(1) 解析器，它们更强大但更难手写，请参阅 LL(1) 和 LR(1) 之间的区别） here).

请注意，现在您知道如何标记字符串，如何查找长度超过 1 个字符的标记？ 问题已解决。您现在正在解析的不是字符流，而是封装匹配的 words.

的标记流

Answer 2

Olivier 关于 lexing/tokenizing 的回答，然后进行解析很有帮助。

但是，对于相对简单的情况，某些解析工具无需单独的标记化步骤即可满足您的需求。 parsy 就是其中之一。您可以从较小的构建块构建解析器 - 有很好的文档可以提供帮助。

此处是使用 parsy 为您的语法完成的解析器示例：http://parsy.readthedocs.io/en/latest/howto/other_examples.html#proto-file-parser。它比您的要复杂得多，但显示了可能的情况。在允许（但不是必需）空格的地方，它使用 lexeme 实用程序（在顶部定义）来使用可选的空格。

您可能需要加深理解哪些空格是必需的，哪些空格是可选的，以及您真正指的是哪种空格。

简单的解析器，但不是计算器

Simple parser, but not a calculator

python

compiler-construction

parsing

简答

长答案

乐行

正在解析