编译原理(清华大学).ppt

例如，有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中任一句型的推导序列,我们总能为它构造一棵语法树，现在我们提出一个问题：文法的某个句型是否只对应唯一的一棵语法树呢