c++ - 在 (V)C++ (2010) 中创建类似于 PEG 的简单解析器

Question

对于一个学校项目，我需要解析一个包含简化的“假”编程语言的文本/源文件来构建 AST .我看过 boost::spirit，但是由于这是一个小组项目，而且大多数人似乎不愿意学习额外的库，而且讲师/助教建议倾向于在 C++ 上创建一个简单的库。我想过走那条路。是否有一些例子或关于如何开始的想法？我有一些尝试，但还没有真正成功......

逐行解析

• 用一堆正则表达式测试每一行(一个用于过程/函数声明)，一个用于赋值，一个用于 while 等...
  • 但我需要假设一行中没有多个语句:例如。 a=b;x=1;
• 当我到达容器语句、过程、while 等时，我将增加缩进。所以所有嵌套语句都将在这个下面
• 当我到达时，我将减少缩进

有更好的想法或建议吗？我需要解析的示例代码(这里非常简化......)

procedure Hello {
    a = 1;
    while a {
        b = a + 1 + z; 
    }
}

另一个想法是将整个文件读入一个字符串，然后自上而下。匹配所有过程，然后捕获{ ... }中的所有内容，然后开始匹配语句(以;结尾)或容器while { ... }。这类似于 PEG 做事的方式？但我需要阅读整个文件

Answer 1

Multipass 让事情变得更简单。在第一遍中，将内容拆分为标记，例如“=”或“abababa”，或者引号分隔的字符串，或者一 block 空格。不要破坏性的(保留原始数据)，而是将事情分解成简单的 block ，并且可能有一个小的结构或枚举来描述 token 是什么(即空格、字符串文字、标识符类型的东西等) .

所以你的示例代码变成了:标识符(过程)空白()标识符(Hello)空白()操作({)空白(\n\t)标识符(a)空白()操作(=)空白()数字(1)操作(;)空白(\n\t) 等

在这些标记中，您可能还想存储行号和行上的偏移量(这将有助于稍后生成错误消息)。

一个快速测试是将其转换回原始文本。另一个快速测试可能是在 html 或其他东西中转出 pretty-print 版本(你将空白着色为粉红色背景，标识符为浅蓝色，操作为浅绿色，数字为浅橙色)，并查看你的分词器是否正在制作感觉。

现在，您的语言可能对空格不敏感。如果是这种情况，请丢弃空格! (C++ 不是，因为当 // 注释结束时你需要换行符来学习)

(注意:专业的语言解析器会尽可能接近一次通过，因为它更快。但是你是一名学生，你的目标应该是让它工作。)

所以现在你有了这样的 token 流。在这一点上有很多方法。您可以拿出一些严肃的解析印章并构建一个 CFG 来解析它们。 (你知道CFG是什么吗？LR(1)？LL(1)？)

一种更简单的方法可能是更临时地进行。查找 operator({) 并通过向上和向下计数找到匹配的 operator(})。寻找语言关键字(如过程)，然后需要一个名称(下一个标记)，然后是一个 block ({)。一个非常简单的语言的临时解析器可能工作得很好。

我已经为一种非常简单的语言完成了这个，其中的解析器由一个非常简单的 PDA 组成。它可能对你们有用。或者它可能不会。