上次课内容回顾.pptVIP

3.2 上下文无关文法(CFG) CFG的定义与表示 上下文无关文法，Context Free Grammar，CFG 定义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）。 3.2 上下文无关文法(CFG) [例3.1] 简单算术表达式的上下文无关文法可表示如下： N = {E} T = {+，*，(，)，-，id} S = E P: E → E + E （1） E → E * E （2） E →（E） （3） E → -E （4） E → id （5） 产生式的一般读法 记号 → 读作“定义为”或者“可导出”。 “E → E + E” 表述为“算术表达式定义为两个算术表达式相加”；或者“一个算术表达式加上另一个算术表达式，仍然是一个算术表达式”。 3.2 上下文无关文法(CFG) 2.产生式表示也被称为巴克斯范式（Backus-Naur Form，BNF），其中→用::=表示 E ::=E + E | E * E | (E) | -E | id 3.2 上下文无关文法(CFG) 3.终结符与非终结符书写上的区分 (a) 用大小写区分： E → id (b) 用 区分： E → id E → E + E (c) 用 区分： E → E + E 教材约定：大写英文字母A、B、C表示非终结符； 小写英文字母a、b、c表示终结符； 小写希腊字母α、β、δ表示任意文法符号序列 3.2 上下文无关文法(CFG) 产生式的缩写形式 当多个产生式的左部非终结符相同时，可合并为一个产生式。新的产生式的左部是此非终结符，右部是所有原来右部的或运算（并集合）。 [例3.3] G3.1可以重写为如下形式： E → E + E （1） | E * E （2） |（E） （3） | -E （4） | id （5） 用“|”连接的每个右部称为一个候选项，具有平等的权利。 3.2 上下文无关文法(CFG) CFG产生语言的基本方法－推导 CFG（产生式）通过推导的方法产生语言。 通俗地讲，产生式产生语言的过程是从开始符号S开始，对产生式左部的非终结符反复地使用产生式：将产生式左部的非终结符替换为右部的文法符号序列（展开产生式，用标记=表示），直到得到一个终结符序列。 [例3.4] 用算术表达式的上下文无关文法产生终结符序列-(id+id)可如下： E → E + E （1） | E * E （2） |（E） （3） | -E （4） | id （5） 3.2 上下文无关文法(CFG) 定义3.2 利用产生式产生句子的过程中，将产生式A→γ的右部代替文法符号序列αAβ中的A得到αγβ的过程，称从αAβ直接推导出αγβ，记作：αAβ=αγβ。 若对于任意文法符号序列α1，α2，...αn，均有α1=α2=...=αn，则称此过程为零步或多步推导，记为： α1=*αn，其中α1=αn的情况为零步推导。 若α1≠αn，即推导过程中至少使用一次产生式，则称此过程为至少一步推导，记为：α1=+αn。 两点注意： ?α，有α=*α，即推导具有自反性； 若α=*β，β=*γ，则α=*γ，即推导具有传递性。 3.2 上下文无关文法(CFG) 定义3.3 由CFG G所产生的语言L(G)被定义为: L(G) = { ω┃S= + ω and ω∈T* }， L(G)称为上下文无关语言(Context Free Language, CFL)，ω称为句子。 若S=α*，α∈(N∪T)*，则称α为G的一个句型。 定义3.4 在推导过程中，若每次直接推导均替换句型中最左边的非终结符，则称为最左推导，由最左推导产生的句型被称为左句型。 类似可定义最右推导与右句型，最右推导也被称为规范推导。 E = -