LL(k)和回溯解析器实现

《Language Implementation Patterns》读书笔记

LL(k)解析器

LL(k)文法中的k表示lookahead，即向前看几个字符。
最常用的LL(1)中，向前看一个词法单元即可选择到对应的解析表达式，比如if语句，如果下一个词法单元为if，要选择if语句的表达式进行解析。
要实现LL(k)的解析器，在解析时要缓存k个词法单元(Token)，实现时，可以使用k长度的数组，但是在访问的时候要使用环形的方式，访问到最后一个词法单元，获取下一个时，要返回到数组的第一个元素。伪代码如下：

private Token[] lookahead = new Token[k];
private Lexer lexer;
int pos = 0;

public void consume() {
    lookahead[p] = lexer.nextToken(); // 在下一个位置放入词法单元
    pos = (pos + 1) % k; // 自增下标，使用取余方式，当到达缓存区末尾，自增时从0开始
}

// 返回向前看i的词法单元
public Token LT(int i) {
    return lookahead[(pos + i - 1) % k]; // 环式取值
}
// 返回向前看i的词法单元类型
public int LA(int i) {
    return LT(i).type;
}

public void match(int x) {
    if (LA(1) == x) {
        consume();
    }
    throw new Exception();
}
复制代码

回溯解析器

回溯解析器使用任意多的向前看符号进行解析，所以Parser中的缓存区要能够动态扩容，除此之外，还要标记解析词法单元的起始位置。伪代码如下：

private List<Token> lookahead; // 大小可变的缓存区
private List<Integer> markers; // 栈，存放记录位置的标记
private Lexer lexer;
int pos = 0;

// 返回向前看i的词法单元
public Token LT(int i) {
    return lookahead[(pos + i - 1) % k]; // 环式取值
}
// 返回向前看i的词法单元类型
public int LA(int i) {
    return LT(i).type;
}

public void match(int x) {
    if (LA(1) == x) {
        consume();
    }
    throw new Exception();
}

public void consume() {
    pos++;
    // 非推断状态，而且到达了缓冲区末尾
    if (pos == lookahead.size() && !isSpeculating()) {
        pos = 0; // 到了末尾，从0开始填入新的词法单元
        lookahead.clear();
    }
    sync(1); // 取一个新的词法单元
}

public void sync(int i) {
    if (pos + i - 1 > (lookahead.size() - 1)) {
        int n = (pos + i - 1) - (lookahead.size() - 1); // 获取n个词法单元
        fill(n);
    }
}
public void fill(int n) {
    for (int i = 1; i <= n; i++) {
        lookahead.add(lexer.nextToken());
    }
}

// 标记相关
public int mark() {
    markers.add(pos);
    return pos;
}
public void release() {
    int marker = markers.get(markers.size() - 1);
    markers.remove(markers.size() - 1);
    seek(marker);
}
public void seek(int index) {
    pos = index;
}
public bookean isSpeculating() {
    return markers.size() > 0;
}

// 解析
public void stat() {
    if (speculate_stat_alt1()) {
        list(); match(Lexer.EOF);
    }
}
// 尝试匹配选项1
public boolean speculate_stat_alt1() {
    boolean success = true;
    mark(); // 标记当前位置
    try {
        list();
        match(Lexer.EOF);
    } catch (RecognitionExceptin e) {
        success = false;
    }
    release(); // 不管是否匹配，都要放回输入
    return success;
}
复制代码