【编译原理系列】语法分析与上下文无关文法

秒速五厘米 2023-01-10 11:49 612阅读 0赞

# 语法分析 #

词法分析：

*  字母是元素，组成字符串，记号的集合，线性结构，以字符流为输入

语法分析：

*  记号是元素，组成句子， 句子的集合，**树结构**，以记号流为输入

语法的双重含意：

1.  语法**规则**：上下文无关文法（子集－LL文法或LR文法）
2.  语法**分析**：下推自动机（LL或LR分析器），**自上而下**和**自下而上分析** （这两种都只能处理上下文无关文法的子类）

# 语法分析器 #

语法分析器是编译器前端的重要组成部分，中心部件

语法分析器的两个重要作用：

1.  根据词法分析器提供的记号流，为语法正确的输入**构造分析树（或语法树）**
2.  **检查**输入中的**语法（可能包括词法）错误**，并调用出错处理器进行**适当处理**

## 语法错误处理原则 ##

源程序中可能出现的错误：

*  语法（包括词法）错误
    
     *  **词法错误**如**非法字符**或**拼写错关键字、标识符**等
     *  **语法错误**是指**语法结构出错**，如少分号、begin/end不配对等
 *  语义错误
    
     *  **静态语义错误**（涉及的是**编译时**可检查出来的错误）：如类型不一致、参数不匹配等
     *  **动态语义错误**（程序**运行时的**逻辑错误）：如死循环、变量为零时作除数等

目标：

*  清楚而准确地**报告错误的出现**（地点正确，不漏报、不错报也不多报
 *  迅速从每个错误中**恢复**过来（以便分析继续进行）
 *  不应对语法正确源程序的**分析速度**降低太多

基本恢复策略

1.  紧急方式恢复：**抛弃若干输入**，直到遇到某个指定的合法记号（称为同步记号）集合为止同步记号一般是定界符，如分号或end等【最简单，但最容易造成错报、漏报和多报语法错误的现象】
2.  短语级恢复：采用**串替换**的方式对剩余输入进行**局部纠正**（抛弃+插入）
3.  出错产生式：用**出错产生式**捕捉错误（**预测错误**），**预置型的短语级恢复方式**（YACC采用的方式）
4.  全局纠正：对错误输入序列x，找相近序列y，使得x变换成y**所需的修改、插入、删除次数最少**【代价太大】

# 上下文无关文法CFG #

CFG：Context Free Grammar

*  CFG是一个四元组G =（N，T，P，S），其中
    
     *  （1） N是**非终结符**（Nonterminals）的**有限集合**；
     *  （2） T是**终结符**（Terminals）的有限集合，且N∩T=Φ；
     *  （3） P是**产生式**（Productions）的有限集合，  
        A→α，其中**A∈N（左部）**，α∈(N∪T)\*（右部），  
        若α=ε，则称A→ε为空产生式（也可以记为A →）；
     *  （4） S是非终结符，称为文法的**开始符号**（Start symbol）
 *  可以将产生式中的记号→读作 **“定义为”** 或者 **“可导出”**
    
     *  如：“E → E + E”可用自然语言表述为“算术表达式定义为两个算术表达式相加”， 或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”

各元素要求

*  文法开始符号S是第一个产生式的左部；
 *  N是可以出现在产生式左边符号的集合；
 *  **T**是**绝不出现**在**产生式左边符号的集合（记号)** ,所以T不一定是一个句子的那种终结符，也可以是一个短语的终结符，如+、-、(、)等等

约定：

*  **大写**英文字母A、B、C表示**非终结符**；
 *  **小写**英文字母a、b、c表示**终结符**；
 *  小写**希腊**字母α、β、δ表示**任意文法符号序列**
 *  产生式中，用“|”连接的每个**右部**称为一个**候选项**，具有**平等**的权利

**CFG的产生式**表示也被称为**巴克斯范式BNF**，规范的BNF中，`->`用`::=`来表示

## CFG产生语言的基本方法——推导 ##

推导：产生式产生语言的过程是**从开始符号S开始，对产生式左部的非终结符反复地使用产生式**：将产生式左部的非终结符替换为右部的文法符号序列(展开产生式，用标记=>表示)，直到得到一个**终结符序列**

