初识编译器设计

最近终于开始自己动手写编译器了。老师给了一个名为 SIMPLE 的语言，叫我们写一个词法分析和语法分析。我是用 C++ 写的，刚刚把语法分析做出来了，总的来说还是有点心得的。

词法方面更多的还是参照了《编译原理与实践 (Compiler Construction Principles and Practice, Kenneth C. Louden) 》的 TINY Compiler，原因主要还是因为对编译器不熟，现在有比较成熟的方法，先拿来再说。分析的方法还是先在纸上构造出相应的 DFA，然后用一个 switch 语句选择各种状态分别处理。实际编写的时候，还是发现了很多和 TINY 不同的地方，所以自己也在他的基础上进行了修改。

我们的 SIMPLE 语言比 TINY 要复杂很多（Simple > Tiny ?），所以语法分析方面，相应的函数也多了很多。语言是符合 LL(1) 文法的，所以用的还是递归下降分析法（后来发现，其实还是有一个表达式不符合 LL(1)，不过找到了解决办法）。因为有一个非终结符的两个候选式的 First 集合有交集，所以一时想不到该怎么去选择候选式。后来发现，可以用以下办法解决这个问题：将两个候选式 First 集合的交集抽出来，如果一个候选式可以推出另一个候选式（前者比后者大），那么在遇到交集里的终结符时，选择大的候选式。其他的非交集部分则选择各自候选式。举个例子：

abc → id | | id relation id | arith_exp relation arith_exp

arith_exp 是算术表达式，可以是 id + id，也可以是 id，还可以是 id + num，等等。可以看出，由于 arith_exp 和 id 的 First 集合具有交集 id，如果当前符号是 id，则不知道应该选择哪一个候选式。因为 arith_exp 可以推出 id，所以我把上式改成了

abc → arith_exp [relation arith_exp]

因为如果满足了 id，则一定满足 arith_exp，反之如果满足 arith_exp，不一定满足 id。事实上，上面的例子只是一个简化了的表达式，实际中还要考虑一些其他因素，不过总的思路就是这样了。当然，最好的方法还是仔细的设计标准的 LL(1) 文法，这也算是一点教训吧。