本次习题可能对于初学者比较困难, 量力而行. 在阅读之前, 读者最好了解一下什么是BNF文法.
本来想想应该放一个参考实现, 想想还是算了. 为了能够简单明了地写出程序, 读者最好要了解一下模式匹配这样的语言功能, 但即便不使用它, 只要理解基本的原理, 写起来也很简单.
更新: Racket中的参考实现 (只考虑理解, 不考虑效率):
让我们来看一个例子 (加了一行输出中间过程的代码, 为了便于读者理解):
其中用到了一个用于模式匹配的宏match:
