编译原理教程_2 文法和语言

迈不过友情╰ 2022-11-10 03:47 908阅读 0赞

> **文章下载地址**  
> https://gitee.com/fakerlove/fundamentals-of-compiling

### 文章目录 ###

*  2. 文法和语言
 *   *  2.1 概念
     *   *  2.1.1 语法(文法)
         *   *  1) 词法规则
             *  2) 语法规则
         *  2.1.2 语义
         *  2.1.3 语法规则符号相关概念
         *   *  (1)非终结符
             *  (2)终结符
             *  (3)开始符号
             *  (4)产生式
             *  (5)推导
             *  (6)归约
             *  (7)句型、句子和语言
             *  (8)文法规则的递归定义
             *  (9) 文法规则的扩充表示
             *  (10)元语言符号
         *  2.1.4 总结
     *  2.2 字母表与符号串(单词符号)
     *   *  2.2.1 概念
         *  2.2.2 符号串集合的运算
         *   *  1) 连接（乘积）运算：
             *  2) 字母表的闭包与正闭包:star:
     *  2.3 文法和语言的形式定义
     *   *  1.文法定义
         *  2.推导定义
         *  3.语言定义
         *  4.递归文法
         *  5.句型的短语、简单短语和句柄
     *  2.4 文法和语言分类
     *   *  2.4.1 Chomsky对文法的分类:star:
         *   *  0型
             *  1型
             *  2型
             *  3型
         *  2.4.2 i型语言
         *  2.4.3 文法的构造和简化
         *   *  1) 构造-> 文法
             *  2) 构造->文法
             *  3) 简化文法
         *  2.4.4 构造无ε产生式的上下文无关文法
     *  2.5 语法树与二义性文法
     *   *  2.5.1 语法树
         *   *  1) 概念:star:
             *  2) 短语，直接短语，句柄
             *   *  解析：
             *  3) 素短语，最左素短语
             *   *  解析：
         *  2.5.2 二义性
         *   *  1) 判断二义性文法
             *  2) 子树与短语
             *  3) 规约

# 2. 文法和语言 #

> 一个程序设计语言是一个记号系统，如同自然语言一样，它的完整定义应该包括**语法和语义**两个方面，所谓一个语言的语法是指一组规则，用它可以形成和产生一个合适的程序
> 
> **语言是定义在一些有限字母表上的**
> 
> **语言是一个层次化的记号系统，有字母表上的字母按照一定的规则构成单词，由单词按照一定的规则构语句和文章**

## 2.1 概念 ##

### 2.1.1 语法(文法) ###

> 描述词法规则和语法规则的工具是文法

#### 1) 词法规则 ####

> 语言中具有独立意义的最基本结构。

– 词法规则规定了字母表中那些字符串是单词符号。

– 单词符号一般包括：常数、标识符、基本字、算符、界限符等。

– 我们用正规式和有限自动机理论来描述词法结构和进行词法分析。

#### 2) 语法规则 ####

> – 表达式、子句、语句、函数、过程、程序

– 规定了如何从单词符号来形成语法单位。

– 现在多数程序语言使用上下文无关文法来描述语法规则。

– 语言的词法规则和语法规则定义了程序的形式结构，是判断输入字符串是否构成一个形式上正确的程序的依据。我们通过建立一组规则，来描述句子的语法结构。规定用“::=”表示“由……组成”。

例如： 
<句子>::=<主语><谓语> 
<主语>::=<代词>|<名词> 
<代词> ::=你|我|他 
<名词>::= 王民|大学生|工人|英语 
<谓语>::=<动词><直接宾语> 
<动词>::=是|学习 
<直接宾语>::=<代词>|<名词>

### 2.1.2 语义 ###

> 对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义。
> 
> – 离开语义，语言只是一堆符号的集合。
> 
> – 各种语言中有形式上完全相同的语法单位，含义却不尽相同。
> 
> – 对某种语言，可以定义一个程序的意义的一组规则称为语义规则。
> 
> – 目前，大多数编译程序使用基于属性文法的语法制导翻译方法来分析语义。

### 2.1.3 语法规则符号相关概念 ###

#### (1)非终结符 ####

