编译原理课堂笔记

自顶向下分析：

从开始符号出发推出句子，判断句子是否和给定的目标句子相等，过程中会涉及回溯。可以通过前看符号来避免回溯

算法伪码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
tokens[];
i=0;
stack = [s] //s是开始符号
while (stack !=  []) {
    if (stack[top] is a terminal t) { //如果是终结符
        if (t == tokens[i++]) 
            pop();
        else backtrack(); //t不能匹配tokens输入流的当前符号，因此回溯，回溯涉及将产生包含t的产生式的所有右部出栈、左部压栈，游标前移
    } else if (stack[top] is a nonterminal T) { //非终结符
        pop();
        push(the next right hand side of T); //将右部逆序压栈，这里如果没有下一个right hand side了怎么办————回溯
        if (there is no rhs of T any more) backtrack(); //这里回溯掉产生包含T的的产生式。可能需要另外一个栈来记住产生式选择以方便回溯
    }
}

算法比较昂贵，我们需要线性时间的算法：

避免回溯
引出递归下降分析算法和LL1分析算法

递归下降分析：

每个非终结符对应一个分析函数。分析函数的结果是当前输入token能否被代表这个函数的产生式接受（吃掉）。在每个分析函数内部用当前的前看符号选择一个产生式，如果没得选择报错。接下来，对这个选择的产生式进行分析，假设产生式中即包含终结符也包括非终结符，那么对于终结符判断当前输入符号是否匹配，对于非终结符递归调用该非终结符的parse函数。
问题：怎么根据前看字符来选择产生式？对算术表达式的递归下降分析

1
2
3
4
5
E -> E + T
    | T
T -> T * F
    | F
F -> num

可以看成： E -> T + T + T + …. + T, T -> F * F * … * F

1
2
3
4
5
6
7
8
parse_E() {
    parse_T();
    token = tokens[i++];
    while (token == '+') {
        parse_T();
        token = tokens[i++];
    }
}

1
2
3
4
5
6
7
8
parse_T() {
    parse_F();
    token = tokens[i++];
    while (token == '*') {
        parse_F();
        token = tokens[i++];
    }
}

为什么递归下降只需扫描一次输入流，看书时思考下递归下降其实就是上一节的自顶向下的算法的递归版本，区别在于对非终结符产生式的选择，自顶向下算法中栈模拟的就是这个递归调用过程，产生式的选择也是盲目的一个个尝试。

LL(1)分析算法

从语法声明式规范自动生成语法分析器代码的工具：ANTLR、YACC、bison

表驱动的分析算法

行：非终结符列：终结符表中元素Xij代表：栈顶元素为i行时，遇到j列非终结符时，选择产生式Xij

表怎么生成

定义非终结符的first集:

对 N -> a… : first(N) U= {a}
对 N -> M… : first(N) U= first(M)

伪码：(不动点迭代算法)

1
2
3
4
5
6
7
8
9
10
11
12
13
foreach (nonterminal N) {
    first (N) = {};
}
while (some set is changing) { //迭代的终止条件是没有集合发生变化
    foreach (production p: N -> beta1 .. betan) {
        if (beta1 == a) {
            first(N) U= {a};
        }
        if (beta1 == M) {
            first(N) U= first(M);
        }
    }
}

思考：怎么证明算法正确且能终止

定义任意串的first集：

1
2
3
first_s(beta1...betan) = 
    first(N), if beta1 == N;
    {a}, if beta1 == a;

构造LL(1)分析表：遍历每个production p，将分析表中行位p左部，列在p右部的first集中的元素填上p

定义NULLABLE集：非终结符X属于集合NULLABLE，当且仅当：

基本情况： X ->
归纳情况： X -> Y1 … Yn, Y1 … Yn都属于NULLABLE集

NULLABLE集构造算法：

1
2
3
4
5
6
7
8
9
NULLABLE = {};
while (nullale is still changing) {
    foreach (production p : X -> beta)
        if (beta == '')
            NULLABLE U= {X};
        if (beta == Y1 ... Yn) 
            if (Y1 belong to NULLABLE && ... && Yn belong to NULLABLE)
                NULLABLE U= {X};
}

现在重新redine下非终结符的first集的定义：

