编译原理（三）语法分析：2.上下文无关文法CFG和上下文无关语言CFL

【编译原理博客列表】》》》》》》

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 简单算术表达式的上下文无关文法可表示如下：

约定：

当若干个产生式具有相同的左部非终结符时，可以将它们合并为一个产生式。 产生式以该非终结符命名。

例3.3 G3.1 P: E → E + E （1） E → E * E （2） E →（E） （3） E → -E （4） E → id （5）

重写为如下形式：

称其为E产生式

推到的定义将产生式左部的非终结符替换为右部的文法符号序列(展开产生式，用标记=>表示)，直到得到一个终结符序列。

推导的符号：=> 推导的输入：产生式左部 推导的输出：一个终结符序列

例3.4 用(G3.2)产生终结符序列-(id+id)可如下： E → E + E （1） | E * E （2） |（E） （3） (G3.2) | -E （4） | id （5）

定义3.2 利用产生式产生句子的过程中，将产生式A→γ的右部代替文法符号序列αAβ中的A得到αγβ的过程，称αAβ直接推导出αγβ，记作：αAβ=>αγβ。

根据推导的步数分类：

推导的特性：

定义3.3 由CFG G所产生的语言L(G)被定义为：L(G) = { ω|S=+>ω and ω∈T* }，L(G)称为上下文无关语言(Context Free Language, CFL)，ω称为句子。

解析： L(G)是由句子ω组成的集合，ω由CFG的开始符号S至少一步推导出的终结符T序列(ω是由终结符组成T的)。

若S=*>α，α∈(N∪T)*，则称α为G的一个句型。 若S=+>ω，ω∈T*，则称ω为G的一个句子。 句子∈句型

例子见下面的最左推导

定义3.4 在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为最左推导。 由最左推导产生的句型被称为左句型。

类似的可以定义最右推导（也叫规范推导）与右句型。

例子：最左推导

句型：αi都是 句子：α6

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

例3.11 从正规式r=(a|b)*abb的NFA构造CFG：

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

分析树是推导的图形表示

定义3.5 对CFG G的句型，分析树被定义为具有下述性质的一棵树。 （1） 根由开始符号所标记； （2） 每个叶子由一个终结符、非终结符、或ε标记； （3） 每个内部结点由一个非终结符标记； （4） 若A是某内部节点的标记，且X1，X2，…，Xn是该节点从左到右所有孩子的标记，则A→X1X2…Xn是一个产生式。若A→ε，则标记为A的结点可以仅有一个标记为ε的孩子。

最左推导和最右推导的中间过程对应的分析树可能不同，因为句型不同： -(id+E) 或 -(E+id) 但是最终的分析树相同，因为最终是同一个句子： -(id+id)

例3.5 再考察-(id+id)的推导过程。 E => -E => -(E) => -(E+E) => -(id+E) => -(id+id)

中间过程的分析树不同： 最终的分析树相同：

定义3.6 对CFG G的句型，表达式的语法树被定义为具有下述性质的一棵树: （1） 根与内部节点由表达式中的操作符标记； （2） 叶子由表达式中的操作数标记； （3）用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中。

例3.6 句子-(id+id)

例：句型if C then s1 else s2

实质上，语法树与分析树的最根本区别在于它们的内部节点（包括根节点）：