上下文无关文法 自顶向下分析 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)