上下文无关文法 自顶向下分析 4.1~4.4
上下文无关文法 自顶向下分析 4.1~4.4
32上下文无关文法CFG) CFG的定义与表示 上下文无关文法, Context Free grammar,CFG 定义31CFG是一个四元组: G=(N,T,P,S),其中 1)N是非终结符( Nonterminals)的有限集合; (2)T是终结符( Terminals)的有限集合,且N∩T=① (3)P是产生式( Productions)的有限集合,形如: A→0,其中A∈N(左部),a∈(N∪T*(右部), 若α=ε,则称A→ε为空产生式(也可以记为A→); (4)S是非终结符,称为文法的开始符号( Start symbol)
3 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）
32上下文无关文法CFG) [例3.2]简单算术表达式的上下文无关文法可表示如下 N={E}T={+,,(,),-,id}s=E P:E→E+E(1) E→E*E(2) E→(E)(3)(G3.1) E→E E→id (5) 1.产生式的一般读法 记号→读作“定义为”或者“可导出”。 E→E+E”表述为“算术表达式定义为两个算术表达式 相加”;或者“一个算术表达式加上另一个算术表达式, 仍然是一个算术表达式
4 3.2 上下文无关文法(CFG) [例3.2] 简单算术表达式的上下文无关文法可表示如下： N = {E} T = {+， * ，(，)，-，id} S = E P: E → E + E （1） E → E * E （2） E →（E） （3） (G3.1) E → -E （4） E → id （5） 1. 产生式的一般读法 记号 → 读作“定义为”或者“可导出”。 “E → E + E” 表述为“算术表达式定义为两个算术表达式 相加”；或者“一个算术表达式加上另一个算术表达式， 仍然是一个算术表达式
32上下文无关文法CFG) 2.由产生式集表示CFG 前提:若文法正确 结论:文法开始符号S是第一个产生式的左部; N是可以出现在产生式左边符号的记号集合; T是绝不出现在产生式左边符号的记号集合; P:E→E+E(1) S=E E→E*E(2) E→(E)(3)N={E T={+,*,(,),-,id} EE E (5) 产生式表示也被称为巴克斯范式( Backus-Naur form, BNF),其中→用∷=表示
5 3.2 上下文无关文法(CFG) 2. 由产生式集表示CFG 前提： 若文法正确 结论： 文法开始符号S是第一个产生式的左部； N是可以出现在产生式左边符号的记号集合； T是绝不出现在产生式左边符号的记号集合； P: E → E + E （1） E → E * E （2） E →（E） （3） E → -E （4） E → id （5） 产生式表示也被称为巴克斯范式（Backus-Naur Form， BNF），其中→用::=表示 S=E N={E} T={+， * ，(，)，-，id}
32上下文无关文法CFG) CFG产生语言的基本方法一推导 CFG(产生式)通过推导的方法产生语言 通俗地讲,产生式产生语言的过程是从开始符号S开始,对产 生式左部的非终结符反复地使用产生式:将产生式左部的非 终结符替换为右部的文法符号序列(展开产生式,用标记 >表示),直到得到一个终结符序列。 [例34用(G32)产生终结符序列-(idid可如下 E→E+E(1) E=>-E E*E(2) >-(E)by(3) (E)(3)(G3.2) >-(E+E)by(1) -E(4) >-(id+)by(5) id(5) =>-(id+id) by (5)
6 3.2 上下文无关文法(CFG) CFG产生语言的基本方法－推导 CFG（产生式）通过推导的方法产生语言。 通俗地讲，产生式产生语言的过程是从开始符号S开始，对产 生式左部的非终结符反复地使用产生式：将产生式左部的非 终结符替换为右部的文法符号序列（展开产生式，用标记 =>表示），直到得到一个终结符序列。 [例3.4] 用(G3.2)产生终结符序列-(id+id)可如下： E → E + E （1） | E * E （2） |（E） （3） (G3.2) | -E （4） | id （5） E => -E by(4) => -(E) by(3) => -(E+E) by(1) => -(id+E) by(5) => -(id+id) by(5)
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等