*  利用产生式产生句子的过程中，将产生式A→γ的右部**代替**文法符号序列αAβ中的A得到αγβ的过程，称αAβ**直接推导**出αγβ，记作：αAβ=>αγβ
 *  若对于任意文法符号序列α1，α2，…αn，均α1=>α2=>…=>αn，则称此过程为零步或多步推导，记为： α 1 = ∗ > α n α1=^\*>αn α1=∗>αn，其中α1=αn的情况为**零步推导**；若α1≠αn，即推导过程中至少使用一次产生式，则称此过程为**至少一步推导**，记为： α 1 = + > α n α1=^+>αn α1=\+>αn
 *  对于所有α，有 α = ∗ > α α=^\*>α α=∗>α，即推导具有**自反性**
 *  若 α = ∗ > β α=^\*>β α=∗>β， β = ∗ > γ β=^\*>γ β=∗>γ，则 α = ∗ > γ α=^\*>γ α=∗>γ，即推导具有**传递性**

### CFL上下文无关语言 ###

*  由CFG G所产生的语言L(G)被定义为:
 *   L ( G ) = \{ ω ∣ S = + > ω   a n d   ω ∈ T ∗ \} L(G)=\\\{\\omega|S=^+>\\omega\\ and\\ \\omega\\in T^\*\\\} L(G)=\{ ω∣S=\+>ω and ω∈T∗\}
 *  **L(G)称为上下文无关语言**(Context Free Language, CFL)，**ω**称为**句子**，若**S=\*>α**，**α∈(N∪T)\***，则称α为G的一个**句型**

第一个是文法开始符号，最后一个是句子，其他的都是句型，但广义来说，第一个和最后一个也是句型

*  在推导过程中，若每次**直接推导**均替换句型中**最左边的非终结符**，则称为**最左推导**，由最左推导产生的句型被称为**左句型**；
 *  类似的可以定义最右推导与右句型，**最右推导**也被称为**规范推导**

### 分析树 ###

*  分析树是推导的图形表示，直观并且同时反映语言结构的实质和推导过程

对CFG G的句型，**分析树**被定义为具有下述性质的一棵树。

*  （1） **根**由**开始符号**所标记
 *  （2） 每个**叶子**由一个**终结符、非终结符、或ε**标记
 *  （3） 每个**内部结点**由一个**非终结符**标记
 *  （4） 若A是某内部节点的标记，且X1，X2，…，Xn是该节点从左到右**所有孩子**的标记，则A→X1X2…Xn是一个**产生式**。若A→ε，则标记为A的结点可以仅有一个标记为ε的孩子

分析树与语言和文法的关系：

1.  每一**直接推导**(每个产生式)，对应一棵仅有**父子关系的子树**，即产生式左部非终结符“长出”右部的孩子
2.  分析树的**叶子**，从左到右构成G的一个**句型**；若叶子**仅由终结符标记**，则构成**一个句子**

### 语法树 ###

*  为了仅关注**句型**，并且**忽略推导**过程，产生了语法树：

对CFG G的句型，表达式的**语法树**被定义为具有下述性质的一棵树:

*  （1） **根**与**内部节点**由表达式中的**操作符**标记；
 *  （2） **叶子**由表达式中的**操作数**标记；
 *  （3）用于改变运算优先级和结合性的**括弧**，被**隐含**在语法树的结构中

分析树和语法树又被称为**具体语法树**和**抽象语法树**AST

### 二义性与二义性的消除 ###

*  若文法G对同一句子产生**不止一棵分析树**，则称G是**二义的**

产生原因：

*  在产生句子的过程中某些直接推导有**多于一种选择**；
 *  文法中**缺少**对文法符号**优先级和结合性**的规定；一个句子有多于一颗分析树，**仅与文法和句子有关，与采用的推导方法无关**（对于某些文法和句型，无论采用最左推导还是最右推导都会有歧义的）

文法二义性不能说明程序设计语言是二义的

*  程序设计语言不能二义；
 *  只有当产生一个语言的所有文法都是二义的时，这个语言才被认为是二义的

**二义文法不是CFG**

消除文法二义的两种方法：

1.  改写二义文法为非二义文法
2.  规定二义文法中符号的优先级和结合性，使仅产生一颗分析树

现给出一个二义文法：

E→E+E 
     | E*E
     |（E） 
     | -E
     | id

#### 改写二义文法为非二义文法 ####

对于上述二义文法进行改写：

E → E + T  | T			
    T → T * F  | F 
    F →（E）    | -F | id

**改写二义文法的方法：**

