数值求值的栗子:
LISP Javascript
(+ 3 2) (3 + 2)
(- 7 1) (7 - 1)
(/ (- 72 10) (+ 4.5 2)) ((72 - 10) / ( 4.5 + 2))
如果某一天我们脑洞大开,想使用LISP的语法形式去编写Javascript,或许我们会使用到编译原理,将LISP语法形式的代码编译成Javascript。就像我们编写ES6标准的代码,通过Babel编译成浏览器都支持的ES5标准一样,这非常有趣。那么编译原理对于Javascript开发者有用吗?其实编译原理在很多开源项目上都进行了使用,比如Bebel、TypeScript、CoffeScript、Flow等等,可见掌握一些编译原理对于理解它们是很有用的一件事情。如上是一个数值求值的例子,接下来将演示将如上LISP语法编译为Javascript语法的整个编译过程。源码见https://github.com/jan-wong/tiny-compiler
一般而言,编译原理会被划分为三个阶段:解析(解析又分为词法分析(tokenize)、语法分析(parse))、转换(transform)、代码生成(code generation)
词法分析器的作用是将输入(input)的字符串序列划分成一个个标记对象(token)组成的数组,以便进行语法分析,标记对象包含标记类型和标记的字面值。标记是什么?标记是源代码的最小单位,一般用空格分开。编程语言的标记种类是有限的,比如有数据类型(字符串、数值、数组等)、操作符(算数操作符、比较操作符、逻辑操作符等)、分隔符(逗号、分号、括号等)、保留字、标识符等等。对'(/ (- 72 10) (+ 4.5 2))'进行词法分析可以得到如下, 源码见tokenize.js:
[ { type: 'parren', value: '(' },
{ type: 'arith', value: '/' },
{ type: 'parren', value: '(' },
{ type: 'arith', value: '-' },
{ type: 'number', value: '72' },
词法分析(tokenize) { type: 'number', value: '10' },
'(/ (- 72 10) (+ 4.5 2))' =================>>> { type: 'parren', value: ')' },
{ type: 'parren', value: '(' },
{ type: 'arith', value: '+' },
{ type: 'number', value: '4.5' },
{ type: 'number', value: '2' },
{ type: 'parren', value: ')' },
{ type: 'parren', value: ')' } ]
语法分析器的作用是将输入标记数组(tokens)重新格式化,让标记与标记之间形成关联,最后形成程序、语句或者表达式。我们会用一棵树来描述这种形成相互关系的程序,这棵树唤做抽象语法树(AST)。继续进行语法分析,过程如下,源码在parse.js:
{"type": "program",
"body": [
{
"type": "arithCall",
"name": "/",
[ { type: 'parren', value: '(' }, "params": [
{ type: 'arith', value: '/' }, {
{ type: 'parren', value: '(' }, "type": "arithCall",
{ type: 'arith', value: '-' }, "name": "-",
{ type: 'number', value: '72' }, "params": [
{ type: 'number', value: '10' }, 语法分析(parse) { "type": "number", "value": "72" },
{ type: 'parren', value: ')' }, ==================>>> { "type": "number", "value": "10" }
{ type: 'parren', value: '(' }, ]
{ type: 'arith', value: '+' }, },
{ type: 'number', value: '4.5' }, {
{ type: 'number', value: '2' }, "type": "arithCall",
{ type: 'parren', value: ')' }, "name": "+",
{ type: 'parren', value: ')' } ] "params": [
{ "type": "number", "value": "4.5" },
{ "type": "number", "value": "2" }
]
}
]
}
]}
转换器的作用是将符合LISP语法的语法树(AST)转换为符合Javascript语法的语法树。转换后如下:
{
"type": "program",
"body": [
{
"type": "arithExpression",
"name": "/",
"arguments": [
{
"type": "arithExpression",
"name": "-",
"arguments": [
{ "type": "number", "value": "72" },
{ "type": "number", "value": "10" }
]
},
{
"type": "arithExpression",
"name": "+",
"arguments": [
{ "type": "number", "value": "4.5" },
{ "type": "number", "value": "2" }
]
}
]
}
]
}
代码生成器的作用是将newAst生成javascript语法形式的代码。具体实现参考generation.js,结果如下:
((72 - 10) / (4.5 + 2))