编译原理(龙书)第二版

引论

……

编译技术的应用

新计算机体系结构的设计

计算机体系结构设计的早起, 编译器在机器建好后开发.

而现在, 使用高级程序设计语言是一种规范, 决定一个计算机系统性能的不是它的原始速度, 还包括编译器能够以何种程度利用其特征. 因此, 在现代计算机体系结构开发中, 编译器在处理器设计阶段就进行开发.

RISC

Reduced Instruction-Set Computer 精简指令集计算机

在RISC之前, 趋势是开发的指令集越来越复杂, 以使得汇编编程变得更容易. CISC(Complex Instruction-Set Computer)

专用体系结构

数据流机器, 向量机, VLIW(非常长指令字)机器, SIMD(单指令, 多数据)处理器阵列, 心动阵列(systolic array), 共享内存的多处理器, 分布式内存的多处理器. 每种体系结构概念的发展伴随着相应编译器技术的研究和发展. 这些思想一部分已经应用到嵌入式机器的设计中.

由于规模经济效用, 通用处理器的体系结构具有趋同性. 专用应用处理器则与此相反, 体现出计算机体系结构的多样性.

程序翻译

  • 二进制翻译
  • 硬件合成
  • 数据查询解释器
  • 编译然后模拟

软件生产率工具

一个有意思, 有前景的辅助性方法: 通过数据流分析技术静态(程序运行之前)定位错误

错误探测器可以不是健全的, 但优化器必须是保守的, 任何情况下都不能改变程序的语义.

  • 类型检查
  • 边界检查
  • 内存管理工具
    • 垃圾收集机制是在效率和易编程及软件可靠性之间进行折中处理的一个极好的例子.

Purify是一个能够动态捕捉内存管理错误的被广泛使用的工具.

程序设计语言基础

静态和动态的区别

如果一个语言使用的策略支持编译器静态决定某个问题, 那么我们说这个语言使用了一个静态(static)策略, 或者说这个问题可以在编译时刻(compile time)决定. 另一方面, 一个只允许在运行程序的时候做出决定的策略被成为动态策略(dynamic policy), 或者被认为需要在运行时刻(run time)做出决定.

我们需要注意的另一个问题是声明的作用域.

一个简单的语法制导翻译器

引言

分析阶段的工作是围绕着待编译语言的“语法”展开的. 一个程序设计语言的语法(syntax)描述了该语言的程序的正确行使, 而该语言的语义(semantics)则定义了程序的含义, 即每个程序在运行时做什么事情.

2.2节中给出一个广泛使用的表示方法来描述语法, 这个方法就是上下文无关文法或BNF(Backus-Naur范式).

上下文无关文法不仅可以描述一个语言的语法, 还可以指导程序的翻译过程.

2.3中介绍一种面向文法的便以技术, 即语法制导翻译(syntax-directed translation)技术. 语法扫描, 或者说语法分析.

语法定义

文法定义

一个上下文无关文法(Context-free grammar)由四个元素组成

  1. 一个终结符号的集合, 它们有时也称为“词法单元”. 终结符号是该文法所定义的语言的基本符号的集合.
  2. 一个非终结符号集合, 它们有时也称为“语法变量”. 每个非终结符号表示一个终结符号串的集合.
  3. 一个产生式集合, 其中每个产生式包括一个称为产生式头或左部的非终结符号, 一个箭头, 和一个称为产生式体或右部的由终结符号及非终结符号组成的序列. 产生式主要用来表示某个构造的某种书写形式. 如果产生式头非终结符号代表一个构造, 那么该产生式体就代表了该构造的一种书写方式.
  4. 指定一个非终结符号为开始符号.

推导

根据文法推导符号串时, 我们首先从开始符号出发, 不断将某个非终结符号替换为该非终结符号的某个产生式的体. 可以从开始符号推导得到的所有终结符号串的集合称为该文法定义的语言(language)