【编译原理】高级语言及其语法描述

绝地灬酷狼 2022-06-16 05:48 1225阅读 0赞

# 高级语言及其语法描述 #

--------------------

*  高级语言及其语法描述
    
     *  程序语言的定义
        
         *  语法
         *  语义
     *  程序语言的语法描述
        
         *  基本概念
         *  符号串的运算
         *  符号串集合的运算
     *  文法和语言的形式定义
        
         *  基本相关概念
         *  文法的形式定义
         *  句型的分析
         *  语法树和文法的二义性
            
             *  语法树
             *  文法的二义性
         *  文法的化简和改造
            
             *  无用符号和无用产生式
             *  \-产生式的删除
                
                 *  不属于LG
                 *  属于LG
             *  单产生式的删除
         *  文法和语言的Chomsky分类
 *  习题和答案

--------------------

## 程序语言的定义 ##

20世纪50年代，语言学家Noam Chomsky（乔姆斯基）提出了一个用来描述语言的数学系统，把用一组数学符号和规则来描述语言的方式叫做形式描述，而把能用数学符号和规则描述的语言称为形式语言。  
形式化就是不关注符号本身含义，只关注符号之间的推导关系。  
形式描述：用一种数学符号和规则来描述语言的方式。  
形式语言：把用来描述语言的数学符号和规则称为形式语言。  
这种理论对程序设计语言的设计和编译程序的构造有着重大的作用。程序设计语言就是形式语言。

### 语法 ###

任何语言程序都可以看作是一定字符集（称为字母表）上的一字符串（有限序列）。  
所谓一个语言的语法是指这样一组规则，用它可以形成和产生一个合式的程序。这些规则的一部分被称为词法规则，另一部分被称为语法规则（或产生规则）。

1.  词法规则：单词符号的形成规则。也就是规定了字母表中哪些字符串是一个单词符号。  
    理论基础：正规式和有限自动机理论
2.  语法规则：是语法单位的形成规则。也就是规定了如何从单词符号形成更大的语法单位。  
    理论基础：上下文无关文法和有限自动机

### 语义 ###

所谓一个语言的语义是指这样一组规则，使用它可以定义一个程序的意义。这些规则称为语义规则。  
语义：可以定义程序意义的规则。语言离开语义就只是一堆符号的集合。  
理论基础：语法制导翻译方法

## 程序语言的语法描述 ##

### 基本概念 ###

字母表：字母表Σ是有穷符号元素的非空集合。也可称为“符号集”。  
符号：字母表中的元素。典型的符号有字母、数字、各种标点符号和各种运算符。  
符号串：字母表中的符号所组成的任意有穷序列。注意：符号串中的符号与顺序有关（01 和 10 不同的符号串）。  
空符号串：不含任何符号的符号串， 用 ε 表示。

例如，集合\{a，b，c，+，\*\}是一个含有5个符号的字母表，而字母表\{0，1\}只有2个符号。  
例如，有字母表\{a，b，c，+，*\}，则a,b,c,+,*,aa,ab,ac,a+,a\*,ba,bb,bc,b+,b\*,aaa,bbb等等都是该字母表上的符号串。  
而所有二进制数都是定义在字母表\{0，1\}上的符号串。  
显然，一个字母表上的全部符号串所组成的集合是无穷的。

符号串的长度：指符号串x中所含符号的个数，记为|x|。 如：|abc|=3，|abc+\*abc|=8，**|ε|=0**。  
符号串的前缀：指从符号串x的末尾删除0或多个符号后得到的符号串，如ε 、 a、ab、abc都是abc的前缀。  
符号串的后缀：指从符号串x的开头删除0或多个符号后得到的符号串，如ε 、 c、bc、abc都是abc的后缀。  
符号串的子串：指从符号串x的开头和末尾删除0或多个符号后得到的符号串，如abc的子串为ε 、 a 、b 、c 、ab 、bc 、abc。 符号串的前缀、后缀都是它的子串。

### 符号串的运算 ###

符号串的连接：若x、y是两个符号串，则xy表示连接，是将符号串y连接在符号串x的后面。若x、y是字母表∑上的两个符号串，则xy也是字母表∑上的符号串。 如： x=ab，y=ba，那么 xy=abba。

