愿你坚持不懈，努力进步，进阶成自己理想的人

—— 2017.09, 写给3年后的自己

《编程语言实现模式》学习笔记（一）：LL(1)递归下降的词法分析器

一、什么是Lexer？

在阅读的时候，人们会无意识地将字母合成单词，然后将合成的单词组成句子，之后考虑语法结构，最终明白句子的含义。在编译的过程中，编译器为了更好地进行语法分析，就也需要先将字符流识别分类为有意义的一个个单元，而这些单元便称之为词法单元，编译器解析字符流到生成词法单元的过程便是词法分析，即：

字符流 --> Lexer --词法分析--> Parser --语法分析--> AST

和日常生活中的例子做类比，就如同我们阅读do jobs这句话，我们会依次拿到d，o，，j，o，b，s这么一堆字符，这些字符就好比字符流，而经过词法分析，我们会把这些字符组成do和jobs两个单词，do和jobs就好比词法单元，更进一步讲，他们可以表示成<vt, 'do'>和<n, 'jobs'>，而这么一个词法单元序列可经由语法分析器解析，判断是否是符合英语语法的句子，我们都知道vt+n是合法的语法结构，那么语法分析器就能够方便地利用词法单元里的信息来做解析了，这便是词法分析的意义所在，而Lexer便是能处理输入字符流的识别器


二、词法单元(Token)类型

词法分析的最终结果是产出词法单元流，每个词法单元则都有两个重要的属性：词法类型和词法内容，所以我们需要事先定义好词法类型
本文中将以分析“[a, b, [c, dd]]”这类语法为例。在这个例子里，我们可以明确包含的字符可以分为：

  • NAME：表示变量名称，如“a”、“b”、“c”、“dd”都是变量名称
  • LBRACK：表示左括号“[”
  • RBRACK：表示右括号“]”
  • COMMA：表示逗号“,”

所以，我们可以定义TokenType如下：

// TokenType.ts
export enum TokenType {
    NAME = 1,
    COMMA = 2,
    LBRACK = 3,
    RBRACK = 4
}

此外，还需要定义一个类，来表示Token这一数据结构：

import { TokenType } from './TokenType'

export default class Token {
    public type: TokenType
    public text: string
    constructor(type, text) {
        this.type = type
        this.text = text
    }
    public toString() {
        return `<'${this.text}', ${TokenType[this.type]}>`
    }
}

其中，NAME比较特殊，它是一或多个字母所组成的，所以我们可以定义它的规则为：('a' ... 'z'|'A' ... 'Z')+


三、规则实现

规则通常有以下这么几类，可以图示为：

具体而言：

  • alternatives?，optional，表示可选可不选，因此可以编码实现为：
if (/* 看到相应的向前看字符 */) {
    match(alternatives)
}
  • alternatives+，one or more，表示一或多个，因此可以编码实现为：
do {
    match(alternatives)
} while(/* 看到相应的向前看字符 */)
  • alternatives*，zero or more，表示零或多个，因此可以编码实现为：
while (/* 看到相应的向前看字符 */) {
    match(alternatives)
}

所以，回到刚刚的例子，NAME的定义是('a'...'z'|'A'...'Z')+，所以它的实现是采用do-while：

private _NAME(): Token {
    let buf = ''
    do {
        buf += this._char // this._char表示当前读取到的字符
    } while (this._isLetter())
    return new Token(TokenType.NAME, buf)
}

而一般在词法分析中，空白是不重要的，我们一般的做法是跳过空白，空白可以定义为(' ' | '\t' | '\n' | '\r')*，因此它的实现是采用while语句：

private _WS(): void {
    while (
        this._char === ''
        || this._char === '\t'
        || this._char === '\n'
        || this._char === '\r'
    ) {
        this._consume()
    }
}


四、Lexer抽象类

为了方便地实现我们的词法解析器，我们需要定义一个Lexer抽象类，它包含了一些内部状态和公用操作方法，即：
状态：

  • _input: string：输入字符串
  • _index: number：表示当前扫描到字符串中第几位的指针
  • _char: string | TokenType.EOF：表示当前扫描到的字符（向前看字符）

方法：

  • consume()方法：用以每次调用时都向前扫描一个字符，当扫描完毕后返回EOF
  • match(x: string)方法：确保x是输入流中的下一个字符，如果不是就报错

因此，Lexer类实现如下：

import { TokenType } from './TokenType'

export default abstract class Lexer {
    protected _input: string
    protected _index: number
    protected _char: string | TokenType.EOF
    constructor(input: string) {
        this._input = input
        this._index = 0
        this._char = input.charAt(0)
    }
    public consume() {
        this._index++
        if (this._index >= this._input.length) {
            this._char = TokenType.EOF
        } else {
            this._char = this._input.charAt(this._index)
        }
    }
    public match(charToMatch: string) {
        if (this._char === charToMatch) {
            this.consume()
        } else {
            throw new Error(`Expecting ${charToMatch}; found ${this._char}`)
        }
    }
}