– 出现在规则的左部、用<>括起来、表示一定语法概念的词。

– 非终结符集合用VN表示。

#### (2)终结符 ####

– 语言中不可再分割的字符串(包括单个字符组成的串)。注：终结符是组成句子的基本单位。

– 终结符集合用VT表示

#### (3)开始符号 ####

– 表示所定义的语法范畴的非终结符。

– 注：开始符号又称为识别符号。

#### (4)产生式 ####

– 是用来定义符号串之间关系的一组(语法)规则。

– 形式：A → α （A产生α ）

#### (5)推导 ####

– 推导是从开始符号开始，通过使用产生式的右部取代左部，最终能产生语言的一个句子的过程。

– 最左（右）推导：每次使用一个规则，以其右部取代符号串最左（右）非终结符。

注：最左推导和最右推导称为规范推导

#### (6)归约 ####

– 归约是推导的逆过程，即，从给定的源语言的句子开始，通过规则的左部取代右部，最终达到开始符号的过程。

– 最左(右)归约是最右(左)推导的逆过程。

– 注：最左归约和最右归约称为规范归约

#### (7)句型、句子和语言 ####

*  句型：
    
    > – 句型是从文法的开始符号S开始，每步推导（包括0步推导）所得到的字符串α。
    > 
    > – 记作：S α，其中α ∈ （VN∪ VT ）\*
 *  句子：是仅含终结符的句型

#### (8)文法规则的递归定义 ####

– 非终结符的定义中包含了非终结符自身。

– 使用文法的递归定义要谨慎

#### (9) 文法规则的扩充表示 ####

> 扩充的BNF表示
> 
> *BNF的元符号*： <, >, ::=, | 
> *扩充的BNF的元符号*： <, >, ::=, |, \{, \}, \[, \] (, ) 
> 1.\{ t \}：t可重复连接0到任意多次。如果有限制（上标m，下标n），则可重复连接n到m次。 
> 2.\[ t \]：t可有可无。 
> 3.( )：元符号，注意不要与Vt混淆。
> 
> * () ——提因子
> 
> 例:把U→ax|ay|az 改写为U→a(x|y|z)
> 
> * \{\} ——重复次数的指定
> 
> 例：<标识符>→<字母>\{<字母>|<数字>\}50.
> * \[\] ——任选符号
> 
> 例:<整数>→\[+|-\]<数字>\{<数字>\}

#### (10)元语言符号 ####

用来说明文法符号之间关系的符号，如，“→”和“|”称为元语言符号

**例题**

> 有了一组规则之后，可以按照一定的方式用它们去推导或产生句子。 
> 推导方法：从一个要识别的符号开始推导，即用相应规则的右部来替代规则的左部，每次仅用一条规则去进行推导。 
> <句子> => <主语><谓语> 
> <主语><谓语> => <代词><谓语> 
> …… …… 
> 这种推导一直进行下去，直到所有带< >的符号都由终结符号替代为止。 
> *说明*： 
> (1) 有若干语法成分同时存在时，我们总是从 **最左的语法成分**进行推导，这称之为最左推导。类似地还有最右推导（一般推导、规范推导）。 
> (2) 除了最左和最右推导，还可能存在其它形式的推导。 
> (3) 从一组规则可推出不同的句子

### 2.1.4 总结 ###

*  任何语言程序都可以看成是一定字符集（字母表）上的字符串。
 *  语法使得这串字符形成一个形式上正确的程序。
 *  语法＝词法规则＋语法规则
 *  例如：0.5*x1+c*
    
    – 0.5、x1、c、\*、+是语言的**单词符号**
    
    – 0.5\*x1+c是语言的**语法单位**

## 2.2 字母表与符号串(单词符号) ##

### 2.2.1 概念 ###

<table> 
 <thead> 
 <tr> 
 <th>名称</th> 
 <th>概念</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>字母表</td> 
 <td>– 是符号的非空有穷集合。 – 用Σ、V表示。</td> 
 </tr> 
 <tr> 
 <td>符号</td> 
 <td>是语言中最基本的不可再分的单位。</td> 
 </tr> 
 <tr> 
 <td>符号串</td> 
 <td>– 符号串是字母表中符号组成的有穷序列。 – 空串：不含有任何符号的串称作空串，记作ε。</td> 
 </tr> 
 <tr> 
 <td>句子</td> 
 <td>字母表上符合某种规则构成的串。</td> 
 </tr> 
 <tr> 
 <td>语言</td> 
 <td>字母表上句子的集合</td> 
 </tr> 
 </tbody> 
