- 1、本文档共105页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
例如,有0型文法G=(VN,VT,P,S)其中,VN={S,B,C,D},VT={a,b,c}其描述的0型语言为:L0(G[S])={a2i|i≥0}P:S?ACaBCa?aaCCB?DB|EaD?DaAD?ACaE?EaAE?ε2.3.3形式语言鸟瞰由上述四类文法的定义可知,从0型文法到3型文法,是逐渐增加对规则的限制条件而得到的,因此每一种正则文法都是上下文无关的文法,每一种上下文无关的文法都是上下文有关的文法,而每一种上下文有关的文法都是0型文法,而由它们所定义的语言类是依次缩小的,有L0?L1?L2?L3。2.3.3形式语言鸟瞰四种类型描述能力比较0型1型2型3型本章重点介绍了文法、语法树、文法的二义性以及各类文法,主要内容有:1.设计一个文法定义一个已知的语言(1)文法是一个四元组G=(VN,VT,P,S),文法四大要素中,关键是一组规则,它定义(或描述)了一个语言的结构。从文法定义可知,对于编译程序设计者来说,文法给出了语言的精确定义和描述。本章小结(2)分析已知语言句子的结构特征,设计出相应的一组规则,但不唯一。(4)若语言是无穷集合,该语言的文法一定是递归的。 (3)设计的文法必须能定义已知的语言,不能超出或缩小所定义语言的范围。本章小结2.已知一个文法,确定该文法所定义的语言。(2)给定一个文法,可根据语言和推导定义推导出文法的句子,从而确定出该文法所定义的语言。(1)文法所定义的语言L(G[S])={x|S?x且x∈VT*}*本章小结①自然语言描述。例如,L={x|x∈{a,b}+且x中a,b个数相同}②式子描述。例如L={a2nbb|n≥0}。(3)语言可用本章小结3.文法二义性的判断一个文法存在某个句子对应两棵不同的语法树或对应两个不同的最左(最右)推导,则该文法是二义性的。本章小结4.文法的实用限制文法的实用限制主要是指:(1)文法不包含有害规则;(2)文法不含多余规则;如果文法满足上述条件,则称该文法是压缩过的或化简了的。本章小结5.文法和语言的分类(1)0型文法与0型语言(2)1型文法与1型语言(3)2型文法与2型语言(4)3型文法与3型语言本章小结P36:6、7、8、9、10、11作业*程序设计语言(10)
Alan?J.?Perlis?(1966)?--?ALGOL
Edsger?Wybe?Dijkstra?(1972)?--?ALGOL
John?W.?Backus?(1977)?--?FORTRAN
Kenneth?Eugene?Iverson?(1979)?--?APL程序语言
Niklaus?Wirth?(1984)?--?PASCAL
John?Cocke?(1987)?--?RISC??编译优化
Ole-Johan?Dahl,Kristen?Nygaard?(2001)?--?Simula语言和面向对象概念
Alan?Kay(2003)?--?SmallTalk语言和面向对象程序设计
Peter?Naur(2005)?--?ALGOL60以及编译设计形式语言,?程序语言语义?(4)
Robert?W.?Floyd?(1978)?--?编程语言语义,自动程序验证
C.?Antony?R.?Hoare?(1980)?--?Hoare?Logic,?CSP
Robin?Milner?(1991)?--?LCF,ML,CCS,PI-calculus
Amir?Pnueli?(1996)?--?时序逻辑和系统验证*存放方式:按行存放(C,PASCAl),按列存放(FORTRAN)*A0={e}*设A={a,;},则A≡⊙∷=∞∝!≠=##12◆,.┍┎**** 从前面的讨论可以看出,对于文法G中任一句型的推导序列,我们总能为它构造一棵语法树,现在我们提出一个问题:文法的某个句型是否只对应唯一的一棵语法树呢
文档评论(0)