编译程序是将高级语言书写的源程序翻译成低级语言程序

资源描述

《编译程序是将高级语言书写的源程序翻译成低级语言程序》由会员分享，可在线阅读，更多相关《编译程序是将高级语言书写的源程序翻译成低级语言程序（78页珍藏版）》请在金锄头文库上搜索。

1、N编译程序是将高级语言书写的源程序翻译成低级语言程序。一般包括词法分析，语法分析，中间代码生成，代码优化，目标代码生成五个部分，还应该包括表格管理和出错处理。N其中中间代码生成和代码优化并不是每个程序都需要的。 N词法分析器用于识别单词，语法分析器用于发现源程序中的语法错误。 N代码优化一般都是在中间代码级上完成的，对中间代码的优化可以使目标程序的运行时间更短或所占的空间更少。第2讲第一章课程复习算符左操作数右操作数结果N词法分析，语法分析，中间代码生成，代码优化，目标代码生成均要与符号表格管理打交道，他们各自把工作产生的一些信息存放在符号表里，都涉及到制造，查询，更新符号

2、表格的工作，所以符号表的存取方法直接影响着编译程序的效率。N许多编译程序采用了一种与“3地址指令”非常相似的“四元式”作为中间代码，格式是：第2章文法和语言QU： 1、AB 2、ABC 在C语言中的，以上两个符号串是否是合法的、正确的？QU：那么，Compiler如何对语法进行定义？是基于什么形式进行判断识别的？ AN：形式语言中的文法是阐明语法的一个重要工具。2.1 引言形式化方法：指用一整套带有严格规定的符号体系来描述问题的方法。 2.2 符号串一、字母表和符号串二、符号串的运算一、字母表和符号串 1、字母表（） Def：是元素的非空有穷集合。 Note1：

3、中至少有一个元素；2：中可以是字母、数字或其它符号。 Ex1：C语言的字母表C保留字，字母，数字，专用符号， C语言 C 一组规则 Ex2：汉语的字母表汉汉字，数字，标点符号， 2、符号与符号串符号（字符）：一个符号是字母表中的元素。符号串：是符号的有穷序列。 EX1：a, b, c，则a, b, c, ab, ba都是上的符号串。 Note1：符号串的顺序很重要，如：abba;2：不含任何符号的符号串称为空串，用表示。符号串长度：a1，ab2， 0二、符号串的运算 1、连接设X和Y是符号串，则串XY称为它们的连接。 EX：XABC，YCDFXY=ABCCDFYX=CDFAB

4、C Note：与X的连接或X与的连接X 2、集合的乘积设A、B是符号串的集合，则定义A与B的乘积为： ABxy | xA, y B EX: A=a, b, B=c, d，则AB =ac,bc,ad,bd A=A=A , = 3、符号串的幂运算设X是符号串，则 X0 注： X0 1 X1X X2XX Xn XXX 例、设Xabc，则X0 X1abc X2abcabc Xn abcabcn个Xn个abc 4、集合的幂运算设A是符号串的集合，则定义：A0 A1A A2AA AnAAAAn-1AEX: A=a, b ,则有A0=ac,bc,ad,bdA1Aa,bA2AAaa, ab, ba,

5、 bbA3A2Aaaa,aab,aba,abb,baa,bab,bba,bbb 5、集合的闭包（A+和A）设A是任意一个集合，则定义： A+A1 A2 A3 A*A0 A+A0 A1 A2A的正闭包，其中无空串A的 * 闭包，其中有空串EX: A=a, b ,则有A+a, b, aa, ab, ba, bb, aaa, aab, A*A0 A ,a ,b, aa, 2.3 文法与语言的形式意义形式语言形式语言的描述文法的形式定义语言的形式定义最左、最右推导归约递归一、形式语言 He me a gave bookQU:句子He gave me a book 语法上是否是正确的？“

6、定义为”或“由组成” 推导出同样还可推导出： He gave He a book, Me gave me a book Me gave He a book句子主语谓语间接宾语直接宾语代词He动词gave代词me冠词a名词bookNote: 1、形式语言是一种上下文无关的语言，是有别于自然语言的一种语言。 2、定义语言的一组规则及其有关符号，称为文法。因此，我们把定义形式语言的规则和有关符号的集合，称为上下文无关的文法。二、形式语言的描述方式一：当语言为有穷集合时，用枚举法表示。 EX：设字母表Aa, b, c L1a, b, c L2aa, ab ,a ,ac L3c, cc,cc

