第01章 编译原理 引论

20
• 语法分析所依据的是语言的语法规则，语 言的语法规则通常是由递归规则来定义
• 如表达式和赋值语句可由下述递归规则来 定义：
– (1) 任何标识符是表达式； – (2) 任何常数是表达式； – (3) 若表达式1和表达式2都是表达式，则表达 式1+表达式2，表达式1*表达式2都是表达式； – (4) 赋值语句就可以用规则：标识符 = 表达式； 来定义。
14
§1.2 编译程序概述
自然语言翻译过程： 编译程序工作过程：
识别单词
分析句法 初步翻译 译文润饰 正式翻译
词法分析
语法分析
语义分析与中间代码产生
代码优化 目标代码生成
15
1. 词法分析
任务：输入源程序，对字符串扫描分解、识别出 单词(或单词符号、或简称符号)。 单词是高级语言中有实在意义的最小语法单位， 一般分为5类：保留字（begin、end、if、for、 while等）、标识符、常数、运算符和分界符（标 点符号、括号、注释符号等 依循原则：语言的词法规则 (或构词规则)
4
关于学习编译原理
课程特点:
• 理解性 • 技术性
考核：
• 作业、课堂练习及实验、考勤：30% • 笔试：70%
5
参考书
Compilers Principles， Techniques and Tools， A. V. AHO 编译原理典型题解析与实战模拟 刘春林、王挺等
6
7
§1.1 什么叫编译程序
38
表 0.5 四元式表 QT OPR OPN1 OPN2 RESULT (1) link (2) par INCWAP 1 M (3) par INCWAP 2 N (4) + M 1 K (5) + N 4 M (6) := K N (7) return
39
3. 出错处理
出错处理程序：发现源程序中的错误，把 有关错误信息报告给用户
编译原理
1
课程地位
编译理论与方法
• 计算机科学与技术中理论和实践相结合的最好典范 • ACM 图灵奖，授予在计算机技术领域作出突出贡献 的科学家
程序设计语言、编译理论与方法约占1/3
意义:
• 学习编译程序构造原理，技术 • 更好地理解高级语言 • 编译的原理和方法有助于构造一些实用的工具
44
5. 编译前端与后端(概念上) 源语言
前端
中间语言
后端
目标语言
• 编译前端：与源语言有关，如词法分析，语法 分析，语义分析与中间代码产生，与机器无关 的优化 • 编译后端 ：与目标机有关，与目标机有关的 优化，目标代码产生
目标代码生成器：把中间代码翻译成 目标程序。
35
2. 表格与表格管理
• 常见的表格:符号名表，常数表，标号表，入 口名表，过程引用表。 • 格式: 信息 名字
常量名 值
一个名字 变量名 类型、内存大小、地址
过程名 地址、参数 处理定义时 登记 处理引用时 查证
36
例: C程序段：
37
表 0.3 入口名表 ENT NAME INFORMATION (1) INCWAP 二目子程序, 入口四元 式:1 void INCWAP(int M，int N)
{
int K; START: K=M+1; M=N+4; N=K; }
表 0.4 标号表 LT NAME INFORMATION (1) START 四元式:(4)
中间代码：一种含义明确，便于处理的记号系统，
通常独立于具体的硬件，或者与现代计算机
的指令形式接近或者容易变换成现代计算机 的机器指令。
24
例：“四元式”三地址中间代码 算符 左操作数 右操作数 结果
对语句 Z = (X+0.418)Y/W 序号 1 2 3 算符 + / 左操作数 X T1 T2 右操作数 0.418 Y W 结果 T1 T2 Z
19
词法分析 线性分析 语法分析 层次结构分析
• 把源程序的单词序列依照语法结构按层次 分组，形成各类语法单元，组成语法短语 (表示成语法树) • id1=id2+id3*10
– Id1 id2 id3是变量 – 单词序列id2+id3*10是表达式 – id1=id2+id3*10是 "赋值语句"
void INCWAP(int M，int N) { int K; START: K=M+1; M=N+4; N=K; }
表 0.1 符号名表 SNT NAME INFORMATION M 形式参数，整 型，值参数 N 形式参数，整 型，值参数 K 整型，变量
表 0.2 常数表 CT 值 (VALUE) (1) 1 (2) 4
语法分析器：简称分析器，对单词符
号串进行语法分析(根据语法规则进行推导
或归约)，识别出各类语法单位，最终判断
输入串是否构成语法上正确的“程序”。
34
语义分析器和中间代码产生器：按照语义规 则对语法分析器归约出(或推导出)的语法单位进 行语义分析并把它们翻译成一定形式的中间代码。 优化器：对中间代码进行优化处理。
语义错：不符合语义规则，语义分析时检测 出来(静态语义)，有时要到运行时才 能检测出来(动态语义)。如：说明错 误、作用域错误、类型不一致等。
41
4. 遍 (Pass)——或趟 对源程序或源程序的中间结果从头到尾 扫描一次，并作有关处理生成新的中间结果 或目标程序。
42
阶段与遍是不同的概念。一遍可以由若干 段组成，一个阶段也可以分若干遍来完成
30
绝对指令代码 可立即执行 目 标 代 码 形 式 可重定位指令代码 借助连接装配程序把 各目标模块连接在一起，确定程序变 量 (或常数)在主存中的位置，装入内 存中指定的起始地址，使之成为绝对 指令代码 (大多数编译程序采用)。 汇编指令代码 汇编器汇编之后运行
31
某些情况下，为加速编译速度，某些
如：
(1) 词法分析，可以单独作为一遍；
(2) 更多时候将词法分析和语法分析合并为一遍； (3) 为处理方便，语法分析和语义分析与中间代 码 产生合并为一遍； (4) 优化要求高时，优化阶段分为多遍
43
一遍中若包含多个阶段时，各阶段穿插进行 词法分析+语法分析+语义分析与中间代码产生： 语法分析器为核心
10
• 解释程序 把源语言写的源程序作为输入，但不产 生目标程序，而是边解释边执行源程序本身
源程序
解释执行 解释 程序
结果
11
编译
• 编译程序先把全部源程序翻译为目标程序， 然后再执行；该目标程序可以反复执行；
12
解释
• 代表：BASIC语言 • 工作方式：边解释边执行
– 解释程序对源程序逐句地翻译执行，目标代码 只能执行一次，若需重新执行，则必须重新解 释源程序。效率低。
27
中间代码为：
序号 OP ARG1 ARG2 结果 注 解 (1) = 1 K K =1 (2) j< 100 K (9) 若100<K转至第(9)个四元式 (3) * 10 K T1 T1 =10*K；T1为临时变量 (4) + I T1 M M =I+T1 (5) * 10 K T2 T2=10*K；T2为临时变量 (6) + J T2 N N=J+T2 (7) + K 1 K K=K+1 (8) j (2) 转至第(2)个四元式 (9)
13
分类(按用途和侧重性)
诊断编译程序(Diagnostic Compiler)
开发、调试
优化编译程序(Optimizing Compiler)
提高代码效率
交叉编译程序(Crossing Compiler)
产生不同于宿主机的机器代码
可变目标编译程序(Retargetable Compiler)
不需重写与机器无关的部分即可改变目标机
仅300次加
29
5. 目标代码生成 任务：把中间代码(或优化后)变换成特定 机器上的低级语言代码。 非常复杂：最后的翻译，有赖于硬件系 统结构和机器指令含义，涉及到硬件功能部件 的运用，机器指令的选择，各种类型变量的空 间分配，以及寄存器和后援寄存器的调度等。 如何产生出足以发挥硬件效率的目标代码是一 件非常不容易的事情。
2
课程目的
掌握和理解编译系统的结构、工作流程以及
编译程序各组成部分的设计原理和实现技术，
获得分析、设计、实现和维护编译系统的初
步能力；
通过学习编译的理论和方法，提高对程序设
计语言、操作系统、计算机原理和体系结构
等课程知识的综合理解。
3
学习方法
认真听课，认真理解书中的基本概念、基本 原理和基本算法 弄懂书中的例题和习题 在看书时或理解例题时，一定要画出相应的 细节变化过程，通过画图来加深理解 在理解的基础上记忆 理论结合实践
描述方法：上下文无关文法
18
词法分析 线性分析
语法分析 层次结构分析 • 识别标识符，因为标识 符的结构是字母打头的 字母和数字串，这只要 顺序扫描输入流，遇到 既不是字母又不是数字 字符时，将前面所发现 的所有字母和数字组合 在一起而构成单词标识 符 • 不能用于识别递归定 义的语法成分，比如 就无法仅用线性扫描 去匹配表达式中的括 号
最大限度发现各种错误，准确指出其性质 及地点，并将其影响限制在尽可能小的范围， 使源程序其它部分能继续被编译，以进一步发 现其它可能的错误。
40
绝大多数错误可在编译的前三阶段检测出来： 语法错：不符合词法规则(“非法字符”， 5X，256.)、或不符合语法规则(“括 号不匹配”，x=(a+(b*c)-1、“缺少；” 等)。