> 注意：  
> 连接没有交换律，即 xy ≠ yx  
> 对于空串ε有 εx=x ε=x

符号串的方幂：一个符号串x与其自身的n-1次连接称为x的n次方幂，即：x0=ε, x1=x , x2=xx ,…，xn=xx…x=xxn-1=xn-1x。如：x=abc, x0= ε, x1=abc, x2=abcabc,…。

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

> 特别定义：  
> 空符号串：ε，表示不含任何符号的符号串  
> 空符号集合：\{ε\}，集合里面有一个元素为ε  
> 空集合：φ=\{ \}，集合里面是空的  
> 注意：  
> εx = xε  
> \{ε\}A=A\{ε\}=A  
> Aφ= φA= φ

符号串集合的乘积：令A、B为两个符号串集合，A和B的乘积AB定义为：  
AB=\{xy|x∈ A ，y ∈ B\}（笛卡儿乘积）。  
例如：A=\{a，b\} B=\{c，d\}，则AB=\{ac，ad，bc，bd\}  
对于\{ε\}有： \{ε\}A=A \{ε\}=A

符号串集合的方幂：设A为符号串集合，则A的方幂定义为：  
A0=\{ε\}，A1=A，A2=AA…… An=AA…A=AAn-1 =An-1A  
例如：A=\{a，b，c\}  
A0=\{ε\}  
A1==\{a，b，c\}  
A2=AA=\{aa ，ab ，ac ，ba ，bb ，bc ，ca ，cb ，cc\}……

符号串集合的闭包：设A为一个集合，则集合A的正闭包用A\+表示，定义为：  
A\+ =A1∪A2∪….∪An∪…=⋃i=1∞Ai  
集合A的闭包用A\*表示，定义为：  
A\*=A0∪A\+=\{ε\}∪A\+  
例如：A ==\{a，b ，c\}，则  
A+ =\{a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,…\}  
A\* =\{ε,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,…\}  
可见，字母表A的正闭包A\+就是由A中字母所构成的一切符号串的集合，而A\*仅比A\+多个ε。

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

从“产生语言”的角度出发，给出方法和语言的形式定义。  
产生语言：指制定出有限个规则，借助这些规则可以产生此语言的全部句子。  
在学习英语时，我们知道句子由主语、谓语组成，主语由冠词、形容词及名词组成等等，这就是说明句子组成的规则。而在形式语言里，这种规则可采用“<句子>::=<主语><谓语>”、“<主语>::=<冠词><形容词><名词>”这种形式来表示。分析一个句子是否正确，就是根据这些规则进行的。实际上，文法就是描述语言语法结构的形式规则（即语法规则）。

### 基本相关概念 ###

文法(Grammar)：是描述语言的语法结构的形式规则。  
语法树(Parse Tree)：句子结构的图形表示方式。类似下图：  
![这里写图片描述][SouthEast]  
规则：规则又叫产生式(production rule)，它是句子结构的另一种表示结构，它引入了符号“::=”或“→”表示“由……组成”，上述句子的结构可以表示如下：

<句子> → <主语> <谓语>
    <主语> → <冠词> <形容词> <名词>
    <冠词> → the
    <形容词> → big
    <谓词> → <动词> <直接宾语>
    <动词> → ate
    <直接宾语> → <冠词> <名词>
    <名词> → elephant
    <名词> → peanut

句子的推导：用规则(产生式)按一定方式去推导或产生句子的过程。

<句子> ⇒<主语><谓语>
          ⇒<冠词> <形容词> <名词> <谓语>
          ⇒ The <形容词> <名词> <谓语>
          ⇒ The big <名词> <谓语>
          ⇒ The big  elephant <谓语>
          ⇒ The big  elephant <动词> <直接宾语>
          ⇒ The big  elephant ate <直接宾语>
          ⇒ The big  elephant ate <冠词><名词>
          ⇒ The big  elephant ate the <名词>
          ⇒ The big  elephant ate the peanut

或者  
<句子>⇒\+The big elephant ate the peanut