*  通过**引入非终结符**，使原来分辨不清的结构受到约束，从而使得对任何一个句子，仅能构造一颗分析树

一些结论：

1.  **新引入的非终结符**，限制了每一步直接推导均有**唯一**选择
2.  最终分析树的形状，**仅与文法有关**，而与推导方法无关
3.  非终结符的引入，**增加了推导步骤**（分析树增高），从而分析树效率降低
4.  **越接近S的文法符号的优先级越低**（如E→E+T）
5.  对于A→αAβ，若 a ∈ β a\\in\\beta a∈β（A在a的左边），则a具有**左结合**性质；若 a ∈ α a\\in\\alpha a∈α（A在a的右边），则a具有右结合性质\*\*\*【如E->E+T，则+具有左结合性，E->T+E，则+具有右结合性】\*\*\*

关键步骤：

1.  引入一个**新的非终结符**，**增加**一个**子结构**并**提高**一级**优先级**
2.  递归**非终结符**在**终结符左边**，运算具有**左结合性**，否则具有**右结合性**

说明

*  先列出优先级，比如这里我可以说从低到高是\[+\] \[\*\] \[(), -, id\]；
 *  然后列出结合性：左结合+,；右结合-；无结合id；因为有三个层次，所以需要再引入两个新变量，首先是优先级最低的，然后是次之，最后是最高的；
 *  在每一个产生式中，又要根据结合性，如果是左结合的则右边应该含有终结符的标号，否则相反，就可以写出来了；当然要注意可以不含有+的问题，所以有个|T的存在\*

对于“悬空”问题（即else和最近还是最远if匹配）

*  因为没有优先级区分，但是结合性应该是右结合，即else与其左边最靠近的then结合，那么只需改写如下：

原来的：
    S → if C then S
       | if C then S else S
       | id := E     
    C → E=E | E<E | E>E
    E → E+E | -E | id | n
    
    改写之后的（MS是完全匹配的意思，即含有if then else；UMS不完全匹配，即含有if then，至于then中是否嵌套，则看如下表示）：
    S  → MS 			   
        | UMS			   
    MS → if C then MS else MS  
        | id := E		   
    UMS→ if C then S		    
        | if C then MS else UMS  
    C → E=E | E<E | E>E
    E → E + T  | T			
    T →（E）    | -T | id | n

然后根据一一比对，比如对于`if x<3 then if x>0 then x:=5 else x:=-5`

比如对于和最远的if匹配的话，

*  先将S展开，如果是MS，则展开为第一种，但是MS展不开了（这里应该是`if x>0 then x:=5`这句话）；
 *  如果是UMS，则展开为第二种，但是MS也展不开了，所以这种匹配不可行；
 *  而和最近的if匹配的话，是可行的，且唯一确定，首先展开成UMS，S再展开成MS的第一种

#### 规定二义文法中符号的优先级和结合性 ####

但是二义文法具有如下优点：

1.  比非二义文法容易理解
2.  分析效率高，分析树低，直接推导步骤少

通过为二义文法规定优先级和结合性（YACC的方法）

#### 修改语言的语法（表现形式被改变） ####

1.  明确给出结束标志，如`end if`
2.  给表达式加括号

## 正规式与CFG ##

### 正规式到CFG的转换 ###

正规式所描述的语言结构均可用CFG描述，反之不一定

*  识别正规语言的自动机是有限自动机，它们的特征是没有记忆功能\*
 *  识别 CFL 的自动机是下推自动机，在有限自动机的基础上增加了一个下推栈，具有简单的记忆功能\*

从正规式到CFG的对应关系：

1.  构造正规式的NFA
2.  **若0为初态**，则 A 0 A\_0 A0为开始符号
3.  对于move(i,a)=j，引入产生式 A i A\_i Ai→ a A j aA\_j aAj
4.  对于move(i,ε)=j，引入产生式  A i → A j A\_i→A\_j Ai→Aj
5.  **若i是终态**，则引入产生式 A i → ε A\_i →ε Ai→ε

为什么用正规式而不用CFG描述**词法**：

1.  词法规则简单，用正规式描述已足够
2.  正规式的表示比CFG更直观、简洁、易于理解
3.  有限自动机的构造比下推自动机简单，且分析效率高
4.  区分词法和语法，为编译器前端的模块划分提供方便

*  正规式适合描述**线性结构**，如标识符、关键字、注释等
 *  CFG适合描述**具有嵌套（层次）性质的非线性结构**，如不同结构的句子if-then-else、while-do等

