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

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

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

语法分析是对词法单元流进行解析,分析其是否符合某一特定的结构,并转换成便于处理的数据结构,简单而言,就是将线性的词法单元序列组成带有结构的解析树,即抽象语法语法树(AST, Abstract Syntax Tree)

一、向前看集合

在编译中,通常采用FIRST运算和FOLLOW运算来计算向前看集合,计算向前看集合的目的是在于 推测出所有可能会出现在一个规则式(非终结符)开头的词法单元,以下介绍一下FIRST运算和FOLLOW运算:

1、FIRST运算

FIRST运算的最终结果是产出终结符集(终结符简单理解就是不能再细分的文法符号),计算FIRST(X)的定义为:

反复执行如下步骤,直到无法加入新的终结符或者ε(空解析选项)
(1) 如果X是一个终结符,那么FIRST(X) = X
(2) 如果X是一个非终结符,且X -> Y1 Y2 ... Yk(k≥1)是一个规则式,那么将FIRST(Y1Y2...Yk)加入FIRST(X)
(3) 如果存在X -> ε,那么把ε加入到FIRST(X)

其中,定义中(2)的求法为:

(1) 将FIRST(Y1)中所有终结符加入FIRST(Y1Y2...Yk)
(2) for (i=1; i<=k-1; i++),如果εFIRST(Yi)中,那么将FIRST{Y(i+1)}中的所有终结符加入,否则break
(3) 如果对于所有的i,ε都在FIRST(Yi)中,那么把ε加入FIRST(Y1Y2...Yk)

下面举个例子:

E  -> TE'
E' -> + TE' | ε 
T  -> FT'  
T' -> * FT' | ε
F  -> ( E ) | id