</table>

### 2.2.2 符号串集合的运算 ###

#### 1) 连接（乘积）运算： ####

> 若串集A=\{α1， α2， …\}，串集B=\{β1,β2， …\}，则乘积AB=\{α β| α ∈ A and β ∈ B\}
> 
> 注：1）串集的自身乘积称作串集的方幂
> 
> 2）A0=\{ε\}
> 
> 3）字母表A的n次方幂是字母表A上所有长度为n的串集

例如：串集A＝\{a\}的各次方幂定义为：

A0=\{ε\}

A1=A=\{a\}

……

An=AAn-1(n>0)=\{a…a\}

#### 2) 字母表的闭包与正闭包⭐️ ####

a. 字母表A的闭包（A\*）：

> A\*=A0∪A1∪A2∪…
> 
> 即：由A上符号组成的所有串的集合（包括空串ε ）。

例 题 : ( a , b ) ∗ 代 表 w ∈ \{ ε , a , b , a b , a a , b b , . . . . \} 例题:(a,b)^\* 代表 w\\in \\\{ε, a,b,ab,aa,bb,....\\\} 例题:(a,b)∗代表w∈\{ ε,a,b,ab,aa,bb,....\}

b. 字母表A的正闭包（A+）：

> A+= A1 ∪A2∪ …=A\*-\{ε\}
> 
> 即：由A上符号组成的所有串的集合（不包括空串ε ）。

c. 语言: 是字母表上符合某种规则的语句组成的。

– **字母表上语言：是字母表上正闭包的子集**

## 2.3 文法和语言的形式定义 ##

### 1.文法定义 ###

>  从 形 式 上 说 文 法 G 是 一 个 四 元 式 ( V N , V T , P , S ) 从形式上说文法G是一个四元式(V\_N,V\_T,P,S) 从形式上说文法G是一个四元式(VN,VT,P,S)

文法 G = （ V n ， V t ， P ， Z ） G =（V\_n，V\_t，P，Z） G=（Vn，Vt，P，Z）

*  Vn：非终结符号集
 *  Vt：终结符号集
 *  P：产生式或规则的集合
 *  Z：开始符号（识别符号） Z∈Vn

*注*：  
①V＝Vn ∪ Vt 称为文法的字汇表  
②规则：规则是一个有序对(U, x), 通常写为 U ::= x 或U→x（其中U∈Vn, x∈V\* 因此也有|U| = 1且|x| >= 0）  
③给定一个文法，实际只需给出产生式集合，并指定识别符号。（识别符号一般约定为第一条规则的左部符号）

> *例：无符号整数的文法*： 
> G\[<无符号整数>\]=（Vn，Vt，P，Z） 
> Vn＝\{<无符号整数>,<数字串>, <数字>\} 
> Vt = \{ 0, 1, 2, 3, … 9 \} 
> P = \{<无符号整数> → <数字串> 
> <数字串> → <数字串> <数字> 
> <数字串> → <数字> 
> <数字> →0 
> <数字> →1 
> ………… 
> <数字> →9 \} 
> Z = <无符号整数>

### 2.推导定义 ###

**一步推导**：  
![推导的形式定义1][1]  
*注*：当符号串已没有非终结符号时，推导就必须终止。因为终结符不可能出现在规则左部，所以将在规则左部出现的符号称为非终结符号。

**多步推导**：  
![在这里插入图片描述][9641381897ad001fe2581314b941795f.png]  
**任意步推导**：  
![在这里插入图片描述][4088aa2b404071d2ac499c59143d96b5.png]  
**规范推导**：  
![在这里插入图片描述][5cb7bc51c5e59f0afa07e34ed58a9887.png]  
直观意义上：规范推导＝最右推导

### 3.语言定义 ###

