郑州大学编译原理第2章.ppt-淘文阁

资源描述

《郑州大学编译原理第2章.ppt》由会员分享，可在线阅读，更多相关《郑州大学编译原理第2章.ppt（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第二章高级语言及其语法描述l概述程序语言的结构和主要的共同特征l介绍程序语言的语法描述方法学习构造编译程序，必须掌握如下内容：源语言（词法、语法、语义）目标语言（硬件系统结构、指令集合、操作系统的功能）编译方法 2.1 程序语言的定义程序语言是一个记号系统，主要有语法、语义和语用等三方面定义。语法定义语言的词法和语法的形式规则语义定义语言的单词符号和语法单位的意义语用定义程序设计技术和语言成分的使用方法，它使语言的基本概念与语言的外界联系起来2.1.1 语法一个语言的语法规则定义了程序的形式结构。任何语言程序都可看成是一定字符集上的一个字符串（有限序列）。语法规则是指这样的

2、一组规则，用它可以形成和产生一合式（合法）的程序。这些规则的一部分称为词法规则，另一部分称为语法规则（或产生规则）。例如：字符串 0.5*0.5*x+cx+c 单词符号：0.5 0.5 x c *+x c *+语法单位：0.5*0.5*x+c x+c （表达式）单词符号单词符号是语言中具有独立意义的最基本结构。词法规则定义了程序中单词符号的形成规则。即字母表中的哪些字符可以构成一个合法的单词。单词符号种类：常量、标识符、基本字、界符、运算符描述词法规则的有效工具：正规式、正规文法、有限自动机语法规则语法规则规定了如何从单词符号串中形成更大的结构（即语法单位）。它是语法单位的形成规则。语法

3、单位包括：表达式、语句、分程序、函数、过程、程序。描述语法规则的有效工具：上下文无关文法2.1.2 语义语义规则是指这样的一组规则，使用它可以定义一个程序的意义。描述语义规则的工具：基于属性文法的语法制导下的翻译方法对于一个语言来说，不仅要定义它的词法、语法规则，而且还要定义它的单词符号和语法单位的意义。这就是语义问题。离开语义，语言只不过是一堆符号的集合。2.1.3 程序所谓程序，是描述一定数据的处理过程，即包括描述数据和对数据的运算两个功能。程序结构：程序子程序或分程序语句表达式数据引用算符函数调用 2.2 高级语言的一般特性高级语言的分类从语言范型来分，程序设计语

4、言分四类：强制式语言（Imperative Language）应用式语言（Applicative Language）基于规则的语言（Rule-based Language）面向对象语言（Object-Oriented Language）程序结构一个高级语言程序通常由若干子程序段（过程、函数）构造。许多语言还引入了类、程序包等更高级的结构。一、FORTRAN一个Fortran程序由一个主程序和若干个辅程序段组成。PROGRAM MAIN ENDSUBROUTINE SUB1 ENDSUBROUTINE SUB1 END二、PascalPascal是一个允许子程序嵌套的语言。Program

5、 EX 说明部分 procedure P1;procedure p11;begin end;begin end;Begin 执行语句部分 End.三、Ada 在Ada语言中引入了程序包（Package），它可以把数据和操作代码封装在一起，支持数据抽象。一个程序包有两部分：可见的规范说明：定义程序包外面可以访问的对象。程序包体：定义程序包的实现细节。见P17 四、JAVA Java 是一种面向对象的高级程序语言，它很重要的方面是类（Class）及继承（Inheritance）的概念。同时支持多态性（Polymorphism）和动态绑定（Dynamic binding）等特性。见P18数据类型与操

6、作一个数据类型通常包括以下三个要素：用于区别这种类型的数据对象的属性；（类型名，作用域）这种类型的数据对象可以具有的值；（取值范围）可以作用于这种类型的数据对象的操作。（运算符）一、初等数据类型数值数据、逻辑数据、字符数据、指针类型二、数据结构数组、记录、字符串、表格、栈和队列三、抽象数据类型一个抽象数据类型包括：（1）数据对象的一个集合；（2）作用于这些数据对象的抽象运算的集合；（3）这种类型对象的封装。语句与控制结构一、表达式表达式是由运算量和运算符组成的。运算量亦称操作数，即数据引用或函数调用；运算符有算术运算符、逻辑运算符、关系运算符等，运算符之间有规定的优先级和结合性。表达式

