LLVM_ Interpreter_解释器(一)

在前一片文章中, 我介绍了与 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 值得你拥有