# 上下文有关语言CSL #

变量的声明与引用、过程调用时形参与实参的一致性检查等无法用CFG描述，所以产生了CSL（Context Sensitive Language)

CFG到CSL的文法所表示的意思都变了

CFG无法表示:
    L1={ ωcω|ω∈(a|b)*}	(标识符声明与引用一致性的抽象)
    L2={ a^n b^m c^n d^m|n≥1和m≥1}	(形参ab与实参cd一致性的抽象)
    L3={ a^nb^nc^n|n≥1} 		(输入n个字符，回退n个字符，加n个底线，计数问题的抽象)
    
    对文法稍加修改，得到相近的CFL：
    【ω^r是ω的逆序】
    L1'={ ωcω^r|ω∈(a|b)*}			（S→aSa|bSb|c）
    L2'={ a^n b^m c^m d^n|n≥1, m≥1}	  （S→aSd|aAd    A→bAc|bc）
    L2''={ a^n b^n c^m d^m|n≥1, m≥1}   （S→AB  A→aAb|ab  B→cBd|cd）
    L3'={ a^m b^m c^n|m, n≥1}		  （S→AC  A→aAb|ab   C→cC|c）
    
    正规式：
    L3''={ a^k b^m c^n|k,m,n>=1} 		a^+ b^+ c^+

命题：L3’不是正规集，因为构造不出可以识别L3’的DFA

*  证明：（反证）
 *  假设L3’是正规集，则可构造n个状态的DFA D，它接受L3’；
 *  考察D读完 ε ， a ， a a ， … ， a n ε，a，aa，…，a^n ε，a，aa，…，an，分别到达 S 0 ， S 1 ， … ， S n S0，S1，…，Sn S0，S1，…，Sn，共有 n + 1 n+1 n\+1个状态。
 *  根据鸽巢原理，序列中至少有两个状态相同，设 S i = S j （ j > i ） S\_i=S\_j（j>i） Si=Sj（j>i），因为 a i b i c k ∈ L 3 ’ a^ib^ic^k∈L3’ aibick∈L3’，所以存在路径 a i b i c k a^ib^ic^k aibick，但是D中也有路径 a j b i c k a^jb^ic^k ajbick，矛盾；故L3’不是正规集

# 形式语言与自动机 #

若文法 G = ( N ， T ， P ， S ) G=(N，T，P，S) G=(N，T，P，S)的每个产生式 α → β α→β α→β中，均有 α ∈ ( N ∪ T ) ∗ α∈(N∪T)^\* α∈(N∪T)∗，且至少含有一个非终结符， β ∈ ( N ∪ T ) ∗ β∈(N∪T)^\* β∈(N∪T)∗，则称G为0型文法

*  任何0型语言都是递归可枚举的；反之，递归可枚举集必定是一个0型语言

对0型文法施加以下第i条限制，即得到i型文法。

1.  G的任何产生式α→β（S→ε除外）满足|α|≤|β|
2.  G的任何产生式形如A→β，其中A∈N， β ∈ ( N ∪ T ) ∗ β∈(N∪T)^\* β∈(N∪T)∗【对于 α A β → α γ β \\alpha A\\beta\\to\\alpha \\gamma\\beta αAβ→αγβ，则A只有在左边是 α \\alpha α，右边是 β \\beta β这样的上下文才可能替换成 γ \\gamma γ
3.  G的任何产生式形如A→a或者A→aB(或者A→Ba)，其中A和B∈N，a∈T

<table> 
 <thead> 
  <tr> 
   <th align="center">文法</th> 
   <th align="center">语言</th> 
   <th align="center">自动机</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">短语文法（0型）</td> 
   <td align="center">短语结构语言</td> 
   <td align="center">图灵机</td> 
  </tr> 
  <tr> 
   <td align="center">CSG （1型）</td> 
   <td align="center">CSL</td> 
   <td align="center">线性界线自动机</td> 
  </tr> 
  <tr> 
   <td align="center">CFG （2型）</td> 
   <td align="center">CFL</td> 
   <td align="center">下推自动机</td> 
  </tr> 
  <tr> 
   <td align="center">正规文法（3型）</td> 
   <td align="center">正规集</td> 
   <td align="center">有限自动机</td> 
  </tr> 
 </tbody> 
</table>

CSG、CFG、正规式能力递减，但是能力越强的文法，其文法的设计和自动机的构造越苦难。