7、的形成规则：（1）变量、常量是表达式；（2）若E1，E2为表达式，是二元运算符，则 E1 E2 也是表达式；（3）若E为表达式，是一元运算符，则 E(或E)也是表达式；(4)若E为表达式,则(E)也是表达式。二、语句 1、赋值句2、控制语句无条件转移语句条件语句循环语句过程（或函数）调用语句返回语句3、说明句4、简单句和复合句2.3 程序语言的语法描述本节介绍高级语言语法结构的形式化描述问题基本概念设是一个有穷字母表，它的每个元素称为一个符号。上的一个符号串是指由中的符号所构成的一个有穷序列。不包含任何符号的序列称为空字，记为。*表示上的所有符号串组成的集合。空字也包括在其中。表

8、示不含任何元素的空集。*的子集U和V的（连接连接）积定义为UV=|U&V 即集合UV中的符号串是由U和V的符号串连接而成的。V自身的n次积（连接）记为 V Vn n =VV VVV V规定 V0=V*=V0 U V1 U V2 U V3 U 称 V*是V的闭包。V+=VV*称 V+是V的正则闭包。例如若若 =a,b a,b 则则 *=,a,b,a,b,aaaa,abab,baba,bb,bb,aaaaaa,上下文无关文法文法文法是描述语言语法结构的形式规则，即语法规则。语法规则必须是正确的，且易于理解。上下文无关文法上下文无关文法是这样一种文法，它所定义的语法范畴是完全独立于这种范畴所可

9、能出现的环境的。以后，凡“文法”一词若无特别说明，则均指上下文无关文法。例如：英文的语法规则 He|me a gave book “”表示“由组成”或“定义为”。有时，“”也用“:=”表示，后者为巴科斯范式（BNF），前者为其简化表示。例如:判断He gave me a book.是否为正确句子方法一：He gave me a book 若能利用语法规则，画出其语法分析树，则证明是正确的句子。方法二：利用规则进行推导。句子 He He He gave He gave He gave me He gave me He gave me a He gave me a book上下文无关文法定义归

10、纳起来，一个上下文无关文法包括四个组成部分：一组终结符号终结符号如：me,book,gave 等一组非终结符号非终结符号如：，等一个开始符号开始符号如:一组产生式产生式如：上下文无关文法定义形式上说，一个上下文无关文法G G是一个四元式：G=（VT，VN，S，），其中：V VT T是一个非空有限集，它的每个元素为终结符号；V VN N是一个非空有限集，它的每个元素为非终结符号且VTVN=S S 是一个非终结符号，称为开始符号；是产生式有限集合，形如 AA 其中：A VN，(VT U VN)*。注：开始符号S是一个特殊的非终结符号，它至少必须在某个产生式的左部出现一次。若产生式的左

12、*E|(E)|i|5一个上下文无关文法是如何定义一个语言呢?从开始符号出发,反复连续使用产生式,对非终结符施行替换和展开,直到推导的字符串全由终结符组成（即句子），所有句子的集合即为该文法定义的语言。例如：文法 G(S):G(S):S S ABAB A A a|a|aAaA B B b|Bb b|Bb则该文法定义的语言为：L(G)=ambn|m,n 0 例题证明 i+5i+5 是一个算术表达式证明：E=E+E (EE+E)=i+E (E i )=i+5 (E 5 )故 i+5 是算术表达式。解释：=仅表示使用一次规则的一步推导。术语1.称串A能直接推出直接推出，即：A 仅当 A A 是一个

13、产生式。2.如果 1 2 n 则称从1可推导出可推导出n 3.用 1 n 表示从1出发，经过一步或多步，可推导出 n +4.用 1 n 表示从 1出发，经过0步或多步，可推导出n 即 1 n 意味着1=n 或 1 n 5.若 S S 是开始符号，且 S S 则称是文法的一个句型若 VT*，则称为文法的一个句子。术语*+*术语例题2.1 设文法G1如下，求所定义的语言？SbA Aa|aA6.文法G G所产生的句子的全体构成一个语言L(G)L(G)=|S&VT*分析：S=bA=ba S=bA=baA=baaA=.=baaa解：L(G1)=ban|n0*例题2.2分析过程：A=aA=aaA=a

