第一章编译程序概论 目的：1.了解三种翻译程序 2.弄清编译过程 3.建立整体概念 一，翻译程序 源程序 翻译程序 目标程序 即源程序是翻译程序的输入，目标程序是翻译程序的输 ●翻译程序：将源程序转换为目标程序的程序。 它是指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序，编译程序以及各种 变换程序的总称。 序：用目标语言所表示的程 目标语言：可以是介于源语言和机器语言之间的“中间语言”，可以是某种机器的机器 语言，也可以是某机器的汇编语言。 ●低级语言：字位码，机器语言，汇编语言 特点：与特定的机器有关，功效高，但使用复杂，繁琐，节时，易出错。 ●高级语言： 特点：依赖具体机器，移植性好，对用户要求低，易使用，易维护等。 翻译程序包括 汇编程序：汇编语言程序一一> 机器语言程序 编译程序：高级语言程序一—> 低级语言程序（机器语言，汇编语言） 解释程序：对源程序逐条解释执行，才生成目标代码 编译程序和汇编程序主要区别：加工对象不同，由于汇编语言格式简单，常与机器 语言之间有一一对应的关系，所以汇编程序所作的翻译工作比编译程序简单的多。 编辑 一编译汇编 运行 翻译或汇编阶段 源程序 一>编译或汇编 一>目标程序 运行阶段输入数据一一>目标程序+运行子程序一一>输出数据 解释程序工作过程： 源程序 输入数据 >解释程序 —>输出数据 编译一解释执行系统： 源程序 编译程序 源程序的中间形成 输入数据一——>解释程序一一>输出数据 编译程序：
第一章 编译程序概论 目的：1.了解三种翻译程序 2.弄清编译过程 3.建立整体概念 一．翻译程序 源程序 ——> 翻译程序 ——> 目标程序 即源程序是翻译程序的输入，目标程序是翻译程序的输出 ● 翻译程序：将源程序转换为目标程序的程序。 它是指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序，编译程序以及各种 变换程序的总称。 ● 源程序：用汇编程序或高级语言编写的程序称为源程序。 ● 目标程序：用目标语言所表示的程序。 目标语言：可以是介于源语言和机器语言之间的“中间语言”，可以是某种机器的机器 语言，也可以是某机器的汇编语言。 ● 低级语言：字位码，机器语言，汇编语言 特点：与特定的机器有关，功效高，但使用复杂，繁琐，节时，易出错。 ● 高级语言：Fortran，C，Pascal 特点：依赖具体机器，移植性好，对用户要求低，易使用，易维护等。 翻译程序包括 汇编程序：汇编语言程序 ——> 机器语言程序 编译程序：高级语言程序 ——> 低级语言程序（机器语言，汇编语言） 解释程序：对源程序逐条解释执行，才生成目标代码 编译程序和汇编程序主要区别：加工对象不同，由于汇编语言格式简单，常与机器 语言之间有一一对应的关系，所以汇编程序所作的翻译工作比编译程序简单的多。 编辑——编译/汇编——运行 翻译或汇编阶段 源程序——>编译或汇编——>目标程序 运行阶段 输入数据——>目标程序+运行子程序——>输出数据 解释程序工作过程： 源程序 ↓ 输入数据——>解释程序——>输出数据 编译—解释执行系统： 源程序 ↓ 编译程序 ↓ 源程序的中间形成 ↓ 输入数据——>解释程序——>输出数据 编译程序：
编译系统 操作系统 裸机 例：C+ >C+编译器 -C Java >Java编译器 >Bytecod (一种高级语言至少对应一种编译程序) 二：编译过程和编译程序的结构 如图p3图13 1. 词法分析（描器 任务：分析和识别单词 单词：是语言的基本语法单位，一般语言有五大类单词 (标识符，保留字，算符，界符，常数) 设计者确定约定 词法规则：规则（约定） 实现者写编译程序 使用者用高级语言编写程序 2.语法分析 任务：单词一>句子（语法单位）一>检查（正确或错误） 语法规则： 即语言的文法 例：先给定文法： 一> 一>= 一之 3.语义分析和中间代码生产 检查语义是否正确 ,翻译中间代码 ●中间代码：一种介于源语言和目标语言之间的中间语言形成 生产中间代码的目的： 便于做优化处理 便于编译程序的移植（中间代码不依赖于目标算法） ● 1.一种高级语言一>不同机器上 2.多种高级语言一>同一机器上
例：C++ ——>C++编译器 ——>C Java ——>Java 编译器 ——>Bytecode （一种高级语言至少对应一种编译程序） 二：编译过程和编译程序的结构 如图 P3 图 1.3 1． 词法分析（扫描器） 任务：分析和识别单词。 单词：是语言的基本语法单位，一般语言有五大类单词 （标识符，保留字，算符，界符，常数） 设计者 确定约定 词法规则： 规则（约定） 实现者 写编译程序 使用者 用高级语言编写程序 2.语法分析 任务： 单词—>句子（语法单位）—>检查（正确或错误） 语法规则： 即语言的文法 例： 先给定文法： —> —> —> := —> . 3.语义分析和中间代码生产 检查语义是否正确 —> 翻译中间代码 ● 中间代码： 一种介于源语言和目标语言之间的中间语言形成 生产中间代码的目的： 便于做优化处理 便于编译程序的移植（中间代码不依赖于目标算法） ● 1.一种高级语言 —> 不同机器上 2.多种高级语言 —> 同一机器上 例： 编译系统 操作系统 裸机
C语言 C语言 Pascal 1 词法分析 词法分析 词法分析 语法分析 语法分析 语法分析 中间代码 中间代码 A机 B机 C机 机器 中间代码形成：编译程序设计者可自行设计。四元式，三元式，逆波兰式等。 4.代码优化 任务：得到高质量的程序（省时，省空间） 例：X=l:y=2:Z 优化 Z2: 例：fork=1to100do 优化后m-斗，nJ Begin for k:=1 to 100 do m=+10*k begin n=J+10*k m=m+10,n=n+10, nd 做300次“+” 200次“*” 做300次“+”，不做“ 5.目标代码的生产 ”1.绝对指令代码 目标代码 2.可重定位的指令代码 3.汇编指令代码 绝对指令代码：直接将程序装入内存中确定的位置 可重定位的指令代码：每个程序开始都是0，需要时装入内存 6.表格管理和出错处理 ●表格管理（符号表组织）：在整个编译过程中始终贯穿着建表（填表 和查表的工作，即把源程序和编译过程中的信息登记在表格，随后编译过程中查找 ●出错处理：出错处理能力的优劣是衡量一个编译程序质量好坏的重要指标，但它只能 判断所有语法错误和部分语义错误 7遍(pass) 前出和后端 ●遍：对源程序（包括其中间形式）从头到尾扫描一次，并做有关的加工处理，生成新的 源程序中间形式或目标程序称为遍， 第一逾 弟一通 S.P->C1->S.P->C2->S.P-> ->O.P ●前端：与源程序有关的编译部分称为前端 词法分析.代码优化一分析部分 ●后端：与目标机有关的优化，目标程序生成（与目标机有关的优化）一综合部分 ,语法和语义 ,高级语言编写 8编译程序结构的三要素 2.目标计算机系统和操作系统 2.使用工具自动生成 3. 生产的方法一> 3.移植
C 语言 C 语言 Pascal ↓ ↓ ↓ 词法分析 词法分析 词法分析 ↓ ↓ ↓ 语法分析 语法分析 语法分析 ↓ ↘ ↙ 中间代码 中间代码 ∕ ∣ ﹨ ∣ A 机 B 机 C 机 机器 中间代码形成：编译程序设计者可自行设计 。 四元式，三元式，逆波兰式等。 4.代码优化 任务：得到高质量的程序（省时，省空间） 例：x=1；y=2；z=x*y 优化： z=2； 例：for k:=1 to 100 do 优化后 m:=I; n:=J; Begin for k:=1 to 100 do m:=I+10*k; begin n :=J+10*k; m:= m+10; n:=n+10; end; end; 做 300 次“+”，200 次“*” 做 300 次“+”，不做“*” 5.目标代码的生产 1.绝对指令代码 目标代码 2.可重定位的指令代码 3.汇编指令代码 绝对指令代码：直接将程序装入内存中确定的位置 可重定位的指令代码： 每个程序开始都是 0，需要时装入内存 6.表格管理和出错处理 ●表格管理（符号表组织） ： 在整个编译过程中始终贯穿着建表（填表） 和查表的工作，即把源程序和编译过程中的信息登记在表格，随后编译过程中查找 ● 出错处理： 出错处理能力的优劣是衡量一个编译程序质量好坏的重要指标，但它只能 判断所有语法错误和部分语义错误 7.遍（pass） 前端和后端 ●遍：对源程序（包括其中间形式） 从头到尾扫描一次，并做有关的加工处理，生成新的 源程序中间形式或目标程序 称为遍。 第一遍 第二遍 S.P —> C1 —> S.P —> C2 —> S.P —> . —> O.P ●前端： 与源程序有关的编译部分称为前端 词法分析.代码优化 — 分析部分 ●后端： 与目标机有关的优化，目标程序生成（与目标机有关的优化） — 综合部分 1.语法和语义 1.高级语言编写 8.编译程序结构的三要素 2.目标计算机系统和操作系统 2.使用工具自动生成 3. 生产的方法 —> 3.移植
开发过程：分析，设计，编辑，调试，形成文本 第二章 文法和语言 目标：1掌握符号串，符号串集合的运算，文法和语言的定义 2几个重要概念：递归，短语，简单短语，句柄，语法树，文法的二义性，文法的 实用限制等 3.掌握文法的表示：BNF,扩充的BNF范式，语法图 4.了解文法和语言的分类 §2.1预备指使一语言概述 ●语言：是由句子组成的集合，是由一组记号所构成的集合 例：汉语：所有符合汉语语法的句子的全体。 程序设计语言： 所有该语言的程序的全体 每个句子（程序）构成的规往 ●研究语言（程序设计语言） 每个句子（程序）的含义 每个句子（程序）和使用者的关系 语言：语言的构成规 ●语言研究的三个方面 语义：语言所代表的含义 语用：涉及到实际应用 一语法：表示构成语言句子的各个记号之间的组合规律 一语义：表示按照各种表示方法所表示的各个记号的特定含义（各个记号和记号所表示的对 象之间的关系) 一语用：表示各个记号所出现的行为中，它们的来源，使用和影响 一文法：语言的完整的语法描述，是形式语言理论的基本概念 形式语言：如果不考虑语义和语用，只从语法这 一侧面来看语言，这种意义下的语言成 为形式语言。形式语言抽象的定义为一个数学系统，“形式”是指这样一个事实，语言 的所有规则只以什么符号串能出现的方式来陈述固定的规格样式。形式语言理论是对符 号串集合的表示法，结构及其性能的研究，是程序设计语言语法分析研究的基础 §2.2符号和符号串 。1.符号和符号串 ●字母表：元素的非空有穷集合 ●符号（字母）：字母表中的元素，不能分解的最小单位 ●符号串：字母表中的符号组成的任何有穷序列 ●空符号串：不包含任何符号的符号串Σ ●符号串集合：字母表∑上的符号串组成的集合 ●符号串长度：符号串中符号的个数 ●符号串连接：例：x=ab,y=123,y=ab123,yx=123ab,灯≠yx,ξx=x5=x=ab, lxyl=xl+lyl=lyxl
开发过程：分析，设计，编辑，调试，形成文本。 第二章 文法和语言 目标：1.掌握符号串，符号串集合的运算，文法和语言的定义 2.几个重要概念： 递归，短语，简单短语，句柄，语法树，文法的二义性，文法的 实用限制等 3.掌握文法的表示：BNF，扩充的 BNF 范式，语法图 4.了解文法和语言的分类 §2.1 预备指使 — 语言概述 ●语言：是由句子组成的集合，是由一组记号所构成的集合 例：汉语：所有符合汉语语法的句子的全体。 程序设计语言：所有该语言的程序的全体。 每个句子（程序）构成的规律 ●研究语言（程序设计语言） 每个句子（程序）的含义 每个句子（程序）和使用者的关系 语言:语言的构成规则 ●语言研究的三个方面 语义：语言所代表的含义 语用：涉及到实际应用 —语法：表示构成语言句子的各个记号之间的组合规律 —语义：表示按照各种表示方法所表示的各个记号的特定含义（各个记号和记号所表示的对 象之间的关系） —语用：表示各个记号所出现的行为中，它们的来源，使用和影响 —文法：语言的完整的语法描述，是形式语言理论的基本概念 ● 形式语言：如果不考虑语义和语用，只从语法这一侧面来看语言，这种意义下的语言成 为形式语言。形式语言抽象的定义为一个数学系统，“形式”是指这样一个事实，语言 的所有规则只以什么符号串能出现的方式来陈述固定的规格样式。形式语言理论是对符 号串集合的表示法，结构及其性能的研究，是程序设计语言语法分析研究的基础 §2.2 符号和符号串 一．1.符号和符号串 ●字母表：元素的非空有穷集合 ●符号（字母）：字母表中的元素，不能分解的最小单位 ●符号串：字母表中的符号组成的任何有穷序列 ●空符号串：不包含任何符号的符号串∑ ●符号串集合：字母表 ∑ 上的符号串组成的集合 ●符号串长度：符号串中符号的个数 |x| ●符号串连接：例：x=ab，y=123，xy=ab123，yx=123ab，xy≠yx，ξx=xξ=x=ab， |xy|=|x|+|y|=|yx|
●符号串方幂：x”例：X=abc,x=ξ，x=abc,x2=abcabc,.即x的n次连接 ●符号串的前缀，后缀，子串：例：u=abb,前缀：，a,ab,abb,b,bb。 2.符号串集合 (注意，集合只看元素 不 例a,b)=b,a ○符号串集合的乘积：A,BA证(xEA且y∈B,(5)AA() 例：A={a,b,B={00,0l,10,A=(a00,a0l,al0,b00,b01,b10} A={xy,yz,zx),B=(ab,be,ca],AB=(xyab,xybe,xyca,yzab, ●符号串生合的方幂：A°=E1.A1=A.A2=AA,A3=AA2=A2A b,A=(5，A- b)(aa,ab,ba,bb) .即符号串的n次方乘积 符号串的闭包与正闭包：UUPL 例：A={a,A"={}U{aU{aaU{aaaU: .={ξ，a,aa,aaa, B={a,b,B=(5}U{a,b}U{aa,ab,ba,bb}U{aaa,aab,.U.两元素a,b任意组合组 成的集合加上ξ，即为 正闭包：A为除ξ以外的所有符号串的集合 例：A=a,b,A =(a,b,ab,ba,bb ,A*={5,a,b,ab, 二。为什么对符号，符号串，符号串集合以及它们的运算感兴趣 若A为某语言的基本字符集，A={a,b,.,Z,0,1,.,9,+,-,/,(),=. B为单词集B=(begin,end,if,then,else,for,，， 则B包含于A· 语言的句子是定义在B上的符号串 若令C为句子集合，则C包含于，程序包含于C §2.3文法和语言 ●如何描述一种语言，定义句子的合法性 语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示 语言是无穷的，需找出语言的有穷表示，两个途径（生成方式，识别方式 生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造，BNF范式 识别方式（自动机）：用一个过程，当输入的任一串属于语言时，该过程经有限次计 算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下 去，语法图通过一组转换图来识别合法的句子。 ●BNF范式：一>true/false,或叫非终结符，t e,false叫终结符 ●元语言：用来描述其它语言的语言，如上式BF范式用来描述C语言等 ●元符号：◇，1，一> 例：一〉|->AlB C.Zlalb.z (数字>一>011121.9 例：验证a4y是否是标识符：（用试探的方法，不成功再回溯 =〉=〉4故回潮.=)〈字母>=)〈)y =)〈标识符>4y=>〈字母>4y=>a4y ●语法图
●符号串方幂：x n 例：x=abc，x 0 =ξ，x 1 =abc，x2=abcabc，. 即 x 的 n 次连接 ●符号串的前缀，后缀，子串：例：u=abb，前缀：ξ，a，ab，abb，b，bb。 2.符号串集合 （注意，集合只看元素，不看顺序，例 A=｛a，b｝=B=｛b，a｝ ●符号串集合的乘积：A，B AB=｛xy|x∈A 且 y∈B｝，｛ξ｝A=A｛ξ｝=A 例：A=｛a，b｝，B=｛00，01，10｝，AB=｛a00，a01，a10，b00，b01，b10｝ A=｛xy，yz，zx｝，B=｛ab，bc，ca｝，AB=｛xyab，xybc，xyca，yzab，.｝ ● 符号串集合的方幂： A 0 =｛ξ｝，A 1 =A，A 2 =AA，A 3 = A A 2 = A 2 A ● A=｛a，b｝，A 0 =｛ξ｝，A 1 =｛a，b｝，A 2 =｛aa,ab,ba,bb｝,. 即符号串的 n 次方乘积 ● 符号串的闭包与正闭包：A * =A0∪A 1∪A 2∪. 例：A={a},A* ={ξ}∪{a}∪{aa}∪{aaa}∪. ={ξ,a,aa,aaa,.} B={a,b},B* ={ξ}∪{a,b}∪{aa,ab,ba,bb}∪{aaa,aab,.}∪.两元素 a,b 任意组合组 成的集合加上ξ，即为 B * 正闭包：A +为除ξ以外的所有符号串的集合 A * =A0∪A + 例：A={a,b},A+={a,b,ab,ba,bb,.},A*={ξ,a,b,ab,.} 二．为什么对符号，符号串，符号串集合以及它们的运算感兴趣 若 A 为某语言的基本字符集，A={a,b,. ,z,0,1,.,9,+,-,/,(,),=.} B 为单词集 B={begin,end,if,then,else,for,.,,,.} 则 B 包含于 A * 语言的句子是定义在 B 上的符号串 若令 C 为句子集合，则 C 包含于 B *，程序包含于 C §2.3 文法和语言 ● 如何描述一种语言，定义句子的合法性 语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示 语言是无穷的，需找出语言的有穷表示，两个途径（生成方式，识别方式） 生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造，BNF 范式 识别方式（自动机）：用一个过程，当输入的任一串属于语言时，该过程经有限次计 算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下 去，语法图通过一组转换图来识别合法的句子。 ● BNF 范式： —> true/false,或<> ::= t/f,“~”由.组成，定义为以上式子 叫“产生式”，或“BNF 规则” 叫非终结符，true,false 叫终结符 ● 元语言：用来描述其它语言的语言，如上式 BNF 范式用来描述 C 语言等 ● 元符号：<> ,|,—> 例： —> | | —> A|B|C.|Z|a|b|.|z —> 0|1|2|.|9 例：验证 a4y 是否是标识符；（用试探的方法，不成功再回溯） => => 4 故回溯. => => y => y => 4y => 4y => a4y ● 语法图
标识符一〉字母 字母一A一一〉 数字 →字母一 或|一B→ 或11 1一数字一 」→C* 1→2→1 1.规则：V一>x或V:=x 2.文法：G=(w,T,P,S),:非终结符集：：终结符集：P:产生式（规则）集合：S 开始符 例：G[A]:A->B跳，B->a则：VN=,B，VT=a,b,S=A,P=(A->B,B->a 字母表：V=UV={A,B,a,b} V={5,A,B,a,b,AB,Aa,.,={A,B,a,b,Aa,AbV包含于V,V,包含于 3.推导和归约：上例：A一》Bh,B一>a Bb =>&ab 例：S 051,s->01,递归 直接推导：0S1=〉0011 或S->051-0011=000111 推导：S=>0S1,S=>0011,S=>000S111, S=S或S=》x.则S=x,经时0步或若干步，S=>S.S=》0S1.+ 4.规范推导，规范归约，又叫做最右推导，归约 例：G[E]:E一>TE+T,T一>FT*R,F一>(E)L,判断i+i是否是句子 最右：E=E+T=)E=)B+IT+IF+I>i+1 最左：E=)E+灯=〉T+T=〉F+灯=〉itT=〉if=〉ii -般推导：E=>E+T=》T+T=>T+F=>T+I=>F+I=>i+i 5句型，句子，语言 一句型：G[S],S=〉xx∈，则x是G[S]的句型 [S],SXxeV,则x是G[S]的句子 -语言：G[S],L(G[S])=xS=>x,x∈V 6.文法等价：若L(G)L(Gz),则文法G和G等价
标识符 —> 字母 —————> 字母 —> A ——> 数字——>0——> ∣→字母→∣ 或 ∣→B →∣ 或∣→1→∣ ∣→数字→∣ ∣→C →∣ ∣→2→∣ 1. 规则： V —> x 或 V::=x 2. 文法：G=（VN，VT,P,S）, VN : 非终结符集；VT : 终结符集；P:产生式（规则）集合；S： 开始符号 例：G[A]：A—>Bb,B—>a 则：VN={A,B},VT={a,b},S=A,P={A—>Bb,B—>a} 字母表 ：V=VN∪VT ={A,B,a,b} V * ={ξ,A,B,a,b,AB,Aa,.},V+ ={A,B,a,b,Aa,Ab.} VN 包含于 V *，VT 包含于 V * 3.推导和归约：上例：A—> Bb,B—>a Bb =>ξab 例：S—> 0S1，S —> 01,递归 直接推导：0S1 => 0011 或 S—> 0S1 => 00S11 => 000111 推导：S => 0S1,S => 0011,S => 000S111,. S=S 或 S => x,则 S => x,经过 0 步或若干步，S => S,S => 0S1,. 4.规范推导，规范归约，又叫做最右推导，归约 例：G[E]:E —> T|E+T,T —> F|T*F,F —> (E)|I,判断 i+i 是否是句子 最右：E => E+T => E+F => E+I => T+I => F+I => i+i 最左：E => E+T => T+T => F+T => i+T => i+F => i+i 一般推导：E => E+T => T+T => T+F => T+I => F+I => i+i 5.句型，句子，语言 —句型：G[S],S => x,x ∈ V * ,则 x 是 G[S]的句型 —句子：G[S]，S => x,x ∈ V * T，则 x 是 G[S]的句子 —语言：G[S],L(G[S])={x|S => x,x ∈ V * T} 6.文法等价：若 L（G1）=L（G2），则文法 G1 和 G2 等价