Compiler03 语法分析
Published:
\newcommand\norm[1]{\left\lVert#1\right\rVert} \newcommand\abs[1]{\left\lvert#1\right\rvert} 写的时候复制到笔记2那里去了…晕，这个点还不睡就是不行啦
CFG
上下文无关语法(Context Free Grammar)，或者说BNF(Backus Naur Form)，是用于描述一类语言的法则，也即是语法
语法包括：
终结符号(terminal)集 $T$
非终结符号(nonterminal)集 $N$
推导规则(rule of inference) $R$
起始符号 $s_0$
任意规则有如下形式：
$h\rightarrow B$，其中 $h$ 是非终结符，$B$ 是 $T\cup N$ 上的串
对于给定的串 $s$，若存在推导规则 $r:h\rightarrow B$，且 $h\in s$，则用 $B$ 替换 $s$ 中的一个 $h$ 得到新串 $s’$ 称为一次推导，记作 $s\underset{r}\Rightarrow s’$，也可以简单记作 $s\Rightarrow s’$
若串 $s$ 中出现多个 $h$，则我们称对最左侧的 $h$ 的替换推导为最左推导(left-most)，同理有最右推导的概念
为了方便，规定 $a\overset{*}\Rightarrow b$ 表示 $a$ 经由零次或多次推导可以得到 $b$，而 $a\overset{lm}\Rightarrow b$ 和 $a\overset{rm}\Rightarrow b$ 分别表示一次最左和最右推导
从起始符号 $s_0$ 开始，若存在串 $e$ 使得 $s_0\overset{*}\Rightarrow e$，则我们称 $e$ 是该语法的一个句型/句式。若 $\forall x(x\in e\rightarrow x\in T)$，则称 $e$ 是一个句子
用 $L(T,N,R,s_0)$ 表示该语法规定的语言，则容易知道所有的句子构成了语言本身(废话)
叫上下文无关，就是因为我们的推理规则要求推理的左侧只能是单独的非终结符，即替换可以发生在任何位置而与被替换的符号的上下文无关
表达能力
如何比较语法的表达能力？或者说，怎么判断一种新的语法和已知语法的表达能力强弱？
直观地，若 $L(G_1)\subseteq L(G_2)$，则我们称语法 $G_1$ 表达能力不强于 $G_2$。
乔姆斯基把语法分成四类，其中两类便是CFG和RG(regular grammar)，可以证明他们的表达能力是存在差异的
命题：正则语法的表达能力严格弱于上下文无关语法
首先证明 $L(RG)\subseteq L(CFG)$。根据正则表达式的递归定义，我们可以这么构造对应的CFG：
$\epsilon$，对应 $h(\epsilon)\rightarrow \epsilon$
$c,c\in\Sigma$，对应 $h(c)\rightarrow c$
$s t$，其中 $s,t$ 是正则表达式，对应 $h(s t)\rightarrow h(s) h(t)$ $st$，对应 $h(st)\rightarrow h(s)h(t)$
$s^$，对应 $h(s^)\rightarrow h(s)h(s^*) \epsilon$ - $(s)$，对应 $h((s))\rightarrow h(s)$
注意到正则表达式长度有限，因此我们构造的非终结符有限，同理推导规则有限，因此这是一个CFG，并且可以归纳证明 $L(CFG)=L(RG)$，即任意正则表达式都存在一种上下文无关语言，使得他们的表达能力相等。这就说明了 $L(RG)\subseteq L(CFG)$
再证明 $L(RG)\neq L(CFG)$，即存在一种CFG能表达但RE无法表达的语言。这个构造很强，而且能说明很多问题，值得体会一会儿
考虑如下上下文无关语法：
| $S\rightarrow aSb | \epsilon$ |
它表示的是所有形如 $ab,aabb,aaabbb\ldots$ 的串的集合。下面证明正则表达式无法表示这种语言
注意到任意正则表达式可以化为等价的DFA，因此只需要证明不存在可以识别该语言的DFA即可
由反证法，假设存在这样一个DFA，不妨设其状态数为$n$，则根据抽屉原理在识别前$n$位的时候，必然存在 $i\neq j$ 使得 $tr(start,a^i)=tr(start,a^j)$
根据定义，DFA能识别串 $a^ib^i$ 和 $a^jb^j$，再根据状态转移的等式有 $tr(start,a^ib^i)=tr(tr(start,a^i),b^i)=tr(tr(start,a^j),b^i)=tr(start,a^jb^i)\in E$，即该DFA也能识别串 $a^jb^i$，这与假设矛盾。
也就是说，任意的 $n\in \mathbb N$，我们都能找到一个串使得其满足CFG规定的形式但是不能被DFA识别。于是证毕
关于正则/DFA的证明大多依赖于反证法和抽屉原理这两大保健，然后结合状态转移的结合性来说明某个状态的接受性，最后得出矛盾。同时这里的问题也直观说明了正则表达式没法表示同时向左和向右无限延伸的串，因为DFA一旦从某一位开始无限延伸，就意味着它前面必须是有限位。
(扯远点，也就是说CFL-Reachability不能简单地用DFA解决，而是要用一个PDA….一周前的我还是太naive了！)
ST
从初始符号开始到任意句子的推导过程隐式地产生了语法树(Syntax Tree)的结构，即考虑任意单次推导 $a\Rightarrow b$，如果我们把 $a$ 视作根，$b$ 中的所有字母看作儿子，那么树形结构就出来了。具体的证明只需要注意到每个字符的父亲唯一(上下文无关的定义)，结合句子的定义说明一下就好了。
有个比较显然的性质：任意语法树的叶子都是终结符，且从 $s_0$ 到句子 $s$ 的推导产生的语法树的 所有叶子的前序遍历序 恰好构成了 $s$ 本身
最左推导
很显然一个推导序列唯一地构造了一棵语法树，然而一棵语法树并不唯一对应一个推导序列(考虑同一层出现了多个非终结符号，选择的次序就产生了不同的推导)
为了构造推导序列到语法树的双射，我们提出了最左推导的概念。即在最左推导下，语法树和推导序列是一一对应的。
二义性
注意到即使我们规定了最左推导，同一句子的推导仍然不唯一，构造的语法树也不唯一，因此自然引出二义性的问题
注意二义性是针对语法而言的而与串无关，即语法 $G$ 有二义性当且仅当存在串 $str\in L(G)$，使得存在两种从初始符号 $s_0$ 开始的推导序列 $l_1,l_2$ 满足 $s_0\overset{}{\underset{l_1}\Rightarrow}str$ 且 $s_0\overset{}{\underset{l_2}\Rightarrow}str$
举个例子，考虑如下语法：
| $Expr\rightarrow \epsilon | Number | Expr+Expr | Expr*Expr$ |
$Number\rightarrow \text{[1-9][0-9]*}$
这里的 $Number$ 是用正则语言表达的
这个语法对于语句 $1+1*2$ 就存在多种推导，但它们都是最左推导
例如 $Expr\Rightarrow Expr+Expr\Rightarrow 1+Expr\Rightarrow 1+ExprExpr\Rightarrow 1+1Expr\Rightarrow 1+1*1$
和 $Expr\Rightarrow ExprExpr\Rightarrow Expr+ExprExpr\Rightarrow 1+ExprExpr\Rightarrow 1+1Expr\Rightarrow 1+1*1$
具体表现出来就是+*优先级冲突的问题
二义性的消除
二义性的消除没有通用方法，需要根据语义和语法灵活处理(这不是说了等于没说吗喂)
虽然没有通用做法，但这一步还是必不可少的！
小结一下就是
最左推导构造了语法树和推导序列的双射
二义性的消除保证了句子的最左推导序列唯一，即每个句子和语法树存在双射
左递归
若语法 $G$ 存在 $A\overset{*}\Rightarrow A\alpha$，其中 $A$ 是非终结符(废话)，$\alpha$ 是 $N\cup T$ 上的非空串，则我们称 $G$ 存在左递归(left recursion)
为了消除二义性我们需要规定一个推导顺序，而规定了推导顺序后自然引出终止的问题。容易发现存在左递归的文法 $G$ 的推导过程不一定终止
这个很好玩，好玩的地方在于它有点像前面造DFA的时候用Arden’s TH解正则式状态方程(事实上这是一个右线性文法，确实是正则语言…)
左递归的消除
| 考虑最简单的形式，即单个直接的左递归如何处理 $A\Rightarrow A\alpha | \beta$ |
由 Arden’s TH 可知 $A$ 能产生的所有串用正则语言表达就是 $\beta{\alpha}^*$。注意到除了第一个字符外，剩下的部分都是若干片段的重复，因此考虑把两部分分开做。
不妨设 $A’\rightarrow \alpha A’|\epsilon$，而 $A\rightarrow \beta A’$，这样就用非左递归的方式表示出了原本存在左递归的语法
对于间接的左递归(即存在推导序列 $l$ 使得 $A\underset{l}\Rightarrow A\alpha$)，我们这么考虑：
首先为所有的非终结符号编号，设共有 $n$ 个，建图
对于一对非终结符 $A_i,A_j$，若存在推导序列 $A_i\Rightarrow A_j\alpha$，则连边 $i\rightarrow j$
于是存在左递归$\iff$ 存在有向圈
问题变成了存在一些具有传递性的边(即 $i\rightarrow j,j\rightarrow k$ 可得 $i\rightarrow k$)，我们已知怎么去掉一个点的自环(消除直接左递归)，问要如何消除所有的有向圈
一个做法就是规定编号为 $i$ 的点只能连向编号大于 $i$ 的点(容易归纳证明这样无环)，对于不满足的边我们用边的传递性使之越过若干中间节点。于是书上的算法就很好理解了
先写到这里，去睡觉/(ㄒoㄒ)/
Top-Down Parsing
再次回顾语法分析的目标：判断给定的串 $code$ 是否是语法 $G$ 的语言，如果是的话给出语法树结构
为了讨论的方便，下面提到的文法都是无二义性文法
考虑对起始符号 $s_0$ 的一个最左推导，若 $s_0\overset *{\underset{lm}\Rightarrow}code$，由文法无二义性可知推导序列唯一，且其作为最左推导唯一对应与一棵语法树。
Top-Down实际上就是在模拟这个过程。即我们每次从当前句型中取出最左的nonterminal $N$，根据某个 $N$ 作为head的产生式替换得到新的句型
递归下降
没啥好讲的很sb的技术，也就是我们每次尝试所有可能的产生式，如果遇到了不能匹配情况就回溯….
LL(1) 文法
在认真研读龙书前，我对语法分析的理解停留在递归下降的层面，并好奇工业上究竟是怎么解决这么一个复杂的问题的….
现实令人吃惊，通常面对一个很难的问题，我们不仅可以用精巧的做法解决它，还可以用更简单的case回避它！LL(1)文法就是这么出现的
准备工作
给定上下文无关文法 $G(N,T,s_0,R)$
首先定义两个函数 $FIRST(\alpha)\colon \left(N\cup T\right)^+\mapsto T\cup\left{\;\epsilon\;\right}$ 和 $FOLLOW(A)\colon N\mapsto T$ ，含义分别如下
$c\in FIRST(\alpha)$ 当且仅当 $\alpha\overset \Rightarrow cy$，其中 $\alpha$ 是非终结符和终结符上的串， $c$ 是某个终结符，$y$ 是终结符上的串。若 $\alpha\overset\Rightarrow\epsilon$，则规定 $\epsilon\in FIRST(\alpha)$
$c\in FOLLOW(A)$ 当且仅当 $\exists yc\in L(G)$ 满足 $A\overset*\Rightarrow y$，其中 $A$ 是某个非终结符，$c$ 是某个终结符，$y$ 是终结符上的串。特殊规定 $code$ 的末端有一个终结符 $EOF$，且 $EOF$ 只能出现在串的末尾
LL(1) 文法要求：
任意共享同一个head的两个产生式 $A\rightarrow \alpha$ 和 $A\rightarrow \beta$，都满足 $FIRST(\alpha)\neq FIRST(\beta)$
任意共享同一个head的两个产生式 $A\rightarrow\alpha$ 和 $A\rightarrow\beta$，都满足至多有一个body的 $FIRST$ 有 $\epsilon$
任意共享同一个head的两个产生式 $A\rightarrow\alpha$ 和 $A\rightarrow \beta$，若 $\epsilon\in FIRST(\alpha)$，则必有 $FOLLOW(A)\neq FIRST(\beta)$，反之亦然。
琢磨一下这几条规则的含义需要首先搞懂两个函数在干什么
$FIRST(\alpha)$ 表明了句型 $\alpha$ 最终产生的所有句子的可能的第一个字符
$FOLLOW(A)$ 表明了非终结符 $A$ 产生的所有终结符序列(不一定是句子，因为 $A$ 不一定是起始符号)在所有句子中后续紧邻着的字符
也就是说，LL(1)文法所有共享head的产生式都走向了不相交的分支，确定走哪一个只需要根据下一个非终结符的从属关系就能判断了
由此自然得到LL(1)文法的真正含义：从左往右读取(第一个L)，最左推导(第二个L)，推导非终结符时产生式的选择只需1个终结符即可判定 的文法
于是也就可以理解为什么上面要提到提取左公因子的做法了，只是为了把非LL(1)文法改造成LL(1)文法而已
求 $FIRST(),FOLLOW()$
先考虑怎么求FIRST
终结符的FIRST很好求
非终结符的FIRST只需要逐个判断产生式，再顺序判断产生式的每一项就好了
终结符和非终结符的串的FIRST可以看成是某个不存在的非终结符的body，那么就和上面一样了
再看看怎么求FOLLOW
起始符号的FOLLOW很好求，是$EOF$
对于每个非终结符，找到所有body包含它的产生式，往后根据FIRST规定集合的约束。有些来自FOLLOW，有些来自head的FOLLOW，这部分和FIRST是差不多的
制表
可以预处理出 $N\times T$ 的表，表示对于不同的状态(非终结符)和下一个输入(终结符)，我们应该采取哪一条产生式
由于任意两个产生式的FIRST不交，因此只需要枚举每个产生式和它body的FIRST，就可以得到表项了
对于表中空出的位置我们可以填入报错信息，也可以额外填入对应的错误处理方法
PDA
这个很有意思，但我还不是很懂，大概写一下定义就跑路(
下推自动机的形式化定义为一个七元组 $(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$
$Q$：状态的有穷集合
$\Sigma$：符号的有穷集合
$\Gamma$：一个叫堆栈(Stack)的数据结构，支持：1. 在顶端插入一个字符 2. 取出顶端的字符 3. 读取而不取出顶端的字符
$\delta$：转移函数 $Q\times \Sigma\times\Sigma\mapsto Q$，即转移状态由当前状态、输入和栈顶状态共同决定
$q_0$：初始状态
$Z_0$：初始符号，即初始栈中的元素
$F$：接受态的集合
Bottom-Up Parsing
自底向上语法分析期望做到这样一件事情：我们手上时刻保存着一个最右句型，并根据当前局面的情况作出如下操作：将连续若干符号收缩(用某条产生式的逆替换)成一个非终结符，且不改变最右句型这一性质。
换句话说，假设我们得到了起始符号 $s_0$ 到最终句子 $c$ 的一个最右推导序列 $l_{rm}$，那么我们需要希望通过对 $c$ 的分析得到 $l_{rm}$ 的逆 ${l_{rm} }’$。
具体的实现需要用到一个栈，保存当前最右句型仍未展开的部分；以及剩余全部已经展开为终结符的字符流。在栈顶和字符流的最左端，就是上一次发生推导的位置。注意到所有在当前栈顶的非终结符展开之后才展开的非终结符，必然都已经展开成了字符流(有点绕但一定要看明白)，否则违反最右句型的定义。因此每次面临的选择只有两个：
规约(Reduce)，将栈顶的若干符号根据某产生式的逆，替换为一个非终结符，记作一次规约
移入(Shift)，目前任意栈的前缀都无法匹配任何产生式的右端，表明所有栈顶位置之前的符号都已经规约完毕，继续规约需要用到栈顶位置往后的终结符，因此移入一个终结符到栈顶。
因此一个通用的LR Parser由四部分组成：
token流的buffer
一个栈
一个
GOTO表一个
ACTION表
与上面直观的分析不同，此处的栈储存的是状态
这里通用的真正含义在于：所有不同的LR方法的区别仅在于构造的GOTO和ACTION表不同，或者说构造算法存在差异。这就很适合自动生成了
实际上GOTO表、ACTION表、栈共同组成了一个下推自动机(Push Down Automata)
GOTO和ACTION表
$GOTO[x,ch]=y$ 表示在PDA的状态$x$，遇到非终结符 $ch$ 时，会转移到状态 $y$
$ACTION[x,tch]$ 记录了在状态 $x$，遇到终结符 $tch$ 时，应该进行什么操作(移入还是规约？移入什么状态？用哪条产生式的逆进行规约？)。这是不同LR策略之间的最本质区别
于是一个通用LR Parser的工作流程就可以描述为：
记栈顶为 $top$， 每次读入符号 $ch$，根据 $ACTION[top,ch]$ 判断是否规约
如果规约，则从栈中弹出产生式的右端(对应的状态)。记产生式的左端为 $H$，那么当前到达的状态就是 $GOTO[top’,H]$，其中 $top’$ 是弹出产生式右端后，得到的栈顶。
否则根据$ACTION$表，移入新的当前状态
在处理过程中可能出现下面的冲突情况：
移入-规约冲突，即当前可以规约，但是再移入几个可以规约成更大的非终结符
规约-规约冲突，即当前既可以规约栈的一个前缀$s$，又可以规约栈的另一个前缀$s’$
一个好的LR策略，应当恰当地处理这些冲突(后面会看到SLR的做法就是不处理….)
LR(0) 自动机
这是为后面的SLR技术作铺垫
其实是PDA的一个真子集，可以看成是一个特殊的DFA
首先对语法 $G$，我们构造等价的增广语法 $G’$，唯一的区别在于增添一条产生式 ${s_0}’\rightarrow s_0$，表示一个新的起始符号
项，项集
我们称一个项(term)为一个产生式加上一个点，例如 $A\rightarrow ab\cdot cde$
直观的含义就是，我们目前已经读到了这个产生式右端的某个前缀，于是在这个前缀的位置打上标记。特殊地 规定 $A\rightarrow \epsilon$ 的项只有唯一的 $A\rightarrow \cdot$
| 不妨记所有项组成的集合为 $T$，一个粗略的估计为 $ | T | =\sum\limits_{p\text{ 是产生式，b是p的body} } { | b | +1}$ |
再造两个项上的操作 $cur:T\mapsto \mathbb N$ 和 $next:T\mapsto T$
规定 $cur(A\rightarrow\alpha\cdot c\beta)=c$，表示我们接下来需要一个终结符 $c$
规定 $next(A\rightarrow\alpha\cdot c\beta)=A\rightarrow\alpha c\cdot\beta$，表示我们又匹配上了一个字符 $c$
项集合的闭包操作
对于一个项组成的集合(a set of terms) $S$，我们构造地定义函数 $I:2^T\mapsto 2^T$ 如下：
$S\subseteq I(S)$
$\forall t\in S$，若 $t$ 中的点后是一个非终结符(即 $t$ 的形式为 $H\rightarrow \alpha\cdot A\beta$)，且存在产生式 $A\rightarrow \gamma$，则 $A\rightarrow\cdot\gamma\in I(S)$
感性的理解很直观，即如果我们已经读完了某个产生式右端的一个前缀，那么对于紧接着的一个非终结符 $A$，我们接下来可以读任何以 $A$ 为head的产生式的右端的第一个符号。
项集作为状态的转移
现在有了一堆元素，自然考虑它们之间的关系以及它们和字符的相互作用。
对于一个项集 $S$，给定一个字符 $c$，则我们记 $trans(S,c)=T$ 当且仅当：
$\forall t\in T$ 都有 $\exists s\in S$ 使得 $next(s)=t$ 且 $cur(s)=c$
$\forall s\in S$ 且 $cur(s)=c$ 都有 $next(s)\in T$
SLR
SLR(Simple LR Parsing)技术其实很简单，大概思路就是只分析最简单能分析得了的LR语法，其余一概不认
假设我们的项集为 $T=\left{\;I_0,I_1,I_2\ldots\;\right}$
构造ACTION
假设我们要求 $ACTION[S,c]$
若 $A\rightarrow\alpha\cdot\in S$ ，且 $c\in FOLLOW(A)$，则用 $A\rightarrow\alpha$ 规约
若 $A\rightarrow\alpha\cdot c\beta\in S$，则规定移入 $trans(A,c)$
若 ${s_0}’\rightarrow s_0\in S$，则表明完成了parsing
最后在空的地方填上错误处理/报错
构造 GOTO
非常简单，规定 $GOTO[x,ch]=trans(I_x,ch)$
大概总结一下。LR分析最重要的就是解决”何时规约”的问题，因为如果不能规约就必须移入了
SLR给出的方案就是，如果我们走到了某个产生式的右端，且紧接着出现了一个可以立即出现在产生式左端之后的终结符，那么就立刻规约到这个产生式。其余的情况则是能移入就移入。其实也就是”能规约就立刻规约，否则能移入就立刻移入” 的意思……
SLR的缺点很明显，存在规约-规约冲突的时候不能做(因为这不是SLR语法的范围)，并且规约策略过于”aggressive”，导致可能得到的局部解走不到一个全局解。课程视频说LALR很好地平衡了LR(1)和SLR的优缺点，但是这部分我还没看。
错误恢复
很显然我们不可能每次编译只找到一个错就停下来。假设每次只报一个错，代码有一万个错的话…..
因此需要一种策略，在找到错误(无法匹配任何一种语法模式)时，迅速恢复到正常模式，对后续的(可能正常的)代码进行检测。
主要讲三种：panic mode和phrase level recovery，还有一种属于体贴型服务
xc原话”由于程序猿写bug的创造力实在太强，甚至会搞爆编译器，因此要求编译器正确找出所有的错也是很困难的事情。”
error recovery的策略通常是根据经验得来的trick，也就是完全不具有普遍性。这也是为什么报错信息这么难读
Panic Mode
这一策略可以描述为：若栈顶的终结符 $A$ 遇到了无法匹配的非终结符 $c$，则开始一直往后读输入的字符流，直到找到某个字符 $c’\in Syn(A)$，停止panic mode并弹出栈顶，然后往后继续分析。
这里的 $Syn(A)$ 是一个字符集，它通常表示了一个语法单元的结束(例如一个分号，一个换行，一个右花括号)。意思是 $A$ 已经识别不出来了，于是赶快找到(可能)包含 $A$ 的最小(尽可能小)语法单元，把它和 $A$ 一起丢弃。
举个生活中的例子就是，你一边听老师上课，一边记笔记。但是因为中间分神了，导致手上还在写第一页，老师已经讲到第五页了。于是你迅速往后跳，直到找到当前老师正在讲的位置，然后继续跟着记笔记(泪
Phrase Level Recovery
意思是我们可以对输入进行若干插入、删除、修改操作，使得它成为一段正确符合语法的串。
最直白的做法是最小编辑距离，但是这个东西在实际中效果并不好(书上原文
打表
对，预测程序猿可能犯什么错：行末没有分号，形参没有类型等等等等
属于是尽力在提升编译结果可读性，但是十分为难的sb做法。只能说确实有这个必要，但是这么做确实很无语….讲出来只是为了开开眼界(