骨架程序 预处理器 源程序 编译器 可重定位目标文件库 目标汇编程序 汇编器 可重定位机器代码 →配连接编辖 语言处理过程 绝对机器码
• 预处理器 编译器 汇编器 装配连接编辑 骨架程序 源程序 目标汇编程序 可重定位机器代码 绝对机器码 可重定位目标文件库 语言处理过程
编译逻辑过程 词法分析 语法分析 语义分析 中间代码生成 中间代码优化 目标代码生成 目标代码优化
编译逻辑过程 词法分析 语法分析 语义分析 中间代码生成 中间代码优化 目标代码生成 目标代码优化
词法分析程序 语法分析程序 表格管理 语义分析程序 中间代码生成程序 出错处理 代码优化程序 目标代码生成程序
出 错 处 理 语法分析程序 语义分析程序 目标代码生成程序 词法分析程序 中间代码生成程序 代码优化程序 表 格 管 理
认知层次 代码优化 目标程序运行时的存储组织和代码生成 语法制导翻译和中间代码生成 符号表和静态语义分析 自底向上分析程序 自顶向下分析程序 语法分析程序 词法分析程序 PL/0编译程序剖析
认知层次 代码优化 目标程序运行时的存储组织和代码生成 语法制导翻译和中间代码生成 符号表和静态语义分析 自底向上分析程序 自顶向下分析程序 语法分析程序 词法分析程序 PL/0编译程序剖析
课程目标 基本理论 正规式,有穷自动机 上下文无关文法及其句型分析 属性文法 基本知 程序设计语言有关概念(作用域,类型) 如何设计编译器(前后端,中间语言,分遍) 基本技能 (使用工具)实现编译器 ·进一步研究的基础 代码优化 编译器后端的设计和实现
课程目标 • 基本理论 正规式，有穷自动机 上下文无关文法及其句型分析 属性文法 • 基本知识 程序设计语言有关概念(作用域，类型） 如何设计编译器（前后端，中间语言，分遍） • 基本技能 （使用工具）实现编译器 • 进一步研究的基础 代码优化 编译器后端的设计和实现
正规式,有穷自动机 正规式一正规集的描述机制 字母表∑上的正规表达式R的文法终结 符是{|,*,a∈Σ} 0)R→>82)R→>RR4)R→>a 1)R→>R|R3)R→>R* 有穷自动机一正规集的识别机制
正规式，有穷自动机 • 正规式－正规集的描述机制 字母表上的正规表达式R的文法,终结 符是{ | ， * ， a }. 0) R –> 2) R –> RR 4) R –> a 1）R –> R | R 3) R –> R* • 有穷自动机－正规集的识别机制
程序设计语言的单词都能用正规式来定义. 例3.1 令2={,d}),则∑上的正规式r1(1d)“定义的正 规集为 dldd 其中代表字母d代表 数字,规式即是字母(字母数字)*它表示的 正规集中的每个元素的模式是“字母打头的字 母数字串”,就是 Pasca和多数程序设计语言允 许的的标识符的词法规则 例32 ∑={d,·,e,+,-}, 则Σ上的正规式dd*|e(+|-|e)d+|e) 表示的是无符号数的集合。其中d为0~9的数字
程序设计语言的单词都能用正规式 来定义. 例3.1 令={l，d}，则上的正规式 r=l(l d) 定义的正 规集为: {l,ll,ld,ldd,……},其中l代表字母,d代表 数字,正规式 即是 字母(字母|数字) ,它表示的 正规集中的每个元素的模式是“字母打头的字 母数字串” ,就是Pascal和 多数程序设计语言允 许的的标识符的词法规则. 例3.2 ={d，•，e，+，-}, 则上的正规式 d (•dd )(e(+- )dd ) 表示的是无符号数的集合。其中d为0~9的数字
有穷自动机 确定的有穷自动机DFA 不确定的有穷自动机NFA NFA的确定化 DA的最小化
有穷自动机 确定的有穷自动机DFA 不确定的有穷自动机NFA NFA的确定化 DFA的最小化
文法和语言 如何来描述一种语言? 如果语言是有穷的(只含有有穷多个句子),可以 将句子逐一列出来表示 如果语言是无穷的,找出语言的有穷表示。语言的 有穷表示有两个途经: 生成方式(文法):语言中的每个句子可以用严 格定义的规则来构造。 识别方式(自动机):用一个过程,当输入的一任 意串属于语言时,该过程经有限次计算后就会停止 并回答“是”,若不属于,要麽能停止并回答“不 是”,(要麽永远继续下去。)
文法和语言 如何来描述一种语言？ 如果语言是有穷的（只含有有穷多个句子），可以 将句子逐一列出来表示 如果语言是无穷的，找出语言的有穷表示。语言的 有穷表示有两个途经： 生成方式 （文法）：语言中的每个句子可以用严 格定义的规则来构造。 识别方式（自动机）：用一个过程，当输入的一任 意串属于语言时，该过程经有限次计算后就会停止 并回答“是”，若不属于，要麽能停止并回答“不 是”，（要麽永远继续下去。）
定义 文法G定义为四元组(VN,Vr,P,S)其中 V:非终结符号(或语法实体,或变量)集; VT终结符号集; P:产生式(也称规则)的集合; Vτ和P是非空有穷集 S:称作识别符号或开始符号的一个非终结符,它至 少要在一条产生式中作为左部出现 V和Ⅴr不含公共的元素,即Vx∩Vr=中 用Ⅴ表示VN∪Vr,称为文法G的字母表或字汇表 规则,也称重写规则、产生式或生成式,是形如 α→B或∷=β的(a,β)有序对,其中α是字母表V 的正闭包V中的一个符号,β是V*中的一个符号 α称为规则的左部,β称作规则的右部
定义 文法G定义为四元组(VN，VT，P，S )其中 VN:非终结符号(或语法实体，或变量)集； VT:终结符号集； P:产生式(也称规则)的集合； VN，VT和P是 非空有穷集。 S:称作识别符号或开始符号的一个非终结符，它至 少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN ∩ VT = φ 用V表示VN ∪ VT ，称为文法G的字母表或字汇表 规则，也称重写规则、产生式或生成式，是形如 →或 ∷=的( ，)有序对，其中是字母表V 的正闭包V+中的一个符号，是V*中的一个符号。 称为规则的左部， 称作规则的右部