编译Lisp：Reader

欢迎回到“编译Lisp”系列。这一次，我想暂停编译，最后添加一个阅读器。我终于对手动输入日益复杂的AST感到沮丧了，所以我想是时候了。在这篇帖子之后，我们将能够输入如下程序：

让我们的编译器为我们制作ast！魔法。这也将为我们增加一些很好的调试工具。例如，假设有一个交互式命令行实用程序，我们可以在其中输入Lisp表达式，然后编译器打印出可读的程序集(和十六进制？也许吧？)。它甚至还可以运行代码。看看这个想象中的演示：

Lisp>；1；mov rax，0x4=>；1lisp>；(Add1)；mov rax，0x4；add rax，0x4=>；2lisp>；

为了使此接口尽可能简单和可测试，我希望readerinterface接受一个C字符串并返回一个ASTNode*：

我们可以稍后添加接口来支持从file*或filedescriptor或其他文件读取，但现在我们只使用字符串和基于行的输入。

如果成功，我们将返回一个完全形成的ASTNode*。但如果弄错了，好吧，霍尔顿。我们不能只返回NULL。在许多平台上，NULL被定义为0，这是我们对整数0进行编码的方式。在另一些情况下，它可以定义为0x55555555 1或其他同样愚蠢的值。无论如何，它的值可能会以某种意想不到的方式与我们的类型编码方案重叠。

这意味着我们必须继续添加另一个直接对象：错误对象。我们有一些开放的即时标记比特，所以肯定的，有什么不可以的。我们还可以使用它来通知运行时错误和其他有趣的事情。这可能会有用。

回到对象标记图。下面我复制了以前帖子中的标签图，但是现在有了一个新的条目(用<；-表示)。这个新条目显示了规范错误对象的编码。

如果我们愿意，我们甚至可以向有效负载(目前全部为0)添加额外的标记位，以发出不同类型错误的信号。过一会儿再说。目前，我们添加ATAG常量以及关联的Object和AST函数：

Const unsign int kErrorTag=0x3f；//0b111111 uword Object_Error(){return kErrorTag；}bool AST_IS_Error(ASTNode*node){return(Uword)node==object_error()；}ASTNode*AST_Error(){return(ASTNode*)Object_Error()；}。

这应该足以让我们暂时出发了。也许我们甚至可以转换COMPILE_SUITE函数来使用这个对象，而不是int。它肯定会提供更多的信息。也许在未来的帖子里。

让我们回到正题，想想我们希望我们的语言是什么样子。这是一个Lisp系列，但实际上您可以让您的读者阅读任何类型的语法。如果你过敏，不需要加括号。

我将使用这个简单的Lisp阅读器，因为它又短又简单，所以我们会有一些括号。

如果您愿意，您可以添加对其他基地的支持，但我不打算在这里这样做。

其次，我们的角色将看起来像C字符--a&39；，b&39；等等。有些实现选择了#a，但在我看来这一直很时髦。

第三，我们的布尔值将是#t和#f。也欢迎您继续使用符号来表示名称，避免使用特殊语法，并让这些符号计算为真和假的值。

第四，nil对象将是()。我们还可以稍后绑定符号nil tomean()。

我将跳过错误对象，因为它们还没有任何类型的用户领域意义-它们现在只是在编译器基础设施中使用。

