编译原理 - 陈火旺版 - 第二章.ppt

1、1,编译方法,中国人民大学信息学院 陈文萍,2,第二章 高级语言及其语法描述,高级程序语言:描述算法和计算机实现 不同的应用侧重点不同: 数值计算- FORTRAN 系统程序设计-C 事务处理-COBOL VLSI设计-VHDL 人工智能-PROLOG 大型嵌入式实时处理-Ada 符号处理-SNOBOL,3,内容,2.1 程序语言的定义 2.2 高级语言的一般特性 2.3 程序语言的语法描述,4,2.1 程序语言的定义,程序设计语言：是由一组记号所构成的集合。 语言的定义 语言用户：语言的成分，使用意义 编译程序：语言的规则，语法单位对应的含义 组成部分 语法 （Syntax） 语义（ Sem

2、antics） 语用（ Pragmatics）,5,语法,语法 （Syntax）：程序构成的一组规则 词法规则：单词符号的形成规则 单词符号：语言中具有独立意义的最基本的结构 类型：常数，标识符，基本字，算符，界符 例如：字符串 100-(8a)*0.5 100，8：整型常数；0.5：实型常数； -,=,*：算符； (,)：界符 分析工具：正规式和有限自动机,6,语法,语法规则：语法单位的形成规则 语法单位：比单词符号更大的语法结构 例如：表达式，语句，分程序，函数，过程，程序 分析工具：上下文无关文法,7,语义,语义（ Semantics）定义程序的含义的一组规则 例如：C 语句 a = 1

3、8+b; 分析方法：基于属性文法的语法制导翻译方法 语用（ Pragmatics）程序设计技术和语言成分的使用方法,8,程序的层次结构,程序,子程序,语句,表达式,数据引用,算符,函数调用,9,2.2 高级语言的一般特性,高级高级语言的分类：按语言范型 强制式语言，应用式语言，基于规则的语言，面向对象的语言 强制式语言：命令驱动，面向语句。一个强制式语言程序由一系列的语句组成，每个语句的执行引起若干存储单元中的值的改变，这种语言的语法形式通常具有如下形式： 语句1； 语句2； 语句n； 例如-C, Fortran, Pascal,10,应用式语言,注重程序所表示的功能，而不是一个语句接一个语句

