编程语言是向人以及机器描述计算过程的 notations。

关于翻译

没办法,编译器是外国人发明的,所以很多词汇在编译原理中含义是不一样的,按惯用法翻译成中文,就无法一一对应(说实话,有些词语在英文里也是混用的)。比如有很多个单词,翻译成中文就都成了 “符号”。但是我实在不想中英夹杂, 因为切换输入法太麻烦了 所以我干脆自己做一个翻译规则表,当然也不是乱翻的,参考了别人的翻译。

英语 汉语
concept/notion 概念
character 字符
notation 记号 / 记法
annotation 标注 / 注解
denotation 直指
mark 标记
symbol (象征) 符号
token 词符
entry (符号表的)条目
sign 正负号 / 征象
- signifier 能指
- signified 所指
signification 意义
semiotics 符号学 *
semantic 语义的 *
pragmatic 语用的 *
string 字符串
identifier 标识符
lexeme 词素
lexical 词法
syntax 句法
grammer 文法
pattern 规式
paradigm 范式
schema 方案
schema 章法
diagram 简图
model 模型
specification 规格
normal form 规范型
sentence 句子
clause 子句
function 函数
tag 挂签
label 标签
category 范畴 / 分类
parameter 形参
argument 实参
attribute 字段
property 函数属性
statement 陈述
assignment 赋值
operator 运算符
operand 运算对象
representation 表示法

1.1 语言处理器

编译器和解释器的差别

编译器(compiler):将源语言翻译为目标语言的程序。翻译的结果称为目标程序(target program)

目标程序的运行过程:

$$ \text{output} = f(\text{input}) $$

解释器(interpreter):基于输入,直接执行源程序规定的操作。

解释器的运行过程:

$$ \text{output} = f(\text{source program, input}) $$