对于文法G\[Z\]：  
（1）句型x：由开始符号Z经任意步推导得到x，且x∈V\*；  
（2）句子x：由开始符合Z经1多步推导得到x，且x∈Vt\*  
（3）语言L：所有根据该文法推到得到的句子组成的集合

形式语言理论可以证明以下两点：  
（1）G →L(G)：已知文法，求语言，通过推导；  
（2）L(G)→G1，G2，……，Gn：已知语言，构造文法，无形式化方法，更多是凭经验。

**等价文法**：G和G’是两个不同的文法，若 L(G) = L(G’) ,  
则G和G’为等价文法。

### 4.递归文法 ###

①递归规则：**规则右部有与左部相同的符号**  
对于 U::= xUy  
若x=ε,即U::= Uy，左递归；  
若y=ε,即U::= xU，右递归。

②递归文法：文法G，存在U ∈Vn  
if U=+=>…U…, 则G为递归文法(自嵌入递归)；  
if U=+=>U…, 则G为左递归文法；  
if U=+=>…U, 则G为右递归文法。

③左递归文法的缺点：不能用**自顶向下**的方法来进行语法分析

④递归文法的优点：可用有穷条规则，定义无穷语言

### 5.句型的短语、简单短语和句柄 ###

给定文法G\[Z\], w::=xuy∈V+，为该文法的句型,  
若 Z==> xUy, 且U=+=>u, 则u是句型w相对于U的短语；  
若 Z==> xUy, 且U==>u, 则u是句型w相对于U的简单短语。  
其中U ∈Vn，u ∈V+，x, y ∈V\*

*短语的直观理解*：短语是前面句型中的**某个非终结符**所能推出  
的**符号串**。  
*句柄*：任一句型的最左简单短语称为该句型的句柄

给定句型找句柄的步骤：  
短语-> 简单短语-> 句柄

**注意**：短语、简单短语是相对于句型而言。一个句型  
可能有多个短语、简单短语，但句柄只能有一个。

## 2.4 文法和语言分类 ##

### 2.4.1 Chomsky对文法的分类⭐️ ###

> 文法和语言分类：0型、1型、2型、3型  
> 这几类文法的差别在于对产生式施加不同的限制。

#### 0型 ####

#### 1型 ####

#### 2型 ####

#### 3型 ####

从 形 式 上 说 文 法 G 是 一 个 四 元 式 ( V N , V T , P , S ) 从形式上说文法G是一个四元式(V\_N,V\_T,P,S) 从形式上说文法G是一个四元式(VN,VT,P,S)

<table> 
 <thead> 
 <tr> 
 <th>文法类型</th> 
 <th>别称</th> 
 <th>对产生式的限制</th> 
 <th>可被接受目标</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>0型文法</td> 
 <td>短语结构文法</td> 
 <td>P:u::=v 其中 u∈V＋,v∈V*</td> 
 <td>图灵机(Turing)</td> 
 </tr> 
 <tr> 
 <td>1型文法</td> 
 <td>上下文敏感（有关）文法</td> 
 <td>P: xUy::= xuy 其中 U∈Vn,x、y、u∈V*</td> 
 <td>线性界限自动机</td> 
 </tr> 
 <tr> 
 <td>2型文法</td> 
 <td>上下文无关文法</td> 
 <td>P: U::= u 其中 U∈Vn,u∈V* 左边的必须是非终结符，右边是字符串</td> 
 <td>下推自动机</td> 
 </tr> 
 <tr> 
 <td>3型文法</td> 
 <td>正则文法</td> 
 <td> ① P : U : : = T 或 U : : = w T 其 中 U 、 w ∈ V n , T ∈ V t ( 右 线 性 ) ② P : U : : = T 或 U : : = T w 其 中 U 、 w ∈ V n , T ∈ V t ( 左 线 性 ) ①P: U::=T 或 U::=wT 其中 U、w∈V_n,T∈V_t(右线性)\\ ②P:U::=T 或 U::=T_w 其中 U、w∈V_n ,T∈V_t(左线性) ①P:U::=T或U::=wT其中U、w∈Vn,T∈Vt(右线性)②P:U::=T或U::=Tw其中U、w∈Vn,T∈Vt(左线性) 人话来说，左边的必须是非终结符， 右边的非终结符要么都在左边，要么都在右边</td> 
 <td>有穷自动机</td> 
 </tr> 
 </tbody> 