15、4)=ambn|mn0 正解：文法G4:S SABAB A Aa|a|aAaA B BaBbaBb|最左推导和最右推导下面两个推导都是正确的:(1)E+E E+ii+i (2)E+E i+Ei+i 从一个句型到另一个句型的推导过程不是唯一的。例如：E+E i+i 为了对句子的结构进行确定性的分析，往往只考虑最左推导和最右推导。+最左推导:是指任何一步推导都是对的最左非终结符进行替换的。最右推导：是指任何一步推导都是对的最右非终结符进行替换的。例如：写出句型(i+i*i)的最左推导。解：E E(E)(E)(E+E)(E+E)(i+E)(i+E)(i+E*E)(i+E*E)(i+i*E)(i+

16、i*E)(i+i*i)(i+i*i)2.3.2 语法分析树和二义性语法分析树也可以描述一个句型的推导。语法树的根由开始符号所标记。随着推导的展开，当某个非终结符被它的某个候选式所替换时，就产生下一代新结，候选式中自左自右的每个字符对应一个新结。在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末（叶子）自左自右排列起来就是一个句型。一棵语法树表示了一个句型的种种可能的不同推导过程，它有助于理解一个句子语法结构的层次。E （E ）E +E i E *E i i例如：画出句子(i+i*i)的语法树。E (E)一棵语法树是一个句型的种种不同推导过程的共性抽象，是它们的代表。一棵语法树完全等价于一

17、个最左（右）推导。文法的二义性一个句型是否只对应唯一的一棵语法树呢？即，它是否只有唯一的一个最左推导？不尽然。例如：句子句子(i+i*i)i+i*i)就存在两个不同的就存在两个不同的最左推导：(1)(1)E E(E)(E)(E+EE+E)(i+E)(i+E)(i+E*E)(i+E*E)(i+i*E)(i+i*E)(i+i*i)(i+i*i)(2)(2)E E(E)(E)(E*EE*E)(E+E*E)(E+E*E)(i+E*E)(i+E*E)(i+i*E)(i+i*E)(i+i(i+i*i)*i)在一个文法中，若存在某个句子有两个不同的最左推导，则称该文法是二义的。或者说，在一个文法中，若存在

18、某个句子有两棵不同的语法树，则称该文法是二义的。注文法的二义性问题是不可判断的。即，不存在一个算法，它能在有限步内判断一个文法是否是二义的。文法的二义性文法的二义性与语言的二义性是两个不同的概念。注意：注意：例题2.4 对算术表达式构造一个无二义的文法。解：无二义的文法如下：ET|E+T TF|T*F F(E)|i|5提示：考虑算符的优先性和结合性。约定作为描述程序语言的文法，有以下几点限制：（1）不能有任何产生式:PP（2）每个非终结符P必须都有用处。即，必须存在含P的句型：S=P 且 P=VT*2.3.3 形式语言鸟瞰（1）自从Chomsky于1956年建立形式语言的描述以来，形式语

19、言的理论发展得很快。这种理论对计算机科学有着深刻的影响，特别是对程序语言的设计、编译方法和计算复杂性等方面更有重大的作用。Chomsky把文法分成四种类型，即0型、1型、2型和3型。这几类文法的差别,在于对产生式的形式施加了不同的限制。从0型到3型依次增强，但它们表达语言的能力则依次减弱。2.3.3 形式语言鸟瞰（2）设G=G=（V VT T，V VN N，S S，）是0型文法，如果它的每个产生式：其中：其中：,(V VT TU UV VN N)*且中至少含有一个符号A AVVN,N,0型文法又称为短语文法。对0型文法施加第 i 条限制，就得到 i 型文法：(1)(1)|，仅S除外但S不能出现

20、在任何产生式右部。(2)(2)G的任何产生式为：P 其中：其中：P P V VN N，(V VT T U U V VN N)*。(3)(3)G的任何产生式为：AB 或 A 其中：其中：A A，B B V VN N，V VT T*2.3.3 形式语言鸟瞰（3）1型文法又称为上下文有关文法。2型文法又称为上下文无关文法。3型文法又称为正则（规）文法（或线性文法）。（1）若3型文法产生式的形式为：A AB B 或或 A A 则称为右线性文法。（2）若3型文法产生式的形式为：A AB B 或或 A A 则称为左线性文法。例2.6 证明：任何右线性文法G都等价于仅含下面两种形式产生式的文法G：A aB

21、或 Aa 证明：设右线性文法G的产生式为：AB 或 A 其中：A，B VN，VT*令为a1 a2 ak 其中ai VT(1)若产生式为A，即A a1 a2 ak 则引入K-1个非终结符B1,B2,Bk-1，此产生式等价于 A a1 B1 B1 a2 B2 Bk-2 ak-1 Bk-1 Bk-1 ak(2)若产生式为AB，即A a1 a2 ak B 则引入K-1个非终结符B1,B2,Bk-1，此产生式等价于 A a1 B1 B1 a2 B2 Bk-2 ak-1 Bk-1 Bk-1 ak B 因此，右线性文法的任何产生式均可表示为：A a B A a （证毕）作业（2）P35-364.6.7.8.9.10.11.13*

展开阅读全文