上次章节内容回顾.ppt
《上次章节内容回顾.ppt》由会员分享,可在线阅读,更多相关《上次章节内容回顾.ppt(24页珍藏版)》请在三一文库上搜索。
1、1,上次课内容回顾,语法分析简介: 词法分析:字母是元素,组成字符串(记号) 语法分析:记号是元素,组成句子 语法分析的作用: 1:识别句子 2:语法错误,2,正规式能定义一些简单的语言,能表示给定结构的固定次数的重复或者没有指定次数的重复 例:a (ba)5, a (ba)* 正规式不能用于描述配对或嵌套的结构 例1:配对括号串的集合 例2:wcw | w是a和b的串,3.2 上下文无关文法(CFG),3,3.2 上下文无关文法(CFG),CFG的定义与表示 上下文无关文法,Context Free Grammar,CFG 定义3.1 CFG是一个四元组: G =(N,T,P,S),其中 (
2、1) N是非终结符(Nonterminals)的有限集合; (2) T是终结符(Terminals)的有限集合,且NT=; (3) P是产生式(Productions)的有限集合,形如: A,其中AN(左部),(NT)*(右部), 若=,则称A为空产生式(也可以记为A ); (4) S(非终结符)称为文法的开始符号(Start symbol)。,4,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
3、(5) 产生式的一般读法 记号 读作“定义为”或者“可导出”。 “E E + E” 表述为“算术表达式定义为两个算术表达式相加”;或者“一个算术表达式加上另一个算术表达式,仍然是一个算术表达式”。,5,3.2 上下文无关文法(CFG),2.产生式表示也被称为巴克斯范式(Backus-Naur Form,BNF),其中用:=表示 E :=E + E | E * E | (E) | -E | id,6,3.2 上下文无关文法(CFG),3.终结符与非终结符书写上的区分 (a) 用大小写区分: E id (b) 用“ “区分: E “id“ E E “+“ E (c) 用区分: + 教材约定:大写英
4、文字母A、B、C表示非终结符; 小写英文字母a、b、c表示终结符; 小写希腊字母、表示任意文法符号序列,7,3.2 上下文无关文法(CFG),产生式的缩写形式 当多个产生式的左部非终结符相同时,可合并为一个产生式。新的产生式的左部是此非终结符,右部是所有原来右部的或运算(并集合)。 例3.3 G3.1可以重写为如下形式: E E + E (1) | E * E (2) |(E) (3) | -E (4) | id (5) 用“|”连接的每个右部称为一个候选项,具有平等的权利。,P: E E + E (1) E E * E (2) E (E) (3) E -E (4) E id (5),8,3.
5、2 上下文无关文法(CFG),CFG产生语言的基本方法推导 CFG(产生式)通过推导的方法产生语言。 通俗地讲,产生式产生语言的过程是从开始符号S开始,对产生式左部的非终结符反复地使用产生式:将产生式左部的非终结符替换为右部的文法符号序列(展开产生式,用标记=表示),直到得到一个终结符序列。 例3.4 用算术表达式的上下文无关文法产生终结符序列-(id+id)可如下: E E + E (1) | E * E (2) |(E) (3) | -E (4) | id (5),E = -E (4) = -(E) (3) = -(E+E) (1) = -(id+E) (5) = -(id+id) (5)
6、,9,3.2 上下文无关文法(CFG),定义3.2 利用产生式产生句子的过程中,将产生式A的右部代替文法符号序列A中的A得到的过程,称从A直接推导出,记作:A=。 若对于任意文法符号序列1,2,.n,均有1=2=.=n,则称此过程为零步或多步推导,记为: 1=*n,其中1=n的情况为零步推导。 若1n,即推导过程中至少使用一次产生式,则称此过程为至少一步推导,记为:1=+n。 两点注意: ,有=*,即推导具有自反性; 若=*,=*,则=*,即推导具有传递性。,10,3.2 上下文无关文法(CFG),定义3.3 由CFG G所产生的语言L(G)被定义为: L(G) = S= + and T* ,
7、 L(G)称为上下文无关语言(Context Free Language, CFL),称为句子。 若S=*,(NT)*,则称为G的一个句型。 定义3.4 在推导过程中,若每次直接推导均替换句型中最左边的非终结符,则称为最左推导,由最左推导产生的句型被称为左句型。 类似可定义最右推导与右句型,最右推导也被称为规范推导。 E = -E = -(E) = -(E+E) = -(id+E) = -(id+id) 1 2 3 4 5 6 6是句子,所有i (i=1.6)均是句型。,11,例 E E + E | E E | (E ) | E | id 最左推导 E lm E lm (E) lm (E +
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 上次 章节 内容 回顾
链接地址:https://www.31doc.com/p-2632099.html