只有咸鱼看不懂的解释器科普 第一步:解析

嗯,这篇文章是我用来介绍自己的解释器 ika 的,不是宜家是乌贼娘!

ika

ika 其实没有什么独创的设计思想都是抄袭来的,所以我觉得要介绍还不如写一篇科普文。

当然这篇科普文会比较简略,毕竟我也扯不出那么多嘛,不过看完了,虽然不能让你闭着眼睛写一门语言,不过该给你的都会给你……吧。

好吧,现在开始。(文中图片均由万恶的微软出品的万恶软件 Visio 画出,免费的正版哦,微人希)

解释器,也就是运行一个程序语言的程序啦。

编译器,是把一种程序语言翻译成另一种程序语言的程序,比如说你把 C 里面的 & 改成“萌萌哒”,并声称这是一种新的萌萌哒语言,那么你只需要写一个把字符串字面量(也就是代码里面被引号框起来的那部分)以外的“&”字符串替换成“萌萌哒”的程序,你就得到了 C -> 萌萌哒语言 编译器。

总而言之言而总之,一个解释器或者编译器的第一步是什么?嗯,你编程实际上就是打字,打出来的都是字符串(当然忽略一些奇葩语言,比如说图形化编程的语言),不管是解释器还是编译器,总不可能直接处理这些字符串的(当然忽略一些奇葩语言,比如说上面的萌萌哒语言),他们会吧字符串转化成便于处理的树状结构(这东西叫 AST,抽象语法树的意思),比如说下面的代码:

解析后所生成的树大概是这样:

ast

很好理解吧?仅仅是把你的字符串转化成程序内部的数据结构而已,但是基本没有任何处理,不会处理成这样:

compiled

这是很多很多步以后的事情了。

这种转换叫做解析(Parse),进行这种转换的程序叫做解析器(Parser)看起来这种转换不麻烦,但实际上还是挺麻烦的,比如说这样的代码:

仔细看看,就可以知道,解析过程是要涉及到两个难点的,一个是递归,一个是回溯。

递归就是为了处理表达式的嵌套,回溯是为了处理诸如运算符优先级之类的情况,就是里面的 2 + 20 * 2 ,2+20 解析出来了,碰到一个 * 就要丢弃原本的结果。还有各种边界条件什么的,因为解析器是直接处理用户的代码,和用户打交道就是这样那样的麻烦事一堆。

插句题外话,之所以 Lisp 的语法那么酷炫,就是因为 Lisp 其实没有语法的,程序员就直接在写树状结构的特殊 AST (S-表达式),所以 Lisp 家族的语言解析器要处理的东西比绝大多数语言都少,我之前只用了几行就写出了一个基本的S-表达式解析器(当然要借助后文的解析器生成器):

言归正传,我手写了几次以后,还是投入到解析器自动生成程序的怀抱,你只用给程序一些规则,程序就会自动按照这种规则生成解析器,非常棒。

常用的解析器生成器,有著名的 Yacc,被很多人推荐的 ANTLR,各种语言还有自己的工具,比如说我之前推荐的 pyPEG

至于如何解析,首先你需要做的是分词:

需要被转换成:

这样的字符串列表,这些列表的元素被称为语素(Token),如果不这样做的话,如果你遇到" printf () "这样的情况你就会处理错误。执行这一步的程序叫词法分析器(Lexical analysis,Lexer,Tokenizer)。

自此,程序员单挑的两个关键元素就介绍完成了!

实际上 Lexer 有的时候是分离的,有的时候是和 Parse 一起执行的,要用 Lexer ,你首先要懂得正则表达式

那么 Parse 的规则是怎么样的呢?一般使用 BNF 文法。但是还是太抽象了,我把这种规则用图片来表示:

exprrule

解析规则也是树形的。(这里没处理括号,运算符优先级之类的情况。)

但是和上面说的 AST 不同,注意看,这个树形的解析规则是自指的,里面有好几个节点引用了自己。

另外,这个图片里面的两个框图:顺序排列和析取,可以用来把多个语法元素组合成一个新的语法元素,也是语法规则中最重要的一部分。

基本上,把这个语法规则塞进 Parser 生成器,就会给你吐出来一个 Parser,你把代码塞进 Parser 里面,就会吐出来 AST,然后把 AST 放进求值器(evaluator),求值器就会吐出来程序运行结果。

解析的部分就讲到这里了,之后几篇都会把注意力放到求值器上面。

只有咸鱼看不懂的解释器科普 第一步:解析》上有8条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注