第五，配对看起来像(1 2 3)，意思是(cons 1(cons 2(Cons 3nil)。我不打算添加对点对语法的支持。空格将变得微不足道。

第六，符号将看起来像任何旧的ASCII标识符：Hello，world，fooBar。我还将在其中包含一些标点符号，例如，我们可以使用+和-作为符号。或者，我们甚至可以使用完整的Lisp并使用列车案例标识符。

我将跳过闭包，因为它们没有语法表示-它们只是运行时已知的对象。矢量和字符串现在还没有任何实现，所以我们稍后会将它们添加到阅读器中。

就这样!。要点是：注意你的加号和减号，因为它们可以同时出现在整数和符号中；不要读出结尾；玩得开心。

既然我们已经相当非正式地指定了我们的语言是什么样子，我们就可以编写一个小型阅读器了。我们将从上面的Reader_Read函数开始。

这是因为我们需要携带更多的状态来读取此字符串。我们需要知道我们在这条线上走了多远。我选择用另外一个词来表示索引。有些人可能更喜欢查尔酒**而不是。你说了算。

对于任何递归读取器调用，我们应该遍历所有空格，因为它对我们没有任何意义。出于这个原因，我们有一个非常好用的Skip_Whitespace函数，它可以读取所有空格，然后返回下一个非空格字符。

Void Advance(word*pos){++*pos；}char next(char*input，word*pos){Advance(Pos)；return input[*pos]；}char跳过空白(char*input，word*pos){char c='；\0'；；for(c=input[*pos]；isspace(C)；c=next(input，pos){；}return c；}。

我们可以在READ_REC函数中使用SKIP_WILESPACE来获取下一个非空格字符。然后，我们将使用该字符(有时也包括后面的字符)来确定我们将要读取的结构。

Bool start_bol(Char C){switch(C){case'；+'；：case'；-'；：case'；*'；：case'；>；'；：case'；='；：case'；？'；：return true；默认值：return isalpha(C)；}}ASTNode*read_rec(char*input，word*pos){char c=跳过空格(input，pos)；if(isdigit(C)){return read_teger(input，pos，/*sign=*/1)；}if(c=='；+'；&；&；isdigit(input[*pos+1]){Advance(Pos)；//跳过'；+'；返回READ_INTEGER(INPUT，POS，/*SIGN=*/1)；}IF(c=='；-'；&；&；isdigit(INPUT[*POS+1])){Advance(POS)；//跳过'；-'；RETURN READ_INTEGER(INPUT，POS，/*SIGN=*/-1)；}IF(STARTS_SYMBOL(C)){RETURN READ_SYMBOL(INPUT，POS)；}if(c=='；\'；'；){Advance(位置)；//跳过'；\'；'；返回read_char(input，位置)；}if(c=='；#'；&；&；input[*pos+1]=='；t'；){Advance(位置)；//跳过'；#'；前进(位置)；//跳过'；t'；return AST_NEW_BOOL(True)；}if(c=='；#'；&；&；input[*pos+1]=='；f'；){前进(位置)；//跳过'；#'；前进(位置)；//跳过'；f'；return AST_new_bool(False)；}if(c=='；('；){Advance(Pos)；//跳过'；('；return read_list(input，pos)；}返回AST_ERROR()；}。

请注意，我将整数大小写放在符号大小写之上，因为我们希望将-123作为整数而不是符号，并将-A123作为符号而不是整数。

稍后我们可能会向starts_symbol添加更多条目，但这些条目应该涵盖了我们到目前为止已经使用过的名称。

对于每种类型的子案例(整数、符号、列表)，基本思想都是相同的：当我们仍在子案例中时，将其相加。

ASTNode*READ_INTEGER(char*input，word*pos，int sign){char c='；\0'；；word result=0；for(char c=input[*pos]；isdigit(C)；c=next(input，pos)){result*=10；result+=c-'；0'；}return AST_NEW_INTEGER(sign*result)；}

它还接受一个符号参数，所以如果我们看到一个显式的-，我们可以求反整数。

Const word ATOM_MAX=32；bool is_Symbol_char(Char C){return starts_Symbol(C)||isdigit(C)；}ASTNode*read_Symbol(char*input，word*pos){char buf[ATOM_MAX+1]；//+1，表示NUL字长=0；for(Length=0；Length<；ATOM_MAX&；&；IS_SYMBOL_CHAR(INPUT[*pos]))；Length++){buf[length]=input[*pos]；Advance(Pos)；}buf[length]='；\0'；；return AST_NEW_SYMBOL(Buf)；}。

为简单起见，我避免了动态调整大小。我们最多只能拿到32码的标志。哦，好吧。

请注意，符号中也可以有尾随数字，只是不在前面-就像Add1一样。

对于字符，我们只有三个潜在的输入字符可供查看：引号、字符、引号。不需要循环：

ASTNode*read_char(char*input，word*pos){char c=input[*pos]；if(c=='；\'；'；){return AST_error()；}Advance(Pos)；if(input[*pos]！='；\'；'；){return AST_error()；}Advance(Pos)；return AST_new_char(C)；}。

对于布尔值，我们可以内联处理这些问题，因为只有两个案例，而且都是微不足道的。检查#t和#f是否已完成。

最后，对于列表，这意味着我们递归地构建对，直到我们达到零：

ASTNode*read_list(char*input，word*pos){char c=跳过空格(input，pos)；if(c='；)'；){Advance(Pos)；return AST_nil()；}ASTNode*car=read_rec(input，pos)；assert(car！=AST_error())；ASTNode*Cdr=read_list(input，pos)；assert(cdr！=AST_error())；Return AST_NEW_Pair(car，cdr)；}。

请注意，我们仍然必须在开头跳过空格，这样我们就可以捕捉到在开始括号之后或结束括号之前有空格的大小写。或者两者兼而有之！

就是这样--这就是整个解析器。现在让我们编写一些测试。

我添加了一个新的阅读器测试套件。我想把它们归类是很好的。下面是最初以这样或那样的方式把我绊倒的套件中的一些更棘手的测试。

负整数最初解析为符号，直到我发现必须颠倒大小写顺序：

测试堆{char*read_with_negative_integer_returns_integer(void)="；-1234"；；ASTNode*节点=读取器_READ(输入)；ASSERT_IS_INT_EQ(节点，-1234)；AST_HEAP_FREE(节点)；PASS()；}。

哦，并且ASSERT_IS_INT_EQ和即将到来的ASSERT_IS_SYM_EQ宏是断言类型和值的帮助器。

测试堆(空){char*read_with_leading_whitespace_ignores_whitespace="；\t\n1234"；；ASTNode*NODE=读取器_READ(输入)；ASSERT_IS_INT_EQ(节点，1234)；AST_HEAP_FREE(节点)；PASS()；}

TEST READ_WITH_LIST_RETURNS_LIST(Void){char*INPUT="；(1 2 0)"；；ASTNode*NODE=读取器_READ(INPUT)；ASSERT(AST_IS_Pair(节点))；ASSERT_IS_INT_EQ(AST_Pair_CAR(节点)，1)；ASSERT_IS_INT_EQ(AST_pair_car(AST_pair_cdr(node))，2)；ASSERT_IS_INT_EQ(AST_pair_car(AST_pair_cdr(AST_pair_cdr(node)))，0)；ASSERT(AST_is_nil(AST_pair_cdr(node)；ASTHEAP_FREE(节点)；PASS()；}。

下面是一些滑稽的符号，以确保所有这些符号字符都能正常工作：

Test read_with_Symbol_Returns_Symbol(Void){char*input="；hello？+-*=>；"；；ASTNode*node=Reader_Read(Input)；assert_is_SYM_EQ(node，"；hello？+-*=>；"；)；AST_heap_free(Node)；pass()；}。

测试READ_WITH_SYM_WITH_TRAILING_DIGITS(Void){char*input="；add1 1"；；ASTNode*node=Reader_Read(Input)；assert_is_SYM_EQ(node，"；add1"；)；AST_heap_free(Node)；pass()；}。

现在，我们可以结束测试了，但我确实提到了一些有趣的功能，比如REPL。下面是一个函数repl，您可以从主函数调用它，而不是运行测试。

Int repl(){do{//读取一行fprintf(stdout，&34；lisp&>；&34；)；char*line=null；size_t size=0；ssize_t nchars=getline(&；line，&；size，stdin)；if(nchars<；0){fprintf(stderr，&34；再见。\n"；)；free(Line)；Break；}//分析行ASTNode*node=Reader_Read(Line)；free(Line)；if(AST_is_error(Node)){fprintf(stderr，"；parse error)。\n"；)；Continue；}//编译行缓冲区buf；buffer_init(&；buf，1)；int result=Compile_expr(&；buf，node，/*STACK_INDEX=*/-kWordSize)；AST_HEAP_FREE(节点)；IF(RESULT<；0){fprintf(stderr，"；编译错误。\n"；)；buffer_deinit(&；buf)；Continue；}//打印(size_t i=0；i<；buf)的汇编代码。Len；i++){fprintf(stderr，"；%.02x"；，buf.。Address[i])；}fprintf(stderr，"；\n"；)；buffer_deinit(&；buf)；}while(True)；return 0；}。

Int run_test(int argc，char**argv){Greest_Main_Begin()；run_Suite(Object_Test)；run_Suite(Ast_Test)；run_Suite(读取器测试)；run_Suite(Buffer_Tests)；run_Suite(编译器测试)；Greest_Main_End()；}int Main(int argc，char**argv){if(argc==2&；&；strcmp(argv[1]，"；)；}int main(int_armc，char**argv){if(argc==2&；&；strcmp(argv[1]，"；--repl-Assembly"；)==0){return repl()；}return run_test(argc，argv)；}。

它使用最后几个帖子中的所有机器，然后将结果以十六进制成对打印出来。交互如下所示：

红杉%./bin/编译-读取器--repl-Assemylisp>；148 c7 c0 04 00 00 00 lisp>；(Add1)48 c7 c0 04 00 00 00 48 05 04 00 00 lisp>；'；a'；48 c7 c0 0f 61 00 00lisp>；Goodbye.Sequoia%。

太棒了。对于读者来说，一个有趣的练习可能是更进一步，执行编译后的代码并打印结果，如上所述。我认为，最棘手的部分(因为我们还没有相应的基础设施)将是打印结果。

另一个有趣的练习可能是向编译器添加一种模式，将文本汇编打印到屏幕上，就像调试跟踪一样。这应该很简单，因为我们已经有了非常具体的操作码实现。

不管怎样，谢谢你的阅读。下一次我们将继续编译和处理小程序表达式。

请参阅凯特发布的关于在Tenra编译器中更改NULL值的一系列推文。-↩