26 个回答
题主原本的问题:
我想自己用C/C++做一个脚本语言 解析器 ,但是不知道需要什么知识?
首先,请问题主想写的是“解析器”(parser)还是“解释器”(interpreter)?
在编程语言实现的上下文里,“解析”其实通常是指“语法分析”;“解释”才是跟执行代码相关的名词。这俩名词经常被各种混用,是不对的。
其次,编译器跟解释器是怎样的关系,我想放这个传送门:
Java为什么解释执行时不直接解释源码? - RednaxelaFX 的回答里面我举了个简单的例子讲一个“一般的编译器”的工作流程是如何可以一点点转变为一个“解释器”。可以看到,解释器里许多概念其实还是跟编译器共同的,只是有些事情可以省略不做,或者本来应该在编译器里做的分析留到了运行时由解释器来做而已。具体请跳传送门看。
再次,写解释器需要怎样的知识。前面有不少靠谱的答案,题主可以参考它们先练手试试看。
像是说写个简易的LISP实现/Scheme实现,很容易上手。这条路子读读
《Structure and Interpretation of Computer Programs》和
《The Little Schemer》作为辅助都挺好。
如果想实现个类似C的语法的命令式语言的解释器,那可以从最基础的地方出发慢慢练习。下面是一个假想的顺序:
- 简单的四则混合运算计算器,支持加减乘除、运算符优先级(乘除优先于加减、括号。例如可以运算 "12+3*5-6" 这样的表达式,不用考虑空格之类的问题。
- 此时需要的知识非常简单:知道如何使用数据结构的“栈”就可以了。用两个栈就可以求出这样表达式的值,一个用来放操作数,一个用来放运算符;这种算法叫做 Shunting-yard algorithm 。“词法分析”“语法分析”之类的概念都可以先不用管——尽管这个概念中实际上已经做了词法和语法分析,但还很简单,不用特别学什么。
- 在上述基础上扩展,更好的支持“词法分析”的概念,例如允许空格的出现
-
继续扩展,添加变量、赋值的支持。此时可以解释执行像是:
a = 1 + 2; b = a + 3 * 4;
- 更正式的语法分析:要能切分出赋值语句,然后里面的混合运算还是跟之前一样处理
- 变量表:要有一个记录 (变量名 -> 值) 的表
- 继续扩展,添加控制流语句,例如 if-else 语句。事情从这里开始就好玩了:之前的步骤里,所有代码都会按顺序被执行;而一旦添加了控制流语句的支持,输入的程序里就可能会有一些被条件执行,这要如何处理就有许多发挥空间了,例如说要不要引入抽象语法树(AST)。
- 续集扩展,支持循环语句。
- 续集扩展,支持函数的声明与调用。
做完上面步骤之后,一个初具雏形的解释器就出来了。
正巧,近来
@许式伟做的
《一周一语言》演讲也是以类似的思路演化出一门语言的解释器实现。题主感兴趣也可以参考他的经验。
他做的qlang解释器的实现思路我在另一个回答里也提到了一点,有兴趣请读读看:
有哪些关于c4 - C in four function 编译器的文章? - RednaxelaFX 的回答