编译原理

T型

左右分别是源语言和目标语言，下方是编译器自身实现语言

目标语言和编译器实现语言都为机器语言，这种编译器可以和自身bootstrap

可以将A语言实现的A2K编译器和H语言实现的A2H编译器结合得到H语言实现的A2K编译器，称为交叉编译器

进一步，将A语言实现的A2K再和交叉编译器结合可以得到K语言实现的A2K编译器。至此，通过K语言实现的A2K编译器，成功借助现有编译器将A语言编译到了K语言平台

一个简单的递归下降

只支持 只有一种分解情况正确返回的情况

Predictive Parser

向后看若干个token，不需要回溯

需要接受LL(k)语法

left-to-right

left-most derivation

k tokens look ahead

将左因子转换为右因子

使用parsing table

first sets

$$\mathrm{First}(X)=\{t\mid X{\to }^{\ast }t\alpha \}\cup \{\epsilon \mid X{\to }^{\ast }\epsilon \}$$

X可以是非终结符或终结符

一些结论：

1.终结符的first集是自身 First(t)={t}

2.ε∈First(X)

当X→ε或者X→A1A2…An并且ε∈First(Ai) 对1到n都成立

3.First(α)包含于First(X)

当X→A1A2…Anα并且ε∈First(Ai) 对1到n都成立

其实也就是说对于任何一个产生式的右侧的第一个符号Y都是有First(Y)包含于First(X)（？）

T[A,t]=alpha

follow sets

$$\mathrm{Follow}(X)=\{t\mid S{\to }^{\ast }\beta Xt\delta \}$$

并不是说A可以推导t，而是说t可以在某个推导中紧跟在A后

一些结论：

1.EOF ∈Follow(S)

2.First(β)-{ε}包含于Follow(X) 对于A→αXβ

3.Follow(A)包含于Follow(X) 对于A→αXβ ε∈First(β)

找Follow set应当关注符号在右边的出现（产生）

正则表达式到NFA

有几种固定的模式将各种运算符结合起来

NFA到DFA

利用空串转移的若干状态都合成为一个新状态

DFA化简

一开始划分为接受状态集合和其他状态集合

观察对于输入，整个状态集合是否产生相同的输出（指输出同属一个集合）

南大编译原理学习记录

Knuth在算法分析（计算复杂的时间复杂度？）方面有很大贡献，此外被人忽视的是他在程序语言设计上的贡献，他有一本LR语法分析的论文？

编译器重点好像在后端阶段，而我们的课程集中在前半阶段（已经成熟了）。

符号表中存在嵌套关系（函数作用域？）

clang的读音 不是c lang

dump（打印内存信息）抽象语法树

clang -Xclang -ast-dump hello.c
//不需要该代码可运行

分词

clang -fsyntax-only -Xclang -dump-tokens hello.c

antlr支持非贪婪匹配 优先级匹配（使用的表达式） 整体匹配（不会把小数拆成整数和一个以点开头的小数来识别）

所以用antlr实现时可能不太需要注意优先级和二义性问题

语法和语义

nfa到dfa的转换 不动点

dfa最小化 hopcroft 划分 死状态

函数调用图和计算器实现的例子