文章目录 一、CFG的定义1.定义3.12.产生式的读法3.终结符与非终结符书写上的区分4.产生式的缩写形式 二、CFG产生语言的基本方法：推导1.推导的定义2.上下文无关语言CFL3.句型和句子：4.最左推导和最右推导 三、正规式到CFG的转换四、分析树1.定义2.分析树与语言和文法的关系3.特性4.推导和分析树 五、语法树1.定义2.语法树与分析树的区别
【编译原理博客列表】》》》》》》
上下文无关文法CFG（Context Free Grammar）上下文无关语言CFL（Context Free Language） 一、CFG的定义 1.定义3.1
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），S∈N
【注意】
N是可以出现在产生式左边符号的集合，T是绝不出现在产生式左边符号的集合
例3.2 简单算术表达式的上下文无关文法可表示如下：
N = {E}T = {+，*，(，)，-，id}P:E → E + E（1）E → E * E（2）E →（E）（3）E → -E（4）E → id（5）S = {E} 2.产生式的读法 产生式中的记号→读作“定义为”或者“可导出”。“E → E + E”可用自然语言表述为“算术表达式定义为两个算术表达式相加”。
或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”。 3.终结符与非终结符书写上的区分 （一般用这个就行）用大小写区分： E → id用””区分：E → “id” E → E “+” E用<>区分：<E> → <E> + <E>
约定：
大写英文字母A、B、C表示非终结符；小写英文字母a、b、c表示终结符；小写希腊字母α、β、δ表示任意文法符号序列。 4.产生式的缩写形式
当若干个产生式具有相同的左部非终结符时，可以将它们合并为一个产生式。
产生式以该非终结符命名。
例3.3 G3.1
P: E → E + E （1）
E → E * E （2）
E →（E） （3）
E → -E （4）
E → id （5）
重写为如下形式：
E → E + E（1）| E * E（2） |（E）（3） | -E（4） | id（5）
称其为E产生式
二、CFG产生语言的基本方法：推导 1.推导的定义
推到的定义将产生式左部的非终结符替换为右部的文法符号序列(展开产生式，用标记=>表示)，直到得到一个终结符序列。
推导的符号：=>
推导的输入：产生式左部
推导的输出：一个终结符序列
例3.4 用(G3.2)产生终结符序列-(id+id)可如下：
E → E + E （1）
| E * E （2）
|（E） （3） (G3.2)
| -E （4）
| id （5）
E => -Eby(4) => -(E)by(3) => -(E+E)by(1) => -(id+E)by(5) => -(id+id)by(5)
定义3.2 利用产生式产生句子的过程中，将产生式A→γ的右部代替文法符号序列αAβ中的A得到αγβ的过程，称αAβ直接推导出αγβ，记作：αAβ=>αγβ。
根据推导的步数分类：
零步或多步推导（一个整体词语）：α1=*>αn
定义：对于任意文法符号序列α1，α2，…αn，均有α1=>α2=>…=>αn
其中α1=αn的情况为零步推导至少一步推导：α1=+>αn
定义：α1≠αn，即推导过程中至少使用一次产生式
推导的特性：
自反性： ∀ α \forall{α} ∀α，有α=*>α，即推导具有自反性；传递性：若α=*>β，β=*>γ，则α=*>γ，即推导具有传递性。 2.上下文无关语言CFL
定义3.3
由CFG G所产生的语言L(G)被定义为：L(G) = { ω|S=+>ω and ω∈T* }，L(G)称为上下文无关语言(Context Free Language, CFL)，ω称为句子。
解析：
L(G)是由句子ω组成的集合，ω由CFG的开始符号S至少一步推导出的终结符T序列(ω是由终结符组成T的)。
3.句型和句子：
若S=*>α，α∈(N∪T)*，则称α为G的一个句型。
若S=+>ω，ω∈T*，则称ω为G的一个句子。
句子∈句型
例子见下面的最左推导
4.最左推导和最右推导
定义3.4
在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为最左推导。
由最左推导产生的句型被称为左句型。
类似的可以定义最右推导（也叫规范推导）与右句型。
例子：最左推导
E => -E => -(E) => -(E+E) => -(id+E) => -(id+id) α1 α2 α3 α4 α5 α6
句型：αi都是
句子：α6
三、正规式到CFG的转换
从正规式到CFG的对应关系：
构造正规式的NFA；若0为初态，则A0为开始符号；对于move(i,a)=j，引入产生式Ai→aAj；对于move(i,ε)=j，引入产生式 Ai→Aj；若i是终态，则引入产生式Ai →ε。
例3.11 从正规式r=(a|b)*abb的NFA构造CFG：
A0 → aA0|bA0|aA1A1 → bA2A2 → bA3A3 → ε
推论3.1 正规式所描述的语言结构均可用CFG描述，反之不一定。
四、分析树
分析树是推导的图形表示
1.定义
定义3.5
对CFG G的句型，分析树被定义为具有下述性质的一棵树。
（1） 根由开始符号所标记；
（2） 每个叶子由一个终结符、非终结符、或ε标记；
（3） 每个内部结点由一个非终结符标记；
（4） 若A是某内部节点的标记，且X1，X2，…，Xn是该节点从左到右所有孩子的标记，则A→X1X2…Xn是一个产生式。若A→ε，则标记为A的结点可以仅有一个标记为ε的孩子。
2.分析树与语言和文法的关系 每一直接推导(每个产生式)，对应一棵仅有父子关系的子树，即产生式左部非终结符“长出”右部的孩子；分析树的叶子，从左到右构成G的一个句型。若叶子仅由终结符标记，则构成一个句子。 3.特性 越接近S的文法符号的优先级越低。最终分析树的形状，仅与文法有关，而与推导方法无关 4.推导和分析树
最左推导和最右推导的中间过程对应的分析树可能不同，因为句型不同： -(id+E) 或 -(E+id)
但是最终的分析树相同，因为最终是同一个句子： -(id+id)
例3.5 再考察-(id+id)的推导过程。 E => -E => -(E) => -(E+E) => -(id+E) => -(id+id)
中间过程的分析树不同：
最终的分析树相同：
五、语法树 1.定义
定义3.6
对CFG G的句型，表达式的语法树被定义为具有下述性质的一棵树:
（1） 根与内部节点由表达式中的操作符标记；
（2） 叶子由表达式中的操作数标记；
（3）用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中。
例3.6 句子-(id+id)
例：句型if C then s1 else s2
2.语法树与分析树的区别
实质上，语法树与分析树的最根本区别在于它们的内部节点（包括根节点）：
分析树的内部节点是非终结符，语法树的内部节点是操作符（运算符）；语法树中省略了反映分析过程的非终结符。