> 注意：  
> ⇒：代表一步推导  
> ⇒\+：代表多步推导

文法的EBNF表示：所谓文法的EBNF表示，就是在书写文法的规则时，可采用一些特殊的符号“|”、“\{”和“\}”、 “（” 和“）”、“\[” 和“\]”来表示文法，这些符号叫做元符号。其中“\{”和“\}”、 “（” 和“）”、“\[” 和“\]”这些元符号总是成对出现。  
1. 元符号“|”：表示“或”.对于具有相同左部的那些规则，如α → β 1、 α→β 2、…、 α→β n，  
可以缩写为：α → β 1 | β 2 | … | β n 。  
2. 元符号“\{”和“\}”：表示可重复连接，\{ t\}mn表示符号串t可重复连接n到m次，而\{ t\}表示符号串t可重复连接0到无穷次。  
例如，<无符号整数>→\{ <数字>\}31  
与<无符号整数>→<数字>|<数字><数字>|<数字><数字><数字>相同  
E→E+T|T 与 E→T\{+T\} 相同  
而字母打头、后面可跟数字或字母的不超过8个字符的标识符文法则为：  
<标识符>→<字母>\{ <字母>|<数字>\}70

3.元符号“\[”和“\] ”：表示括起的内容可有可无。如\[t\]表示符号串t可有可无。  
例如：

<IF语句>→IF <布尔表达式> THEN <语句>
    <IF语句>→IF <布尔表达式> THEN <语句> ELSE <语句> 可写成：
    <IF语句>→IF <布尔表达式> THEN <语句> [ELSE <语句>]

4.元符号“（”和“）”：表示括号内的成分优先。常用于在规则中提取公因子。  
例如，U→xy | xw | …… | xz 可写成：U→x（y | w | …… | z）

### 文法的形式定义 ###

定义1： 产生式(或规则)是一有序对(A, α)，通常写为：  
A→ α或 A∷= α 其中A是一个符号作为产生式左部，α为有穷符号串作为产生式的右部，“→”或“∷=”表示“定义为…”或“由…组成“。

定义2：文法是一个四元组：G\[S\]=(VN, VT, P, S)，其中：  
VN是一个非空有穷集合，该集合中的每个元素称为**非终结符号**。如上例中VN=\{<句子>、<主语>、<谓语>、<直接宾语>、<名词>、<动词>、<冠词>\}  
VT是一个非空有穷集合，该集合中的每个元素称为**终结符号**。如上例中VT=\{monkey、banana、ate、has、the、a\}

并且VN∩VT=φ，而Ｖ＝VN∪VT称为该文法的字汇表。  
P是一个非空的有穷集合，它的每个元素叫做产生式或规则。产生式的形式为：α→β或α::=β  
α是产生式的左部且不能为空，β是产生式的右部，并且α、β∈V。  
S是VN集合的一个特殊的非终结符号，称为文法的**开始符号**。它至少必须在某个产生式的左部出现一次。<句子>就是上例文法的识别符号。

定义3 ：符号串的推导与归约：已给文法G=(VN,VT,P,S)，V= VN∪VT，令x,y,α,β∈V\*，且α→β∈P，此时，由  
符号串xαy能够直接产生出符号串xβy，我们称：  
符号串xβy是符号串xαy的直接推导；  
符号串xαy是符号串xβy的直接归约；  
记作: xαy ⇒ xβy  
例如有文法  
1. <无符号整数> → <数字串>  
2. <数字串> → <数字串><数字>|<数字>  
3. <数字> → 0|1|2|3|4|5|6|7|8|9  
对符号串<无符号整数>利用规则1可直接推导出<数字串>：<无符号整数> => <数字串>  
对符号串<数字串>利用规则2可直接推导出<数字串><数字>：<数字串> => <数字串><数字>  
对符号串<数字串><数字>利用规则3可直接推导出<数字串>2：<数字串><数字> => <数字串>2  
将上述三个推导连接起来，可得如下推导过程：<无符号整数> => <数字串> => <数字串><数字> => <数字串>2