</table>

**注**：

*  **3型文法是我们判断单词是否正确的方法**
 *  **2型语言是我们判断句子是否正确的方法**
 *  2型文法与BNF表示相等价。
 *  3型语言（L3）又称正则语言、正则集合
 *  **四种语言的关系：**  
    ![在这里插入图片描述][ca47bf3f842e097750f77d9559b5cab9.png]

### 2.4.2 i型语言 ###

由i型文法生成的语言成为i型语言。

– 记为：L(G)；L(G)=\{w|w ∈VT\* ，且S →+ w\}

### 2.4.3 文法的构造和简化 ###

#### 1) 构造-> 文法 ####

例一

> 设文法G1＝(\{S\},\{a,b\},P,S)
> 
> 其中P为:
> 
> (0) S →aS
> 
> (1) S →a
> 
> (2) S →b
> 
> L(G1)=\{ai(a|b)|i>=0\}

例二

> 设文法G2＝(\{S\},\{a,b\},P,S)
> 
> 其中P为:
> 
> (0) S →aSb
> 
> (1) S →ab
> 
> L(G2)=\{anbn|n>=1\}

#### 2) 构造->文法 ####

>  设 L 2 = a i b j c k ∣ i , j , k > = 1 且 a , b , c ∈ V T 试 构 造 生 成 L 2 的 文 法 G 2 设L\_2=\{a^ib^jc^k | i,j,k>=1 且a,b,c ∈ V\_T\}试构造生成L\_2的文法G\_2 设L2=aibjck∣i,j,k>=1且a,b,c∈VT试构造生成L2的文法G2
> 
> 解：S →aS
> 
> S → aB
> 
> B →bB
> 
> B →bC
> 
> C →cC | c

> 设L4=\{ω | ω ∈(0,1)\* 且ω中1的个数为偶数\}试构造生成L4的文法G4
> 
> 解：
> 
> S → ε
> 
> S →0S， S → 1A
> 
> A →0A , A →1S

#### 3) 简化文法 ####

简化规则

*  查找有无形如P→P的产生式，若有则删除；
 *  若某个产生式在推导过程中永远不会被用到，删除它；
 *  若某个产生式在推导过程中不能从中导出终结符，删除它；
 *  最后，整理所有剩余产生式，就得到简化的文法。

例题

> 简化
> 
> (0)S → Be (1)S → Ec (2)A → Ae (3)A →e
> 
> (4)A →A (5)B →Ce (6)B →Af (7)C →Cf
> 
> (8)D →f
> 
> 答案
> 
> (0) S → Be
> 
> (1)A → Ae
> 
> (2)A →e
> 
> (3)B →Af

### 2.4.4 构造无ε产生式的上下文无关文法 ###

无ε产生式的上下文无关文法要满足条件

> P中要么不含有ε产生式，要么只有S → ε；
> 
> 若S → ε，则S不出现在任何产生式右部。

构造无ε产生式的上下文无关文法变换算法：

G = ( V N , V T , P , S ) G ’ = ( V ’ N , V ’ T , P ’ , S ’ ) G=(V\_N,V\_T,P,S) G’=(V’\_N,V’\_T,P’,S’) G=(VN,VT,P,S)G’=(V’N,V’T,P’,S’)

*  由文法G找出所有经过若干步推导能推出ε的非终结符，放在V0集合中。
 *  再按下列步骤构造G’的产生式集合P’；
    
     *  A)若V0集合中的某元素出现在某产生式的右端，则将它变成两个产生式：分别以ε和其原型代入；将新产生式加入P’
     *  B)不满足上一条的P中其他产生式除去ε产生式后也加入P’
     *  C)如果P中有产生式S → ε，将它在P’中改为S ‘→ ε | S，S’是新的开始符号， 把 它 加 入 V N ， 形 成 V ’ N 把它加入V\_N，形成V’\_N 把它加入VN，形成V’N

