90分钟实现一门编程语言——极简解释器教程

王朝学院·作者佚名  2016-05-16
窄屏简体版  字體: 小  |  中  |  大  |  超大  

90分钟实现一门编程语言——极简解释器教程关键字解释器, C#, Scheme, 函数式编程

关于本文介绍了如何使用C#实现一个简化但全功能的Scheme方言——iScheme及其解释器,通过从零开始逐步构建,展示了编程语言/解释器的工作原理。

作者Lucidaa.k.aLuc

如果你是通过移动设备阅读本教程,或者认为本文的代码字体太小的,请使用该链接以获得更好的可读性(博客园的markdown解析器实在诡异,这里就不多吐槽了)。

提示如果你对下面的内容感兴趣:

实现基本的词法分析,语法分析并生成抽象语法树。实现嵌套作用域和函数调用。解释器的基本原理。以及一些C#编程技巧。那么请继续阅读。

如果你对以下内容感兴趣:

高级的词法/语法分析技术。类型推导/分析。目标代码优化。本文则过于初级,你可以跳过本文,但欢迎指出本文的错误 :-)

代码样例代码示例

public static int Add(int a, int b) { return a + b;}>> Add(3, 4)>> 7>> Add(5, 5)>> 10

这段代码定义了Add函数,接下来的>>符号表示对Add(3, 4)进行求值,再下一行的>> 7表示上一行的求值结果,不同的求值用换行分开。可以把这里的>>理解成控制台提示符(即Terminal中的PS)。

什么是解释器

解释器(InterPReter)是一种程序,能够读入程序并直接输出结果,如上图。相对于编译器(Compiler),解释器并不会生成目标机器代码,而是直接运行源程序,简单来说:

解释器是运行程序的程序。

计算器就是一个典型的解释器,我们把数学公式(源程序)给它,它通过运行它内部的"解释器"给我们答案。

iScheme编程语言iScheme是什么?

Scheme语言的一个极简子集。虽然小,但变量,算术|比较|逻辑运算,列表,函数和递归这些编程语言元素一应俱全。非常非常慢——可以说它只是为演示本文的概念而存在。OK,那么Scheme是什么?

一种函数式程序设计语言。一种Lisp方言。麻省理工学院程序设计入门课程使用的语言(参见MIT 6.001和《计算机程序的构造与解释》)。

使用波兰表达式(Polish Notation)。更多的介绍参见Scheme编程语言。以计算阶乘为例:

C#版阶乘

public static int Factorial(int n) { if (n == 1) { return 1; } else { return n * Factorial(n - 1); }}

iScheme版阶乘

(def factorial (lambda (n) ( if (= n 1) 1 (* n (factorial (- n 1))))))

数值类型由于iScheme只是一个用于演示的语言,所以目前只提供对整数的支持。iScheme使用C#的Int64类型作为其内部的数值表示方法。

定义变量iScheme使用def关键字定义变量

>> (def a 3)>> 3>> a>> 3