若有α1,α2,…,αn∈V\* 且α1 ⇒ α2 ⇒ … ⇒ αn-1 ⇒ αn 。则称αn是α1的推导。记作：α1 ⇒\+ αn 。  
特别约定：若在推导关系α1 ⇒\+ αn 中允许α1= αn，则称 αn 是 1 的广义推导。记作：α1 ⇒∗ αn 。

定义4： 句型和句子：设G=(VN，VT，P，S)是一文法，  
若 S ⇒∗ α，α∈V∗，则称α为文法G的句型。  
若 S ⇒∗ α，α∈V∗T，则称α为文法G的句子。

句型是从识别符号开始经过0步或多步推导出的可由终结符号和非终结符号组成的符号串而句子是从文法的识别符号推导出的完全由终结符号组成的符号串。句子是特殊的句型，是完全由终结符号组成的句型。从文法的开始符号利用规则进行推导，一旦推导出句子，推导过程就不能再继续进行，因为句子中没有非终结符号。假设符号串ｘ是某一推导的结果，那么，ｘ是句子的必要条件是从S到ｘ的推导长度大于等于１，即 S ⇒\+ x,而不可能是S ⇒∗ x。这是因为识别符号S是非终结符号，而ｘ是终结符号串，显然，S不可能与ｘ相等，所以S不可能经过０步推导就等于ｘ。

文法G所对应的语言，记作L(G)=\{ω|ω∈V∗T，且S ⇒\+ ω\} 。  
语言是所有句子构成的集合，它是所有终结符号串所组成的集合V∗T的子集，即L(G) ⊆ V∗T

定义5：规范推导(归约)：对于直接推导xαy ⇒ xβy，如果y只包含终结符号或为空符号串，那么就把这种直接推导称为规范(最右)推导，跟其对应的归约称为规范(最左)归约，且记作：  
xαy ⇒r xβy 。即：每次对符号串中最右非终结符号进行替换。  
每一个句子都有一个规范推导,但并非每一个句型都有规范推导，只有那些能用规范推导产生的句型才是规范句型。

形式语言理论可以证明以下两点：  
1. 给定一个文法G，就可以从结构上唯一地确定其语言：G ⇒ L(G)  
2. 给定一种语言L，能确定其文法，但这种文法可能不是唯一的： L ⇒G1或G2  
定义6 ：等价文法：如果L(G1)=L(G2) ，那么称G1和G2为等价文法。

定义7： 递归产生式和递归文法：设给定文法G=(VN，VT，P，S)  
若存在产生式A→α∈P 且有 A ⇒\+ xAy成立，则称产生式A→α是递归产生式；  
若x=ε且y≠ε,则称产生式A→α是左递归产生式；B →Bb  
若x≠ε且y=ε,则称产生式A→α是右递归产生式。B →bB  
递归文法：若文法中至少存在一条显式递归产生式则称该文法是直接递归的文法；  
若有A ⇒\+ xAy, 或 A ⇒\+ Ay，或者A ⇒\+ xA，则称文法为间接递归的文法。  
可见，对于文法中任一非终结符号，若能建立一个推导过程，在推导所得的符号串中又出现了该非终结符号本身，则文法是递归的。应当注意，一般的文法都是递归的，文法G只有递归定义，L(G)中句子才是无穷的 。  
总之，使用递归文法，可用有穷的产生式来描述无穷的语言，反之，一个语言若是无穷的，则描述语言的文法必定是递归的。(程序设计语言一般是无穷的)。

定义8：短语、简单短语和句柄  
设文法G=(VN，VT，P，S) ，且 U ∈ VN，x,y,u ∈ V∗  
1. 若有S ⇒∗ xUy ⇒\+ xuy，则称u为句型xuy相对于U的短语。  
2. 若有S ⇒∗ xUy ⇒ xuy，则称u为句型xuy相对于U的简单（直接）短语。  
3. 任意句型的最左简单短语称为该句型的句柄（即规范分析中，最先被规约的子串）。

> 说明：当句型有两个以上的简单短语同时存在时，我们把位于最左边的那个简单短语称为“最左简单  
> 短语”，即该句型的句柄；若句型只有一个简单短语，那么，它就是最左简单短语，即句柄。