五、ListLexer

ListLexer才是我们要实现的词法解析器。这里回到标题“基于LL(1)递归下降的Lexer”，这里LL(1)的L的意思是Left-to-Right，即表示：解析器从左向右解析输入内容，下降解析时也是按从左到右顺序遍历子节点，1则是每次只向前看一个字符。
所以我们是通过向前看一个字符串来判定词法类型的，因此ListLexer的实现主要是实现nextToken()方法，如下：

public nextToken(): Token {
    while (this._char !== TokenType.EOF) {
        // 通过查看向前看字符，确认词法类型
        switch(this._char) {
            // 如果向前看字符是' '，'\t'，'\n'，'\r'，则匹配空白
            case ' ':
            case '\t':
            case '\n':
            case '\r':
                this._WS()
                continue
            // 如果向前看字符是','，则匹配逗号
            case ',':
                this.consume()
                return new Token(TokenType.COMMA, ',')
            // 如果向前看字符是'['，则匹配左方括号
            case '[':
                this.consume()
                return new Token(TokenType.LBRACK, '[')
            // 如果向前看字符是']'，则匹配右方括号
            case ']':
                this.consume()
                return new Token(TokenType.RBRACK, ']')
            // 如果向前看字符不是以上情况，则可能是NAME，也有可能出错
            default:
                if (this._isLetter()) {
                    return this._NAME()
                }
                throw new Error(`invalid character: ${this._char}`)
        }
    }
    return new Token(TokenType.EOF, '<EOF>')
}

这里我们NAME的合法组成是字母，因此我们可以实现_isLetter()方法如下：

private _isLetter(): boolean {
    const charCode = (<string> this._char).charCodeAt(0)
    return charCode >= 'a'.charCodeAt(0) && charCode <= 'z'.charCodeAt(0)
        || charCode >= 'A'.charCodeAt(0) && charCode <= 'Z'.charCodeAt(0)
}

最终，ListLexer的实现如下：

import { TokenType } from './TokenType'
import Lexer from './Lexer'
import Token from './Token'

export default class ListLexer extends Lexer {
    constructor(input: string) {
        super(input)
    }
    private _WS(): void {
        while (
            this._char === ' '
            || this._char === '\t'
            || this._char === '\n'
            || this._char === '\r'
        ) {
            this.consume()
        }
    }
    private _NAME(): Token {
        let buf = ''
        do {
            buf += this._char
            this.consume()
        } while (this._isLetter())
        return new Token(TokenType.NAME, buf)
    }
    private _isLetter(): boolean {
        const charCode = (<string> this._char).charCodeAt(0)
        return charCode >= 'a'.charCodeAt(0) && charCode <= 'z'.charCodeAt(0)
            || charCode >= 'A'.charCodeAt(0) && charCode <= 'Z'.charCodeAt(0)
    }
    public nextToken(): Token {
        while (this._char !== TokenType.EOF) {
            switch(this._char) {
                case ' ':
                case '\t':
                case '\n':
                case '\r':
                    this._WS()
                    continue
                case ',':
                    this.consume()
                    return new Token(TokenType.COMMA, ',')
                case '[':
                    this.consume()
                    return new Token(TokenType.LBRACK, '[')
                case ']':
                    this.consume()
                    return new Token(TokenType.RBRACK, ']')
                default:
                    if (this._isLetter()) {
                        return this._NAME()
                    }
                    throw new Error(`invalid character: ${this._char}`)
            }
        }
        return new Token(TokenType.EOF, '<EOF>')
    }
}


六、tokenizer

最终我们写出来的tokenizer为：

function tokenizer(input: string) {
    const result: Array<Token> = []
    const lexer: ListLexer = new ListLexer(input)
    try {
        let token: Token = lexer.nextToken()
        while (token.type !== TokenType.EOF) {
            result.push(token)
            token = lexer.nextToken()
        }
    } catch (e) {
        console.error('Tokenized error:', e.message)
    }
    return result
}

测试：

console.log(
    tokenizer('[a, c, ee, [a,b    ,c]]')
)

输出：

[ Token { type: 3, text: '[' },
  Token { type: 1, text: 'a' },
  Token { type: 2, text: ',' },
  Token { type: 1, text: 'c' },
  Token { type: 2, text: ',' },
  Token { type: 1, text: 'ee' },
  Token { type: 2, text: ',' },
  Token { type: 3, text: '[' },
  Token { type: 1, text: 'a' },
  Token { type: 2, text: ',' },
  Token { type: 1, text: 'b' },
  Token { type: 2, text: ',' },
  Token { type: 1, text: 'c' },
  Token { type: 4, text: ']' },
  Token { type: 4, text: ']' } ]