> 设G1=(\{S\},\{a,b\},P,S),其中
> 
> – P: (0) S → ε (1) S →aSbS (2) S →bSaS
> 
> (1)V0=\{S\}
> 
> (2)P’: (1) → S →abS|aSbS|aSb|ab
> 
> (2) → S →baS|bSaS|bSa|ba
> 
> (0) → S’ → ε | S
> 
> 故：文法G1’=(\{S’,S\},\{a,b\},P’,S’),其中
> 
> P’: (0) S’ → ε | S
> 
> (1) S →abS|aSbS|aSb|ab
> 
> (2) S →baS|bSaS|bSa|ba

## 2.5 语法树与二义性文法 ##

### 2.5.1 语法树 ###

#### 1) 概念⭐️ ####

语法树的叶子节点是句子的单词，非叶子节点的是语法成分。

<table> 
 <thead> 
 <tr> 
 <th>名称</th> 
 <th>内容</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>子树</td> 
 <td>除叶子结点之外的任意结点连同它的所有子孙结点构成子树。</td> 
 </tr> 
 <tr> 
 <td>修剪子树</td> 
 <td>除叶子结点之外的任意结点连同它的所有子孙结点构成子树。</td> 
 </tr> 
 <tr> 
 <td>句型</td> 
 <td>在一棵语法树生长过程中的任何时刻，所有那些叶子结点排列起来就是一个句型。</td> 
 </tr> 
 <tr> 
 <td>短语</td> 
 <td>子树的末端符号自左到右连成串，相对于子树树根而言称为短语。</td> 
 </tr> 
 <tr> 
 <td>简单短语（直接短语）</td> 
 <td>定义： 若 S ⇒* αβδ，且文法中包含产生式 A → β，则称 β 是句型 αβδ 相对于非终结符 A 的直接短语。 语法树： 在语法树中表示为该短语只有上下相邻父子两代 人话就是 ，是由所有叶子节点组成，并且叶子节点的父亲，没有其他子树</td> 
 </tr> 
 <tr> 
 <td>句型的短语</td> 
 <td>该句型中哪些符号串可构成某子树根的短语。</td> 
 </tr> 
 <tr> 
 <td>句柄</td> 
 <td>“可规约串”，句柄对应某个产生式的右部，是某个，但不是任意一个。作为一种规约对象，句柄表示最左直接短语。 语法树： 在语法树上，则表示为最左边的只包含相邻父子节点的短语（最左直接短语）</td> 
 </tr> 
 <tr> 
 <td>素短语</td> 
 <td>定义： 是指一个短语至少包含一个终结符，并且除它自身之外不再包含其他素短语</td> 
 </tr> 
 <tr> 
 <td>最左素短语</td> 
 <td>定义： 最左素短语就是句型最左边的素短语，是算符优先分析法的规约对象。 语法树： 通过语法树分析时，要注意先判断是否为素短语，再找相对最左端的素短语。</td> 
 </tr> 
 </tbody> 
</table>

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KimI76QC-1615862510916)(picture/image-20210129092501778.png)\]

**语法图**

![在这里插入图片描述][dbc427c29cd1ceb8c5de6c6eb7420988.png]

**例题**

![image-20210129144134662][]

直接短语的为 S 、（T）、b，短语有S、（T）、b、Sd（T)、Sd（T）db 、（Sd（T）db）。

(T),为什么都是直接短语，是因为(T)，三个都是叶子节点，父亲节点S没有其他子树

d不是直接短语,因为d所在的树还有子树所以它不是 ！

#### 2) 短语，直接短语，句柄 ####

**给定句型：**

T\*P↑(T\*F)

**给定文法：**

> **G\[T\]:  
> T → T\*F|F  
> F → F↑P|P  
> P → (T)|i**

##### 解析： #####

**推导步骤为：**

T ⇒ T*F  
⇒ T*F↑P  
⇒ T*P↑P  
⇒ T*P↑(T)  
⇒ T*P↑(T*F)

**画出语法树为：**

![在这里插入图片描述][34cd015173c9a66544510c08f45a0c61.png]

**该语法树的 5 个子树及 5 个短语为：**

![在这里插入图片描述][470afb9ca68794c51e729339c09bc5bf.png]

