编译原理（一）

词法分析

编译器的目的是根据源码生成可以执行的文件，想一步到位完全不靠谱，可以先进行分词处理，那么这就是词法分析要完成的工作了！

用正则表达是来描述词法规则是比较简单的，而用状态机进行匹配则是比较迅速的，那么比较重要的就是在他们之间的互相转换：

这里有：

概念	含义
NFA	不确定自动机，从当前状态根据字符转移的时候，下一个状态是不确定的
DFA	确定自动机，状态转移时下一个状态时确定的

来看一个NFA的例子，对于(a|b)*abb这样的词，对应的NFA为：

在遍历的过程中顺便更新状态就可以了，用代码来描述一下：

S = ε-closure(s0); // 注意：这里的S是个集合
c = nextChar();
while(c != eof){
    S = ε-closure(move(S,c));// 状态转移+空转移
    c = nextChar();
}
if(S ∩ F != ∅) return "yes";
eles return "no";

看起来NFA的模拟方式效率并不高，而且代码写起来也有点小复杂，而DFA则完全不一样：

s = s0;
c = nextChar();
while(c != eof){
    s = move(s, c);
    c = nextChar();
}
if(s在F中) return "yes";
else return "false";

是不是简单了很多？但是也更显然，NFA与正则之间的关系更加直观，那么先来看从正则到NFA的转换：

用这种方式从(a|b)*a得到的NFA为：

既然DFA相对于NFA来说是有优势的，那么如果有一个方法能将NFA转换为DFA，那么可以一劳永逸。这里子集构造法还是相当的直观的的：

一开始，ε-closure(s0)是Dstates中唯一状态，且它未加标记;
while(在Dstates中一个未加标记状态T){
    给T加上标记;
    for(每个输入符号a){
        U = ε-closure(move(T,a));
        if(U不在Dstates中)
            将U加入到Dstates中，且不加标记;
        Dtran[T,a] = U;
    }
}

其中的：

操作	描述
ε-closure(s)	能够从NFA的状态s开始只通过ε转换到达的NFA状态集合
ε-closure(T)	能够从T中某个NFA状态s开始只通过ε转换到达的NFA状态集合
move(T,a)	能够从T中某个状态s出发通过标号a的转换到达的NFA状态的集合

那么现在就有一条路径了：正则->NFA->DFA也太累了，有没有正则->DFA这样一条通路？答案是肯定的，首先根据正则构造出抽象语法树：

