编译原理扫盲帖

[tsy77]

最近复习了一下编译原理，编译原理主要有以下几个阶段：

1.词法分析，将原文件中的字符分解为一个个独立的单词符号——TOKEN。词法分析的输入是字符流，输出的一个个词法单元（<类型, 值>）。
2.语法分析，分析程序的短语结构。语法分析从语法分析器输出的token中识别各类短语，并构造语法分析树。
3.语义分析，推算程序的含义。语义分析负责收集标志符的属性信息并存在符号表中；负责语义检查
4.中间代码生成
5.代码优化
6.目标代码生成

其中，语法分析、语义分析、中间代码生成三个阶段可以合为语法制导翻译。

本文将针对上述几个阶段进行简要介绍。

词法分析

语法分析器从左到右的扫描程序中的字符，识别出各个单词，并确定单词类型，输出统一的词法单元token。

我们在做词法分析器时，主要遵循以下几个步骤：

1.确定Token的分类，比如关键字、常量、运算符、标志符、空格、注释等
2.为每一类token确定相应的正则及匹配函数
3.在主流程中逐一匹配正则并削减剩余字符串

我们以sql-parser中的词法分析部分为例：

正则及匹配函数

WHITESPACE = /^[ \n\r]+/;

Lexer.prototype.whitespaceToken = function() {
      var match, newlines, partMatch;
      if (match = WHITESPACE.exec(this.chunk)) {
        partMatch = match[0];
        newlines = partMatch.replace(/[^\n]/, '').length;
        this.currentLine += newlines;
        if (this.preserveWhitespace) {
          return { name, value: partMatch }
        }
      }
};

主流程

while (this.chunk = sql.slice(i)) {
        token = this.keywordToken() || this.starToken() || this.booleanToken() || this.functionToken() || this.windowExtension() || this.sortOrderToken() || this.seperatorToken() || this.operatorToken() || this.mathToken() || this.dotToken() || this.conditionalToken() || this.betweenToken() || this.subSelectOpToken() || this.subSelectUnaryOpToken() || this.numberToken() || this.stringToken() || this.parameterToken() || this.parensToken() || this.whitespaceToken() || this.literalToken();
        if (token.length < 1) {
          throw new Error("NOTHING CONSUMED: Stopped at - '" + (this.chunk.slice(0, 30)) + "'");
        }

        this.tokens.push(token)
        i += token.value.length;
}

文法

文法用来描述语言的规则，文法G定义为一个四元组（VN,VT,P,S），其中，VN为非终结符集合，VT终结符集合；P是产生式结合；S称为识别符或开始符号，也是一个非终结符，至少要在一条产生式的左边出现。

产生式的形式是α → β，α称为产生式左部，β称为产生式右部，α属于VN，β∈(VN∪VT)*，α∉ε

上下文无关文法

文法分为上下文有关文法和上下文无关文法，故名思义，上下文无关文法就是匹配产生式时，与上下文(前后已经推倒出的结果)无关，上下文无关文法的产生式左侧只有非终结符。只要文法的定义里有某个产生式，不管一个非终结符前后的串是什么，就可以应用相应的产生式进行推导。

消除左递归

一个文法含有下列形式的产生式之一时：

1.A→Aβ，A∈VN，β∈V*
2.A→Bβ，B→Aα，A、B∈VN，α、β∈V*

则称该文法是左递归的。

左递归的产生式是无法做自顶向下分析语法分析的，所以需要我们消除左递归。消除直接左递归的方式是将其转换成右递归。比如产生式：

P -> Pa|b 

P表示的是ba{1,}，那么我们可以将其转换成如下右递归，

P -> bP'
P' -> aP'|ε

消除左递归有一套通用的算法，算法如下：

从 i = 1 到 n {
    从 j = 1 到 i - 1 {
        设Aj -> d1 | d2 | ... | dk
        将所有规则 Ai -> Aj y换成
        Ai -> d1 y | d2 y | ... | dk y
        移除Ai规则中的直接左递归
    }
}

简单用Javascript实现了一个消除直接递归的函数：

function removeDirectLeftRecursion(grammar) {
    for (let i = 0; i < grammar.length; i++) {
        let left  = grammar[i].getLeft(),
            right = grammar[i].getRight();

        let continueFlag = true;
        for (let j = 0; j < right.length; j++) {
            if (left === right[j].charAt(0)) {
                continueFlag = false;
                break;
            }
        }

        if (continueFlag) continue;

        let newLeft  = `${left}'`;
        grammar.add(new Rule(newLeft));
        grammar.get(grammar.size()-1).add("~");

        let generated = [];
        for (let j = 0; j < right.length; j++) {
            if (left === right[j].charAt(0)) {
                grammar.get(grammar.size()-1).add(ss.substring(1) + newLeft);
            } else {
                generated.push(right[j] + newLeft)
            }
        }

        right.set(generated);
    }
}

语法分析

语法分析的目的是构造分析树，按照分析树的构造方向，可以将语法分析分成自顶向下和自底向上分析法两种，下面来分别介绍。

自顶向下