算术|逻辑|比较操作与常见的编程语言(C#, java, C++, C)不同,Scheme使用波兰表达式,即前缀表示法。例如:

C#中的算术|逻辑|比较操作

// Arithmetic opsa + b * ca / (b + c + d)// Logical ops(cond1 && cond2) || cond3// Comparing opsa == b1 < a && a < 3

对应的iScheme代码

; Arithmetic ops(+ a (* b c))(/ a (+ b c d)); Logical ops(or (and cond1 cond2) cond3); Comparing ops(= a b)(< 1 a 3)

需要注意的几点:

iScheme中的操作符可以接受不止两个参数——这在一定程度上控制了括号的数量。iScheme逻辑操作使用and,or和not代替了常见的&&,||和!——这在一定程度上增强了程序的可读性。顺序语句iScheme使用begin关键字标识顺序语句,并以最后一条语句的值作为返回结果。以求两个数的平均值为例:

C#的顺序语句

int a = 3;int b = 5;int c = (a + b) / 2;

iScheme的顺序语句

(def c (begin (def a 3) (def b 5) (/ (+ a b) 2)))

控制流操作iScheme中的控制流操作只包含if。

if语句示例

>> (define a (if (> 3 2) 1 2))>> 1>> a>> 1

列表类型iScheme使用list关键字定义列表,并提供first关键字获取列表的第一个元素;提供rest关键字获取列表除第一个元素外的元素。

iScheme的列表示例

>> (define alist (list 1 2 3 4))>> (list 1 2 3 4)>> (first alist)>> 1>> (rest alist)>> (2 3 4)

定义函数iScheme使用func关键字定义函数:

iScheme的函数定义

(def square (func (x) (* x x)))(def sum_square (func (a b) (+ (square a) (square b))))

对应的C#代码

public static int Square (int x) { return x * x;}public static int SumSquare(int a, int b) { return Square(a) + Square(b);}

递归由于iScheme中没有for或while这种命令式语言(Imperative Programming Language)的循环结构,递归成了重复操作的唯一选择。

以计算最大公约数为例:

iScheme计算最大公约数

(def gcd (func (a b) (if (= b 0) a (func (b (% a b))))))

对应的C#代码

public static int GCD (int a, int b) { if (b == 0) { return a; } else { return GCD(b, a % b); }}

高阶函数和Scheme一样,函数在iScheme中是头等对象,这意味着:

可以定义一个变量为函数。函数可以接受一个函数作为参数。函数返回一个函数。iScheme的高阶函数示例

; Defines a multiply function.(def mul (func (a b) (* a b))); Defines a list map function.(def map (func (f alist) (if (empty? alist) (list ) (append (list (f (first alist))) (map f (rest alist))) ))); Doubles a list using map and mul.>> (map (mul 2) (list 1 2 3))>> (list 2 4 6)

小结对iScheme的介绍就到这里——事实上这就是iScheme的所有元素,会不会太简单了? -_-

接下来进入正题——从头开始构造iScheme的解释程序。

解释器构造iScheme解释器主要分为两部分,解析(Parse)和求值(Evaluation):

解析(Parse):解析源程序,并生成解释器可以理解的中间(Intermediate)结构。这部分包含词法分析,语法分析,语义分析,生成语法树。求值(Evaluation):执行解析阶段得到的中介结构然后得到运行结果。这部分包含作用域,类型系统设计和语法树遍历。词法分析词法分析负责把源程序解析成一个个词法单元(Lex),以便之后的处理。

iScheme的词法分析极其简单——由于iScheme的词法元素只包含括号,空白,数字和变量名,因此C#自带的String#Split就足够。

iScheme的词法分析及测试

public static String[] Tokenize(String text) { String[] tokens = text.Replace("(", " ( ").Replace(")", " ) ").Split(" \t\r\n".ToArray(), StringSplitOptions.RemoveEmptyEntries); return tokens;}// Extends String.Join for a smooth API.public static String Join(this String separator, IEnumerable<Object> values) { return String.Join(separator, values);}// Displays the lexes in a readable form.public static String PrettyPrint(String[] lexes) { return "[" + ", ".Join(lexes.Select(s => "'" + s + "'") + "]";}// Some tests>> PrettyPrint(Tokenize("a"))>> ['a']>> PrettyPrint(Tokenize("(def a 3)"))>> ['(', 'def', 'a', '3', ')']>> PrettyPrint(Tokenize("(begin (def a 3) (* a a))"))>> ['begin', '(', 'def', 'a', '3', ')', '(', '*', 'a', 'a', ')', ')']

注意个人不喜欢String.Join这个静态方法,所以这里使用C#的扩展方法(Extension Methods)对String类型做了一个扩展。相对于LINQ Syntax,我个人更喜欢LINQ Extension Methods,接下来的代码也都会是这种风格。不要以为词法分析都是这么离谱般简单!vczh的词法分析教程给出了一个完整编程语言的词法分析教程。语法树生成得到了词素之后,接下来就是进行语法分析。不过由于Lisp类语言的程序即是语法树,所以语法分析可以直接跳过。

以下面的程序为例:

程序即语法树

;(def x (if (> a 1) a 1)); 换一个角度看的话:( def x ( if ( > a 1 ) a 1 ))

更加直观的图片:

这使得抽象语法树(Abstract Syntax Tree)的构建变得极其简单(无需考虑操作符优先级等问题),我们使用SExpression类型定义iScheme的语法树(事实上S Expression也是Lisp表达式的名字)。

抽象语法树的定义

public class SExpression { public String Value { get; private set; } public List<SExpression> Children { get; private set; } public SExpression Parent { get; private set; } public SExpression(String value, SExpression parent) { this.Value = value; this.Children = new List<SExpression>(); this.Parent = parent; } public override String ToString() { if (this.Value == "(") { return "(" + " ".Join(Children) + ")"; } else { return this.Value; } }}

然后用下面的步骤构建语法树:

碰到左括号,创建一个新的节点到当前节点(current),然后重设当前节点。碰到右括号,回退到当前节点的父节点。否则把为当前词素创建节点,添加到当前节点中。抽象语法树的构建过程

public static SExpression ParseAsIScheme(this String code) { SExpression program = new SExpression(value: "", parent: null); SExpression current = program; foreach (var lex in Tokenize(code)) { if (lex == "(") { SExpression newNode = new SExpr

 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
© 2005- 王朝網路 版權所有 導航