georgehu学习生活 - 编译技术（3）-语法分析

第3章语法分析

语法分析要解决的问题：对任一个上下文无关文法$G[S]=(V_T,V_N,P,S)$与一个任意的$w\in V_T^*$，判断$w$是不是在$G[S]$定义的语言$L(G)$中？

实现语法分析有两种大方向：自顶向下（推导）和自底向上（归约）

由于推导更符合大多数人的思维习惯，若根据该文法推导出了待判断的符号串，则这个符号串是符合语法的

确定的自顶向下语法分析

“确定的”指的是可以根据文法的一些特点，启发式地唯一确定非终结符的推导选择。

例如对于下述文法，要判断$aaab$是否符合语法

$$ \begin{align*} &S\rightarrow AB\\ &A\rightarrow aA|a\\ &B\rightarrow bB|b \end{align*} $$

从开始符号$S$出发，窗口设为2（即两个单词两个单词看）推导思路如下

要以$a$开头，$S$只能选择推导为$AB$，得到$S\Rightarrow AB$
要推导出$aa$，$A$只能选择推导为$aA$，得到$AB\Rightarrow aAB$，匹配上一个a，窗口后移1，后移后窗口中为$aa$
同样要推导出$aa$，只能选择$aAB\Rightarrow aaAB$，窗口后移1，后移后窗口中为$ab$
只需要匹配一个$a$，$A$选择$a$进行推导，得到$aaAB\Rightarrow aaaB$，窗口后移1，窗口中剩下$b$
只需要匹配一个$b$，$B$选择$b$进行推导，得到$aaaB\Rightarrow aaab$，判断$aaab$是符合语法的

显然，这种“启发式”的推导非常局限，对于需要结合待判断符号串很后面信息进行判断时，这种方法就很不现实，看不到未来的信息

LL(1)文法

LL(1)文法可以在最左推导过程中，实现只读取一个单词，就可以做出唯一、确定的推导选择。在此之前，需要学习几个计算

FIRST集

FIRST($\gamma$)，即$\gamma$的首符号集，其中$\gamma\in(V_T\cup V_N)$。FIRST($\gamma$)指出了$\gamma$经过若干步推导后，转换成的东西的第一个终结符的所有可能。下面是其严格定义

$$ FIRST(\gamma)=\left\{a|\gamma\overset{*}{\Rightarrow}a\theta,a\in V_T,\theta\in(V_T\cup V_N)^*\right\} $$

显然，若$\gamma\in V_T$，$FIRST(\gamma)=\{\gamma\}$；特别的，对于产生式$X\rightarrow \varepsilon$，有$\varepsilon\in FIRST(X)$

计算FIRST(A)，可按如下步骤进行

初始化所有$V_N$的FIRST集为空
依次扫描各个产生式，按FIRST集性质修改FIRST集，直到本遍扫描中没有任何新元素被添加到FIRST集中

例如扫描$S\rightarrow AB$时，要把FIRST(A)加到FIRST(S)中去，若A可能推导为$\varepsilon$，则还要把FIRST(B)加到FIRST(S)中

FOLLOW集

FOLLOW($A$)，即$A$的后继符号集，其中$A\in V_N$。FOLLOW($A$)指出了$A$经过若干步推导后，其后面紧贴着的终结符的所有可能。下面是其严格定义（#表示序列结束）

