编译原理学习-词法分析器 Lexer(第二章)

1. wiki

牙医教你 450 行代码自制编程语言 - 2, 两个魔法就可以实现永动机

词法分析器就是将源代码解析成 EBNF 中定义的最小元素(也叫Token)的过程。

2. 定义 Token

定义常量，包括变量的前缀 $，包裹函数参数的括号 ( )，甚至还有函数名称 print 。

对于之前的 EBNF，由于 SourceCharacter 的范围太大，每个字符都按照范围去匹配的话会影响性能，因此我们采用另外的方式去匹配它。

const (
    TOKEN_EOF         = iota  // end-of-file，用于标记代码的结束，检测到它就不会继续解析下去了
    TOKEN_VAR_PREFIX          // $
    TOKEN_LEFT_PAREN          // (
    TOKEN_RIGHT_PAREN         // )
    TOKEN_EQUAL               // =
    TOKEN_QUOTE               // "
    TOKEN_DUOQUOTE            // ""，代表空字符串，为了简化，词法解析时直接把空串当成 Token
    TOKEN_NAME                // Name ::= [_A-Za-z][_0-9A-Za-z]*
    TOKEN_PRINT               // print                
)

3. 自动机

假设有两个函数 func NextTokenIs(token int) (tokenName string) {} 和 func LookAhead() (token int) {}。

• NextTokenIs() ：用于断言下一个 Token 是什么，如果不是，就证明输入的代码出语法错误了。
• LookAhead()：它没有参数，但执行它时，会向前看一个 Token，告诉我们下一个 Token 是什么。

3.1. NextTokenIs()

Print ::= "print" "(" Ignored Variable Ignored ")" Ignored

解析 Print 函数，由于 Print 的结构是固定的，所以可以如下定义一个解析 Print 的函数：

func parsePrint() {
    NextTokenIs(TOKEN_PRINT)        // "print"
    NextTokenIs(TOKEN_LEFT_PAREN)   // "(" 
    parseVariable()                 // 调用解析变量的函数
    NextTokenIs(TOKEN_RIGHT_PAREN)  // ")"
}

此时不断递归调用，即可完成了整个编程语言的 Parser (语法解析器)，这个解析器就叫做 递归下降解析器 。也可以代码自动生成递归下降解析器，例如使用 Flex/Bison 等自动化代码生成器。

3.2. LookAhead()

Statement       ::= Print | Assignment
Print           ::= "print" "(" Ignored Variable Ignored ")" Ignored
Assignment      ::= Variable Ignored "=" Ignored String Ignored
Variable        ::= "$" Name Ignored

解析 Statement ，其可以是 Print 或 Assignment，于是需要 LookAhead() 函数：

func parseStatement() () {
    switch LookAhead() {
        case TOKEN_PRINT:               // "print" 
            return parsePrint()
        case TOKEN_VAR_PREFIX:          // "$"
            return parseAssignment()
        default:
            return nil, errors.New("parseStatement(): unknown Statement.")
    }
}

4. 实现 Lexer 数据结构

本质上 Lexer 是一个状态机，只要能处理当前状态和跳到下一个状态，则可以一直工作下去。

// Lexer 结构
type Lexer struct {
    sourceCode          string 
    lineNum             int    
    nextToken           string 
    nextTokenType       int 
    nextTokenLineNum    int
}
// new 函数
func NewLexer(sourceCode string) *Lexer {
    return &Lexer{sourceCode, 1, "", 0, 0} // start at line 1 in default.
}

• sourceCode：指源代码，直接读取源代码文件并输入进来就可以了。
• lineNum：用于记录当前执行到的代码的行号。
• nextToken：指下一个 Token 的内容。
• nextTokenType：指下一个 Token 的类型，对应我们定义的 Token 类型常量。
• nextTokenLineNum：指下一个 Token 的行号。