7、c EX：设字母表0, 1，则有 0,1,00,10,001,000,这是一个无穷集合。其中，任何一个元素就相当于一个程序！本身则相当于某一语言的所有程序的集合。方式二：当语言为无穷集合时，用文法表示。 EX(续上例）：设用A表示，用式子A0表示0A（读作：“A产生0” ）。符号：“”定义为“产生”、“生成”、“导出”等。反复用 A0 A1 AA0 AA1以上四条规则式，则可以生成无穷的集合。设字母表0, 1，则有 0,1,00,10,001,000,三、文法的形式定义1、规则（产生）式一个规则式是一个符号与一个符号串的有序偶（对），形如:（A，）、A 或 A : ，用以描述语言

8、中的句子是怎样产生的。一组规则可以描述一个语言的语法结构。非终结符，一般在左边，它能派生出符号、符号串。用大写字母表示,如上述中的A。与之对应地，终结符用小写表示，由它不能派生出任何符号，是一个不可再分的基本单位，即字母表（）中的一个元素。2、文法的形式定义一个文法是规则的非空有穷集合。常用一个四元组表示，定义为G（VT，VN，S，P）其中： VT：所有终结符的集合 VN：所有非终结符的集合 S：开始符 P：规则式的集合EX:一个文法G（VT，VN，S，P）,其中：VT0, 1 所有终结符的集合 VNA 所有非终结符的集合 SA 开始符 PA01A0A1 规则式的集合Qu: 给定

10、：GA：ABDBaaaBaDbb|bDbNote1：给定一个语言时，文法不是唯一的。2：用文法描述语言时，要准确，既不能扩大也不能缩小。Ex2：用文法定义一个含，运算符的算术表达式。解1：非形式化描述，1、变量是一个表达式；2、若E1和E2是一个表达式，则E1E2、E1E2、（E1）也是一个表达式。解2：形式化描述：GE：E iEE + EE E | ( E )以上所描述的句子的集合为：i , ( i ), i+i, ii, i+ii, . Ex3：设计一个表示所有标识符 I 的文法。分析：标识符字母或字母开头的字母数字串。解1：形式化描述：GI：ILILIDLa | b | c z |

11、 A | B | C | Z |D1 | 2 | 3 | 9 |解2:GI：ILILDLa | b | c z | A | B | C | Z | D1 | 2 | 3 | 9 | Ex4：已知L ( n ) n | n 0, 1 , 2 , , 求文法G。解： L , ( ) ,( ), ( ), GS：S ( S )C1、字母表、符号串、符号串的长度、空串 C2、符号串运算：连接、符号串的幂 C3、集合的运算：集合乘、集合的幂、集合的闭包 C4、形式语言的描述：（1）枚举法描述（2）用文法描述 C5、文法的形式定义G（VT，VN，S，P）复习基本概念文法的作用是什么？第3讲四、语言的形

12、式定义 1、直接推导设X，Y是符号串，如果使用一次规则式可以从X推导出Y，则Y为X的直接推导。记为： XY Ex: 设GS：S0S101，则 S01 S 0S1 0S1 0011 0S1 00S11 2、+推导 (正推导）设X，Y是符号串，若使用一次或多次规则可以从X推导出Y，则Y为X的推导。记为：X YEx: 设GS：S0S101，则 S01 S 0S1 00S11 000111 所以 S 0001113、*推导 (广义推导）设X，Y是符号串，若使用0次或多次规则可以从 X推导出Y，则Y为X的*推导。记为：X YEx: 设GS：S0S101，则 SS S01 S 0S1 00S11

13、 000111 所以 S 000111区别: 直接推导长度1 正推导长度1 广义推导长度 0 即：直接推导正推导广义推导4、句型、句子设有文法GS，若从文法开始符号S x,则称符号串x为文法GS的句型；仅仅由终结符组成的句型叫句子。若x是一个句型，则x （VNVT）若x是一个句子，则x VTEx: S0S101 S 01 S 0S1 S 000111(句型、句子） (句型） (句型、句子）Ex: 设GE：EEEEE（E）i，试证明符号串( i * i + i )是文法GE的一个句子证明：从E出发，只要证明符号串x = ( i * i + i ) 对于文法GE 存在一个推导。 E

14、（E）（EE）（EEE）（ i*E+E）（i*i+E）（i * i + i ）以上从文法的开始符E ( i * i + i )，所以符号串( i * i + i )是GE的一个句子。5、语言L(GS) 对一个文法GS，其句子的全体所组成的集合即语言L(GS)。 L(GS)x | S x 且 xVT*换言之，文法描述的语言是该文法一切句子的集合。 Note1: 若文法给定，则语言也确定了。 2: 一个语言是所有终结符VT的子集（所有满足文法规定的终结符的集合）。VT*L(GS)Ex1:已知文法GS：S0S101，求L？ S 0S100S11 000S111 0n-1S1n-1 0n1n 即S 0n1n L(GS)=0n1n | n1Ex2:已知文法GS：S0S1S，求L？ L

展开阅读全文