二者比较

  1. 使用编译通常有更高的执行性能(如 C/C++/Go)
  2. 使用解释通常有更好的兼容能力(如 Java/C#/Python)

1.2 编译器的结构

编译器包含两部分: 分析综合(analysis and synthesis)

分析:将源程序分解为组分(constituents),在其上施加一个语法结构(grammatical structure)。然后利用这个结构,制造源程序的中间表示(intermediate representation)。如果有句法(syntactical)或(semantical)的问题,就会反馈一些提示消息(informative message)。分析部分还会收集关于源程序的信息,然后存储在符号表(symbol table)中。符号表和中间表示会传递到综合部分。

编译是分阶段(phases)进行的,每一阶段都会将程序的一种表示变换为另一种。典型的阶段划分如下:

image-20210731131538277

1.2.1 词法分析

词法分析(lexical analysis),又称扫描(scanning)会读取字符流输入,将其划分为有意义的序列,称为词素,对于每个词素,词法分析器产生如下形式的词符(Token)输出:

$$ \left\langle \text {词符名}, \text {字段值} \right\rangle $$

词符的 词符名 是一个用于下阶段 句法分析(syntax analysis)的抽象符号, 字段值 则指向一个符号表中的条目(entry)。

例如有一个赋值陈述:

position = initial + rate * 60

则会产生如下词素:

  • position:将会被映射到一个词符 <id, 1>,其中 id 是一个表示标识符(identifier)抽象符号,1 表示标识符的条目(entry)在符号表的位置。
  • =:将会映射到词符 <=>
  • initial:将会映射到词符 <id, 2>
  • +:将会映射到词符 <+>
  • rate:将会映射到词符 <id, 3>
  • *:将会映射到词符 <*>
  • 60:将会映射到词符:<number, 60>

于是经过词法分析,我们得到了这样的序列:

<id,1> <=> <id,2> <+> <id,3> <*> <60>

1.2.2 句法分析

句法分析(syntax analysis,也叫 parsing)将会使用词符作为输入,用来创建一个树状中间层,从而表示词符流的语法结构。以上例,输出将是:

        =
       / \
    id,1  \
           + 
          / \
         /   \
       id,2   *
             / \
            /   \
           id,3  60 

这称为句法树(syntax tree)

1.2.3 语义分析

语义分析(semantic analysis)利用句法树和符号表检查源程序,保证同语言定义(language definition)的语义一致性(semantic consistency)。同时收集类型信息并将其保存在句法树或符号表中,以便下一步生成中间代码。

语义分析的一个重要部分是类型检查,从而保证运算符与运算对象匹配。(比如数组取数操作要求索引值为非负整数)。

语言规格(language specification)有可能允许隐式类型转换(type coercions)。例如例子中可能要把 60 转换为浮点数,则语义分析需要指明这种转换(例中 inttofloat

1.2.4 中间码生成

在编译过程中,有可能用到不止一种中间表示,表示的形式也可以各有不同。在句法分析和语义分析之后,编译器往往会生成一种详细、低级或者像机器码一样的中间表示层,其特点是结构非常简单,容易生成,页容易翻译成目标机器的机器语言。例:

t1 = inttofloat(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3

这种中间形式(intermediate form)称为三地址码(three-address code),即一个运算符,三个运算数:

f = OP(R1, R2, R3)

1.2.5 代码优化

就字面意思,比如上面的可以优化成:

t1 = id3 * 60.0
id1 = id2 + t1

1.2.6 代码生成

就生成机器码,比如生成下面的 RISC 码:

LD      R2,     id3
MULF    R2,     R2,     #60.0
LDF     R1,     id2
ADDF    R1,     R1,     R2
STF     id1,    R1

1.2.7 符号表管理

编译器的一个基本功能是记录源程序使用的变量名,并收集每个名称的字段信息。这些字段包括:分配的存储空间、类型、作用域、参数的数量和类型、传参的方式(引用还是值)。

符号表是一个保存变量名、名称的字段信息的数据结构。

1.2.8 Pass

几个阶段(phase)的组合称为一个 Pass(没想到合适的翻译),它能读入一个文件并输出一个文件。

例如,编译的前端(front-end)阶段包括:词法分析、句法分析、语义分析和中间代码生成。这些合起来是一个 Pass。

而代码优化可以是一个选择性的 Pass。而后端 Pass 则是生成具体的目标语言代码。

这体现了一种分层抽象接口的原则,因此可以让不同的前端编译出相同的中间代码,然后共用一个后端,生成目标机器码。

1.2.9 编译 - 构建工具

解析器生成器(Parser generators):能够从语法描述生成句法分析器。

扫描器生成器(Scanner generators):能够从语言的词符的正则描述生成词法分析器。

面向句法的翻译引擎(Syntax-directed translation engine):能够生成 routine 集,以便遍历解析树并生成中间代码。

代码生成器生成器(Code-generator generators):从规则生成代码生成器,以便将中间语言的每个操作,翻译到目标机器语言。

数据流分析引擎(Data-flow analysis engines):分析数据在程序各部分之间的传输。

编译器 - 构建工具包(Compilers-construction toolkits):提供 routine 的集成,以便构建一个编译器的不同阶段。

1.3 编程语言的演进

1.3.1 走向高级语言

第一代语言:机器语言

第二代语言:汇编语言

第三代语言:高级语言,如 Fortran,Cobol,Lisp,C,C#,Java

第四代语言:领域应用语言,如 NOMAD(报表生成),SQL(数据库查询),Markdown。

第五代语言:基于逻辑和约束的语言,比如 Prolog 和 OPS5。

命令式语言(imperative):程序指明计算的流程(how to)

声明式语言(declarative):指明程序要进行的计算(what to)

函数式语言(functional):将一切运算视为函数,抗拒引入状态

老组合逻辑电路了

声明式语言包括函数式语言如 ML、Haskell 以及 Prolog。

冯诺依曼语言:计算模型基于冯诺依曼体系结构。

面向对象语言:支持面向对象编程的语言,程序视为对象之间的交互。

脚本语言:解释执行的语言。

1.4 设计编译器的科学

1.4.1 编译器设计的建模以及实现

主要涉及自动机和规则式理论、代码优化以及程序的结构表示和翻译等。

1.4.2 代码优化

编译器优化必须满足以下设计目标

  • 优化必须是正确的。即不改变程序的含义
  • 优化必须能提高大量程序的性能
  • 编译时间要合理
  • 整个工程要便于管理

1.5 编译技术的应用

可以用来:

  • 实现高级编程语言
  • 针对计算机架构优化
  • 设计新的计算机架构
  • 程序翻译(比如用于硬件设计的 VHDL)
  • 软件生产力工具(如类型检查、边界检查)

1.6 编程语言的基础

1.6.1 静态和动态之分

  • 在编译时可完成判定,则是静态语言
  • 在运行时可完成判定,则是动态语言

作用域(scope):在某范围内,所有对 $x$ 的引用都指向某个声明,则此范围是 $x$ 的作用域。

静态作用域:在编译时可以确定一个声明的作用域。又称词法作用域(lexical scope)。否则成为动态作用域。

例如 static 修饰的 Java 类变量,在编译期就可以确定其内存位置(相对位置),则是静态的。而去除 static 修饰之后,必须在程序运行之后,对象的内存分配之后,才知道其内存位置,这就是动态的。

1.6.2 环境与状态

从名称到值存在两步映射

  1. 从名称到内存位置的映射。这个映射称为环境(environment)
  2. 从内存位置到值的映射。这个映射称为状态(state)

名称、标识符和变量

标识符:一个字符串,用于指代一个数据对象

名称:编译时的名字

变量:运行时的内存地址

1.6.3 静态作用域和块结构

块:声明和语句的组合。C 使用 {} 进行块的界定。

静态作用域就是可以在编译器确定的作用域,一个声明的作用域在声明的位置隐式地决定。

1.6.4 显式访问控制

一些 OO 语言提供 public, private, protected 这样的关键字,用于控制对超类成员名称的访问权限。

  • 公有:可以被任何地方访问
  • 私有:只能被自己访问
  • 保护:只能被自己和后代访问

声明:告知名称的类型。如 int i

定义:告知名称的值。如 i = 1

1.6.5 动态作用域

动态作用域:作用域要在程序执行时才知道

传参机制

实参:在调用时使用的参数

形参:在定义时表示的参数

值调用(call-by-value):使用值局限于过程,不会修改实参。

引用调用(call-by-ref):实参的地址被传给被调者,因此有可能修改参数。