### 句型的分析 ###

所谓句型的分析，是指构造一种算法，用以判定给定的符号串是否为某一文法的句型（或句子）。  
通常，句型分析的方法可大致分为两类，即自顶向下的分析和自底向上的分析。前者是从文法的开始符号出发，以给定的符号串为目标，试图推导出此符号串；后者恰好和前者相反，它从给定的符号串出发，反复用文法中规则的左部去替换当前符号串中的相应子串，以期最后“归约”到文法的开始符号。这与分析过程中构造句型相应语法树的方向有关。  
采用自底向上的语法分析时，每按一个产生式进行一次归约，就用该产生式的左部去替换当前句型中的子串。从语法树的角度来看，就是把该句型的语法树的一棵直接子树的末端节点剪去。换言之，语法分析每次所归约的符号串必然是当前句型的某一直接短语。但是，由于一个句型中的直接短语可能不止一个，故为了使语法分析按一种确定的方式来进行，通常我们只考虑最左归约即规范归约。

### 语法树和文法的二义性 ###

#### 语法树 ####

语法树: 设文法G=(VN，VT，P，S) ，所谓语法树是一张图，这张图表示一个句型的推导过程。语法树结构是一棵倒立的树结构，语法树是一棵有序有向树，每个节点都有标记。根节点代表文法的识别符号；每个内部节点（非叶节点）表示一个非终结符号，其子节点由这个非终结符号在这次推导中所用产生式的右部各个符号代表的节点组成；每个末端节点（叶节点）代表终结符号或非终结符号，它们从左向右排列起来，构成句型。如果叶节点都是终结符号，则从左向右构成句子。推导过程不同，生成语法树的过程也不同，但最终生成的语法树是相同的。

例：文法G[E]：E→E+T│T
                T→T*F│F
                F→(E)│i 
    句型E+F*i对应的语法树。

![这里写图片描述][SouthEast 1]

子树：由语法树的某个结点（子树的根）连同它下面射出的部分组成语法树的子树。只含有单层分支的子树为简单子树或直接子树。  
子树与短语：在句型所对应的语法树中，若某些符号按从左到右的顺序组成某棵子树的末端结点，那么由这些末端结点所组成的符号串是相对于子树根结点的短语。原则上语法树有多少棵子树，就有多少个短语。  
![这里写图片描述][SouthEast 2]  
虚线圈住的都是子树，蓝色的是简单子树。

文法G[S]：S →aAcBe
             A →b | Ab
             B →d
    求句型abbcde的短语，直接短语和句柄。

语法树：  
![这里写图片描述][SouthEast 3]

b是句型abbcde相对于A的短语
    bb是句型abbcde相对于A的短语
    d是句型abbcde相对于B的短语
    abbcde是句型abbcde相对于S的短语
    b是句型abbcde相对于A的直接短语
    d是句型abbcde相对于B的直接短语
    b是句柄

#### 文法的二义性 ####

文法的二义性：若一个文法存在某个句子对应两棵不同的语法树，则称此文法是二义性文法。

例：文法G[E]：E→E+E | E*E | (E) | i
    试为符号串E*E+i构造语法树.

![这里写图片描述][SouthEast 4]  
明显两个语法树都可以表示符号串E\*E+i，但是表示的含义并不相同，左边的语法树表示先先乘后加，而右边的语法树表示先加后乘。这就产生了二义性。文法是二义性的。在进行语法分析时通过人工干预(规定算符的优先级)，确定归约(分析)顺序。

文法的二义性是不可判定的，即不存在一种算法，它能够在有限步内判定一个文法是否是二义性的。若一个文法G含有既是左递归又是右递归的非终结符号A，即有A ⇒ A u A，u ∈ V∗或A ⇒ A 或A ⇒ A α 及 A ⇒ β A ，则G必定是二义性文法。

### 文法的化简和改造 ###

1.  无用符号和无用产生式的删除。
2.  ε-产生式的删除。
3.  单产生式的删除。

#### 无用符号和无用产生式 ####