**求直接短语方法：** 该句型的语法树有两颗直接子树（最左边的两颗子树），由这两颗直接子树的叶子结点组成的符号串（或者说只包含两层的子树叶子结点对应的），就是句型的两个直接短语，直接短语 P 和 T\*F。

**求句柄：** 因为 P 相对 T\*F，在语法树上的左侧，所以句柄是 P

**最终结果：**

#### 3) 素短语，最左素短语 ####

**给定句型：**

FF↑*a*

**给定文法：**

> **G\[T\]:  
> T → T\*F|F  
> F → F↑P|P  
> P → (T)|i**

##### 解析： #####

**推导步骤为：**

T ⇒ TF\*  
⇒ TF*F*  
⇒ TF↑\*\\F\*  
⇒ TF↑*a*

**画出语法树：**

![在这里插入图片描述][a4e2b2bea2ffab163fb4f61f383830e9.png]

**最终结果：**

根据定义可以找出素短语有：

<table> 
 <thead> 
 <tr> 
 <th>类型</th> 
 <th>内容</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>素短语 2 个</td> 
 <td>F↑，a</td> 
 </tr> 
 <tr> 
 <td>最左素短语</td> 
 <td>F↑</td> 
 </tr> 
 </tbody> 
</table>

### 2.5.2 二义性 ###

#### 1) 判断二义性文法 ####

依据：文法所能产生的句子，可以用不同的推导原则（使用产生式顺序不同）将其推导出来。如果文法是非二义性文法，那么语法树的生成规律不同，但最终生成的语法树形状完全相同；如果文法是二义性文法，那么最终生成的语法树形状有可能不相同。  
方法1：若对于一个文法的某一句子存在两棵不同的语法树（或两个不同的 **规范推导**）；或者自底向上看，对于同一个规范句型，存在两个不同的句柄。则该文法是二义性文法，否则是无二义性文法。  
方法2：即不改变二义性文法，而是确定一种**编译算法**，使该算法满足无二义性充分条件。  
**文法二义性的判定？？**：在理论上已经证明：**文法的二义性是不可判定的**，即不可能构造出一个算法，通过有限步骤来判定任一文法是否有二义性。解决方法：提出一些限制条件，称为无二义性的充分条件。当文法满足这些条件时，就可以判定文法是无二义性的。

#### 2) 子树与短语 ####

子树：子树由语法树中的某个结点（子树的根）连同它向下派生的部分所组成。  
关系：某子树的末端结点按自左向右顺序为句型中的符号串，则该符号串为该句型的相对于该子树根的短语。

#### 3) 规约 ####

自下而上地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次规约。  
**规范规约**：对句型中最左简单短语（句柄）进行的规约称为规范规约。  
*注*：规范规约与规范推导 **互为逆过程**。

**规范句型**：通过规范推导或规范规约所得到的句型称为规范句型。

[1]: /images/20221023/2419e325c0924da2b0714c09f1fff5b9.png
[9641381897ad001fe2581314b941795f.png]: /images/20221023/ecad599f53b345ac99dd457ac0435a80.png
[4088aa2b404071d2ac499c59143d96b5.png]: /images/20221023/96e28e0877f94e5f9b1d93553740bb6a.png
[5cb7bc51c5e59f0afa07e34ed58a9887.png]: /images/20221023/b28414f88151409880c84e4898699b57.png
[ca47bf3f842e097750f77d9559b5cab9.png]: /images/20221023/f4586e2426204975a3e1f48d880f1ca5.png
[dbc427c29cd1ceb8c5de6c6eb7420988.png]: /images/20221023/fd87bcb110184ba0ade908f54404728c.png
[image-20210129144134662]: /images/20221023/0c2565b8224540098029a7847449e932.png
[34cd015173c9a66544510c08f45a0c61.png]: /images/20221023/ce71b444f167432fbff6cdc86d580b93.png
[470afb9ca68794c51e729339c09bc5bf.png]: /images/20221023/0ae1eae901764e0ba5f0b60a995343fd.png
[a4e2b2bea2ffab163fb4f61f383830e9.png]: /images/20221023/6111c6c98ecd469fad2f82f89994c0b8.png