基本情况:X -> a firsr(X) U= {a}
归纳情况:X -> Y1 … Yn
- first(X) U= first(Y1)
- if (Y1 belong to NULLABLE), first(X) U= first(Y2)
- if (Y1, Y2 belong to NULLABLE), first(X) U= first(Y3)
- ….

那么非终结符first集构造算法redine后如下：

1
2
3
4
5
6
7
8
9
10
11
12
foreach (nonterminal N)
    first(N) = {};
while (some set is changing) {
    foreach (production p : N -> beta1 ... betaN)
        foreach (betai from beta1 to betan) { //相比原来多了一层对产生式右部的符号的迭代
            if (betai == a...) {first(N) U= {a}; break;}
            if (betai == M...) {
                first(N) U= first(M);
                if (M is not in NULLABLE) break;
            }
        }
}

思考：怎么证明算法正确，并且能终止？1）集合元素有限，因此算法肯定能终止 2）反证法证明当算法终止时，结果集合就是要求的目标集合

OK, 有了非终结符的first集完整定义和构造算法后，来分析串的first_s集：

原来的定义是：对于N -> beta1 … betan first_s(beta1…betan) = first(M), if beta1 == M; {a}, if beta1 == a;

现在beta1可能是NULLABLE，同样beta2、…、betan都可能是NULLABLE的，first_s除了可能包含betai的first集外，还可能包含串之外的非终结符，即follow(N)。因此引入follow集的概念

非终结符follow集：非终结符后可能跟随哪些终结符构成的集合

这里可以先定义每个产生式右部符号的temp集,对于产生式 N -> beta1 … betan而言：

基本情况: temp(betan) = follow(N)

归纳情况:

if betai+1 is terminal, temp(betai) = {betai+1}
if betai+1 is nonterminal && betai+1 is not NULLABLE, temp(betai) = first(betai+1)
if betai+1 is nontermianl && betai+1 is NULLABLE, temp(betai) = first(betai+1) U temp(betai+1)

temp集是干嘛的呢？每个非终结符的follow集必定包含它所在的每个产生式中它的temp集。因此，对于非终结符的follow集构造算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
foreach (nonterminal N) 
    follow(N) = {};
while (some set is changing) {
    foreach (prodcution p : N -> beta1 ... betan) {
        temp = follow(N); //定义temp集，每轮循环开始前temp是可能跟在betai后的非终结符集合
        foreach (betai from betan downto beta1) {
            if (betai == a...) temp = {a};
            if (betai == M...) {
                follow(M) U= temp;  //M的跟随集里增加新元素
                if (M is not NULLBALE)
                    temp = first(M); //M不在NULLABLE内，因此betai-1的temp集只能是first(M)
                else temp U= first(M); //M在NULLABLE内，betai-1的temp集是first(M) U temp(betai)
            }
        }
    }

}

最后，给出串的first_s集算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
foreach (production p) 
    first_s(p) = {};

calculate_first_s (production p : N -> beta1 ... betan) {
    foreach (betai from beta1 to betan) {
        if (betai == a ...) { 
            first_s(p) U= {a};
            return;
        }
        if (betai == M ...) {
            first_s(p) U= first(M);
            if (M is not NULLABLE) return;
        }
    }
    first_s(p) U= follow(N);//为什么需要并上follow(N)，此时p可以推出空，结合下first_s的作用就知道了为什么了
}

现在，终于可以构造LL(1)分析表了，其实和之前完全一样。那么LL(1)分析器的算法框架如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
tokens[];
i=0;
stack = [s] //s是开始符号
while (stack !=  []) {
    if (stack[top] is a terminal t) { //如果是终结符
        if (t == tokens[i++]) 
            pop();
        else error(..) //如果不匹配则直接报错
    } else if (stack[top] is a nonterminal T) { //非终结符
        pop();
        push(table[T, tokens[i]]); //将table[T, tokens[i]]号产生式的右部逆序压栈
    }
}

冲突处理

改变文法以去掉冲突

消除左递归（一般变成右递归）
提取左公因子

LL（1）分析算法的缺点

文法类型受限
可能需要文法改写

LR分析算法（移进-归约）

自底向上 YACC、bison、CUP 最右推导的逆过程

kaspterio code as a hacker