在前一片文章中, 我介绍了与 LLVM 相关的一些内容, 里面涉及到一些应用
- 做语法树分析, 实现语言转换, 入如OC转Swift, JS 或 其他语言
- 编写ClangPlugin, 用于代码的命名规范, 编写规范
- 编写Pass, 代码混淆优化.
这里我们以 interpreter 为起点, 逐步实现一个简单版的语言转换, 之所以打算开这个系列的文章, 主要还是看了戴铭在 2018Swift 大会上做的关于解释器的演讲, 他在这篇文章里做了一些介绍.
什么是 interpreter ?
interpreter (解析器) 处理并执行源程序而不首先将其翻译成机器语言.
compiler 将源程序翻译成机器语言, interpreter 是 compiler 的一部分.
1. Lexer 词法分析
lexical analysis(lexer) : 词法分析, 将输入的源码分解为 Token 的过程, 其中, lexeme 是一系列形成 Token 的字符. Token 包括以下几种.
- 关键字：语法中的关键字，if else while for 等。
- 标识符：变量名
- 字面量：值，数字，字符串
- 特殊符号：加减乘除等符号
2. Paeser 语法分析
Paeser 读取由 Lexer 生成的 Token 序列，并根据语法构建程序的抽象语法树（简称AST）. 也一过程叫 syntax analysis, 语法分析.
什么是语法呢?
syntax diagrams : 语法图, 描述编程语言 syntax 规则的图示.
grammars : 这是 context-free grammars 的简称,
- 也叫 BNF (Backus-Naur Form), 是用于无上下文语法的符号技术，通常用于描述计算中使用的语言的语法，例如计算机编程语言，文档格式，指令集和通信协议. 它们适用于需要语言准确描述的地方：例如，官方语言规范，手册和编程语言理论教科书.
- 与之相关 EBNF (Extended Backus–Naur form) : 它是一种表达形式语言语法的代码
grammars 以简洁的方式指定编程语言的语法。
与 syntax diagrams 不同，grammars 非常紧凑。
下面是
syntax diagrams图
上面可以表示3, 3 + 2, 3-2, 3 + 2 - 2 等语法 上面可以表示3, 3 * 2, 3 * 2 / 7等语法
grammars 的表示方法
描述 3 * 2 / 7 的语法可以这么写
image.png
-
grammars由一系列 rules / productions 组成. -
head部分由 non - terminal 组成, 包括 expr, factor, non - terminal 由 terminal 组成. -
body部分由 non - terminal / terminal 组成. - 第一条规则的 head 称为
start symbol, 在这里指 expr. - 解读 expr:
- expr可以是一个因子，也可以在因子后面跟乘法或除法运算符，再跟另一个因子，后面可以跟乘法或除法运算符再跟另一个因子，依此类推等等.
- | :表示或者, 备选方案, 实例中为 MUL 或者 DIV.
- (...) :表示如（MUL | DIV）中的终端或非终端的组合.
- (...)* : 表示将组内的内容匹配0次或多次.
- 仔细看, 其实这个和正则表达式很像.
这个语法是怎么工作的?
|
|
|---|---|
|
语法通过解释它可以形成的语句来定义语言.首先从开始符号expr开始，然后用非终端的规则体重复替换非终端，直到你生成一个仅包含终端的句子为止, 这些句子构成语法定义的语言.
如何将语法转化为代码呢?
针对这个, 做一个简单演示, 将 Token 按照语法规则转化为代码 3 * 8 / 2.
我们已经将 3 * 8 / 2 这样的代码转化为 Tokens,
以下面这种 enum 结构封装
public enum LCOperationType {
case plus
case minus
case mult
case intDiv
}
public enum LCConstant {
case integer(Int)
}
public enum LCToken {
case operation(LCOperationType)
case constant(LCConstant)
case eof
}
factor() 用来取出 tokens 中的 integer value, 这里面有一个 eat(), 用来 feed value, 也就是 tokenIndex += 1.
/**
返回一个 Integer Token value
factor : INTEGER
*/
private func factor() -> Int {
let token = currentToken
var outputNum = 0
if case let .constant(.integer(num)) = token {
eat(token)
outputNum = num
}
return outputNum
}
expr() 用来做计算
/**
expr : factor ((MUL | DIV) factor)*
factor : INTEGER
*/
private func expr() -> Int {
var result = factor()
let operationTokens = [LCToken.operation(.mult),
LCToken.operation(.intDiv)]
while operationTokens.contains(currentToken) {
if currentToken == .operation(.mult) {
eat(currentToken)
result = result * factor()
}else if currentToken == .operation(.intDiv) {
eat(currentToken)
result = result / factor()
}
}
return result
}
4. Semantic analyzer 语义分析器
Semantic analyzer 对 AST 进行静态语义检查.
- 它目前检查是否事先声明了所有使用的变量, 以及是否有任何重复的声明.
- 语义分析的结果是一个Symbol表, 它包含目标程序使用的所有符号, 当前以类型（Integer，Boolean，String）和声明的变量名称构建.
5. Interpreter 解释器
Interpreter 从 Parser 读取代表目标程序的 AST，并通过递归地遍历AST来解释它.
这个系列后面还会继续更新. 如果你也对这块感兴趣, 欢迎交流.
- 文中戴铭的这个项目 HTN 对理解 Interpreter 具有一定的参考价值.
- SwiftPascalInterpreter 这个项目是对 Pascal language 解释器的实现.
- Let’s Build A Simple Interpreter 这个系列文章是对 Pascal language 解释器的实现的详细解读, 作者对计算机语言理解很深, 讲解深入浅出, 文章需要翻墙阅读.
- SwiftRewriter 这个项目是对 OC 转 Swift 的完整实现, 值得一看.
- 如果你想快速使用 OC 转 Swift, 这个商业化的网站 objectivec2swift 值得你拥有
网友评论