计算:
(1) FIRST(E) = FIRST(TE') = {'(', id}
(2) FIRST(E') = FIRST(+TE') U FIRST(ε) = {'+', ε}
(3) FIRST(T) = FIRST(FT') = {'(', id}
(4) FIRST(T') = FIRST(*FT') U FIRST(ε) = {'*', ε}
(5) FIRST(F) = {'(', id}

2、FOLLOW运算

follow运算是求得紧跟在规则式后面的终结符集,算法如下:

反复执行如下规则,直到无法加入新的终结符和$
(1) 如果S是开始符,则将$加入FOLLOW(S)$表示输入结束
(2) 如果有规则A -> αBβ,则将FIRST(β)(不包含ε)加入FOLLOW(B)
(3) 如果有A -> aB或者A -> αBβ 且 ε ∈ FIRST(β),则将FOLLOW(A)加入FOLLOW(B)

下面举个例子:

E  -> TE'
E' -> + TE' | ε 
T  -> FT'  
T' -> * FT' | ε
F  -> ( E ) | id

我们在上面已经求出了这些的FIRST集,那么它们的FOLLOW集可求得如下:
(1) FOLLOW(E) = {')', $}
(2) FOLLOW(E') = FOLLOW(E) = {')', $}
(3) FOLLOW(T) = (FIRST(E') - {ε}) U FOLLOW(E') = {'+', ')', $}
(4) FOLLOW(T') = FOLLOW(T) = {'+', ')', $}
(5) FOLLOW(F) = (FISRT(T') - {ε}) U FOLLOW(T) = {'*', '+', ')', '$'}

3、向前看集合的简单计算法则

(1)看一个规则式是以什么为起始的,如果规则式有多个子规则式,那么将这几个子规则式并起来,如下:

stat: 'if'...       // 以'if'终结符开头,那么是 {'if'}
    | 'while'...    // 以'while'终结符开头,那么是 {'while'}
    | 'for'...      // 以'for'终结符开头,那么是 {'for'}
    ;

所以stat的向前看集合是{'if', 'while', 'for'},再看以下例子:

body_element: stat  // 向前看集合是 {'if', 'while', 'for'}
    | LABEL ':'     // 向前看集合 {LABEL}
    ;

像这种由规则式终结符组成的规则式,求它的向前看集合,就先求涉及的所有规则式的向前看集合,最后再和终结符一起求并集,所以body_element的向前看集合是{'if', 'while', 'for', LABEL}
(2)如果一个规则式包含空解析选项,那么情况就稍微复杂了。如一个初始化语句,即可以是a = 1也可以是a,所以对于这种语法,规则式是这样子的:

optional_init: '=' expr // 向前看集合是 {'='}
    | 空解析选项
    ;

那么这种的向前看集合除了自身可求出的向前看集合外(即:{'='}),还应该考虑所有出现在optional_init规则式之后的规则式和终结符,求出这些规则式的向前看集合,最终optional_init的向前看集合是上述所有向前看集合的并集。距离如下:

declare: 'int' ID optional_init ';'
    ;
arg: 'int' ID optional_init
    ;
func_call: ID '(' arg ')'
    ;

这里,我们可以看到出现在optional_init之后的有{';'}{')'},其中{')'}是怎么得来的呢?这是因为optional_init出现在arg中,而arg出现在func_call中,显而易见它之后跟着的是),所以出现在optional_init之后的词法单元组合起来,求出向前看集合为{';', ')'},最终optional_init的向前看集合为{'=', ';', ')'}


二、确定性解析策略

如果要应用LL解析策略,需要注意的是:规则式中的每一个解析选项(子规则式或者终结符)的向前看集合都需要保证 互不相交,如下:

expr: '-'? (INT | FLOAT)    // 向前看集合为 { '-', INT, FLOAT }
    | ID                    // 向前看集合为 {ID}
    ;

集合没有交集,因此它们是互不相交的,可以应用LL解析策略。这是因为我们知道只要出现'-'INTFLOAT我们就能按第一个选项解析,出现ID就能按第二个选项解析,但是对于如下例子就不行了:

expr: ID '++'   // 向前看集合 { ID }
    | ID '--'   // 向前看集合 { ID }
    ;

它们是相交的,所以无法判断应该利用那一个解析选项。为了解决这个问题,策略是:

提取左公共子式
因此,expr最终变为:

expr: ID ('++'|'--')
    ;


三、实战

我们继续以实现解析如下语法为例:

list: '[' elements ']'
    ;
elements: element (',' element)*
    ;
element: NAME   // 向前看集合 { NAME }
    | list      // 向前看集合 { '[' }
    ;

求出它们的FIRST集如下:
(1) FIRST(list) = { '[' }
(2) FIRST(element) = FIRST(NAME) U FIRST(list) = { NAME, '[' }
(3) FIRST(elements) = FIRST(element)

1、Parser基类

Parser类是一个抽象类,它包含内部状态和工具方法,实现如下:

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

export default abstract class Parser {
    // 当前向前看字符
    protected _lookahead: Token
    // 当前词法单元流
    protected _input: Lexer
    // 抽象语法树
    protected _ast: Array<string | Array<string>>
    constructor(input: Lexer) {
        this._input = input
        this.consume()
    }
    // 查看下一个词法单元
    public consume(): void {
        this._lookahead = this._input.nextToken()
    }
    // 确保向前看词法单元匹配的是类型type的
    public match(type: TokenType) {
        if (this._lookahead.type === type) {
            this.consume()
        } else {
            throw new Error(`Expecting ${TokenType[type]}; found ${this._lookahead}`)
        }
    }
}

2、ListParser

ListParser是我们这个语法解析器的核心实现类,它基于LL(1),所以我们需要根据文法实现递归下降的方法,如下:

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

export default class ListParser extends Parser {
    constructor(input: Lexer) {
        super(input)
    }
    // 文法:list: '[' elements ']'
    private _list() {
        // 吃掉 '['
        this.match(TokenType.LBRACK)
        // 递归下降
        this._elements()
        // 吃掉 ']'
        this.match(TokenType.RBRACK)
    }
    // 文法:element (',' element)*
    private _elements() {
        // 递归下降
        this._element()
        // 实现 (',' element)*
        while (this._lookahead.type === TokenType.COMMA) {
            this.match(TokenType.COMMA)
            this._element()
        }
    }
    // 文法:element: NAME | list
    private _element(): void {
        // 根据 FIRST(element) = {NAME, '['}
        // 匹配 NAME 时进入 NAME 解析选项
        if (this._lookahead.type === TokenType.NAME) {
            this.match(TokenType.NAME)
        // 匹配 '[' 时进入 list 解析选项
        } else if (this._lookahead.type === TokenType.LBRACK) {
            this._list()
        // 都不匹配时表示出错
        } else {
            throw new Error(`Expecting NAME or list; found ${this._lookahead}`)
        }
    }
}

以上解析器已经能实现语法结构的分析了,但是我们希望进一步将输入流转换成AST,那么怎么办呢?我们可以分析如下:
(1) _list()中执行的是列表的解析。因此当匹配了'['时,表示列表开始,向栈中加入一个新的列表;而在匹配']'时表示列表结束,进行出栈操作,可以得到一个解析后的列表;此时应该对栈进行分析,如果栈不为空,表示刚刚得到的列表是当前栈顶元素的子元素,如果栈为空,则刚刚得到的列表就是整个AST的入口
(2) _element()中执行的是元素的分析操作,当匹配的是一个NAME时,我们可以将这个name加入栈顶元素所表示的那个列表中
因此,最终完整的ListParser实现如下:

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

function top(stack) {
    if (stack.length) {
        return stack[stack.length - 1]
    }
    return false
}

export default class ListParser extends Parser {
    private _stack: Array<Array<string>>
    constructor(input: Lexer) {
        super(input)
        this._stack = []
    }
    public parse() {
        this._list()
    }
    public show() {
        console.log(JSON.stringify(this._ast, null, 2))
    }
    private _list() {
        this.match(TokenType.LBRACK)
        this._stack.push([])
        this._elements()
        this.match(TokenType.RBRACK)
        const list = this._stack.pop()
        if (list && this._stack.length) {
            top(this._stack).push(list)
        } else {
            this._ast = list
        }
    }
    private _elements() {
        this._element()
        while (this._lookahead.type === TokenType.COMMA) {
            this.match(TokenType.COMMA)
            this._element()
        }
    }
    private _element(): void {
        if (this._lookahead.type === TokenType.NAME) {
            if (top(this._stack)) {
                top(this._stack).push(this._lookahead.text)
            }
            this.match(TokenType.NAME)
        } else if (this._lookahead.type === TokenType.LBRACK) {
            this._list()
        } else {
            throw new Error(`Expecting NAME or list; found ${this._lookahead}`)
        }
    }
}

测试:

import ListLexer from './lib/ListLexer'
import ListParser from './lib/ListParser'

const input = process.argv[2] || ''

const lexer: ListLexer = new ListLexer(input)
const parser: ListParser = new ListParser(lexer)

try {
    parser.parse()
    parser.show()
} catch (e) {
    console.log(e)
}

输入:

$ ts-node index.ts '[a, b, c, d, [e, f, [g, h, i, [j, k], l, [mn]]]]'

输出:

[
  "a",
  "b",
  "c",
  "d",
  [
    "e",
    "f",
    [
      "g",
      "h",
      "i",
      [
        "j",
        "k"
      ],
      "l",
      [
        "mn"
      ]
    ]
  ]
]