语法分析实战

上下文无关文法(CFG, Context Free Grammar)属于二类文法,其能力等价于下推自动机(PDA)。相对于三类文法即正则文法,上下文无关文法能够对非终结符做状态转移。
自上而下和自下而上是两种常用的上下文无关文法分析方法。
自上而下的方法的难点在于选择哪个产生式进行推导,自下而上的分析方法难点在于在不同的格局下选择移进或归约的矛盾。

上下文无关文法

C不是上下文无关语言,因为它们都要求标识符的声明先于引用,并且允许标识符任意长。由于这一点,描述这些语言语法的文法只是用id这样的记号来代表所有的标识符,而在这些语言的编译器中,由语义分析阶段检查标识符的声明必须先于引用。同样VB和Fortran也不是上下文无关语言,因为它们会同时出现数组A(i)和函数A(i),这同样需要语义分析程序进行处理,在语法分析阶段可以把数组的slice和dimension部分看作一种特殊形式的参数表。事实上,很多需要用更强的文法分析方法的问题可以在语义阶段较轻松地解决
推导,从开始符号推导出和输入串相匹配的句子。最右推导称为规范推导,指每次选择句型最右边的非终结符。
归约,用非终结符代替一段文法符号串。通常需要解决两个问题,一是何时进行归约,二是使用哪一个产生式进行归约。称自左向右的归约过程(最左归约)为规范归约。

自上而下的分析方法

自顶向下分析方法相对来说比较符合人的思维(我们交谈时一个句子听到一点中能估计到大概的意思,而不是要把一句话听完才能恍然大悟),编译器写起来也方便。自上而下的分析方法分为非确定的和确定的两种,确定指的是根据当前的输入符号,选择用来推导产生式是唯一确定的;对应的,非确定的自顶向下分析可以在关于一个非终结符有多个候选产生式的时候进行回溯,效率较低。确定的分析方法对文法要求较高,例如文法中就不能出现左递归和左公因子。

递归下降法

LL(1)预测分析法

LL分析(以下出现的LL分析指代LL(1)分析),是一种确定的自顶向下分析技术,确定体现在在推导过程中可以完全按照当前的输入符号(或者再向前看k-1个符号)决定哪个产生式向下推导。一般手写LL分析是很方便的,这是因为在语法分析的同时可以借助于语义分析来避免潜在的语法冲突。而常常借助于程序生成解析器的LR方法并不容易在里面嵌入语义分析模块。
FIRST集:FIRST集是对于一个句型α来讲的,得到一个终结符集合。句型是推导过程中生成的产生式,例如在S->A->aB->ab中,AaBab都是句型,特别地,只含有终结符的句型称为句子。FIRST集表示一个句型所有可能的第一个非终结符。注意如果α可推导为ε,则ε也属于FIRST集。可以得到所有文法符号的FIRST(Xi)集的生成方法:

  1. 终结符的VT的FIRST集是自己,这是显然的
  2. 非终结符的FIRST集包含以下内容:
    1. ε
      如果该非终结符有ε产生式。
      或者该非终结符全部由非终结符组成的产生式,并且这些非终结符全部有ε产生式。例如X->Y1Y2...Yn,且所有的Yx都能推出ε。
    2. 终结符a
      如果该非终结符有以a开头的产生式
    3. 所有非终结符的FIRST集,但是要除去所有的ε
      如果该非终结符全部由非终结符组成的产生式,并且存在一个非终结符没有ε产生式。例如X->Y且Y能推导出ε,则加入FIRST(Y) - ε。又例如X->Y1Y2且其中Y1能推出ε而Y2不能推出ε,则加入(FIRST(Y1) - ε) ∪ FIRST(Y2)。这是显然的,因为X->Y1Y2不能推出ε,但如果写成FIRST(Y1) ∪ FIRST(Y2),里面就包含了ε。

SELECT集:SELECT集是对于一个产生式A->α而言的,返回的是终结符的集合。表示在推导A且当前读取位置为a时,对于A的所有产生式A->α,如果SELECT(A->α)中含有终结符a,那么使用产生式A->α推导。显然有且仅有一个这样的产生式,当出错时没有(注意,SELECT(A->α)集合中可能有多个元素,但是对于相同的非终结符A,同一个终结符a只会在它的一个SELECT集中,即通过键值对<A, a>可以唯一确定一个产生式)。容易发现SELECT(A->α)有两部分组成,一部分是α不推导为ε时候,是FIRST(α),一部分是α推导为ε时候,是FOLLOW(α)。