自顶向上是从分析树的顶部（根节点）向底部（叶）节点方向构造分析树。

每一步推导中，都需要做两个选择：

1.替换当前句型中的哪个非终结符
2.用该非终结符的哪个候选式进行替换。

针对第一个选择，有最左推导和最右推到，由于我们通常都是从左到右的遍历，所以通常使用最左推导。针对第二个选择，将在下面分析法中介绍。

自顶向下的分析法，对文法有一定的要求，可能需要做文法转换，比如消除左递归，这里不再赘述。

递归下降分析

递归下降由一组过程组成，每个非终结符都对应一个分析过程。该方法从起始非终结符S开始，递归的调用其他的非终结符的对应过程。如果S对应的过程恰好扫描了整个输入串，则成功的完成了递归分析。

这里针对第二个选择，当同一个非终结符对应多个产生式时，可以使用错误回溯或预测分析的方法。回溯的方法会挨个尝试非终结符的产生式，如果后面的解析发生错误，则尝试下一个，这种方法称之为回溯；预测分析通过向前看输入流的k个字符，决定应用的产生式，也就是LL(k)分析法。

预测分析法在每一步推导中根据当前句型的最左非终结符A和当前输入符号a，选择一个正确的A的产生式。对于预测分析法，需要计算非终结符的First集和Follow集，通过这两个集合，可以计算产生式的Select集（eg.SELECT(A -> aB)）来帮助预测分析，通过每个产生式的SELECT集就可以构造预测分析表，预测最细最终就是通过预测分析表来决定选用哪个产生式的。预测分析表的例子如下：

基于回溯的递归下降分析法，每一个非终结符的助理过程大致如下：

function A(scanner) {
    // 选择A的某个产生式，A -> X1X2...XK
    for (i to k) {
        if (Xi为非终结符) {
            X1(scanner)
        } else if (Xi为终结符 && Xi == scanner.read()) {
            scanner.next()
        } else {
            //  发生错误
        }
    }
}

递归的预测分析法通过预测分析表，决定调用哪个过程。我们在这里假设非终结符A对应两个表达式，分别的SELECT集为{:}、{,}大致过程如下:

function A(scanner) {
    // 选择A的某个产生式，A -> X1X2...XK
    for (i to k) {
        if (Xi为非终结符) {
            if (scanner.read() == ':') {
                // 第一个产生式               
            } else if (scanner.read() == ';') {
                //第二个产生式
            }

        } else if (Xi为终结符 && Xi == scanner.read()) {
            scanner.next()
        } else {
            //  发生错误
        }
    }
}

非递归预测分析

非递归的预测分析又叫做表驱动的预测分析，结构如下：

主要由预测分析表、扫描器和一个栈组成。原理与树的深度优先遍历类似，将匹配的产生式入栈，当栈顶与当前的输入符号相同时，栈顶出栈，输入符号向后移一位。

算法的大致流程如下：

X = 栈顶符号

// 栈顶不为空
while (X == '$') {
    if (X为终结符) {
        if (X == scanner.read()) {
            stack.pop();
            scanner.next()
        } else {
            throw Error;
        }
    }

    // 需查预测分析表M
    if (X为非终结符) {
        if (!M[X, a]) {
            throw Error
        } else {
            // 有对应产生式
            stact.pop();
            // 将产生式中的符号从右向左一次入栈
        }
    }
} 

自底向上

自顶向上是从分析树的底部（叶节点）向顶部（根节点）方向构造分析树。

移入-归约分析

自底向上的分析通用框架是移入-归约分析。

移入-归约分析的过程如下：

1.移入，对输入串从左到右扫描，将若干个字符入栈，直到可以对符号串进行归约为止
2.归约，栈顶字符归约成某个产生式的左部
3.语法分析器不断循环上述部分，直到栈顶包含了文法开始符号并且输入串为空；当然还有一种情况是检测到了语法错误

这里有个选择是当可以归约时，是继续移入还是直接归约，确定移入还是归约需要向前查看k个输入符号来决定，这就是LR(k)分析。

由于合适的产生式（句柄）是逐步形成的，所以句柄识别情况是有“状态“的，LR分析法用以下方式描述状态：

S -> bBB
S -> .bBB
S -> b.BB
S -> bB.B
S -> bBB. 

LR分析器的结构如下图所示：

与LR分析器结构不同在于多了一个状态栈，用来描述当前的句柄状态；同时有动作转移表用来描述在某一状态下，遇到某一终结符或非终结符时的动作，该动作有可能是移入、归约、状态变化或成功。

LR分析表的结构如下图所示：

LR分析算法大致流程如下：

while(1) {
    if (ACTION[s, a] == st) {
        // 状态t入状态栈
        // a入符号栈
    } else if (ACTION[s, a] == 归约 A -> X1X2...Xk) {
        // 弹出栈顶k个符号
        // A入符号栈
        // GOTO[t, A]入状态栈
    } else if (ACTION[s, a] == success) break
    else { threo Error }
}

