语法分析

一、引言

语法分析生成语法树

文法

一种用于描述程序设计语言语法的表示方法，能够自然地描述程序设计语言构造的层次化语法结构

基于文法构造语法分析器

语法分析器

输入：词法分析器输出的词法单元序列

输出：语法树表示

语法分析器的类型：

通用型
自顶向下：处理LL文法
自底向上：处理LR文法

代表性文法

上面为LR文法类；下面为LL文法类（无左递归，自顶向下分析）

二、上下文无关语法

CFG

CFG的构成：

终结符号：组成串的基本符号
非终结符号：语法变量
一个开始符号
一组产生式：描述将终结符号和非终结符号组成串的方法

什么是上下文？
前后已经推导出的部分结果就是上下文

上下文无关：之前推导出的不管（只要文法的定义里有某个
产生式，不管一个非终结符前后的串是什么，就
可以应用相应的产生式进行推导）

上下文无关例子：

其中：英文字母为非终结符；汉字为终结符；|表示或

上下文有关例子：

用于描述算术表达式的文法定义：

符号约定

推导

产生式又可称为重写规则

推导：将待处理的串中的某个非终结符号替换为这个非终结符号的某个产生式的体

例如：

句型：如果S零或多步推导出α，那么α就是文法的一个句型

句子：不包含任何非终结符号的句型

语言：文法G的语言就是G的句子的集合，记为L(G)

语法分析的任务：接受一个终结符号串作为输入，找出从文法的开始符号推导出这个串的方法

非终结符号的推导顺序

最左推导：总是选择每个句型的最左非终结符号（箭头下为lm）
最右推导：总是选择最右边的非终结符号（箭头下为rm）

语法分析树：

根结点的标号是文法的开始符号
每个叶子结点的标号是非终结符号、终结符号或ε
每个内部节点的标号是非终结符号
每个内部结点表示某个产生式的一次应用

-(id+id)的语法分析树：

二义性文法

如果一个文法可以为一个句子生成多棵不同的语法分析树，则该文法为二义性文法

例如：id+id*id的语法分析树

程序设计语言的文法通常都应该是无二义性的

例如：stmt:if expr then stmt | if expr then stmt else stmt | other就是无二义性文法

语言

由文法的开始符号出发，能够推导得到的所有句子的集合

验证文法生成的语言：双向验证

证明L(G)包含于L：按照推导序列长度进行数学归纳
证明L包含于L(G)：按照符号串的长度来构造推导序列

词法分析和语法分析

词法分析和语法分析比较：

文法的类别：Chomsky文法类

0型文法：短语结构文法，α->β
1型文法：上下文相关文法，αAβ->αγβ
2型文法：上下文无关文法。A->γ
3型文法：正则文法，A->t，A->tB

0包含1包含2包含3

上下文无关文法的表达能力比正则表达式更强

例如： ${a^nb^n|n>0}$ 可以使用上下文无关文法：S->aSb描述，但是语言无法用DFA识别。（DFA无法数数）

为NFA构造等价文法：

对NFA每个状态i，创建一个非终结符号Ai
如果有i通过a到达j，就加入Ai->aAj；如果这个a是ε，那么加入Ai->Aj
如果i是一个接受状态，加入产生式Ai->ε
如果i是自动机的开始状态，令Ai为所得文法的开始符号

进行语法分析前，需要对文法做以下处理：

消除二义性
消除左递归（文法中一个非终结符号A使得对某个串α，存在一个推导A一步或多步推出Aα，则称这个文法是左递归的）
提取左公因子

消除二义性：例如if/then/else的例子中，保证then和else之间的语句是已匹配的then（通常并不是改变文法来消除二义性）

消除立即左递归：(立即左递归：一步推出)

为什么要消除左递归？以下是个人的一些理解：

假如有文法S->a|Sa，当出现一个非终结符号，并需要解析一个串时，通常这个串都是一个字节一个字节读入的。当我读到第一个符号为a时，由于我不知道在后面是否还会出现另外的符号a，我不确定S究竟是直接转化为a还是应该扩展为Sa。如果扩展为a，那么就无法处理后面还出现另一个a的情况。如果扩展为Sa，那么就无法处理后面没有a的情况。