设G是一文法，我们说G中一符号X是有用的，是指X至少出现在一个句子的推导过程中，即X必须同时满足以下两个条件：  
1. X必须在某个句型中出现，即存在α，β ∈ V∗，有S ⇒∗ αXβ  
2. 必须能够从X推导出终结符号串，即存在w∈V∗T ，使 αXβ ⇒∗ w，否则就说X是无用的。  
3. 含有无用符号的产生式称为无用产生式。

以下算法用来将文法G=(VN，VT，P，S)改造为等价的文法G1=(VN1，VT，P1，S)，使得对于每个X∈VN1,都有w1 ∈ V∗T，满足X ⇒∗ w1。（满足上述条件2）

**算法①：**  
1. 分别置VN1，P1为空；  
2. 对于P中的每一产生式A → α，若α ∈ V∗T，则将A置于VN1中；  
3. 对于P中的每一产生式A →X1X2…Xm，若每一个Xi都属于VT或VN1，则将A置于VN1中；  
4. 重复步骤3，直到VN1不再增大为止；  
5. 对于P中的每一产生式B →Y1Y2…Yn，若B及每一个Yi都属于VT或VN1，则将此产生式置于 P1中。

对于给定的文法G，若执行以下算法，便能得到一等价的文法G′=(V′N，V′T，P′，S)，使得对于每个X∈V′N ∪ V′T，都存在α，β ∈ （ V′N ∪ V′T）\* ，有S ⇒∗ αXβ 。（满足上述条件1）

**算法②：**  
1. 分别置V′N，V′T，P′为空；  
2. 将文法G的开始符号S置于V′N中；  
3. 对于G中任何形如A →α1∣α2∣…∣αm的产生式，若A属于V′N ，则将符号串α1，α2，…，αm中的全部非终结符置于V′N中，而将其中的全部终结符置于V′T中；  
4. 重复步骤3，直到V′N和V′T都不再增大为止；  
5. 将P中左右部仅含V′N∪V′T中的符号的所有产生式置于P′中。

例如，对于文法G=({S,U,V,W}, {
       a ,b ,c}, P, S) 
    其中，P为    S → a S    S→W     S→U U →a
                V →b V     V →ac   W →a W
    对G执行算法①步骤如下：
    由于U →a及V →ac，故 Vn1＝｛U,V｝;
    对于产生式S→U ，由于U∈Vn1，故 Vn1＝｛S,U,V｝;
    Vn1不再增大；
    G１=({S,U,V}, {
       a ,b ,c}, P１, S) 
    其中，P1为　　S → a S S→U U →a
                V →b V     V →ac
    再对G1执行算法②步骤如下：
    置Vn′={S};
    由于S→U及U →a，故Vn′={S,U}， Vt′={
       a};
    Vn′及 Vt′不再增大;
    G ′=({S,U}, {
       a}, P′, S) 
    其中， P′为 　S → a S   S→U      U →a

> 如果要使用这两个算法进行无用产生式的消除，先后顺序一定不能颠倒。

#### ε-产生式的删除 ####

所谓ε-产生式，是指右部为一空符号串ε的产生式。  
如果一个语言L(G)中不含有ε，则可以消除全部ε-产生式；而当ε∈L(G)时，G中的ε-产生式不能全部消除。因此，为了判断一个语言L(G)中是否含有ε，同时也为了构造消除ε-产生式算法的需要，我们首先给出算法③，该算法能够找出所有能导出空串ε(即满足A ⇒∗ ε)的非终结符号A。

**算法③：**  
1. 作集合W1 =\{A∣A →ε ∈P\}  
2. 作集合序列 Wk\+1=Wk ∪ \{B → β ∈P，且 β ∈Wk\} 对于此集合序列，必存在一个i，使Wi=Wi\+1=Wi\+2=…若令W=Wi，则对每一个A ∈W，有A ⇒∗ ε。特别，当S∈W时，则ε∈L(G)；否则ε ∉ L(G)。

ε-产生式的删除分为两种情况：  
1. ε不属于L(G)  
2. ε属于L(G)

##### ε不属于L(G) #####