初始化Dstates,使之只包含未标记的状态firstpos(n0),其中n0是r(#)的抽象语法树的根节点;
while(Dstates中存在未标记的状态S){
    标记S;
    for(每个输入符号a){
        令U为S中和a对应的所有位置p的followpos(p)的并集;
        for(U不在Dstates中)
            将U作为未标记的状态加入到Dstates中;
        Dtran[S,a] = U;
    }
}

其中：

定义	含义
nullable(n)	节点n的子表达式的语言中包含ε
firstpos(n)	以节点n为根的子表达式中第一个符号的位置的集合
lastpos(n)	以节点n为根的子表达式中最后一个符号的位置的集合
followpos(p)	可能出现在位置p后面的位置的集合

其实背后的底层原理与从NFA到DFA还是比较相似的，只不过是用不同的构造方式来做。DFA确实要比NFA好处理一些，但并不是说生成DFA之后就没事了，其中的状态数可以压缩：

1. 根据接收、非接收状态分为两组；
2. 遍历分组、字符，如果同一组内的状态根据该字符到达了不同的组，那么将继续将当前的分组进行分割；
3. 重复执行步骤2直到没有变化；
4. 每个分组中选择一个代表状态，重新构造DFA，最小化完成；

可以证明最小化状态数的DFA唯一性，然而最小化的过程更加容易让我们去理解状态机的本质。来个最小化状态数的例子：

语法分析

语法分析器从词法分析器得到TOKEN流，生成语法分析树或者抽象语法树，方便进一步地处理。预发处理的规则通常是用上下文无关文法来描述：

• E → E+T|T // 从E+T可以推导出E，也可以从T推导出E
• T → T*F|F
• F → (E)|id

对于一个TOKEN流，语法分析器的目的是就是把这些规则“套”上去，从而知道输入的内容是什么样的结构，而输出可能是：

左边是分析语法树，右边是抽象语法树，比较而言抽象语法树更简单一些，而且便利起来更加容易。如果通过一个语法在推导某个式子的时候可以得到两个不同的语法树，那么说明这种语法是有二义性的，比如if E1 then if E2 then S1 else S2中的else就不知道应该对应哪个if，那么进行修改：

消除二义性好像没有什么万能的方法，但是消除左递归却是有的：

按照某个顺序将非终结符号排序为A1、A2....
for(从1到n的每个i){
    for(从1到i-1的每个j){
        将每个形如Ai→Ajϒ的产生式替换为产生式组Ai→δ1ϒ|δ2ϒ|...
        其中Aj→δ1|δ2|....是所有Aj的产生式
    }
    消除Aj产生式之间的立即左递归
}

是不是有点像拓扑排序？有了这些规则那么就需要写程序来按照其描述的逻辑进行处理，说白了就是用程序的结构去模拟预发的结构：

void A(){
    选择A的一个产生式，A→X1X2X3...
    for(i = 1 to k){
        if(Xi是一个非终结符号)
            调用过程Xi();
        else if(Xi等于当前输入符号a)
            读入下一个输入符号
        else
            /* 发现错误，需要回溯 */
    }
}

典型的自顶向下分析的方法，用递归来实现很容易与语法规则对应起来，但是在出现错误的时候就退回重试显示效率低下的处理方式。在知道下一个TOKEN是什么的情况下就知道用那个产生式，那么就不需要那么多无谓的尝试了，这就是LL(1)的想法，需要两个集合：

集合	含义
FIREST(α)	可以由α推导得到的串的终结符的集合
FOLLOW(A)	在某些句型中紧跟在A右边的终结符号的集合

那么之后在终结符号A处使用FOLLOW(A)中的产生式来进行处理即可，这时候非递归的写法也是非常简单的。其实构造FIRST和FOLLOW的过程还是挺简单的，不再赘述。

下面接着来看自底向上的分析过程：

在这种方式中我们并不是从“根”出发的，而是在看到能处理的部分就把它处理掉，可以用栈来实现：

比较麻烦的是，我们不知道当前有哪些是可以处理的，按道理来说每次在需要的时候去遍历产生式并递归来做也是可以搞定的，但是不免会有很多的遍历是重复劳动，那么就需要预处理了。对于表达式A→XYZ，如果考虑位置的话有四种情况：

1. A→.XYZ
2. A→X.YZ
3. A→XY.Z
4. A→XYZ.

我们将这些称为项，由一个语法的产生式对应的过个产生式中有一些是等价的，将他们放在同一个集合（项集）中，比如对于语法 ：

• E’→E
• E→E+T|T
• T→T*F|F
• F→(E)|id

生成项集之后，在遇到一个TOKEN的情况下就知道下个项集是什么了，这样我们根据上面的语法就得到了一个状态图：

项集闭包的构造方法比较简单：

SetOfItems CLOSURE(I){
    J = I;
    repeat:
        for(J中的每个项A→α.Bβ)
            for(G的每个产生式B→γ)
                if(项B→.γ不在J中)
                    将B→.γ加入J中;
    until 在某一轮中没有新项被加入到J中;
    return J;
}

有了状态的定义，那么接下来需要定义状态之间的转换：GOTO(I,X)表示了形如A→α.Xβ所在的项集到A→αX.β的转换，构造方法如下：

void items(G'){
    C = {CLOSURE([S'→.S])};
    repeat
        for(C中的每个项集I)
            for(每个文法符号X)
                if(GOTO(I,X)非空且不在C中)
                    将GOTO(I,X)加入C中;
    until 在某一轮中没有新的项集被加入到C中;
}

有了上面这些，我们可以开始构造一个SLR(1)语法分析表了：

1. 如果[A→α.aβ]在Ii中并且GOTO(Ii,a)=Ij，那么将ACTION[i,a]设置为“移入j”;
2. 如果[A→α.]在Ii中，那么对于FOLLOW(A)中所有的a，将ACTION[i,a]设置为规约“规约A→α”;
3. 如果[S’→S.]在Ii中，那么将ACTION[i,$]设置为“接受”;

在分析程序中用一个栈来记录当前看到的状态，然后根据ACTION来进行操作即可。

在LR(0)中能规约的时候就规约，这样做很不科学，但是在有冲突的时候好像没有别的方法，只能“向前看”。规范LR充分地利用了向前看符号，利用一个很大的项集来工作，每个项的格式如下：

形式为[A→α.Bβ,a]，前半部分不变，后半部分为向前看符号

构造方法如下：

SetOfItems CLOSURE(I){
    repeat
        for(I中的每个项[A→α.Bβ,a])
            for(FIRST(βa)中的每个终结符号b)
                将[B→.γ,b]加入到集合I中
    until 不能向I中加入更多的项
    return I;
}
SetOfItems GOTO(I,X){
    将J初始化为空集;
    for(I中的每个项[A→α.Xβ,a])
        将项[A→αX.β,a]加入到集合J中
    return CLOSURE(J);
}
void items(G'){
    将C初始化为{CLOSURE}({[S'→.S,$]});
    repeat
        for(C中的每个项集I)
            for(每个文法符号X)
                if(GOTO(I,X)非空且不在C中)
                    将GOTO(I,X)加入到C中;
    until 不再有新的项集加入到C中;
}

对于文法：

• S’→S
• S→C C
• C→c C | d

得到的规范LR项集的状态图如下：

此时构造分析表的方法如下：

1. 如果[A→α.aβ，b]在Ii中且GOTO(Ii,a)=Ij，那么将ACTION[i,a]设置为“移入j”;
2. 如果[A→α.,a]在Ii中且A≠S’，那么将ACTION[i,a]设置为“规约A→α.”;
3. 如果[S’→S,$]在Ii中，那么将ACTION[i,$]设置为“接受”;

这种方式和SLR的运行方式类似，不再赘述！

向前看LR(LALR)基于LR(0)项集族，和基于LR(1)项的典型语法分析器相比，状态要少很多，通过想LR(0)项中小心地引入向前看符号，我们使用LALR方法处理的文法比使用SLR处理的文法更多，同时构造得到的语法分析表并不比SLR语法分析表大，通常情况下LALR方法是最合适的选择。

可以将LALR看做是将LR(1)中有相同核心项的项集合并，那么按照这种思路就可以从LR(1)构造得到LALR的分析表和GOTO，但是耗费空间巨大，基本思想为：

将LR(1)中相同核心项集合并，在新的项集族上计算GOTO，进而生成分析表。

总共有三种冲突：

1. 规约-规约
2. 规约-移入（不可能出现）
3. 移入-移入

然后跟上面一样在合并完的结果上构造语法分析表，如果出现冲突则说明该文法不是LALR(1)的。从LR(1)合并得到LALR(1)需要较大的内存，另一种高效的思路是从LR(0)添加向前看符号，添加途径有两种：

1. 自发
2. 传播

第二种方式会将源头所有的向前看符号都“传播”给目标，这里有一个简单的办法来区分自发和传播：令#为一个不在当前文法中的符号，对于LR(0)项集I的内核K以及一个文法符号X：

for(K中的每个项A→α.β){
    J:=CLOSURE({[A→α.β,#]});
    if([B→ϒ.Xδ,a]在J中，并且a不等于#)
        断定GOTO(I,X)中的项B→ϒ.Xδ的向前看符号a是自发生的
    if([B→ϒ.Xδ,#]在J中)
        断定向前看符号从I中的项A→α.β传播到了GOTO(I,X)中的项B→ϒX.δ上
}

下面来看构造LALR(1)项集族内核的计算方法(输入增广文法G)：

1. 构造G的LR(0)项集族的内核
2. 对每个内核和文法符号通过上面方法计算自发、传播
3. 初始化表格，表中给出每个内核项的向前看符(最初每个项的向前看符只有自发产生的符号)
4. 在扫描中根据传播的关系，从源头复制向前看符集合到目标项，不停地扫描知道没有新的向前看符号被传播为止

对于下面文法：

• S’→S
• S→L=R|R
• L→*R|id
• R→L

得到的向前看符号传播和向前看符号的计算结果如下：

到目前为止我们总是在构建ACTION出现冲突的时候说：这不是XXX文法。但是反过来想一下其实二义文法在描述的时候还是非常简单的，我们可以通过一些额外的手段来消除二义（在ANTLR中非常明显）。

总结

到这里基本上可以随意搞Lexer和Parser了，可以看编程语言实现模式来来熟悉一下实际的代码是什么样的（可惜这本书只有LL的）!