消除多步左递归：

就是把后面出现的前面的式子给替换掉，然后转换成消除立即左递归

提取左公因子

假如 $A\rightarrow ab_1|ab_2|...|ab_n|y$ ，那么可以替换为 $A\rightarrow aA'$ ，并且 $A'\rightarrow b_1|b_2|...|b_n$

这里提取的是最长左公因子

注意：非上下文无关语言通常不都再语义分析阶段完成

自顶向下分析技术

递归下降分析框架。输入一个式子时，先读一个字母。如果是终结符号并且相等，就读入下一个字母。如果非终结符号就展开。

预测分析技术：每次都从最左边的非终结符号选择适当的产生式

两个函数：

FIRST(α)：可以从α推导得到的串的首符号集合（可以包括ε）
FOLLOW(A)：可能在某些句型中紧跟在A右边的终结符号的集合

FIRST可以用于预测产生式的选择。方法：将非终结符号不断替换，直到首字母是一个终结符号

如果FIRST(X1X2…Xn)，先添加FIRST(X1)，如果它包含ε，就把FIRST(X2)的东西加进去。以此类推

FOLLOW如果A位于最右边，那么可以使用$，这个符号表示结束标记。

FOLLOW可以用于当A可以推出ε时帮助我们选择恰当的表达式

简单的算法：注意：我们不是一个一个字母算的，而是一个式子一个式子考虑的，当考虑完全部的式子之后所有的字母的FOLLOW也会自然出来。

先计算出所有的=字母的First值
先列出所有的字母的FOLLOW括号，并在其中包含一个$
选一个式子。考虑右侧式子。其中，第n个字母的follow值为第n+1个字母的first值。这一步先遍历一遍所有的式子。
考虑左侧字母。最右边字母的follow值包含了这个左侧字母的follow值。当然，如果最右边字母的first包含了ε，那么需要继续考虑右边第二个字母的follow值，它也包含这个左侧字母。注意这一步不展开，而是直接写成follow的形式
然后开始把所有的follow表达式代换。注意只有一个字母自己的follow中不包含任何其他follow值，才可以用来在其他的字母中代换

LL(1)文法

第一个L表示自左向右推导；第二个L指产生最左推导；而1则表示向前看一个输入符号

定义：

FIRST(α)∩FIRST(β) = Φ;
如果ε∈FIRST(β)，那么FIRST(α) ∩FOLLOW(A) = Φ；反之亦然。

LL1文法预测分析技术

预测分析表：可以由当前非终结符号A和输入符号a推出选择哪条产生式

规则/方法：（对于每个元素来说）

先遍历A的产生式，看看产生式中的First哪个包含a，谁有就选哪个产生式
先看看a在不在A的Follow中。如果在，再找一下A的产生式中谁可以推出ε。如果有，就选择这个产生式。
如果a现在是$，那么只要这个符号在Follow(A)中，就直接随便从A中选一个产生式。

方法：（最快构造的方法，从每个非终结符号来出发）

对于每个非终结符号A：

遍历它每个产生式α，产生式的First有哪些符号，就在对应A的行、对应符号列下面填入A->α
在做上面的步骤时，如果其中一个产生式的First包含了ε，就直接对A的Follow做上一步的操作（Follow有哪些符号（包括$），就在对应A的行、对应符号列下面填入A->α）

完成后，如果有格子没有产生式就填为Error

二义性文法的预测分析表：会有多个项在一个格子中

非递归的预测分析

分析处理过程：

初始化时，栈中仅包含开始符号。
替换栈顶的非终结符号（使用预测分析表）

文法符号栈
输入缓冲区
控制程序

三、语法分析技术

自底向上语法分析

为一个输入串构造语法分析树的过程

从叶子（输入串的终结符号）开始，向上到达根结点

通用框架：移入-规约

每一步规约，就把一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号。一次规约实际上是一个推导的反向操作

但是有时候不确定选择哪部分规约

句柄

最右句型：每次都选择最右侧的非终结符号进行替换。

满足下述条件的产生式A→β及串β在γ中出现的位置

条件：将这个位置上的β替换为A之后得到的串是γ的某个最右推导序列中出现在位于γ之前的最右句型

