概念

语法分析

语法分析器接收词法分析器提供的记号串,检查它们是否能由源程序语言的文法产生.

语法分析器的输出是对词法分析器产生的记号流的分析树的某种表示.

上下文无关文法

对于文法G产生的语言L(G),当且仅当文法G的开始符号S经过一步或多步推导得到终结符串w时,我们说终结符串w是G的句子.如果两个文法产生同样的语言,则称这两个文法等价.

分析树和推导

推导的每一步有两个选择:1)选择被替换的非终结符 2)选择用于替换该终结符的产生式.若每一步都替代最左非终结符的推导,这样的推导叫做最左推导.由最左推导得到的文法符号的串,称为该文法的左句型.

分析树可以看作推导的图形表示,但其不能显示出替代顺序的选择.比如图中两个E->id的替代顺序.所以每个分析树都有唯一的最左和最右推导.然而每一个句子不一定只有一个分析树.存在这样句子的文法G称为二义性文法.语法分析器在处理具有二义性的文法时,需要有消除二义性的规则,从而保留唯一一棵分析树.

实现

实现部分阅读建议: 从文法识别开始阅读,当识别过程中提到文法的某种设计要求或特征时,阅读文法设计对应细节.

文法设计

从NFA到上下文无关文法

挺好理解的,每个状态转移对应一个产生式.

文法处理

消除左递归

直接左递归可以用这种方式来消除.

而对于非直接左递归产生式,如:

进行如下的消除算法.
简单说说算法的思想:
先将所有的非终结符编号1-n,从A1开始对每一个非终结符Ai,对于Ai->Aj γ的产生式,用Aj的产生式替换Ai->Aj γ中的Aj,经过N轮后,对于任意产生式Ai->Aj γ,一定有j >= i.意味着每次推导产生的非终结符的序号一定不小于原非终结符的序号,类似于单调的概念.故无法从一个非终结符推导出它的”祖先”非终结符.

也就消除(其实是转化)了非直接左递归.之前的消除直接左递归的算法就可以使用了.当然这是从宏观上看的该算法,实际上在算法中每次外循环后都已经消除Ai的非直接左递归,并完成了消除直接左递归的操作.

提取左因子

当不清楚应该用两个选择中的哪个来替换非终结符A时,可改写A产生式来推迟这种决定,直到看见足够多的输入能做出正确选择为止.

LL(1)文法

Predictive parsers, that is, recursive-descent parsers needing no backtracking,can be constructed for a class of grammars called LL(1). The first “L” in LL(1) stands for scanning the input from left to right, the second “L” for producing a leftmost derivation, and the “1” for using one input symbol of lookahead at each step to make parsing action decisions.

文法识别

自顶向下语法分析

自顶向下语法分析的目的是为输入字符串寻找最左推导,或者说,从根节点开始,自上而下,从左到右地为输入字符串建立一棵分析树.

递归下降语法分析

递归下降语法分析是自顶向下分析的一般形式,它可能需要回溯,也就是重复地扫描某段输入.

典型的递归下降语法分析算法:
为每个非终结符创建一个函数(procedure).当语法分析器开始分析非终结符A,非终结符A的对应的函数被调用.其选择一个非终结符的推导,若产生式的记号为终结符,右移输入指针表示成功匹配,若为非终结符Xi,调用Xi的函数.该算法用函数调用的栈隐式地记录了非终结符的处理顺序.

该算法有两个点需要注意,这两个点也就是导致该算法需要回溯的原因.

1. 非终结符A可能有多个产生式,如何选择?递归下降语法分析的策略是遍历每一个产生式.
2. 若选择的产生式不能匹配输入,触发一个non-ultimate failure,该错误使得输入回退到line1,也就是选择产生式的时.这意味着该算法需要在每次遍历选择时保存输入指针的位置.继续遍历,选择一个新的产生式.直到遍历完A的所有产生式,报告一个错误(该句子不是文法的语言).

该算法有一个问题,对于含有A->Aa这样产生式的左递归文法,分析器在处理A时,不断的调用A的处理例程,但输入指针并没有前移,形成死循环.详见文法设计部分消除左递归

预测语法分析器

有的文法可以用不带回溯的递归下降语法分析器来构造.不带回溯的递归下降语法分析器称为预测语法分析器.

看这样一个例子.当前输入符号是a,此时正在处理的非终结符A有两个产生式:A->aB,A->bB,很明显我们应该选择前者,这便是预测,其实可以类比词法分析选择状态转移的过程.(其实不太懂为什么叫预测,词法分析的时候也没DFA见叫预测有限有穷自动机).

所以我们应该为输入符号和非终结符产生式创建一个关联,称作分析表(当然也有其他的结构).类比于词法分析中将NFA转换成DFA进行模拟,我们应该对文法提取左因子来保证不存在同一非终结符对于输入符号a的多种产生式.

预测分析表的构造

表驱动的预测分析算法

自底向上语法分析

自叶子节点向上建立分析树.
大量概念名词预警

归约: 一个匹配某产生式右部的字符串w被产生式左部替代的过程,推导的逆过程.
自底向上语法分析就是将一个句子一步步归约到文法的开始符号.

从定义可以看出,自底向上语法分析主要解决两个问题:

1. 什么时候进行归约
2. 选择哪个产生式进行归约

句柄: 一个符号串的句柄是和一个产生式右部匹配的字串,且对该字串的归约过程是最右推导逆过程的一步.

移进归约分析法

移进归约分析法用栈来保存文法符号,用输入缓冲区来保存要分析的串w,用$来标记栈底和输入串的右端.初始时栈为空.

语法分析其将零个或多个输入符号压入栈,直到句柄B在栈顶出现为止,然后选择合适的产生式将句柄B归约,重复此过程直到发现错误或栈中只有开始符号且输入为空.