设G=(VN，VT，P，S)是一文法，则可按下述算法构造一文法G′=(VN，VT，P′，S)，使L(G′)=L(G)，且G′中不含任何ε-产生式。  
**算法④：**  
1. 按算法③求出集合W。  
2. 设A →X1X2…Xm是P中任一产生式，按如下规则将形如A →Y1Y2…Ym的产生式放入P′中，对于一切1≤i≤m：

1.  若Xi ∉ W，则取Yi=Xi;
2.  若Xi ∈W，则分别取Yi为Xi和ε，即如果X1X2…Xm中有j个符号属于W，1≤j≤m，则将有2j个形如A →Y1Y2…Ym的产生式放入P′中，但若所有的Xi均属于W，则不能把所有的Yi都取为ε。

例如，设有文法G=({S,A,B,C}, {
       a, b, c}, P, S)
    其中，P为    S→ a A     A →BC       B →b B
                C →c C     B → ε      C → ε
    对G执行算法③有W={
       A,B,C};
    再对G执行算法④有P′:
    S→ a A      S→ a        A →BC       A →B        A →C 
    B →b B      B →b        C →c C      C →c

##### ε属于L(G) #####

**算法⑤：**  
如果在原文法中，开始符号S不出现在任何产生式的右边，则可直接执行算法④得到P′，令P1= P′∪ \{ S →ε \}，VN1=VN，S1=S，则G1=(VN1，VT，P1，S1)即为所求之文法。  
但若文法的开始符号S出现在某些产生式的右边，则  
1. 引入新的符号S1作为前面算法④中G′的开始符号，并令VN1=VN∪ \{ S1\}；  
2. 作产生式集P′=P ∪ \{ S1 →α∣ S →α∈ P\}  
3. 对文法G′=(VN1，VT，P′，S1)执行算法④，同理，再添加产生式S1 →ε得到P1 。

例如，设有文法G=({S,A,B,}, {
       a, b, c}, P, S)
    其中，P为    S→ c S     S →AB       A →a A b
                B →B b     A → ε      B → ε
    引入新的符号S1；
    作产生式集P′=P∪{S1 →c S,S1 →AB}
    执行算法④并加入产生式S1 →ε得到P1
    S1→ c S        S1→ c       S1→AB       S1 →A        S1 →B      S1 →ε
    S→ c S         S→ c        S→AB        S→A          S→B 
    A→ a A b       A→ a b
    B →B b         B →b

#### 单产生式的删除 ####

右部仅含一个非终结符号的产生式，即形如A→B(A,B∈Vn)的产生式称为单产生式。  
**算法⑥：**  
1. 设Vn=\{A1,A2,…An\}，对于每个Ai（1≤i≤n）作集合序列W1(Ai)=\{Ai\}  
Wk+1(Ai)=Wk(Ai) ∪\{ D∣C→D∈P，C ∈Wk(Ai)，D ∈Vn\} (k≥1)  
则必存在一个j，使Wj(Ai)=Wj+1(Ai)=…  
令Wi=Wj(Ai)  
即Wi=\{ B ∣Ai =\*> B, B ∈Vn \}  
2. 构造产生式集P′= ⋃i=1n\{Ai→α∣B→α∈P，B ∈Wi，α ∉ Vn\}

例如，设有文法G=({S,A,B,}, {
       a, b}, P, S)
    其中，P为    S →AB       S →A         S →B        A →a A b
                A → a b      B →B b      B → b
    W(S)={S,A,B}             W(A)={
       A}               W(B)={B}
    P′={S →AB，S →a A b，S → a b，S →B b ，S → b} ∪{
       A →a A b，A → a b } ∪{B →B b，B → b}

### 文法和语言的Chomsky分类 ###

