跳到主要内容

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

· 阅读需 11 分钟

语言就是程序员的酒精/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