选用栈来进行移进归约分析基于这样一个事实: 句柄总是出现在栈顶而不是栈中.
其实就是非终结符总是出现在上一个右句型的左部.

但对于一些上下文无关文法,根据栈中的内容和下一个输入符号不能决定是移进还是归约,或不能决定按哪一个产生式进行归约,如二义性文法.这类文法不属于LR(k)类文法.

算符优先语法分析

LR语法分析

为什么选择LR语法分析?简单来说就是,广泛有效性.

LR语法分析器通过记录当前状态(state)来决定移进归约的操作,状态是项目(item)的集合,项目指示对某个产生式的识别状态(区分于语法分析器的状态).

One collection of sets of LR(0) items,called the canonical LR(0) collection,provides the basis for constructing a deterministic finite automaton that is used to make parsing decisions.Such an automatonis called an LR(0) automaton.

SLR语法分析

LR语法分析器依靠自动机来完成移进归约操作的决定,
LR(0)规范集,其实就是LR语法分析器状态的集合(项目(item)集合(set)的集合(collection)),是构造该自动机的基础.

为文法G构造LR(0)规范集,需要增广文法,闭包(closure)函数,转移(goto)函数.

拓广文法: 加入一个新的开始符号和产生式S’ -> S,使得仅当S归约到S’时到达接受状态.(原开始符号可能有多个产生式,也就有多种归约能到达接受状态)

解释一下闭包函数的作用:
对于项目E’ -> ·E,指示了语法分析器此刻期望从输入中得到E(回忆一下,项目指示了对某产生式的识别状态),当然,如果存在产生式E->T,分析器同样可能期望得到一个T.为了节约存储空间,我们使用closure来计算出分析器在某状态时的项目集合,指示当前状态所有可能期望得到的串.

这里再引入两个概念,核心项目和非核心项目.非核心项目可以通过对核心项目求闭包来重新生成.

GOTO(I,X)就是在状态I识别到文法符号X后到达的新状态.
看这样一个例子:
在状态I识别到符号+,状态I的项目(后文在说状态的项目时默认是求闭包后的结果)中期待得到符号+的项目只有E->E· +T,识别+后称为E->E+ · T,则新状态应该是项目E->E+ · T的闭包.

LR(0)语法分析器的识别过程.

活前缀的有效项目,我的理解,有效项目指示当前栈中活前缀在遇到下一个文法符号β时的动作,若β为ε,则归约,否则移进.

规范LR(1)

SLR语法分析依靠活前缀的有效项目进行归约或移进操作的指示,然而对于一些文法,可能有一个活前缀的多个有效项目指示分析器做不同的操作,产生移进-归约冲突.看下面这样一个例子:

对于如下文法:

构造其LR(0)标准集,其中一个状态是这样的.该状态对于活前缀L且即将识别符号=时,有两个有效的项目分别指示移进和归约.语法分析器不能决定.

然而该冲突其实并不存在,因为文法中不存在以R=开始的右句型(=不在FOLLOW(R)中),所以应该选择移进操作.由此可见,如果让状态蕴含更多的信息,可以解决这样的冲突.

回顾一下在自顶向下分析中,我们解决推导冲突的办法: 提取左因子,合并状态,也可以说成减少状态蕴藏的信息,得到唯一的状态转换.
在这里正好逆一下,分裂状态,使状态蕴含更多的信息,得到唯一的状态转换.

同样是消除冲突,为什么会有相反的两种思想?

本质上是相同的,减少目标状态信息,增加当前状态信息.解决推导冲突所需要的信息,在多个输入符号之后,所以我们暂时减少目标状态的信息以推迟决定,直到当前状态搜集到足够多能做出决定的信息.而解决(类似示例中的)归约冲突所需要的信息,存在于文法本身,若文法设计本身不存在这样的归约冲突,语法分析器便可根据文法本身解决问题,所以要做的就是从文法中产生这样的信息并保存到状态中.

规范LR(1)语法分析的项目:

还记得我们说SLR语法分析依靠活前缀的有效项目进行归约或移进操作的指示吗?规范LR(1)可以理解为提高了有效项目的要求.

规范LR(1)项目集的构造

规范LR(1)分析表的构造

LALR

为了减少规范LR语法分析表的大小,使用一种LALR的分析方法.

来看这样一个文法和对应的规范LR的GOTO图.

状态I4和I7都只有一个项目
对于状态I4,当下个文法符号是c或d时,根据项目的第一分量(产生式)进行归约,对于状态I7,当下个文法符号是$时同样根据项目第一分量进行归约,而这两个第一分量(core)相同.所以我们可以合并这两个状态,而不破坏原本对分析器的指示.
(这样的合并可能会延后错误的发现,但不会遗漏).

来分析一下这样合并的有效性:

是否会引进移进-归约冲突?

不会.进行合并的状态的项目一定有相同的core,对一个core而言,是如何决定进行移进还是归约的?根据·是否到了产生式的结尾.也就是只和core有关而与第二分量无关.有的人可能会说,归约的条件还有一个下一文法符号符合第二分量,但在限定了对一个core而言,这其实是决定归约或报告错误,与移进无关.若合并后存在移进-归约冲突,说明该冲突本身就存在于规范LR(1)分析中,该文法不是LR(1)文法.

是否会引进归约-归约冲突?

可能会.在规范LR(1)中,如何决定进行归约的产生式?由第二分量决定.对于这样两个即将被我们合并的状态,各自在识别下一个符号e和d的时候能够根据第二分量选择正确的产生式,而在合并之后,第二分量相同,无法决定,产生归约-归约冲突.

简易但耗空间的LALR表的构造.

更efficient的构造方式,还是利用分析过程中通过对核心项目的计算来减小分析表的大小.