4、地执行 程序的开发过程是从前面已有的函数出发构造出更复杂的函数 这种语言通常的语法形式是： Function n(function2(function1(data) 程序执行：执行一个个函数，得到数据上的变换，最终得到的结果 例如：ML，Lisp,11,基于规则的语言,程序的执行过程：检查一定的条件，当它满足值，则执行适当的动作。 也称逻辑程序设计语言：基本允许条件是谓词逻辑表达式。 这类语言的语法形式通常为： 条件1 动作1 条件2 动作2 条件3 动作3 例如：Prolog,12,面向对象的语言,主要特征：封装性，继承性和多态性 例如：C+, JAVA,13,程序结构,不同的语言，如 Fo

5、rtran, Pascal， Ada，Java 程序结构不同 名字的作用域不同 例如：Pascal 的最近嵌套原则 procedure P; var x: interger ; procedure Q; var x: real ; begin x := 1.2; end; begin x := 5; end;,14,数据类型,数据类型的三要素：属性，值，操作 属性：包括类型和作用域 类型：决定数据可以是什么样的值，允许的运算，计算机内如何表示 作用域：值的有效范围 初等数据类型 数值数据：如整型，实型 逻辑数据：布尔型 字符数据：字符型（字符串型） 指针类型：指向另一种数据类型,15,数据类型

6、,数据结构：从初级数据定义的复杂（高级）数据 数组 内情向量：便于计算数据元素的地址，包括：维数，各维的上、下限，首地址，数组元素类型等。 例如： Pascal的说明 var a: array1.50 of char 是一个下标从1至50的字符数组 记录：由已知类型的数据组合而成 例如： Pascal 语言中 Student: record name: array 120 of char ; age: integer ; id: array 18 of char ; major: integer ; classid: integer ; end; 字符串，表格，栈，队列 抽象数据类型：数据对象

7、，运算，封装,16,语句与控制结构,表达式：由操作数和算符组成 例如：x-y, -x 通常的形成规则 变量，常数是表达式 若E1,E2是表达式，是二元算符，则E1E2是表达式 若E是表达式，是一元算符，则E或 E是表达式 若E是表达式，则(E)是表达式 算符的优先级,17,语句,分类：按功能 说明性语句：定义名字的性质 执行性语句：描述程序动作 赋值语句 控制语句 转移语句：goto 条件语句：如 if then else 循环 语句：如while do 过程调用语句：如 call 返回语句： 如 return 输入/输出语句: 如 read, write,18,2.3 程序语言的语法描述,预

8、备知识 上下文无关文法 语法分析与二义性 形式语言概述,19,预备知识,符号：可以相互区别的记号（元素） 字母表：符号（元素）的非空有穷集合，用表示 符号串：由字母表中的符号组成的任何有穷序列 1.空符号串(没有符号的符号串)是上的符号串 2.若x是上的符号串,a是的元素,则xa是上的符号串 3. y是上的符号串,当且仅当它可以由1和2导出。 例如， 字母表=a,b，则,a,b,aa,ab,ba,bb,aaa,aab,都是上的符号串,20,预备知识,符号串的运算 符号串的长度：符号串中符号的个数. 符号串s的长度记为|s|，的长度为0 连接：符号串x、y的连接,是把y的符号写在x的符号之后得到

9、的符号串xy 如 x=ab,y=cd 则 xy=abcd 有a = a 方幂：符号串自身连接n次得到的符号串 an 定义为 aaaa （n个a） a1=a, a2=aa a0=,21,预备知识,符号串的集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。 * ：表示上的所有符号串的全体 空集：，不含任何元素 符号串集合的运算： 积（连接）：两个符号串集合A和B的积定义为 AB =xy|xA且yB 例如： 集合A=ab,cde B = 0,1， 则 AB =ab1,ab0,cde0,cde1 闭包： V* = V 0 V 1 V 2 V 3 ., *称为的闭包 V 0=

10、 ,22,预备知识,正则闭包：V+= V 1 V 2 V 3 ., V *= V + ， +称为的正闭包。 例：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, +=a,b,aa,ab,ba,bb,aaa,aab,23,上下文无关文法,语言的表示 语言有穷：将句子逐一列出 语言无穷：找出语言的有穷表示，两个途径： 生成方式 （文法）：语言中的每个句子可以用严格定义的规则来构造。 识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回答“是”；若不属于，要么能停止并回答“不是”，要么永远继续下去,24,上下文无关文法,文法：描述语言的语法结构

11、的形式规则。 形式数学系统：可由下列基本成分来刻画：一组基本符号，一组形成规则，一组公理，一组推理规则 上下文无关文法：所定义的语法范畴完全独立于语法范畴可能出现的环境。 例如：语法规则： I am a student,25,上下文无关文法,分析句子：I am a student 句子 主语 谓语 宾语 代词 谓语 宾语 I 谓语 宾语 I 动词 宾语 I am 宾语 I am 冠词 名词 I am a student 语法树：如右图,26,上下文无关文法,四个组成部分：四元式（VT,VN,S,P） 终结符号：VT, 不可再分的基本符号，如基本字、标识符、常数、算符、界符等词法符号。 非终结符

12、号：VN, 语法范畴，表示类记号，不是个体记号。 VN和VT不含公共的元素，即VN VT = , 用V表示VN VT ，称为文法G的字母表或字汇表 开始符号：S,特殊的非终结符号，至少要在一条产生式中作为左部出现。 产生式：P，定义语法范畴的一种书写规则。 形如或 =的( ，)有序对，其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。 称为规则的左部， 称作规则的右部。 例如：E i | E+E | E*E | (E) 候选式,27,上下文无关文法,举例 文法G=（VN，VT，P，S） VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号 习惯上只将产生式写出

13、，并有如下约定： 第一条产生式的左部是开始符号 用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符 G可写成GS，S是开始符号 G：SaAb Aab AaAb A GS： SaAb Aab AaAb A 缩写形式 GS：SaAb Aab |aAb |,28,上下文无关文法,直接推出： “” 定义：是文法G的产生式，若有v,w满足：v=,w= , 其中,（VTVN），则称v直接推出到w,记作 v w 推导：若存在v w0 w1 . wn=w,(n0)， 则称此序列为v到w的一个推导记为 ：经过至少一步推导 ：经0步或若干步 推导每前进一步总是引用文法中的一个产生

14、式 若有 则或 v=wn，或,29,上下文无关文法,句型 对文法G，若 ，则称是文法G的句型。 句子 有文法G，若 ，且VT*，则称是文法G的句子。例：G： S0S1， S01 S 0S1 00S11 000S111 00001111 G的句型：S,0S1 ,00S11 ,000S111,00001111 G的句子：00001111, 01 由文法G生成的语言记为L(G),它是文法G的一切句子的集合:,30,上下文无关文法,例：文法G: SAB，AaA|a，BbB|b 从开始符号出发，可以推出如下句子： 所以， 最左推导：任何一步推导，都对右部最左非终结符进行替换 最右推导：任何一步推导，都对

15、右部最右非终结符进行替换,31,思考,1，文法G： S0S1， S01， L(G)？ 2，文法GS： （1）SaSBE （2）SaBE （3）EBBE （4）aBab （5）bBbb （6）bEbe （7）eEee L(G)？,32,上下文无关文法,已知语言描述，写出文法 例：若语言由0、1符号串组成，串中0和1的个数相同，构造其文法G(A) A 0B|1CB 1|1A|0BBC 0|0A|1CC,33,上下文无关文法,文法G1A：ADB 与G2S：S0S1 ADE S01 EAB D0 B1 文法的等价：若L（G1）=L（G2），则称文法G1和G2是等价的。,34,语法分析树,语法分析树：句

16、型推导的直观方法 文法： ，推导（i*i+i),E i | E+E | E*E | (E),E,E,）,（,E,E,E,E,*,i,i,E,E,）,（,*,E,E,E,E,+,i,i,i,i,35,语法分析树,给定文法G，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树满足下列4个条件： 1、每个结点都有一个V中的符号作标记 2、根的标记是开始符号S 3、若一结点n至少有一个子孙，并且n有标记A，则AVN 4、如果结点n的直接子孙，从左到右的次序是结点n1,n2,nk，其标记分别为A1,A2,Ak，那么AA1A2,Ak一定是P中的一个产生式,36,二义性,文法的二义性：一个文法存在某

17、个句子对应两个不同的语法树，或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。 上例中，句型 （i*i+i） 的两个不同的最左推导： 推导1：E （E） （E+E） （E*E+E） （i*E+E） （i*i+E） （i*i+i） 推导2：E （E） （ E*E） （i*E） （i*E+E） （i*i+E） （i*i+i） 消除二义性：修改文法，规定优先顺序和结合律 ET|E+T TF|T*F F(E)|i,37,上下文无关文法,对文法的限制 不含PP形式的产生式 每个非终结符P都必须有用 必须存在含P的句型（可到达） 且P不存在永不终结的回路（可终止）,38,形式语

18、言概述,形式语言：从语法这一侧面来看语言。 分类：通过对产生式施加不同的限制，Chomsky将文法分为四种类型 /wiki/Chomsky_hierarchy 0型文法（短语结构文法）：对任一产生式，都有(VNVT)+， (VNVT)*。识别系统是图灵机。 1型文法（上下文有关文法）：对任一产生式，都有|； 仅仅 S除外，但S不能出现在任何产生式右部。识别系统为线性有界自动机。,39,形式语言概述,2型文法（上下文无关文法）：对任一产生式，都有VN。识别系统为下推自动机。 3型文法（正规文法）：任一产生式的形式都为AB或A，其中AVN ，BVN ，VT *。识别系统为有限自动机。 右线性文法：任一产生式的形式都为AaB或Aa 左线性文法（正规文法）：任一产生式的形式都为ABa或Aa,40,文法类型,例1: 文法GS： SCDAbbA CaCABaaB CbCBBbbB ADaD C BDbD D AabD,41,文法类