如何从0到1实现一门语言

July 26, 2019

语言就是程序员的酒精/Languages are alcohol to programmer。🍺 ⏤ wener

DSL

DSL 全名为 Domain-specific Lnaguage/领域特定语言,说到 domain-specific 会不会第一个想到的是 DDD 呢?DDD 中的语言叫做 Ubiquitous Language,即通用语言,指的是在当前 Domain 下使用统一的自然语言进行沟通交流便于上下文的理解和沟通。DSL 的目的是非常类似的,为特定领域实现的语言,目的是为了更加高效便捷的解决特定领域的问题。

DSL 是领域特定语言,与之相反的语言叫做 General purpose language/通用语言。通用语言均为图灵完备语言,而DSL则不必要具备这样的能力。一个通用语言也有其特定的应用领域,例如 系统编程、Web编程、脚本 等,来区别于其它语言,因此某种程度上来说通用语言也是“DSL”。

常见的DSL

语言领域
JSON数据交换
CSS样式编排
SQL结构查询
JSX结构化组件

但无论领域为何,DSL本质是语言,有特定的词法、语法和上下文逻辑。当需要实现一种DSL语言时,需要考虑

  • 语言的目的
  • 期望的语法词法
  • 处理逻辑

驱动实现一门语言,往往因为

  • 设计理念不同
  • 更安全可控 - 限制语言能力
  • 为应用提供更加灵活的处理能力 - 脚本
  • 扩展现有语言增强表达能力 - 转译 - JSX、TS
  • 利用现有的运行环境实现更简洁高效的语言 - Kotlin、Elixir
  • 能够更快更容易的解决/描述特定领域问题 - DSL

目的不同驱动实现的方式也各不相同,每种的做法也不尽相同,在这里以实现一个简单的数学计算语言作为演示。

实现一门语言

  • 目的: 实现简单的数值计算,支持基本的三角函数
  • 语言 数学操作支持 加减乘除 三角函数支持 sin、cos * 运行时数值类型均为双精度浮点数

当语言的基础确定后,需要将语言的语法以某种形式表现出来,表现语言语法的方式也是使用一门语言(♻️😄)。EBNF - 扩展巴科斯范式,语法表述如下

表达式 = 操作符表达式 | 函数表达式 | 数值
操作符表达式 = 表达式 操作符 表达式
函数表达式 = 函数名 ( 表达式 )
操作符 = + | - | * | /
数值 = 一个或多个 数字
数字 = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

语法能用通用的 EBNF 表述出来,在各种语言里面有实现类似 EBNF 表达语言语法结构的库,在这里使用 pegjs 来进行原型验证和实验。

在 pegjs 的在线Demo我们可以看到已经有一个支持数学运算的语言。现将左侧语法替换为将要实现的语法描述

表达式 = 加减表达式
加减表达式 = 乘除表达式 (('+' / '-') 乘除表达式)*
乘除表达式 = 函数表达式 (('*' / '/') 函数表达式)*
函数表达式 = 函数名 '(' 表达式 ')' / 数值
数值 = [0-9]+
函数名 = [a-z]+

💡 PEG 细心的你可能会发现我们这里定义的语法与 EBNF 有一定区别,例如单独定义了 加减表达式,乘除表达式,并且是自顶向下嵌套的,而不是 EBNF 的 表达式 = 操作符表达式 | 函数表达式 | 数值 一层直接展开。

之所以书写成这样,是因为 pegjs 是 PEG 类的解析器,不能做左递归。该细节涉及到如何实现语言解析和语法的优先级处理,将会在额外的文章中进行阐述解释,并讲解如何实现一个解析语言的语言。

然后在右上输入表达式 sin(1)*2+3, 解析完成后,右下角出现如下 JSON 内容

[
[
[
[ "s", "i", "n" ], "(", [ [ [ "1" ], [] ], [] ], ")"
],
[ [ "*", [ "2" ] ] ]
],
[
[ "+", [ [ "3" ], [] ] ]
]
]

该 JSON 是 pegjs 的输出,在没做任何处理的情况下,也可以理解为语法树。其中每一个数组对应了语法描述中的一个定义。例如 [ "s", "i", "n" ], "(", [ [ [ "1" ], [] ], [] ], ")" 对应语法树中的 函数名 '(' 表达式 ')',表示对1执行函数sin

