下载此文档

第二章 形式语言基础.ppt


文档分类:IT计算机 | 页数:约62页 举报非法文档有奖
1/62
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/62 下载此文档
文档列表 文档介绍
第二章 形式语言基础.ppt南京邮电大学计算机学院蒋凌云******@:《编译技术原理及其实现方法》pilerPrinciples1第二章形式语言基础知识§、形式语言提出二、语言描述方法§、巴科斯范式二、语法和语义三、语法树§、元语言二、符号和符号串三、产生式(规则)四、文法五、推导和归约六、句型和句子七、语言八、递归文法九、短语和简单短语十、最左推导和最右推导十一、文法二义性§、自顶向下语法分析二、自底向上语法分析§、文法分类二、文法和自动机三、压缩过文法§、扩充巴科斯范式二、语法图2§、语言设G[Z]为一文法,由该文法所产生的一切句子的集合称为由该文法所定义的语言,记为L(G[Z])(或记为L(G)),即L(G)={x|Z*x且x∈VT*}有时我们称这样定义的语言为形式语言,以区别于自然语言。上述公式包含两层意思:语言是句子集合,是VT*一个子集合,即VT中行集合子集。句子必须有该语言文法识别符推出。例如:G[Z]=(VN,VT,P,S)VN={S}VT={0,1}P:{S∷=01,S∷=0S1}S:识别符很容易推出:L(G)={0n1n|n≥1}3已知语言求文法构造如下语言的相应文法L(G)={0n1n|n≥0}P:{S∷=01,S∷=0S1}S:识别符很容易推出:L(G)={0n1n|n≥1}4已知语言求文法构造如下语言的相应文法L(G)={0m1p|m,p≥1}P:{S∷=01,S∷=0S1}S:识别符很容易推出:L(G)={0n1n|n≥1}如果两个文法,尽管它们的规则不尽相同,但所描述的语言完全相同,则称这两个文法是等价的。5要使一个文法G能正确描述相应语言L(G)必须保证:由文法G产生的每个句子都在L(G)中,在语言L(G)中的每个符号串都能由G产生6又如:写一个文法,使其语言为偶整数集合。首先分析以下偶整数(1)偶整数最后一个数字应该是偶数字0,2,4,6等(2)偶整数前面符号可以是+,-或不带符号由此得其文法应由下列规则组成:<偶整数>∷=<符号><偶数字>|<偶数字>|<符号><数字串><偶数字>|<数字串><偶数字><偶数字>∷=0|2|4|6|8<数字>∷=1|3|5|7|9|<偶数字><数字串>∷=<数字>|<数字串><数字><符号>∷=+|-所以文法可表示为:G=(VN,VT,P,<偶整数>)其中:VN={<偶整数>,<偶数字>,<数字>,<数字串>,<符号>}VT={0,1,2,3,4,5,6,7,8,9,+,-}7对于通常的程序设计语言其文法为:G[程序]=(VN,VT,P,〈程序〉)其中VN={〈程序〉,〈说明〉,〈语句〉,…}VT={0,1,…,9,a,…,z,-,(,),…}P={<程序>∷=…,〈说明〉∷=…,〈语句〉∷=…,…}L(G)={w|〈程序〉*w且w∈VT*}由此可知,每一个w就是一个源程序,所谓PASCAL语言也就是所有PASCAL程序的集合。8第二章形式语言基础知识§、、*上几种运算三、产生式(规则)、文法五、推导和归约六、句型和句子七、语言八、、、最左推导和最右推导十一、§、递归文法构成一个语言的句子集合可以是有穷的,也可以是无穷的,10

第二章 形式语言基础 来自淘豆网www.taodocs.com转载请标明出处.

非法内容举报中心
文档信息
  • 页数62
  • 收藏数0 收藏
  • 顶次数0
  • 上传人dyx110
  • 文件大小329 KB
  • 时间2020-09-24