通俗的讲，就是假如有一个表达式，它被规约了。那么被规约的那一部分就是句柄。例如：有规则E->a+b，在规约c*a+b的过程中，把它规约到了c*E，那么这个步骤中a+b就是句柄。

句柄的形式定义：S推出αAw推出αβw，那么紧跟α的β可以一步规约到A。w是所有终结符号串

句柄剪枝：反向最右推导过程

如何找到句柄？

移入-规约分析技术

使用一个栈保存规约/扫描移入的文法符号。栈中符号（从底向上）和待扫描的符号组成一个最右句型。

开始时，栈中只包含 $，输入为w$ 。
成功时，栈中 $S，输入为$

动作：

移入：将下一个符号移动到栈顶
规约：将句柄规约为相应的非终结符号。注意：句柄总是在栈顶，规约时将句柄弹出并压入规约后的形式

移入-规约技术不能处理所有上下文无关文法（不能确定是否是句柄，存在多个可能的归约）

例如：

怎么解决冲突？

LR语法分析技术

LR(k)的语法分析概念：L表示最左扫描，R表示反向构造出最右推导，K表示最多向前看k个符号

我们只考虑k<=1的情况

LR语法分析器试图用一些状态来表明我们在移进规约语法分析的过程中所处的位置，从而做出移入-规约决定

项：指明在语法分析过程中的给定点上，我们已经看到了一个产生式的哪些部分。项的集合对应于一个状态

LR(0)项：文法的产生式加上其中某处一个点。

直观含义：项A->α.β表示已经扫描/规约到了α，并期望接下来的输入中经过扫描/规约得到β，然后把αβ规约到A

项也可以用一对整数(i,j)，i表示第i条规则，j表示右部第j个位置

以项为基础构造自动机

开始状态：S’->S
转换：A->α.Bβ到B->.γ有一个ε转换；从A->α.Xβ到A->αX.β有一个X转换
接收状态：A->α.，即点在最后的项

三个概念：

增广文法
项集闭包CLOSURE
GOTO

增广文法：

G的增广文法G’是在G中新开始符号S’并假如产生式S’->S而得到的。引入的目的是告诉语法分析器何时宣布接收输入符号串，即用S’->S进行规约时，表明分析结束

构造时用到的子函数：

CLOSURE(I):I的项集闭包，对应于DFA算法的ε-closure；
GOTO(I,X)：I的X后继，对应于DFA算法的MOVE(I,X)；

CLOSURE(I)的构造算法：（I是文法G的一个项集，也就是说I是多个推导式的集合）

将I中的所有项加入
如果A->α.Bβ在闭包中，就把任意B->.γ加入到闭包中，不断重复

（简单来说就是：推导式本身加入。然后推导式的点后面是哪个字母，就将从那个字母推出的式子也加入，重复）

内核项：初始项S’->.S、以及所有点不在最左边的项

非内核项：除了S’->.S之外，点在最左边的项

由于表可能很大，实现算法时可以考虑只保存非终结符号，然后使用时调用closure去算

GOTO(I,X)函数的构造算法：

定义：I中所有形如[A->α.Xβ]所对应的项[A->αX.β]的集合的闭包

简单来说计算方法就是：先在I中找到所有含有.X的项，然后每个把它转化为点在后面的形式，即把A->α.Xβ转化为A->αX.β，然后这个时候去求这个式子的闭包即可

为文法G构造LR(0)项集规范族C

构造增广文法G’:S’->S…
构造I0=CLOSURE(S’->.S)，I0是C的初始项集
对C中的每个项集 $I_i$ 及每个文法符号 $x_j$ ，将GOTO( $I_i,X_j$ )加入到C中

例子：

简单来说方法就是：

先把最开始的增广文法放到I0中，就是E’->E。此时只有I0一个
然后每次创建一个新的I，就去求它的闭包。
求完闭包之后，就去求这里面每个点后面字母的MOVE。这样它可以构造出其他的I。让原来的I指向新产生的I。然后就回到上一步不断重复。

构造完毕后，如何决定是否移入或规约：