为了更好的展示语法树,我们在语法树中调整返回结果

表达式 = 加减表达式
加减表达式 = a:乘除表达式 b:(op:('+' / '-') right:乘除表达式 {return {type:'Op',op,right}})* {return b.reduce((left,right)=>(right.left=left,right),a)}
乘除表达式 = a:函数表达式 b:(op:('*' / '/') right:函数表达式 {return {type:'Op',op,right}})* {return b.reduce((left,right)=>(right.left=left,right),a)}
函数表达式 = name:函数名 '(' arg:表达式 ')' {return {type:'Func',name,arg}} / 数值
数值 = [0-9]+ {return {type:'Int',value:parseInt(text())}}
函数名 = [a-z]+ {return {type:'Name',name:text()}}

对同样的表达式 sin(1)*2+3 我们得到的语法树为

{
"type": "Op",
"op": "+",
"left": {
"type": "Op",
"op": "*",
"left": { "type": "Func", "name": { "type": "Name", "name": "sin" }, "arg": { "type": "Int", "value": 1 } },
"right": { "type": "Int", "value": 2 }
},
"right": { "type": "Int", "value": 3 }
}

这时候看上去更像是树的结构,type 为每个节点的类型。

  • Func 函数调用节点 - 有 name 和 arg 属性
  • Op 数学操作符节点 - 有 op、left、right 属性
  • Int 数值节点 - 有 value 属性
  • Name 名字节点 - 有 name 属性

语法结构表现的内容与表达式本身是完全等价的,可认为是程序/计算机理解的表达式,是更加结构化的内容。 语法树会有很多应用场景,因为语法树与表达式等价,也包含了完整的计算逻辑和上下文信息,并且不需要解析器进行解析。可用于生成更加底层的表现形式,也可用于直接执行。场景的场景包含

  • 生成 IR - 中间形式,便于进行更多后续处理 - .Net、GnuRTL、LLVM
  • 生成汇编 - 生成能直接在目标平台执行的二进制 - x86
  • 代码转译 - 利用一定的规则生成非原始类型代码 - Gwt(Java to Js)、java2objc
  • 代码优化 - 语法树结构比较通用,程序便于处理,可利用公共的规则进行匹配判断
  • 代码简化 - 在不影响语义的情况下调整代码 - UglifyJs、代码混淆 - 生成原始类型代码
  • 代码分析 - 静态类型、安全、“坏”代码检测
  • 代码索引 - 一般生成的语法树节点都可以包含原始代码位置,可实现基于方法或引用等进行快速索引 - sourcegraph
  • 代码预处理
  • ...

表达式转换成语法树,就好比使用机器学习从自然语言中抽取出意图、实体、上下文等信息,是计算机对理解“人”要做什么的第一步。

既然同样的语法能调整为生成语法树,那么也就能调整为直接计算结果,因此得到如下内容

表达式 = 加减表达式
加减表达式 = a:乘除表达式 b:(('+' / '-') 乘除表达式)* {return b.reduce((r,[o,v])=>o=='+'?r+v:r-v,a)}
乘除表达式 = a:函数表达式 b:(('*' / '/') 函数表达式)* {return b.reduce((r,[o,v])=>o=='*'?r*v:r/v,a)}
函数表达式 = name:函数名 '(' arg:表达式 ')' {return Math[name](arg)} / 数值
数值 = [0-9]+ {return parseInt(text())}
函数名 = [a-z]+ {return text()}

输入表达式 sin(1)*2+3,得到的输出值为 4.6829419696157935

至此,一门简单的语言便验证实现完成了。

总结

pegjs 是非常方便的工具,但实际在生产中使用时,语法的解析处理需要在个个语言里找类似的实现,当然也可以解析与计算是异构的,例如通过服务端解析完成,下发语法树到客户端进行执行。这也与最近一个 js 标准请求的目的类似,tc39/proposal-binary-ast 希望浏览器能执行二进制的语法树,而不再是每次都进行解析 js,这样的好处是显而易见的。二进制的语法树与汇编/bytecode几乎只有一线之隔,然后这也正是webassembly的目的,直接让浏览器执行汇编,😄。语言与运行环境是周而复始迭代的,多么的“自然”。

附录:常用的语法解析器

解析器目标语言
flex/yaccC
Antlr4Java、JS、Python、Switf、C#、C++、Go
JavaCCJava
pegjsJavaScript