3.2-上下文无关文法(CFG)资料讲解-豆柴文库

您所在位置：网站首页 / 3.2-上下文无关文法(CFG)资料讲解.ppt / 文档详情

免费试读已结束，剩余 19 页请下载文档后查看

10 金币

下载文档

/ 24

下载提示

如果您无法下载资料，请参考说明：

1、部分资料下载需要金币，请确保您的账户上有足够的金币

2、已购买过的文档，再次下载不重复扣费

3、资料包下载后请先用软件解压，在使用对应软件打开

文本预览

上次课内容回顾
正规式能定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复
	例：a(ba)5,a(ba)*

正规式不能用于描述配对或嵌套的结构
	例1：配对括号串的集合
	例2：{wcw|w是a和b的串}
3.2上下文无关文法(CFG)3.2上下文无关文法(CFG)3.2上下文无关文法(CFG)3.2上下文无关文法(CFG)3.2上下文无关文法(CFG)3.2上下文无关文法(CFG)3.2上下文无关文法(CFG)例EE+E|EE|(E)|E|id

最左推导
	E	lmElm(E)lm(E+E)
		lm(id+E)lm(id+id)

最右推导（规范推导）
	E	rmErm(E)rm(E+E)
		rm(E+id)rm(id+id)3.2上下文无关文法(CFG)3.2上下文无关文法(CFG)3.2上下文无关文法(CFG)3.2上下文无关文法(CFG)3.2上下文无关文法(CFG)3.2上下文无关文法(CFG)3.2上下文无关文法(CFG)3.2上下文无关文法(CFG)文法具有二义性3.2.1正规式和上下文无关文法的比较（初步思考）
正规式
(a|b)*ab

文法
A0aA0|bA0|aA1
A1bA2
A2
为什么要用正规式定义词法（为什么不用上下文无关文法？）
词法规则非常简单，不必用上下文无关文法
对于词法记号，正规式描述简洁且易于理解
从正规式构造出的词法分析器效率高本次课内容总结作业