LR(0)分析法是就是不参考后续的输入字符，直接归约的分析法，LR(0)分析法使用的条件是不出现移进-归约和归约-归约冲突，也就是同一状态遇到相同输入时只有一种可选动作，没有歧义。虽然应用面比较小，但我们可以通过它来看LR分析表是如何构造的。

讲解LR分析表构造之前，先讲两个概念增广文法和项目集闭包。

增广文法就是在G中加上新开始符号S'和产生式 S' -> S 而得到的文法，该文法是为了保证接收器只有一个起点。

项目集闭包用来表示句柄分析的状态，是相同的句柄分析状态的集合。举例如下：

有了项目集闭包后，我们就可以以初始状态为起点，构造LR分析表。结果如下：

构造项目集闭包的大致过程如下：

// I 为某一项目集（状态）
// 返回项目集闭包
function clousure(I) {
    J = I

    for (J中每一项 A -> a.Bb) {
        for (文法中每个产生式 B -> xxx) {
            if (b -> xxx 不在J中) {
                // 将 b -> xxx 加入J中
            }
        }
    }

    return J;
}

构造后继项目集闭包（扩展整个项目集）的大致过程如下：

// I 为某一项目集（状态），X 为某一非终结符
function goto(I, X) {
    // 初始化J为空集
    for (I中每一项 A -> a.Xb) {
        // 将 A -> aX.b 加入J
    }

    return clousure(J)
}

以上clousure和goto方法我们可以得到文法的所有状态的集合（项目集）,方法是从clousure({ S‘ -> S })开始，循环检查项目集中所有集合goto(I, X)是否在集合中，不在则加入，直到没有新的项目集加入到集合中为止。

有了上述的项目集闭包，构建LR(0)分析表的过程是循环遍历所有项目集中的所有项目，做如下判断：

1.移入，如果项目集i中有 A -> .aB && goto(Ii, a) == Ij， ACTION[i, a] = sj
2.状态变换，如果项目集i中有 A -> .B && goto(Ii, B) == Ij， GOTO[i, a] = j
3.归约，如果项目集i中有 A -> aB.，ACTION[i, a] = rj
4.成功，如果项目集i中有 S' -> S.,ACTION[i, $] = rj

LR(0)没有考虑分析的上下文环境，有时会出现冲突（移进-归约和归约-归约冲突），简单来说就是选择用哪个产生式归约，是移入还是归约。解决这个问题需要知道句柄归约的条件，需要向前看输入字符了，那么就引出了SLR、LR(1)分析法。

SLR分析法借助FOLLOW集来解决冲突，当然这就决定了冲突相关的非终结符的FOLLOW集不能存在交集，器对上述第三个过程进行了改造，设下一个许茹字符为x, 将归约，如果项目集i中有 A -> aB.，ACTION[i, a] = rj改为归约，如果项目集i中有 A -> aB. && x属于FOLLOW(A)，ACTION[i, a] = rj。

在某些情况下，仅仅根据FOLLOW集来解决冲突是不够的，在特定位置，A的后继字符应该是A的FOLLOW集的子集，FOLLOW集可以帮助我们排出错误选项，但无法具体得知真正遇到哪个后继符号时执行归约，这就引出了LR(1)。

LR(1)分析法的关键是得到项目集中每个项目的展望符，也就是后继终结符，当下一个输入字符正好与展望符相同时，说明可是对该项目执行归约操作。展望符是该项目的后继符号，如果存在项目<A -> a.BX, a> , 其中a是A -> a.Bx的展望符，还有项目B -> .b，那么项目B -> .b的展望符等于first(Xa)。

语法制导翻译

语义分析不设计什么算法，只是分析文法对应的动作，完全可以嵌入在语法分析的算法中，其中语法分析、语义分析、中间代码生成可以合为语法制导翻译。

语法制导翻译为文法中每个定义一个属性，属性分为综合属性和继承属性，综合属性依赖于子节点，继承属性依赖于父节点或兄弟节点。SDT(语法制导方案)的文法如下：

语法分析过程中，计算综合属性可以在归约时计算，继承属性则在继承符号出现前执行，同时，在计算属性过程中还可以执行附加动作（比如注册符号表）。

语法制导翻译简单来说就是在语法分析过程中计算非终结符的属性、执行附加动作。

其中自顶向下的分析中，递归的方法比较简单，即每个非终结符处理函数多加一个继承属性的参数，在函数里面依照制导方案执行相应动作即可；非递归的方式则需要对符号栈进行扩展，加入属性栈，并且非终结符应在栈中具有两项（比如F和F.sync），其中F.sync代表F的综合属性，需要其子节点都计算完成后才能计算，F出栈时，F.sync会暂时留在栈中，知道计算完成后出栈。

要想在自底向上的语法分析中加入动作，首先需要替换表达式中间的语义动作，使所有语义动作位于产生式末尾。如下所示：

同时自底向上的语法分析中加入动作也需要扩展符号栈，加入属性栈。

总结

本文简要梳理了词法分析、语法分析、语法制导翻译的过程，可以看出其中关键的就在于自顶向下、自底向上的语法分析，而非递归的语法分析都是借助栈来完成的。