编译原理讲义 (总论) 南京大学计算机系 赵建华
编译原理讲义 (总论) 南京大学计算机系 赵建华
课程目的 了解编译程序的实现原理和技术 利用从本课程学习到的知识,增强编写 和调试程序的能力。 在其它方面的应用: 正文查找; 正文处理 指令识别等
课程目的 • 了解编译程序的实现原理和技术。 • 利用从本课程学习到的知识，增强编写 和调试程序的能力。 • 在其它方面的应用： – 正文查找； – 正文处理； – 指令识别等
课程内容 文法/语言/自动机 词法分析技术 语法分析技术 语义分析技术 代码生成和优化技术
课程内容 • 文法/语言/自动机 • 词法分析技术 • 语法分析技术 • 语义分析技术 • 代码生成和优化技术
程序设计语言的定义(语法) 语法:是指规定如何基本符号组成 个完整的程厅的规则。可以分文一般的 语法规则和词法规则 定义语法的方式 语法图:直观,篇幅大。 BNF表示法:简洁,严谨,精确 自然语言:一般不使用在正式的文本中
程序设计语言的定义（语法） • 语法：是指规定如何由基本符号组成一 个完整的程序的规则。可以分文一般的 语法规则和词法规则。 • 定义语法的方式 – 语法图：直观，篇幅大。 – BNF表示法：简洁，严谨，精确。 – 自然语言：一般不使用在正式的文本中
语法图 程序 Program 标识符 标识符 分程序
语法图 Program 标识符 （ 标识符 ） ， . 分程序 ； 程序
BNF表示方式 ::=〈程序首部〉;〈程序分程序〉 程序首部〉:= Program〈标识符〉(〈程序 参数〉)
BNF表示方式 • ::= 〈程序首部〉 ; 〈程序分程序〉 • 〈程序首部〉::= Program〈标识符〉（〈程序 参数〉）
程序设计语言的定义(语义) 程序设计语言中按照语法规则所构成的 各个语法成分的意义。 定义方式: 般使用比较严格的自然语言进行描述。 形式化的方法:使用数学符号以没有歧义的 方式定义
程序设计语言的定义（语义） • 程序设计语言中按照语法规则所构成的 各个语法成分的意义。 • 定义方式： – 一般使用比较严格的自然语言进行描述。 – 形式化的方法：使用数学符号以没有歧义的 方式定义
程序的执行 程序设计语言的执行基本有两种方式: 解释方式:使用解释程序,对程序逐个语句 进行分析,根据语句的含义进行执行 翻译方式:首先由翻译程序将程序翻译成为 机器语言(或者虚拟机的语言),然后执行 比较: 翻译的方式可以使得一次翻译过后,多次运 行。适于花较大的精力进行优化工作
程序的执行 • 程序设计语言的执行基本有两种方式： – 解释方式：使用解释程序，对程序逐个语句 进行分析，根据语句的含义进行执行。 – 翻译方式：首先由翻译程序将程序翻译成为 机器语言（或者虚拟机的语言），然后执行。 • 比较： – 翻译的方式可以使得一次翻译过后，多次运 行。适于花较大的精力进行优化工作
编译程序的构造 前端:完成分析工作(机器无关) 词法分析:识别各个最小语法单位。 语法分析:识别出各个语法结构 语义分析:确定类型,类型/运算合法性检 査,识别含义和相应处理,静态语义检査。 ·后端:完成综合工作(机器相关) 优化:改善目标代码质量。 目标代码生成
编译程序的构造 • 前端：完成分析工作（机器无关） – 词法分析：识别各个最小语法单位。 – 语法分析：识别出各个语法结构。 – 语义分析：确定类型，类型/运算合法性检 查，识别含义和相应处理，静态语义检查。 • 后端：完成综合工作（机器相关） – 优化：改善目标代码质量。 – 目标代码生成
编译程序的分类 诊断型编译程序 优化型编译程序 可重定目标型编译程序 交叉型编译程序 增量型编译程序
编译程序的分类 • 诊断型编译程序 • 优化型编译程序 • 可重定目标型编译程序 • 交叉型编译程序 • 增量型编译程序