一、什么是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: ']' } ]