软件设计实践大作业

Lv.2 语法分析器

准备妥当，可以开始编写语法分析器了。在 Lisp 中，语法分析器也可以称作“读取器”，即读取一串词法标记，得到一个值的这么个东西。OK，回顾之前提到的要实现的接口，它长这样：

// 现在我们就认为 ValuePtr = std::share_ptr<Value> 了
ValuePtr parse(std::deque<TokenPtr> tokens);

不过这个接口可以写得面向对象一些，比如：

class Parser {
public:
    Parser(std::deque<TokenPtr> tokens);
    ValuePtr parse();
}

至于为什么写成这样而不是过程式的接口，自有它的好处。比如，程序在进行语法分析时需要保存一些状态（当前是否位于括号内、正在分析的词法标记等等），那么这些状态信息作为私有数据成员来保存是再好不过的了。

WARNING

这里不用 const std::deque<TokenPtr>& 的原因是，词法标记序列需要移动到 Parser 内部而不是复制。注意，TokenPtr 是 std::unique_ptr，它不支持复制。

任务 2.1 编写大体框架

新建 parser.h 与 parser.cpp，将刚刚描述的 Parser 类定义于其中。不要忘记包含保护。

构造函数 Parser::Parser 以 std::deque 的形式接受一系列词法标记。你可以将它保存到私有数据成员，供后续读取。接下来就开始考虑 Parser::parse 这个核心函数该如何编写了。

首先考虑最简单的情形，如果词法标记序列的首个词法标记是字面量的话，那就直接返回对应的值就可以。

ValuePtr Parser::parse() {
    auto token = 首个词法标记;
    if (token->getType() == TokenType::NUMERIC_LITERAL) {
        auto value = static_cast<NumericLiteralToken&>(*token).getValue();
        return std::make_shared<NumericValue>(value);
    }
    // [...]
}

这个代码展示了处理数型字面量的分支。剩下的布尔字面量、字符串字面量和符号字面量都是完完全全类似的，抄就是了。

对于其它的词法标记类别，比如引号、括号等等，就比较麻烦了。不过我们先暂时不管，直接抛出一个异常。

#include "./error.h"

ValuePtr Parser::parse() {
    // [...]
    throw SyntaxError("Unimplemented");
}

最后，修改 main.cpp，把语法分析器接在词法分析器后面：

auto tokens = Tokenizer::tokenize(line);
Parser parser(std::move(tokens)); // TokenPtr 不支持复制
auto value = parser.parse();
std::cout << value->toString() << std::endl; // 输出外部表示

 
 

效果就是一个愚蠢的复读机，但是这个复读机竟然实现了复杂的词法分析和语法分析。

>>> #f
#f
>>> 42
42
>>> "abc"
"abc"
>>> eq?
eq?

任务 2.2 处理 S-表达式

接下来就是处理复杂一点的输入——小括号括起的前缀表达式。这种表达式有一个名字叫 S-表达式，在很多非 Lisp 系的语言中也有所运用。跑题了，总之我们需要将一个 S-表达式解析为列表或者说是对子类型的数据。

我们来看一下 S-表达式的构造。S-表达式有两种写法，一种是普通的列表如 (a b c)，一种会带一个 . 如 (a b . c)，我们称它为带点列表。解析列表和带点列表的逻辑是差不多的，只是说遇到 . 之后，接下来就只剩下一个元素作为当前这个对子的右半部分了；而没遇到 . 的时候接下来的值仍然是列表的元素。

具体而言，整个分析流程是这样的：

  1. 当读到一个 ( 的时候，就意味着一个 S-表达式的起点；
  2. 如果下一个词法标记是 )，那么 S-表达式就结束了；
  3. 否则，往下递归地解析一个值。
  4. 这个值后面如果跟着 . 的话，那就再解析一个值，最后应该剩下一个 )，整个表达式的分析就结束了——由刚刚解析的两个值构成的对子。
  5. 如果不是 .，那就意味着后面又是一个新的列表。转到 2。

用伪代码来写的话：