著名的语言学家乔姆斯基在1956年对形式语言进行了定义。他把文法定义为四元组：  
G=（Vn，Vt，P，S）  
其中：  
Vn为非终结符号集合 ， Vt为终结符号集合且Vt∈V，P为有穷规则集合，S识别符号（开始符号），且S∈Vn。  
文法所描述的语言为：L（G）=\{x|x∈V\+t，S ⇒∗x\}  
根据文法中的规则的形式，可定义如下四类文法和相应的四种形式语言：  
1. 0型文法（PSG）  
若文法中有如下形式的规则：α→β ，其中α∈ V\+ ，β∈V∗ ，V= Vn∪Vt  
即规则左部α可以是符号集合V上的符号串但不能为空，而规则右部β也是V上的符号串，可以是空。  
例如 ： aSb→cAd  
0型文法描述的语言为0型语言，用L0表示。  
2. 1型文法(CSG)  
若文法中有如下形式的规则：αUβ→αuβ，其中 U∈Vn，α、β∈V∗， u ∈V\+ ，V= Vn∪Vt  
即规则左部可为符号串，其中U为非终结符号且只有在左右为α和β的环境下U可变为u。因为规则中的α和β不发生变化，所以这种文法也叫**上下文有关文法**。  
例如：aUb→aABBaab  
1型文法描述的语言为1型语言，用L1表示。  
3. 2型文法(CFG)  
若文法中的规则都具有如下形式：U→u，其中 U∈ Vn ， u∈ V∗， V= Vn∪Vt  
2型文法中的规则左部只有一个非终结符号，规则右部u是V上的符号串。该文法相当于对1型文法中的规则形式加以限制，即要求α和β必须为空。2型文法也称作**上下文无关文法**，描述的语言为2型语言，用L2表示。2型文法是描述程序设计语言语法部分的主要文法。  
4. 3型文法  
若文法中的规则都具有如下形式：A→ α 或A → B α （左线性）或 A→ α B（右线性）  
其中 A，B∈ Vn， α ∈ V\+t  
规则右部至多含有一个非终结符号。也称线性文法、正则文法或正规文法。  
3型文法描述的语言为3型语言（正则语言、正规语言），用L3表示。大多数程序设计语言的单词 (标识符、无符号整数) 的文法都是3型文法。

在上述四类文法中，从0型到3型文法对规则的限制逐渐增加，产生的语言类却逐步缩小，即0型语言包含1型语言，1型语言包含2型语言，2型语言包含3型语言。因此，可以说3型文法是2型文法的特例，2型文法是1型文法的特例，1型文法又是0型文法的特例。

# 习题和答案 #

1.文法G1定义的语言

G1: S→bA
         A→aA | a
    
    L(G1)={ban|n≥1}

2.文法G2定义的语言

G2: S→AB
        A→aA | a
        B→bB | b
    L(G2)={ambn|m,n≥1}

3.构造一个文法G3使L(G3)=\{anbn|n≥1\}

G3: S→aSb | ab

4.有文法G \[S\]是否是递归文法，确定什么语言？

S →aB | bB
    B →a | b
    
    非递归文法，L(G[S])={aa,ab,ba,bb}

5.有文法G<无符号整数>是否为递归文法，  
确定的语言是什么？

<无符号整数> →<数字串>
    <数字串> →<数字串><数字> |<数字>
    <数字> →0 |1 |2 |3 |4 |5 |6 |7 |8 |9|
    
    递归文法， L(G)=VT*，所有无符号整数。

6.L(G)=\{ wewR | w∈\{a,b\}\*, wR为w的逆串\}，试构造产生该语言的文法。

G[S]: S →aSa | bSb | e

7.L(G)=\{ anbmcp |n,m,p≥0\},试构造产生该语言的文法。

G[S]:   S →ABC
            A →aA | ε
            B →bB | ε
            C →cC | ε

8.L(G)=\{ anbnci |n,i≥1\},试构造产生该语言的文法。

G[S]:   S →AC
            A →aAb | ab
            C → cC | c

9.该文法产生的语言是什么？

G[S]:S→AB
         A→aA | ε
         B→bBc | bc

L(G)=\{ ambncn|m≥0,n≥1\}

[SouthEast]: /images/20220616/3c251df5c04d4bee8c7311c777f155f1.png
[SouthEast 1]: /images/20220616/0ef385e2fb054453b66924967b115e01.png
[SouthEast 2]: /images/20220616/53b95e30666540938598ad4c414ab5cb.png
[SouthEast 3]: /images/20220616/ae7155a69b0840cc90bcefafd77866b4.png
[SouthEast 4]: /images/20220616/11d67993f1a642428cc66c334db3c4b7.png