Course Overview

Interpreters: on-line (速度慢, 占用内存大)

Compilers: off-line

Compiler Five Phases:

1. Lexical Analysis: syntactic

   recognize words

2. Parsing: syntactic: syntactic

   diagramming sentences

3. Semantic Analysis: types and scopes

   understand meaning (hard), catch inconsistencies

   无法做到真正的解析语义, 所以只是寻找程序中自相矛盾的地方, 比如: 变量重复定义, 变量前后类型不同

4. Optimization

   run faster, use less memory, less power, network, database…

5. Code Generation: translation to another languages, machine code or even high level programming language

编译器的提升:

The Course Project

COOL: Classroom Object Oriented Language

COOL 的语法

1. main 的返回值

2. 继承

3. 递归和递推

4. init 函数

5. 一些特性 (用 Object 模拟泛型)

环境配置

这个的环境配置还是很简单的, 官方是提供了一个系统镜像

1. 根据自己电脑版本下载Virtual Box 并安装

2. 下载系统镜像 (这里可能需要一点魔法)

3. 点击镜像中的 .vbox 文件直接运行即可

4. 进入到桌面, 打开终端 (左下第四个图标) 进行测试

5. 写个 hello.cl, coolc 编译出 hello.s, spim 执行 hello.s

6. 测试成功

Lexical Analysis

Lexical Analysis

每个lexeme被分为不同的token classes

词法分析器接收, 生成类似于键值对的 token 二元组 <type - value>, 然后发送给解析器

过程总结:

Lexical Analysis Examples

Fortran 的一个例子 (因为历史原因, Fortran 中的空格不重要):

DO 5 I = 1,25 // 从此句到有标签 5 的句子做循环, I 是变量, 从 1 加到 25

DO 5 I = 1.25 // 声明一个变量 DO5I, 值为 1.25

在词法分析中虽然会扫描到关键字 DO, 但只有扫描到后面的 , 才能确定这是循环的关键字

lookahead: 根据后面的词语来确定当前词语的作用

Regular Language

总而言之, 正则语言是一个强大的工具

Formal Language

将语义和语法分离, 不同语法会有相同语义, 二者之间的映射关系必须是多对一

Lexical Specifications

Implementation of Lexical Analysis

Lexical Specification

1. 对于每个表达式用正则去匹配;
2. 如果匹配到了多个正则, 则按照优先级进行识别; 如果没有则判断为一个错误

Finite Automata

基本介绍:

DFA 和 NFA:

Regular Expressions into NFAs

词法分析器:

转换示例:

一个例子:

NFA to DFA

方法:

例子:

Implementing Finite Automata

优化一下 (压缩空间):

NFA 需要对每个状态都进行一次搜索, 所以就很慢:

DFA 和 NFA 的权衡:

Introduction to Parsing

Introduction to Parsing

Parsing:

Context Free Grammars

Derivations

Parse Tree:

最左推导:

最右推导:

Ambiguity

Syntax-Directed Translation

Error Handling

error kinds:

error detect:

error correction:

Abstract Syntax Trees

正常的语法树:

AST(Abstract Syntax Tree):

Recursive Descent Parsing

不匹配, 回溯:

匹配成功:

Recursive Descent Algorithm

从上到下, 从左到右

一个完整的例子, 实际上整个过程就是 dfs:

Recursive Descent Limitations

没有遍历所有情况, 所以可能会有提前识别的风险

如上图, int * int 在被识别到第一个 int 后, 指针后移, 于是变成了识别 int 和 * int, 识别错误

Left Recursion

Recursive Descent Algorithm 是从左到右进行分析, 而左递归是从右到左产生语言, 无法使用该算法分析, 所以要将左递归转换为右递归

转换方法:

总结:

Top-Down Parsing & Bottom-Up Parsing I

Predictive Parsing

LL(K): 从左到右扫描, 最左生成, 向前看 K 个 tokens(此章节中 K=1)

像之前的 $T \rightarrow T+E | T$ 的例子中, $T+E$ 和 $T$ 的第一个 token 相同, 所以无法用 LL(1) 语法预测, 所以引入了 left-factored 语法 (提取左边的公因式):

leftmost non-terminal: 最左非终结符

next input token: 下一个输入的 token

rhs of production to use: 生成式的右边部分

使用 LL(1) parsing table 的算法:

一个例子:

First Sets

终结符的 First Set 是他本身, 所以 $First(t) = {t} \dots$

$E$ 根据 LL(1) 会识别到 $T$, 所以 $First(E) \supset First(T) $, 但是因为 $E$ 没有生成新的 (区别于 $First(T)$ ) 终结符, 所以 $First(E) = First(T)$

Follow Sets

LL(1) Parsing Tables

Bottom Up Parsing

rightmost derivation

Shift Reduce Parsing

| 表示输入的位置

lhs: left hand side 推导式的左边部分

rhs: right hand side 推导式的右边部分

Bottom-Up Parsing II

Handlers

Recognizing Handlers

Recognizing Viable Prefixes

Valid Items

SLR Parsing

reduce: 规约, 生成式右到左执行

shift: 移入, 生成式左到右执行

SLR Parsing Example

red : reduce

SLR Improvements

SLR Examples

咕咕咕, 不出意外的话后面是鸽了………