$$ FOLLOW(A)=\left\{a|S\#\overset{*}{\Rightarrow}\xi A\sigma\#,a\in FIRST(\sigma\#),\sigma,\xi\in(V_T\cup V_N)^*\right\} $$

显然，$\#\in FOLLOW(S)$

计算FOLLOW集，可按如下步骤进行

初始化FOLLOW(S)=$\{\#\}$，其他非终结符的FOLLOW集初始化为空
依次扫描包含非终结符的产生式右部，按下面两条规则（以非终结符B为例）修改FOLLOW集，直到FOLLOW集不再改变
- 若存在$A\rightarrow\alpha B\beta$样式的产生式，将FIRST($\beta$)-$\{\varepsilon\}$加到FOLLOW(B)中。其实B后面紧跟的第一个终结符必然包含$\beta$可以产生的东西的第一个终结符
- 若存在$A\rightarrow\alpha B$或$A\rightarrow\alpha B\beta（\beta\overset{*}{\Rightarrow}\varepsilon，即\varepsilon\in FIRST(\beta）$，则将FOLLOW(A)加到FOLLOW(B)中去。其实就是当B后面没东西时，B后面紧跟的必然包含A后面紧跟的

例如对于下面的文法，在扫描$A\rightarrow aCBA|\varepsilon$时，根据第一条规则，需要将FIRST(BA)-$\{\varepsilon\}$加到FOLLOW(C)中、将FIRST(A)-$\{\varepsilon\}$加到FOLLOW(B)中；根据第二条规则，需要将FOLLOW(A)加到FOLLOW(B)中、将FOLLOW(A)加到FOLLOW(C)中

$$ \begin{align*} &S\rightarrow AB\\ &A\rightarrow aCBA|\varepsilon\\ &B\rightarrow bC|\varepsilon\\ &C\rightarrow c \end{align*} $$

充要条件

一个上下文无关文法成为LL(1)文法的充要条件，对于每个非终结符A，且$A\rightarrow\gamma_1|\gamma_2|\cdots|\gamma_n$：

对于任意两个不同的候选式，他们FIRST集的交集为空（显然，若有交集，用后面的方法写代码就无法判断这个交集中的各终结符应该对应哪个分支），即他们不能推导出以相同终结符为首的符号串，也不能同时推导出$\varepsilon$
若有$\gamma_i\Rightarrow\varepsilon$，那么对于$j=1,2,\dots,n$且$j\ne i$，必须满足FIRST($\gamma_j$)$\cap$FOLLOW($\gamma_i$)=$\varnothing$（事实上，这也是为了保证在parseA中与FIRST集中$\varepsilon$对应分支可以唯一判断进入）

左递归与左公因子

存在左递归和左公因子的文法一定不是LL(1)文法

消除左递归的方法：

设左递归的产生式为$P\rightarrow P\alpha|\beta$，将其改写为

$$ P\rightarrow \beta Q\\ Q\rightarrow \alpha Q|\varepsilon $$

消除左公因子的方法：

设有左公因子的产生式为$P\rightarrow \alpha\beta|\alpha\gamma$，将其改写为（非常类似于提取公因子）

$$ P\rightarrow \alpha Q\\ Q\rightarrow \beta|\gamma $$

递归下降的语法分析

采用递归下降的语法分析程序，不断地匹配终结符，对于每个非终结符，使用子函数进行递归处理

$$ \begin{align*} &S\rightarrow aAS|bB|d\\ &A\rightarrow BbS|\varepsilon\\ &B\rightarrow c \end{align*} $$

对于上面的文法，有三个非终结符，即要写三个函数

// 处理非终结符S
void ParseS() {
    // 每个分支对应一个候选式
    // 匹配上第一个候选式的FIRST集
    if (token == a) {
        // 终结符a被此候选式匹配解析掉，调用gettoken让token中存储好下一个待解析的词法符号
        gettoken();
        parseA();
        parseS();
    }
    else if (token == b) { // 匹配上第二个候选式的FIRST集
        gettoken();
        parseB();
    }
    else if (token == d) {  // 匹配上第三个候选式的FIRST集
        gettoken();
        return;
    }
    else { // 碰到语法中没有的情况，报错
        error();
    }
}

// 处理非终结符A
void ParseA() {
    if (token == c) { // 匹配上第一个候选式的FIRST集，FIRST(B)={c}
        parseB();
        if (token == b) {
            gettoken();
        }
        else {
            error();
        }
        parseS();
    }
    else if (token == a || token == b || token == d) { // 空串分支，匹配FOLLOW(A)
        // 这个分支验证了语法的正确性，实际上匹配了空串，但由于空串本身无法作为token存储，也就无需调用gettoken
        return;
    }
    else {
        error();
    }
}

// 处理非终结符B
void ParseB() {
    if (token == c) { // 匹配上第一个候选式的FIRST集，FIRST(c)={c}
        gettoken();
    }
    else {
        error();
    }
}

第3章 语法分析