编译器将高级语言编写的源程序翻译成低级语言程序。.pptVIP

编译程序是将高级语言书写的源程序翻译成低级语言程序。一般包括词法分析，语法分析，中间代码生成，代码优化，目标代码生成五个部分，还应该包括表格管理和出错处理。 其中中间代码生成和代码优化并不是每个程序都需要的。 词法分析器用于识别单词，语法分析器用于发现源程序中的语法错误。 代码优化一般都是在中间代码级上完成的，对中间代码的优化可以使目标程序的运行时间更短或所占的空间更少。;算符 ;第2章　文法和语言;2.1　引言 ;2.2　符号串;一、字母表和符号串;2、符号与符号串 符号（字符）：一个符号是字母表中的元素。 符号串：是符号的有穷序列。 EX1： Σ＝{a, b, c}，则a, b, c, ab, ba都是Σ上的符号串。 Note1：符号串的顺序很重要，如：ab≠ba; 2：不含任何符号的符号串称为空串，用　　　ε 表示。 符号串长度：｜a｜＝1，｜ab｜＝2，｜ ε｜＝0 ;二、符号串的运算;2、集合的乘积 设A、B是符号串的集合，则定义A与B的乘积为： AB＝{xy | x?A, y ? B} EX: A={a, b}, B={c, d}，则AB ={ac,bc,ad,bd} A{?}={?}A=A {?} ?{ }, { }= ?;3、符号串的幂运算 设X是符号串，则X0＝ ? 　　注： X0 ≠1X1＝XX2＝XXXn＝ XX……X;4、集合的幂运算 设A是符号串的集合，则定义： A0＝{?} A1＝A A2＝AA An＝AA……A＝An-1A;5、集合的闭包（A+和A＊） 设A是任意一个集合，则定义： A+＝A1 ∪ A2 ∪ A3… A*＝A0 ∪ A+ 　＝A0 ∪ A1 ∪ A2…… ;2.3　文法与语言的形式意义;一、形式语言;句子 ? 主语谓语间接宾语直接宾语 ? 代词谓语间接宾语直接宾语 ? He谓语间接宾语直接宾语 ? He动词间接宾语直接宾语 ? Hegave间接宾语直接宾语 ? Hegave代词直接宾语 ? Hegaveme直接宾语 ? Hegave me冠词名词 ? Hegave mea名词 ? Hegave meabook;句子;二、形式语言的描述;方式二：当语言为无穷集合时，用文法表示。 EX(续上例）： 设用A表示∑，用式子A?0表示0∈A（读作：“A产生0”）。 符号：“?”定义为“产生”、“生成”、“导出”等。 反复用 A?0 A?1 A?A0 A?A1 以上四条规则式，则可以生成无穷的集合。;三、文法的形式定义;2、文法的形式定义 一个文法是规则的非空有穷集合。常用一个四元组表示，定义为 　G＝（VT，VN，S，P） 其中： VT：所有终结符的集合 VN：所有非终结符的集合 S：开始符 P：规则式的集合;EX: 一个文法G＝（VT，VN，S，P）,其中： VT＝｛0,　1｝　　　　　　所有终结符的集合 VN＝｛A　｝　　　　　 　 所有非终结符的集合 S＝A　　　　　　　　　　 开始符 P＝｛A?0｜1｜A0｜A1｝　规则式的集合;Qu: 给定一个语言L，如何求文法G？;另解：P：A?B｜D B?aa｜aBa D?bb|bDb ∴ 文法G＝（VT，VN，S，P）,其中： 　　　VT＝｛a,　b｝，VN＝｛A，B，D｝，S＝A 　　　P＝{A?B|D, B?aa|aBa, D?bb|bDb} 　　;Note1：给定一个语言时，文法不是唯一的。 　　2：用文法描述语言时，要准确，既不能扩大也不能缩小。;Ex3：设计一个表示所有标识符 I 的文法。;Ex4：已知L＝｛ ( n ) n | n ＝0, 1 , 2 , ……} , 求文法G。;1、字母表、符号串、符号串的长度、空串 2、符号串运算：连接、符号串的幂 3、集合的运算：集合乘、集合的幂、集合的闭包 4、形式语言的描述：　　（1）枚举法描述　　（2）用文法描述 5、文法的形式定义　　G＝（VT，VN，S，P）;四、语言的形式定义;2、+推导　(正推导） 设X，Y是符号串，若使用一次或多次规则可以从X推导出Y，则Y为X的＋推导。 　记为：X ? Y;3、*推导　(广义推导） 设X，Y是符号串，若使用0次或多次规则可以从X推导出Y，则Y为X的*推导。 　记为：X ? Y;4、句型、句子 设有文法G[S]，若从文法开始符号S ?x,则称符号串x为文法G[S]的句型；仅仅由终结符组成的句型叫句子。 若x是一个句型，则x ? （VN?VT）＊ 若x是一个句子，则x ? VT＊;Ex: 设G[E]：E?E＋E｜E＊E｜（E）｜i，试证明符号串( i * i + i )是文法G[E]的一个句子