使用Zig来学习编译原理——第一章习题参考答案

之所以是参考答案是因为我并没有找到任何形式的官方答案，同时可能我对于习题的理解并不正确，导致实现的代码和题目要求的不一样也说不定，最主要的是函数式编程风格我很不擅长

首先，由于时间间隔实在太久了，zig的发生了较大的变化，原项目不做任何修改显然是无法通过编译了，我们不妨重新生成一个zig项目，然后复制原先的代码（0.11在build.zig上做了较大改动）

然后我们来慢慢的修改代码（当然不修改目前版本也依旧可以运行）

先版本的zig可以直接使用union(enum)来创建tagged union而无需专门为union创建一个成员相同的enum，另外这里稍微修改了一下其他的地方的一些细节，同时上一期的maxargs的一种实现已经包含在修改的代码中了（毕竟比较简单）

至于解释器的代码，我们来简单的分析一下，首先，由于原文有要求需要按照函数式编程的理念来进行（其实函数式的话，可能更适合使用Haskell或者ocaml，毕竟这些语言的默认范式是函数式编程），所以这里我们会使用那个似是而非的链表（即原文提到的那个table类型，其实吧都3202年了，我们完全可以使用一些方便点的数据结构，这里就暂时按照原理来操作，之后如果有优化的必要再说吧）

那么，最新版本的zig下的table的代码其实并没有什么变化（主要是将其构造函数改为了返回所有权而非具有所有权的指针，其差别在于是否可以安全的赋值给某个指针）：

按照原文的要求，我们需要一个用于解释程序的函数，该函数接收一个成员的根节点（暂时先这么称呼吧），解释并执行相关的语句和表达式

同时，根据原文对于函数式的要求，我们需要在这函数内部创建table（一下内容涉及指针，解引用等功能，代码未必安全，可能会碰到一些各位当年学c的时候的老朋友，例如segmentation fault之类的，但由于zig本身一定的保证安全性的方案，故而错误不会那么明显）：

首先是这个作为入口的函数，初始化一个空的链表头节点（主要该节点为空，不代表不需要分配内存给它，有些人可能会直接undefined，但后面在遍历链表的时候需要不断的对tail进行解引用，而最开始的节点会在最后，如果它是undefined则会因此崩溃，当然你也可以在后续第一次使用到的时候再初始化，但这貌似违背了函数式编程的规矩）

然后是stm和exp的两个解析函数（稍微加了一点调试用的信息）：

stm的解析函数

exp的解析函数：

这里就不展开讲解代码了，主要需要注意的就是zig的指针默认都是*const，故而不能被另一个指针赋值，只能通过解引用赋值，这样虽然可以解决部分垂悬引用的问题，但会将一部分问题转化为内存泄漏问题，由于zig的字符串不能直接比较，所以这里用了zig的cstr来比较字符串（其实可以使用内存操作来比较），此外，可以看到除法这里调用了一个内置函数，这不是在下特立独行，而是当前版本的zig追加了新的规定，即两个整数类型不能直接使用/进行除法，只能在四个内置的除法函数中选择一个进行调用，具体的可以查看zig的官方文档，这里将绝大部分的错误处理都写成了catch unreachable，主要是这些错误都是内存错误，本就是会导致程序崩溃的，后续处理并不是十分重要，如果需要的话，将unreachable替换为@panic("xxx")即可

至于课后练习的问题，由于当前版本很多针对指针的功能受到了默认不可变指针的影响导致现在很多使用指针的地方需要考虑将不可变指针转换为可变指针，此时使用一层Option类型套在Node外面别说是新手了，我写了这么久代码，我都很头疼你可能会碰到亿点点的expect type *xxx, found *const xxx，如果此时调用内部函数还可能返回error union的话，简直是地狱，代码可读性断崖式下跌，所以这里我们不妨使用zig内置的optional类型来写这个二叉搜索树。

那么，此时该二叉搜索树大概长这样：

member函数可能长这样（这里我们的树存储了一个值，所以查找函数也将返回一个值，而非简单的true或者false）

编写测试验证代码是否正确：

实际上在下对于题目的理解可能有误，member这里也可能是查找的某一个节点是不是树的一员，由于我们一开始的实现就是包含值的，所以这里我们实现的member其实就是第二个问题要求的lookup，而insert一开始就是符合第二题要求的

第三个问题其实很简单，这里在下甚至都不需要具体的例子来说明，简单的描述就是，但我们构建一个二叉搜索树的时候，我们希望它尽可能的是一个树形结构，但有时候如果一组数据非常规整，甚至特殊情况下就是拍好顺序的，此时你可能会得到一个链表，此时时间复杂度上升，资源占用还多余链表，此时就需要我们在构建二叉搜索树的时候尽量让其保持树形，即保持其平衡性

然后最后一个问题，为其实现平衡性，一种立刻就能想到的办法就是记录当前的深度和节点数量，以此判断该树是否平衡，并以此来进行自动排序，也就是题干中所说的自调整树，但该实现非常OOP，不符合函数式规范，故而被出题者禁止了。但同时出题人提出了应当在插入时保持平衡，那么我们也可以很快想到一种实现，即根据左右子树的深度判断是否需要重排，然后分别实现左右两种旋转函数

那么统计高度的函数：

左右选择的函数：

修改后的insert函数：

本来打算习题和下一章一起更新的，但仅仅习题就花费了如此长的篇幅，那么就分开更新吧