- 1、本文档共71页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
编译原理Chat2
) E E E F F T T T T i + * ( E F i i E ?T ?F ?(E) ?(E+T) ?(T+T) ?(T*F+T) ?(F*F+T) ?(i*F+T) ?(i*i+T) ?(i*i+F) ?(i*i+i) 考虑句子(i*i+i) 描述程序设计语言时,对于上下文无关文法的限制 : 1 不含P?P形式的产生式 2 每个非终结符P必须有用处 即: 2.3.3 形式语言鸟瞰 Chomsky于1956年建立形式语言体系,他把文法分成四种类型:0,1,2,3型。 与上下文无关文法一样,它们都由四部分组成,但对产生式的限制有所不同。 0型(短语文法,图灵机): 产生式形如: ? ? ? 其中:?? (VT ? VN)*且至少含有一个非终结符;?? (VT ? VN)* 1型(上下文有关文法,线性界限自动机): 产生式形如: ? ? ? 其中:|?| ? |?|,仅 S?? 例外。 2型(上下文无关文法,非确定下推自动机): 产生式形如: A ? ? 其中:A? VN;?? (VT ? VN)*。 3型(正规文法,有限自动机): 产生式形如: A ? ?B 或 A ? ? 其中: ?? VT*;A,B?VN 产生式形如: A ? B? 或 A ? ? 其中: ?? VT*;A,B?VN 右线性文法 左线性文法 四种类型描述能力比较 0型 1型 2型 3型 L5={anbn|n?1} 不能由正规文法产生,但可由上下文无关文法产生: G5(S): S ? aSb| ab L6={anbncn|n?1}不能由上下文无关文法产生,但可由上下文有关文法产生: G6(S): S ? aSBC| aBC CB ? BC aB ? ab bB ? bb bC ? bc cC ? cc 程序设计语言不是上下文无关语言,甚至不是上下文有关语言。 L7={?c?| ??(a|b)*}不能由上下文无关文法产生,甚至连上下文有关文法也不能产生,只能由0型文法产生。 标识符引用 过程调用过程中,形-实参数地对应性(如个数,顺序和类型一致性) 现今程序设计语言的语言结构,用上下文无关文法描述就足够了。 作业 P36-6,7,8,9,10,11 程序设计语言(10)Alan?J.?Perlis?(1966)?--?ALGOLEdsger?Wybe?Dijkstra?(1972)?--?ALGOLJohn?W.?Backus?(1977)?--?FORTRANKenneth?Eugene?Iverson?(1979)?--?APL程序语言Niklaus?Wirth?(1984)?--?PASCALJohn?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,?CSPRobin?Milner?(1991)?--?LCF,ML,CCS,PI-calculusAmir?Pnueli?(1996)?--?时序逻辑和系统验证 存放方式: 按行存放(C, PASCAl),按列存放(FORTRAN) 3 字符串、表格、栈 字符串:符号处理、公式处理 表格:本质上是一种记录结构 线性表:一组顺序化的记录结构 栈:一种线性表,后进先出,POP, PUSH 三 抽象数据类型 一个抽象数据类型包括: 数据对象的一个集合; 作用于这些数据对象的抽象运算的集合; 这种类型对象的封装,即,除了使用类型中所定义的运算外,用户不能对这些对象进行操作。 程序设计语言对抽象数据类型的支持 Ada语言通过程序包(package)提供了数据封装的支持 Smalltalk、C++和Java语言则通过类(Class)对抽象数据类型提供支持。 2.2.4 语句与控制结构 一.表达式 表达式由运算量(也称操作数,即数据引用或函数调用)和算符(操作符)组成。 形式:中缀、前缀、后缀
文档评论(0)