32上下文无关文法CFG) 定义32利用产生式产生句子的过程中,将产生式A→y的右部 代替文法符号序列αAβ中的A得到ayβ的过程,称αAβ直接推 导出Yβ,记作:aAβ→>ayβ 若对于任意文法符号序列a1,Q2,….n,均有a1=>02>.→>n, 则称此过程为零步或多步推导,记为: a1=*>n,其中a1=an的情况为零步推导。 若α1n,即推导过程中至少使用一次产生式,则称此过程为 至少一步推导,记为:al=+>ano 两点注意: ,有0*,即推导具有自反性; ※若Q=*>β,β=*>Y,则α=*>Y,即推导具有传递性
7 3.2 上下文无关文法(CFG) 定义3.2 利用产生式产生句子的过程中，将产生式A→γ的右部 代替文法符号序列αAβ中的A得到αγβ的过程，称αAβ直接推 导出αγβ，记作：αAβ=>αγβ。 若对于任意文法符号序列α1，α2，...αn，均有α1=>α2=>...=>αn， 则称此过程为零步或多步推导，记为： α1=*>αn，其中α1=αn的情况为零步推导。 若α1≠αn，即推导过程中至少使用一次产生式，则称此过程为 至少一步推导，记为：α1= +>αn。 两点注意： α，有α=*>α，即推导具有自反性； 若α=*>β，β=*>γ，则α=*>γ，即推导具有传递性
32上下文无关文法(CFG) 定义33由CFGG所产生的语言L(G)被定义为 L(G=O S=+>0 and OET*i, C、L(G称为上下文无关语言( Context Free Language, ),O称为句子。 若S=*>0,α∈(NUT)*,则称α为G的一个句型。 定义34在推导过程中,若每次直接推导均替换句型中最左边 的非终结符,则称为最左推导,由最左推导产生的句型被称 为左句型。 类似可定义最右推导与右句型,最右推导也被称为规范推导 E→>→>(E)→>E+E)→>-(id+E)→>-(id+id) a1 a2 a3 04 05 06 06是句子,所有ai(i=1.6)均是句型
8 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 => -E => -(E) => -(E+E) => -(id+E) => -(id+id) α1 α2 α3 α4 α5 α6 α6是句子，所有αi (i=1...6)均是句型
语言与文法简介
语言与文法简介
33语言与文法简介 ⑦正规式与上下文无关文法 1.正规式到CFG的转换 推论3.1正规式描述的语言结构均可用CFG描述,反之不一定 从正规式到CFG的对应关系: ①构造正规式的NFA; ②若0为初态,则AO为开始符号; ③对于move(ia),引入产生式Ai→aAj; 经验的方法: ④对于move(i;l),引入产生式Ai→Aj; A→HT ⑤若是终态,则引入产生式Ai→E。 H→E|HaHb [例3.1从正规式=ab)*ab的NFA构造CFG:T→ab A0→aAO| bANaL A1→bA2 b b 0 A2→bA3 A3→￡
10 3.3 语言与文法简介 正规式与上下文无关文法 1. 正规式到CFG的转换 推论3.1 正规式描述的语言结构均可用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|aA1 A1 → bA2 A2 → bA3 A3 → ε 经验的方法： A → HT H →ε| Ha | Hb T → abb 0 1 2 3 a b b a b
33语言与文法简介 2.为什么用正规式而不用CFG描述词法? ①词法规则简单,用正规式描述已足够; ②正规式的表示比CFG更直观、简洁、易于理解; ③有限自动机的构造比下推自动机简单,且分析效率高 ④区分词法和语法,为编译器前端的模块划分提供方便。 贯穿词法分析和语法分析始终的思想: ①语言的描述和语言的识别是表示一个语言的两个不同侧面, 二者缺一不可;(语言、文法、自动机) ②用正规式和CFG描述的语言,对应的识别方法(自动机) 不同 ③正规式适合描述线性结构,如标识符、关键字、注释等; CFG适合描述具有嵌套(层次)性质的非线性结构,如不 同结构的句子 if-then-else、 while-do等
11 3.3 语言与文法简介 2. 为什么用正规式而不用CFG描述词法？ ① 词法规则简单，用正规式描述已足够； ② 正规式的表示比CFG更直观、简洁、易于理解； ③ 有限自动机的构造比下推自动机简单，且分析效率高； ④ 区分词法和语法，为编译器前端的模块划分提供方便。 贯穿词法分析和语法分析始终的思想： ① 语言的描述和语言的识别是表示一个语言的两个不同侧面， 二者缺一不可；（语言、文法、自动机） ② 用正规式和CFG描述的语言，对应的识别方法（自动机） 不同； ③ 正规式适合描述线性结构，如标识符、关键字、注释等； CFG适合描述具有嵌套（层次）性质的非线性结构，如不 同结构的句子if-then-else、while-do等