# Scheme_Interpreter_Cpp **Repository Path**: iamttp/Scheme_Interpreter_Cpp ## Basic Information - **Project Name**: Scheme_Interpreter_Cpp - **Description**: An extremely simple Scheme interpreter writen by C++ - **Primary Language**: C++ - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2020-03-27 - **Last Updated**: 2020-12-19 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 两天实现一门编程语言———简陋解释器教程 ![avictor](1.png) ## 关于： 参考文章: `http://zh.lucida.me/blog/how-to-implement-an-interpreter-in-csharp/` 该代码还有一些bug，这篇文章主要是记录解释器的实现过程。详情一定参考上面的文章，这篇文章主要给你C/C++实现提供一种思路。 bug包括但不限于（好怂呀 (ノ｀Д)ノ）： 1. iScheme的解释器对iScheme所有定义的变量，常量（字面量和具名量）都没有考虑析构（delete） 这对于大程序应该是致命的。 2. 没有完善的错误处理机制。 3. 语言特性方面有欠缺，具体看我参考的文章。 其他我发现的bug已经解决了，递归也可以了。但是测试Scheme时请一定**仔细检查你的小括号**(技巧：左括号马上跟你想判断的操作)，太闹心了！！！ 编程环境是: `CLion2019.3`,`Win10`,`MinGW`。 如果需要使用交互界面（类似于python那个），不推荐在Clion的命令行直接运行，格式打印有问题，不好看。 ## 解释器构造 ### 词法分析 首先直接用`replaceAddWhite`函数给`(` `)`添加空格。 然后`getTokens`分割得到token(自我感觉比C#的库函数快一点，可能吧 /W\ ) ### 语法树生成 首先定义每个结点的类型`SExpression`。 然后函数 `parseAsIScheme` parse的时候和上面参考文章是一样的。非常巧妙的遇到`(`下一层，遇到`)`上一层。 ### 作用域 作用域可以参考这篇文章：`https://www.jianshu.com/p/9536b75181d5` 每进入一个函数域，或者是每次声明局部变量，都会新建一个符号表， 作为当前的计算环境，并存储上一个环境的地址。 在需要查找符号表的时候，先在当前环境查找，找不到再到前一个环境中查找。 每个域都只保存自己的环境地址，所以不会影响到其它域的使用。 而新建作用域应该是只有初始化，`def`定义，`func`定义才可以用。 这里的作用域直接用的`SScope`，包含一个用于向前查找的指针和一张变量表，map应该是红黑树，效率杠杠滴。 变量表是用`std::map variableTable;`定义的。 我的打算是指针无敌，指哪打哪，速度快 （￣︶￣）↗　，就是看着头疼，而且危险。 ### 类型实现 我直接用的C++的int保存iScheme的数值和Bool型， 将`std::vector vec;`封装为一个结构体表示iScheme的列表，方便添加功能。（指针当元素，有种python的感觉） 函数则是用`SFunction`结构体实现的，保存函数体指针、参数符号（形参的`string`）、作用域指针。 --- ### 内置操作和执行逻辑 这这两步我放一起了（其实是不知道怎么分开），核心函数`evaluate`。 没有将这一函数设置为`SExpression`的方法，不想太面向对象，耽误了效率（好吧，其实面向对象我只能叫入门） 还有就是`evaluate`里面好多跳转语句呀，怎么提高程序效率呀！！！ #### 处理字面量和具名量 叶节点就是字面量和具名量了，直接判断`child`是否为空，为空后再判断是否为`digits`。 如果是数字则返回指针（原来这就是一切皆对象呀！解释程序太低效率了吧！），每次都得去内存里面取，而不是直接编译后传给寄存器。 如果是变量则通过作用域查找变量的值（这个值是通过`scope->define`函数定义的，在iScheme里面写`def`就会调用）。 #### 算数操作和逻辑操作和比较操作 这三类操作不费太多精力，写好一个，复制粘贴一把梭。( •̀ ω •́ )y 特点就是+,-,*,/,and,or,not都是多操作数的，直接遍历就好。这些操作的结果也是直接new的，内存访问，而且没有delete /W\ #### 列表操作 iScheme 的列表操作包括 `first` ， `rest` ， `empty?` 和 `append` ，我只实现了前三个，头晕 当定义`list`的时候，直接计算参数后插入，注意first和rest都是深拷贝的。 #### def操作，if操作，begin操作 def操作会给当前的作用域添加一层，并在新层添加def定义的变量 if操作会根据condition的结果（实质是化为int存储在内存里面的1或者0）,来选择 begin操作会顺序执行，并将最后执行的结果返回。 #### func操作 这个操作和`SFunction`密切相关。定义函数位于`else if (str == "func") `分支，调用函数位于`else` 分支。 仔细想想，Scheme的思想应该是函数和变量统一的（我刚学了半小时 (lll￢ω￢) ），它们都是Scheme的使用者自己定义的，不能提前写好分支。 但是调用（使用）变量一定是叶节点，它就可以放在叶节点的else里面，调用函数一定不是叶节点（是不是呢？），它就放在非叶节点的else里面。 而它们的定义`def` `func`则直接在非叶节点里面定义好分支了。（再次问下，怎么做才能高效率访问呀？） --- 回过头来，`func`操作就是分别赋值函数体、参数（形参）、新的作用域（防止调用函数添加变量表，影响到原先的作用域）。 然后是函数调用操作，位于else分支，分为非具名函数调用如：`((func (x) (* x x)) 3)`，具名函数调用如：`(square 3)`。 计算实参的值后，传入`arguments`。然后根据`arguments`,直接设置变量表。并递归计算函数体和新的作用域。