ValuePtr Parser::parseTails() {
    if (下一个词法标记 == ')') {
        弹出这个词法标记;
        return 空表;
    }
    auto car = this->parse();
    if (下一个词法标记 == '.') {
        弹出这个词法标记;
        auto cdr = this->parse();
        再弹出一个词法标记，它应当是 ')';
        return 对子 (car, cdr);
    } else {
      auto cdr = this->parseTails();
      return 对子 (car, cdr);
    }
}

代码框架已经给好了，照着写就行了。请实现 Parser::parseTails 方法，并在合适的地方调用它，从而实现对 S-表达式的语法分析。

TIP

“弹出”这个词还是蛮形象的；结合一下 std::deque 的接口不难理解。“查看下一个词法标记”，对应的又是 std::deque 的哪个接口方法呢？

WARNING

不要忘记做错误处理。如果期望读取一个词法标记，但是已经没有更多的标记的话，抛出一个 EOF 错误。你既可以定义一个新的异常类型，也可以直接用 SyntaxError。

任务 2.3 处理引号

Mini-Lisp 中有三个特殊的词法标记，'、` 和 ,。它们都是引号，而且你知道 'foobar 等价于 (quote foobar)。其实另外两个也是同样的道理：

  • 'foobar 等价于 (quote foobar)；
  • `foobar 等价于 (quasiquote foobar)；
  • ,foobar 等价于 (unquote foobar)。

暂时不用管后面两个啥意思，你只需要在语法分析时做这么一个等价代换就行。也就是：

if (token->getType() == TokenType::QUOTE) {
    return std::make_shared<PairValue>(
      std::make_shared<SymbolValue>("quote")
      std::make_shared<PairValue>(
          this->parse(),
          std::make_shared<NilValue>()
      )
    )
}

这样子的代码重复三遍，当然你可以用一个更高层次的抽象来概括这三者。

TIP

如果你觉得像这样通过一个又一个 PairValue 来创建列表是令人头疼的，那么你可以编写一个函数直接从 std::vector<ValuePtr> 转换到对应的表示列表的 ValuePtr。这个函数说不准有可能在将来的开发中派上用场……

测试

还是原来的 main 函数定义，但是你现在实现了一个功能健全的复读机！他还能自动简化对子链为列表形式。

>>> 42
42
>>> (a . (b . c))
(a b . c)
>>> '"abc"
(quote "abc")
>>> (#t . (#f . ()))
(#t #f)

阶段性检查

我们提供了一个“测试框架” rjsj_test，定义于 rjsj_test.hpp 中。你需要用该框架的测试结果作为检查成果。

在你的 main.cpp（或包含 main 函数的文件）中，添加如下代码：

// [...]

#include "rjsj_test.hpp"

struct TestCtx {
    std::string eval(std::string input) {
        auto tokens = Tokenizer::tokenize(input);
        Parser parser(std::move(tokens));
        auto value = parser.parse();
        return value->toString();
    }
};

int main() {
    RJSJ_TEST(TestCtx, Lv2, Lv2Only);
    // [...]
}

即，引入 rjsj_test.hpp，定义一个结构体 TestCtx，其 eval 函数将输入的 std::string 作为 Lisp 源码求值后输出，返回一个 std::string。随后，在 main 函数开头写下 RJSJ_TEST(TestCtx, Lv2, Lv2Only);，它的含义是用 Lv2 和 Lv2Only 两个测试用例集，测试 TestCtx 定义的求值过程是否是正确的。

如上修改后，重新编译并运行程序，即可得到类似下面的测试结果的输出：

+------------+-----------+
| NAME       | RESULT    |
+------------+-----------+
| Lv2        |    8/8    |
| Lv2Only    |    8/8    |
+------------+-----------+
| Total      |   16/16   |
+------------+-----------+

在教学网 大作业 / Lv.2 检查 处，提交上述测试的运行截图（包含运行窗口即可）。在 2024 年 5 月 12 日 23:59:59 前提交的，可能获得分数加成。

删除或注释 RJSJ_TEST 宏的调用即可停用测试。关于 rjsj_test “测试框架”的更多信息，请参阅此说明。

如果你使用 VS 编译出错了，那是我们的脚手架有 bug 导致的，抱歉！请手动在项目右键“属性”中，“C/C++”的“预处理器”的“使用标准符合性预处理器”勾选“是”。

Last Updated:
Contributors: Guyutongxue