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

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

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

一、什么是Lexer?

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

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

和日常生活中的例子做类比,就如同我们阅读do jobs这句话,我们会依次拿到dojobs这么一堆字符,这些字符就好比字符流,而经过词法分析,我们会把这些字符组成dojobs两个单词,dojobs就好比词法单元,更进一步讲,他们可以表示成<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: ']' } ]