如果下一个输入符号位a，且当前所处的状态上有a的转换，就移入a
否则就规约。状态中的项会告诉我们使用哪个产生式进行规约

假如输入γ后，当前在状态j。如果j中有一个A->α.，那么如果γ后面添加终结符号可以得到最右句型，α是γ的后缀。

假如j中有一个B->α.Xβ，那么在γ之后添加Xβ，然后再添加一个终结符号串可得到一个最右句型，这个句型中B->αXβ是句柄，此时表示还没有找到句柄，需要移入。

示例：

刚开始栈什么都没有，在状态0.输入符号时前往新状态。如果输入一个符号时没有路径可走，那么就根据当前状态中的式子来规约。规约后的状态的确定就是先把状态栈退一格，然后输入这个规约后的式子，前往新的状态。例如这里从0 2 7 5进行id变F的规约时，我先推导0 2 7，然后再从状态7输入F，前往状态10.因此也就变成了0 2 7 10

LR语法分析器的结构

两个部分：动作ACTION，转换GOTO

ACTION的两个参数：状态i、终结符号a
GOTO函数：GOTO[i,A]=j，表示从状态i上输入A可以进入j状态

格局：包含了栈中内容和余下输入 $(s_0s_1…s_m, a_ia_{i+1}…a_n\$)$

LR语法分析器的每一个状态都对应一个文法符号（S0除外）

LR分析表

其中，s表示转换，即切换到对应数字的状态中；r表示规约，即使用对应数字的规则进行规约。

SLR分析表

SLR：Simple LR

构造算法：

构造G’LR(0)项集规范族C={I0,I1,…In}
对于状态i中的项，如果[A → α·aβ]且GOTO[Ii,a]=Ij, 那么ACTION[i,a]=移入j；如果[A → α·]，那么对于FOLLOW(A)中的所有a， ACTION[i,a]=归约A → α；如果[S’ →S·], 那么ACTION[i,$]=接受
如果GOTOGOTO[Ii,A]=Ij，那么GOTO[i ,A]=j
规则2和3没有定义的所有条目设置为报错

简单来说就是：先构造项集规范族（很多个箭头的那个图），然后去遍历每一个状态中的每一个项。拿到一个项，根据它点的位置进行处理：如果点在中间，那么就直接在表中添加一项：当前状态，碰到点右边的字母，跳到对应的状态。如果点在最右边，那么我就去拿到项左边字母的FOLLOW集，然后在表中添加：当前状态碰到这个follow中的字母就直接规约为点左边的字母。

构造完毕后，如果每个格子最多只有一个条目，说明是SLR(1)文法。如果有格子出现了多个条目，说明不是SLR(1)文法

LR(0)自动机刻画了可能出现在语法分析栈中的文法符号串（能够识别可行前缀）

可行前缀：定义：某个最右句型的前缀，且没有越过该句型的句
柄的右端

有效项：

意义：帮助我们决定移入还是规约（β2不等于空就移入或等待规约；如果β2等于空就规约）

SLR解决冲突：输入一个新的终结符号时，如果当前已经在末尾，同时也可以跳转，那么就去看每个表达式右边的式子中出现的当前规约后的字母。看看在这些字母后面有没有一个跟着当前输入的字母的项，有的话就规约。当然，如果规约后栈中的式子不可能是某个最右句型的前缀就仍然不能按照这个方法规约

语法错误的处理

程序中存在不同层次的错误：

词法错误
语法错误
语义错误
逻辑错误

语法分析器中错误处理程序的设计目标：

清晰报告错误和位置
能从错误恢复，继续检测后面的错误
减少开销

两类错误恢复方法：

恐慌模式
短语层次的恢复

恐慌模式：

忽略输入中的一些符号，直到出现由设计者选定的某个同步词法单元

解释：程序总是视图找到某个非终结符号对应的串，这里就假装已经找到了这个串。同步词法单元就是这个程序结构结束的标志

同步集合的启发式规则：

FOLLOW(A)的所有符号
FIRST(A)的所有符号
栈顶的终结符号匹配错误，可以直接弹出相应的符号

例子：

空条目表示忽略输入符号，synch也表示忽略输入符号，一直忽略，直到这个符号是同步集合中的符号，然后弹出这个非终结符号