FOLLOW集:FOLLOW集是对于一个非终结符A来讲的。表示所有可能在A后面的非终结符。在计算时,{ # }和所有A->αBβ产生始终的FIRST(β)的非空元素都属于FOLLOW(B)。当然β可能推导为空,这样的情况下也将FOLLOW(A)加入FOLLOW(B)中。然后反复直到各个FOLLOW集合不再增大。

将非确定的文法转换成确定的LL(1)文法

提取左公因子

左公因子的存在会导致SELECT集相交,这是显然的。
对于显式的左公因子,直接提出来即可,如

A -> αβ|αγ    

可以变为

A -> αA'
A'-> β|γ    

对于隐式的左公因子(即左边以非终结符开头的情况),可以使用关于该非终结符的所有右部以终结符开头的产生式展开,例如

A -> ad
A -> Bc
B -> aA
B -> bB

展开得到

A -> ad
A -> aAc // B => aA
A -> bBc // B => bB
B -> aA
B -> bB

消除左递归

考虑下面的文法

A -> Ab
A -> a

可以发现对于非终结符A,并不能确定用来推导的产生式,于是只能采用非确定的递归下降法,寻找最左非终结符,于是会陷入展开A的死循环A => Ab => Abb => Abbb
通过改写文法消除左递归后,这就是一个确定的文法了

A -> aB
B -> bB
   | ε

还要注意一点,有些人会将左递归和尾调用等同起来,但这是不同的两个概念

  1. 左递归是针对文法而言的。不消除左递归,不能使用确定的自上向下分析
  2. 尾调用是对于一个函数调用而言的。当一个函数的最后一个工作是调用自己的时候,这样的调用称为尾递归,例如计算阶乘的某些实现。当这个函数计算仅占用常量的栈空间的时候,特别是对于LISP这样的函数式语言,可以进行尾递归优化(Tail Call Optimization, TCO),即可以不在调用栈上面添加一个新的栈帧,而是更新它,如同迭代一般。通过尾递归优化,可以将O(n)的栈帧使用变为O(1),减少部分递归程序的开销

自下而上的分析方法

首先需要介绍一下短语、直接短语和句柄的概念。首先这三个概念的范围是依次缩小的。短语指的是一个符号串,根据对定义的解释,一个句型的语法树中任一子树叶节点所组成的符号串γ都是该句型的短语。我们称γ为这个句型相对于A的短语,其中A为该子树对应的非终结符。直接短语相对于短语进一步要求选择的子树不应该含有其他子树,即它的孩子全部都是叶子。值得注意的是这并不意味着这些叶子都是终结符
不同于自上而下的分析,自下而上的分析方法总是等到句柄(最左直接短语)出现后进行归约。分析器在读取输入串的每一个符号时要选择对这个符号是移进还是归约、按那个产生式规约(LR0,SLR1,LR1,LALR1文法的差别体现于此)。但无论如何先要找到句柄,因此引入活前缀的概念。
定义活前缀,S'=>αAw=>αβw。假设这里w是终结符串,因此A是最右非终结符,这里是规范(最右)推导过程。如果符号串γ是αβ的前缀,那么γ是S的一个活前缀。根据定义,β是句型αβw相对于非终结符A的短语。γ是规范句型(也就是右句型,最右推导得到的句型)的前缀,而一旦栈中出现αβ,也就是形成了A的句柄,那么就可以按照A->β归约,因此,只要输入串的已扫描部分可以归约成一个活前缀,那就意味着已经扫描的部分没有错误。LR分析栈中的文法符号总是构成活前缀。
LR分析器不需要扫描整个分析栈(状态栈和符号栈)就可以知道句柄是否出现在栈顶(而教科书中显示给出了栈是为了方便理解,在编译器实际处理过程中并不需要访问非栈顶元素),因为栈顶的状态符号包含了确定句柄所需要的一切信息。因此LR分析表的转移函数本质上等同于一个识别整个文法的活前缀和可归前缀的有限自动机。因此最直接的生成分析表的方法是构造一个NFA,其中所有产生式的每个项目都对应于NFA的一个状态,而规定拓展文法的开始符号的唯一产生式所对应的项目S'->·E为初始状态。然后可以使用子集法把这个NFA确定化为一个DFA。但也可以不通过确定化NFA或正则文法构造分析表,这引入下面的方法。

LR(0)分析表的一般构造方法

首先定义项目集规范族。定义项目集I是一组项目的集合,对应着DFA中的一个状态。定义构成识别一个文法活前缀的DFA项目集(状态)的全体称为这个文法的项目集规范族。项目集规范族包含一组项目集。
闭包CLOSURE是针对一个项目集I而言的。闭包的求法:

  1. I属于闭包
  2. 对于闭包中的所有项目,如果圆点右边是非终结符,将该非终结符的所有产生式加入闭包。
  3. 如果圆点右边是终结符,那这是一个移进项目,不属于当前状态对应的项目集,不需要加入闭包。
  4. 如果圆点右边是什么都没有,那这是一个归约项目,不需要加入闭包。

定义GO(I, X)=CLOSURE(J),其中I是包含某一项目集的状态,X为终结符或非终结符,J是I中任何型如A->αX·β的项目。即,如果状态I能够识别活前缀γ,那么状态J能识别活前缀γX。
注意GO和GOTO表的意义是不一样的,GOTO(S, X)表示栈顶状态在S时读入文法符号(终结符或非终结符)为X的时候转换到的状态,而转换函数GO用来求出移动圆点之后的新的项目集。
对于LR(0),分析表(GOTO和ACTION)可以按以下方式构造:

  1. 终结符移进:如果项目A->α·aβ属于项目集Ik,并且GOTO(Ik, a)=Ik,当a未终结符时置ACTION(k, a)为S。
  2. 终结符归约:如果项目A->α·属于项目集Ik,则对于所有的终结符a(下面的SLR在这里改进,向前看a从而决定是否移进或如何归约)和#置ACTION(k, a)为rj,j是产生式A->α的符号。
  3. 非终结符移进:如果GO(Ik, A)=Ij,则GOTO(k, A)=j。
  4. 接收状态:如果项目S'->S·属于项目集Ik,则置ACTION(k, #)为acc,也就是接受。

核心项目:所有圆点不在产生式右部左端的项目,初始项目除外。非核心项目相反。每个所需要的项目集都可以由取核心项目集的闭包形成。
求项目集规范族的过程为:

  1. 对初态求闭包,得到一个完整的项目集(通过对核心项目求闭包始终可以得到所有的非核心项目)
  2. 对于得到的项目集中的每个项目,读入一个文法符号,向右移动圆点。读入不同的文法符号会通向不同的新状态/项目集(当然原项目集I中的两个项目在读取同一个文法符号X之后必然属于同一个状态/项目集,即使它们对应的产生式左部不相同,这是由于GO(I, X)是唯一确定的)。对于这些新状态,再求闭包,由此循环。

如果存在规范推导S => δAw => δα·βw那么项目[A->α·β, a]对活前缀δα是有效的。

SLR(1)分析对冲突的解决思想

LR(0)文法相对于LL的预测分析法,将归约的时刻推迟到了读完句柄之后。这减少了冲突,但是因为在能归约的地方总是归约,所以仍存在冲突。考虑变量声明的问题吗,以C语言为例通常为t <varname> [,<varname>],这里省略了赋初值,同时类型标识符作为一个终结符t出现,在上文中解释过这是因为受到上下文无关文法的限制。得到的文法为S'->S S->tD D->D,i D->i,构造文法的项目集族,容易发现会产生移进归约冲突:S->tD· D->D,·i,,也就是说当遇到int i,j这样的情况,编译器现在读到j,已经形成了S->tD的句柄,可以归约了,但是这样的归约是错误的,因为后面的,j就会被丢掉了。显然解决的办法就是再往前看一个字符,如果是,,就继续移进,如果不是就归约。当然也可以引进分号,修改文法为S->tD;避免冲突。所以得到以下方案:
I={X->α·bβ A->γ· B->δ·},则X和A、X和B有移进归约冲突,A和B有规约规约冲突。所以向前读一个输入符号a,

  1. 避免移进归约冲突:若a=b则按照产生式X移进
  2. 避免规约规约冲突:如果a=FOLLOW(A)则按A归约,如果a=FOLLOW(B)则按B归约。显然FOLLOW(A)和FOLLOW(B)必须不相交(当然不能和所有的移进终结符相交)。

可以发现其实这和LL(1)的预测分析法是类似的思路。只不过LL(1)向前读的是当前非终结符的第一个非终结符,但是SLR(1)读的是“下一个非终结符”的第一个非终结符。
SLR(1)算法的分析表(ACTION和GOTO)的构造和LR(0)算法是相似的,不同之处在于读入终结符决定归约时,只对属于FOLLOW(A)的终结符添加ACTION表中记录。

LR(1)分析

SLR(1)不能完全避免移进归约冲突。考虑以下的情况:

S -> α·aβ
A -> α·
a∈FOLLOW(A)

显然按照S产生式面临输入符号a时应当移进,但是按照A产生式应当归约。这种情况的产生是因为a∈FOLLOW(A)说明存在有一种符号串Aa,但不是对于所有的符号串A后面都有a的。因为通常运气不会好到所有FOLLOW集都不会出现两个及以上数目的非终结符,于是我们惊讶前面的SLR(1)算法居然也能跑!其实并不是这样,SLR(1)要求表示移进的终结符不在表示归约的终结符集(也就是FOLLOW集)里面,对于上述文法,可以求得a∈FOLLOW(S),但是根据S->α·aβ可以看到FOLLOW(S)和{ a }是有交集的,所以SLR(1)在前一步就以移进归约冲突报错了。
还可以考虑以下C赋值语句文法的实际意义进一步加深理解:

赋值表达式  S -> V=E|E
左值        V -> *E|id
右值        E -> V

按照SLR分析算法,现在考虑I2项目集S->V·=E E->V·,可以计算出=∈FOLLOW(E),所以句型V=E既可以按照E->V归约,也可以按照S->V=E移进,冲突发生了。但是仔细琢磨,其实文法中的信息没有被完全表达出来。一个左值V完全可以出现在等号的右边,但是一个右值是不能出现在等号的左边的,如果按照E->V归约,那必定会推出V=V形成错误。虽然SLR(1)在前一步就以移进归约冲突报错了。
所以解决的方案就非常显然了,既然FOLLOW集太过笼统,那就对每个项目单独给出后继符号,即搜索符。
首先给出搜索符的定义:对于项目集A->α·Bβ B->·γ,如果使用生成式B->γ归约,则FIRST(β)即为搜索符。搜索符对β非空的项目[A->α·β, a]是不起作用的,但对形式为[A->α·, a]的项目,它表示只有在下一个输入符号是 a时,才能要求按A->α·归约。因此可以看做是FOLLOW集的对每个项目的特化,LR(1)文法的1同时也意味着搜索符是长度是1的终结符。
如果存在规范推导S => δAw => δα·βw其中γ=δα且a是w的第一个符号或者w是ε、a是$,那么项目[A->α·β, a]对活前缀γ是有效的。
LR(1)和SLR(1)的流程大致是相同的,首先也要计算CLOSURE函数。因为LR(1)项目集多了搜索符,因此CLOSURE函数需要一些修改。假设项目A->α·Bβ, a属于CLOSURE(I),那么对于产生式B->γβ∈FIRST(βa)B->·γ, b也在CLOSURE中。
LR(1)算法的分析表(ACTION和GOTO)的构造和LR(0)、SLR(1)算法是相似的,不同之处在于读入终结符决定归约时,只对属于搜索符(是一个终结符)添加ACTION表中记录。

LALR(1)对LR(1)的简化

如果两个项目集除了搜索符其他都一样,那么这两个项目集为同心集。合并同心集后不会产生移进归约冲突,但可能仍会产生规约规约冲突。

冲突的解决思想总结

我们希望我们的文法分析过程是确定性的。这也就是说,对于LL分析,我们希望当推导时碰到某个非终结符的产生式有多个候选的时候,我们能够唯一确定一个候选进行推导;对于LR分析,我们希望能够唯一确定任何一时刻下的分析器的动作应该是移进还是归约(为了避免移进归约冲突,例如C语言的悬空else情况if(..)if(..)else中,在else位置是移进外层的if,还是归约内层的if,当然这个二义文法已经不算是LR文法了)、按照哪个产生式归约(为了避免规约规约冲突,例如前面所说的VB6语言A(i)可能是一个数组元素,也可能是一个函数调用,特别地,(1+2)和func_name(1+2)也可能导致规约规约冲突)。
因此可以发现事实上LR所能描述的文法是LL(1)预测分析法的真超集。回顾LL(1)预测分析法的流程,LL(1)预测分析法由一个栈S和一个预测分析表M组成。M[A,a]表示推导A时当遇到输入符a时,应当选择的A的产生式,这应当是唯一确定的。也就是说,对于任意的产生式A->α,如果a在SELECT(A->α)集合中,那就必须要选择产生式A->α,如果对于A的所有产生式,它们的SELECT集都不出现a,那就报错。因此,这就意味着选择A的哪一个产生式完全取决于a。例如考虑应用产生式A->lβ如下推导S=>αAbw=>rlβbw(其中α为符号串,A为最右非终结符,w为终结符串),LL(1)预测分析法需要在看到l时就作出决定选择产生式A->lβ,但是LR分析法可以在看到b之后再决定是否把lβ规约为A,因此LR实际上获得了更多的信息。同时LL(1)文法还是不能够出现左公因子和左递归的:对于前者可以发现同一个非终结符的所有SELECT集合是存在交集的;对于第二种情况,直接左递归A->Aβ或者间接左递归可以推出它们的SELECT集也是相交的。
有的时候,虽然文法是二义性的,但是语言却可以不是二义性的,这可以通过语义分析解决。

通过重写文法解决二义性

stmt: if expr then stmt else stmt
    | if expr then stmt
    | other

可以提取公因子,重写为:

stmt: if expr then stmt optional_else
    | other
optional_else: else stmt
    | other

一般来说,对于文法

A -> αη
B -> βη

提供一个将η归约为非终结符C的产生式

A -> αC
B -> βC
C -> η

但是这样的坏处是会引入终结符C,并且这个C可能没有明确的语义作用。

通过设置终结符优先级解决二义性

考虑通常的表达式文法,

E->E + E| E * E | (E)| id

对于1 + 2 * 3,能产生两种语法树,产生移进归约冲突,原因在于面临+的时候可以按照E->E + E归约,也可以按照E->E * E移进,于是规定*的优先级高于+,所以选择移进。
对于1 + 2 + 3,同样能产生移进归约冲突,因此规定+是左结合的,因此对于项目id + id · + id,应当归约,而不是移进。
此外,这个文法同样可以通过重写文法来消除二义性,例如E->E+T|T T->T*F|F F->(E)|id,这样的文法产生式的右边会出现单非终结符的产生式,增加了归约的次数。
这种方法常用来解决移进归约冲突

通过设置产生式优先级解决二义性

考虑排版文法:

E -> E ^ E _ E
E -> E ^ E
E -> E _ E
E -> {E}
E -> c

其中^表示上标,_表示下标。
从定义形式语言的角度来讲,第一个产生式是多余规则,因为用2和3产生式能够得到1产生式可推导出的句子。但是从语义的角度来说它作为一个优先归约的特殊规则存在。例如我们考虑会产生的以下三个排版:
ai2 a2i ai2
它们的效果(语义)是不一样的,因此单独将第一个产生式列出来,优先级最高,当满足第一个产生式时,不使用后两个产生式进行归约。同样的方法可以用在处理A(args)(exp)的冲突上面。这种方法常被用来解决归约归约冲突。

使用GLR文法解决二义性

有时候冲突是无法避免的,这时候可以选择使用GLR文法分析器,相对于LALR分析,GLR会BFS所有可能的操作。GLR的最坏时间复杂度是O(n3)的,具体取决于冲突的数量

语义分析上的两种分析方法

语法树

语法树(推导树)的特点是非叶子节点都是非终结符,叶子节点都是终结符。因此从左到右遍历(也就是DFS)语法树即可生成代码。特别地,单趟编译器(one-pass compiler)不先建立语法树后编译。这样的编译器由语法分析带动整个编译流程,在语法分析的同时计算属性值,这样的做法称为语法指导翻译。TCC(Tiny C Compiler)就是这样的一个编译器。属性文法对遵循语法制导语义(syntax-directed semantic)原理的语言最有用,它表明程序的语义内容与它的语法密切相关。

综合属性和继承属性

考虑一棵语法树,综合属性总是自下而上传递的,例如2.4+3*4,在语法树的根节点+,得到了结果14.4,注意到类型从int上升到double体现了自下而上的过程。继承属性是在语法树水平或者从上往下传递的,例如C语言中的变量初始化语句int i = 0, j = 0;,容易得到属性文法:

T -> int| real        T.type = int| real
L -> L1, id| id        L1.in = L.in; do_symbol_table;
D -> TL                L.in = T.type

可以发现,属性先从T横向向右传递给L,然后由L向下传给L1。在产生式上来看,综合属性属于产生式的左部非终结符,从产生式右部的文法符号的属性得到(自下而上),继承属性属于产生式右部的文法符号,从产生式左部(自上而下)或者产生式右部该文法符号之前的文法符号(横向)的属性得到。

L属性文法的自顶向下和自下而上分析

自顶而下的L属性文法会导致翻译模式,也就是需要在产生式的右部文法符号中间嵌入语义计算动作(yacc中使用花括号{}括起来,里面可以写C++的代码,详情可以参考我的另一篇文章:flex和bison使用)。
考虑常见的if..elseif..else..endif文法。

if_stmt : YY_IF exp YY_THEN stmt endif_stmt
    | YY_IF exp YY_THEN stmt else_stmt
    | YY_IF exp YY_THEN stmt elseif_stmt
elseif_stmt : YY_ELSE YY_IF exp YY_THEN stmt
    | YY_ELSE YY_IF exp YY_THEN stmt elseif_stmt
    | YY_ELSE YY_IF exp YY_THEN stmt endif_stmt
else_stmt : YY_ELSE stmt endif_stmt
endif_stmt : YY_END YY_IF