编译器

编译

把人类可读的代码编译成机器可以识别的内容

编译器前端

处理只与被编译的高级语言本身相关的部分,生成中间表示码

编译器后端

处理只与目标操作系统和硬件平台相关的部分,将中间表示码生成目标代码

编译阶段

词法分析 scanning

分析单词的词性

从左到右逐行扫描源程序,识别出每一个单词,确定单词类型

将识别出的单词转换成统一的机内表示——词法单元token

Token<种别码,属性值>

token种别码有如下几类

  • 关键词 if else,每个关键词都有一个种别码

  • 标识符 变量数组名字,函数名字,每个变量名都是同一个种别码,区别变量名的方式是通过token的属性值

  • 常量,例如int,string类型的常量,每种类型的常量都是一个种别码,区别常量具体量的方式是通过token的属性值。立即数的value直接为常量立即数本身

  • 运算符,算数,关系,逻辑运算符+-,==,<>,如果每种类型一个种别码,则要使用token的属性值来区分每个运算符类型下的具体运算符。否则就是每个运算符都有一个独立唯一的种别码

  • 界限符;()「」=(等号特殊),每种界限符一个种别码

语法分析 parsing

分析多个单词组织的单词意义

语法分析器parser从词法分析器输出的token序列中识别出各类短语,构造语法分析树 parse tree

分析生成AST抽象语法树

语法树中,某些特定的token组合会代表一些特定的含义

通过特定文法的组合规则生成AST

语义分析

结合上下文,分析单词的具体实际意义

收集标识符信息,存储在符号表中

  • kind种属,简单变量,复合变量,数组

  • type类型,int,float,point等等

  • length长度,存储的内存位置,根据之前的变量长度,计算出下一个变量应该在内存中的偏移地址,记录到符号表中

  • value值,具体值

  • 作用域

  • 参数和返回信息(函数,过程)

收集标识符的属性信息

语义检查,包括如下几类

  • 标识符未声明就使用

  • 重复声明标识符

  • 运算分量类型不匹配,例如函数和变量相加(可以设计自动类型转换)

  • 操作符与操作数类型不匹配(数组下标必须是整数)

  • 调用非过程名

  • 过程调用参数类型和数目不匹配

  • 函数返回类型有误

中间代码生成

生成三地址码 (Three-address Code)(三地址码由类似于汇编语言的指令序列组成, 每个指令最多有三个操作数(operand))

语法结构树/语法树 (Syntax Trees)

四元式 (Quadruples) (op, y, z, x)

三元式 (Triples)

间接三元式 (Indirect triples)

目标代码生成

为变量分配对应的寄存器

生成对应平台的机器码

代码优化

机器无关和有关代码优化

改进代码,让程序运行更快,占用空间更少

字母表

$\sum$ 表示,sigma

字母表是一个有穷符号的集合

符号包括字母、数字、标点符号

运算

乘积 product

$$
{\sum }_1 {\sum }_2 = { ab | a ∈ {\sum }_1 , b ∈ {\sum }_2 }
$$

例如
$$
{ 0,1 }{ a,b } = { 0a,0b,1a,1b }
$$
位置不变,两两交叉排列组合

次冥 power

n个字母表相乘,相乘就是上面的乘积运算

0次冥就是空串(下面讲串的概念会提到)

正闭包 positive closure

${\sum}^+$

一个字母表的1次冥,2次冥一直到它长度的次冥的并集(长度正数的符号串构成的集合)

克林闭包 Kleene closure

${\sum}^*$

正闭包的基础上加上空集

串 string

设 $\sum$ 是一个字母表,则它的克林闭包里面每一个元素都是这个字母表的一个串

长度

s中的符号个数
$$
|aab|=3
$$

空串

长度为0的串,用 $\epsilon$ 表示
$$
|\epsilon| = 0
$$

运算

连接 concatenation

y 附加到 x 后面

记作 xy
$$
x=dog,y=house. xy=doghouse
$$
空串e是连接运算的单位元,任何串s和空串e运算都有
$$
s \epsilon=\epsilon s = s
$$

前后缀

设 x y z 是三个字符串

如果 $x=yz$

y 是 x 的前缀

z 是 x 的后缀

冥运算

自我连接,结果为n个自己strcat相连

文法

自然语言例子

<句子> -> <名词短语><动词短语>

<句子> -> <形容词><名词短语>

<句子> -> <名词>

<动词短语> -> <动词><名词短语>

<形容词> -> little

<名词> -> boy

<名词> -> apple

<动词> -> eat

尖括号为语法成分,其他为基本符号

定义

文法指的就是一组语言规范,他由各种集合成分组成
$$
G=(V_T, V_N, P, G)
$$

$V_T$:终结符集合 terminal symbol

是文法定义语言的基本符号token,例如上述句子构成中的eat,boy等等

$V_N$:非终结符集合 nonterminal

是用来表示语法成分的符号
$$
V_N = { <句子>,<名词符号>… }
$$
注意:$V_t$ 和 $V_N$之间没有交集,他们是相互独立对立的集合

$P$:产生式集合

描述了终结符和非终结符组合成串的方法集合,例如 a -> b 读作 a定义b

左部

其中a一定属于终结符或者非终结符中的成分,称为产生式的头部或者左部。

右部

b可能是空集,也有可能属于终结符或者非终结符中的成分,称为产生式的体或者右部。

例如
$$
P = { <句子> -> <名词> <动词短语> }
$$

$S$:开始符号

一定属于非终结符集合,指的是该文法中最大的语法成分

例如在自然语言中,最大的语法成分就是句子本身,记作 S=<句子>

产生式

定义一个文法的时候,如果不引起歧义,可以只写产生式集合

简写

对于一组有相同左部的产生式,可以简记为
$$
a -> b_1|b_2|…|b_n
$$
其中 $b_1|b_2|…|b_n$ 称为候选式 candidate

符号约定

终结符

  • 字母表中排在前面的小写字母。a、b、c
  • 运算符。+、*
  • 标点符号。()、,
  • 数字。1、2、3、4、5.
  • 粗体字符串。id、if

非终结符

  • 字母表中排在前面的大写字符。A、B、C
  • 字母S。表示开始符号
  • 小写、斜体的名字。exor、stmt
  • 代表程序构造的大写字符。E表达式、T项、F因子

文法符号

字母表中排在后面的大写字母。X、Y、Z

既可以表示终结符,也可以表示非终结符

终结符号串(包括空串)

字母表中排在后面的小写字母(主要是u、v、…、z)

文法符号串(包括空串)

小写的希腊字母。$\alpha, \beta, \gamma$

除非特别说明,否则第一个产生式的左部就是开始符号

推导和归约

推导

用产生式的右部替换左部

从文法的开始符号推导出具体词串

如果
$$
a_0 => a_1, a_1 => a_2, a_2 => a_3, … , a_{n-1} => a_n,
$$
则可以记作
$$
a_0 => a_1 => a_2 => a_n
$$
称为字符串 $a_0$ 经过 n 步推导出 $a_n$

记作
$$
a_0 =>^n a_n
$$
生成语言

归约

用产生式的右部替换成左部

推导的逆过程

识别语言

句型和句子

如果开始符号 S 经过若干步骤 可以推导出一个文法符号串 $\alpha$

$$
S=>^ \alpha, \alpha ∈ (V_T ∪ V_n)^
$$

则 $\alpha$ 成为这个文法 G 的一个句型

句型

既可以包含终结符,又可以包含非终结符,也可能是空串

句型是概括一个句子形态的东西,他就像抽象类 abstract class 一样

句子

不包含非终结符的句型

他就像最终实现类 final class 一样

语言

由文法 G 的开始符号 S 推导出的所有句子构成的集合成为文法 G 生成的语言

记为 $L(G)$

$$
L(G) = { w | S=>^ w, w∈ V_T^ }
$$

Chomsky文法分类体系

Type-n Grammar

文法逐级限制增加

0型文法

无限制文法 Unrestricted Grammar

短语结构文法 Phrase Structure Grammar,PSG

他对产生式几乎没有什么限制,只要求产生式 $\alpha$ 至少包含1个非终结符
$$
任意 \alpha -> \beta ∈ P
$$
0型文法 G 生成的语言成为 0型语言 L(G)

1型文法

上下文有关文法 Context-Sensitive Grammar,CSG
$$
\alpha -> \beta ∈ P, |\alpha|>|\beta|
$$
产生式一般形式为
$$
a_1Aa_2 -> a_1\beta a_2 (\beta≠\epsilon)
$$
生成的语言称为上下文有关语言

2型文法

上下文无关文法 Context-Free Grammar,CFG
$$
\alpha -> \beta ∈ P, \alpha ∈ V_N
$$
产生式一般形式为
$$
A -> \beta
$$
要求每个产生式左部 必须是一个非终结符

生成的语言称为上下文无关语言

3型文法

正则文法 Regular Grammar,RG

右线性文法 Right Linear

$A->wB$ 或 $A->w$

左线性文法 Left Linear

$A->Bw$ 或 $A->w$

左右线性文法都是正则文法

上下文无关文法CFG的分析树

分析树

根节点的标号为文法开始符号

内部结点表示对一个产生式的应用,该节点的标号是产生式的左部A。标号从左到右构成了产生式的右部 $\beta$

叶节点可以是非终结符也可以是终结符

从左到右排列叶节点得到的符号串称为是这棵树的产出或边缘

句型的短语

给定一个句型,其分析书中的每一棵子树的边缘称为该句型的一个短语 phrase

二义性文法

如果一个文法可以为某个句子生成多棵分析树,则称这个文法是二义性的

判定

对于任意一个上下文无关文法,不存在一个算法,判定它是无二义性的

但能给出一组充分条件,满足这组充分条件的文法是无二义性的

正则表达式

正则表达式 Regular Expression,RE 是一种用来描述正则语言的更紧凑的表达方式

正则表达式可以由较小的正则表达式按照特定的规则递归地构建

每个正则表达式 r 定义(表示)一个语言,记为 $L(r)$

这个语言也是根据 r 的子表达式所表示的语言递归定义的

定义

  • $\epsilon$ 是一个RE,$L(\epsilon) = { \epsilon }$
  • 如果 $\alpha ∈ \sum$ 则 $\alpha$ 是一个 RE , $L(\alpha) = { \alpha }$
  • 假设 r 和 s 都是 RE , 表示的语言分别是 $L(r)$ 和 $L(s)$
    • $r|s$ 是一个 RE, $L(r|s)=L(r)∪L(u)$
    • $rs$ 是一个 RE, $L(rs)=L(r)L(u)$
    • $rs^$ 是一个 RE, $L(r^)=L((r))^*$
    • $(r)$ 是一个 RE, $L((r))=L(r)$

运算符优先级

  • *(克林闭包)
  • 连接
  • |(或)

可以用 RE 定义的语言叫做正则语言或正则集合

正则文法与正则表达式等价

RE代数定律

TODO

正则定义

如下形式的定义序列
$$
d_1 -> r_1\
d_2 -> r_2\
…\
d_n -> r_n
$$
每个 $d_i$ 都是一个新符号,他们都不在字母表中,而且各不相同

每个 $r_i$ 是字母表 $\sum ∪ { d_1, d_2, … , d_{n-1} }$ 上的正则表达式

有穷自动机

Finite Automata,FA 是对一类处理系统建立的数学模型

这类系统具有一系列离散的输入输出信息和有穷数目的内部状态(状态:概括了对过去输入信息处理的状况)

系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为

每当系统处理了当前的输入后,系统的内部状态也将发生改变

FA模型

输入带

用来存放输入符号串

读头

从左向右逐个读取输入符号

有穷控制器

具有有穷个状态数,根据当前的状态和当前输入符号控制器转入下一个状态

转换图表示

结点:FA的状态

初始状态(开始状态)

只有一个,由 start 箭头指向

终止状态(接受状态)

可以有多个,用双圈表示

带有标记的有向边

如果对于输入 a 存在一个从状态 p 到状态 q 的转换

就在 p 和 q 之间画一条有向边,并标记上 a

注意,同一个输入可能对应的下一个状态仍然是原状态,例如 状态机 TODO 接收 abbaabb

FA定义(接收)的语言

给定输入串 x

如果存在一个对应于串 x 的从初始状态到某个终止状态的转换序列

则称串 x 被该 FA 接收

由一个有穷自动机 M 接收的所有串构成的集合称为是该 FA 定义(接收)的语言

记为 $L(M)$

最长子串匹配原则

当输入串的多个前缀与一个或多个模式匹配时

总是选择最长的前缀进行匹配

例如代码中的 <= 和 ++ ,当匹配到 < 号的时候,如果他仍然有下一个状态 = 可以被匹配到,选择这个最长的状态 <=

因此在输入带上如果后面还有符号,FA就继续前进,寻找尽可能长的匹配

FA的分类

确定的FA(Deterministic finite automata,DFA)

确定的有穷自动机可以通过一个五元组来表示
$$
M=(S, \sum, \delta, s_0, F)
$$

$S$

有穷状态集

$\sum$

字母表

$\delta$

将 S 和 $\sum$ 的笛卡尔乘积映射到 S有穷状态集合的转换函数

当 $s ∈ S,a ∈ \sum$ 时

$\delta(s, a)$ 表示从状态 $s$ 出发,沿着标记为 $a$ 的边所能到达的状态

$s_0$

开始状态(初始状态)。属于 S有穷状态集

$F$

接收状态集合(终止状态)。F 是 S 的真子集

非确定的FA(Nondeterministic finite automata,NFA)

区别仅仅是 $\delta$

将 S 和 $\sum$ 的笛卡尔乘积映射到 $2^S$ 的转换函数

从状态 s 出发,可以沿着标记为 a 的边所能到达的状态集合

意味着同一个输入,可能对应着下一个状态是有多个的,所以下一个状态就是不确定的

DFA和NFA的等价性

对任何 NFA N,存在识别同意语言的 DFA D

对任何 DFA D,存在识别同意语言的 NFA N

带有空边的 NFA

空边,意味着不需要特定的输入就能转到下一个工作状态

如果要转换成不带空边的 NFA,需要加上每个带下一个输入的边

等价关系

正则文法,正则表达式,FA有穷自动机

三则完全等价,可以互相表示

正则表达式到有穷自动机

正则表达式直接到 DFA 比较困难,我们一般是先构造出 NFA ,然后 NFA 在转换到 DFA

将正则表达式写出来

串连接直接写成多个状态的级联

串的或运算可以转换成多个边

串的克林闭包可以转换成一个边,自己到自己

NFA转换成DFA的时候通过将一个状态定义成包含多个状态的结点

词法分析阶段错误处理

  • 单词拼写错误
  • 非法字符

因为当前状态和当前输入符号在转换表对应项中为空,也就是当前状态,对应某个输入,找不到任何可以转换的方法,则报错,调用错误处理程序

语法分析

根据给定的文法,识别句子中的短语,构造分析树

自顶向下分析法

从分析树的顶部(根节点)向底部(叶节点)方向构造分析树

可以看成是从文法的开始符号 S 推导出词串 w 的过程

在每一步推导中都需要选择

  • 替换当前句型中的哪个非终结符
  • 用该终结符的哪个候选式进行替换

最左推导

总是选择每个句型的最左非终结符进行替换

$S=>^*_{lm}a$ 得到的句型是最左句型

自顶向下分析一般都是最左推导

最右推导

和最左推导相反

文法转换

直接左递归

假设有如下文法

  • $E->E+T|E-T|T$
  • $T->T*F|T/F|F$
  • $F->(E)|id$

这个文法如果要接收字符串 $id+id*id$

则会出现如下情况
$$
E=>E+T \
\ =>E+T+T \
\ =>E+T+T+T \
\ =>… \
$$
根本原因是文法产生式右边的第一个字符出现了和左部一模一样的非终结符

含有 $A->Aa$ 形式产生式的文法称为是直接左递归的 immediate left recursive

如果一个文法中 有一个非终结符 A 使得对某个串 a 存在一个推导 $A=>^+ Aa$ 那么这个文法就是左递归的

经过两步或两部以上推导产生的左递归称为是间接递归

左递归会使递归下降分析器陷入无限循环

消除直接左递归

$A->A\alpha|\beta $

$r=\beta \alpha$

转换成

  • $A-> \beta A’$
  • $A’->\alpha A’|\epsilon$

把直接左递归转换成右递归即可消除

付出的代价是引入了一些非终结符和空产生式

消除间接左递归

  • $S->Aa | b$
  • $A->Ac|Sd|\epsilon$

文法 S 经过两步推导得到一个直接左递归

$S=>Aa=>Sda$

消除方法为先把 S 定义式带入 A-产生式,得到

$A->Ac|Aad|bd|\epsilon$

然后消除直接左递归得到

  • $A->bdA’|A’$

  • $A’->cA’|adA’$

提取左公因子

多个候选式存在左公共前缀

将公共前缀提取出来作为一个新的产生式

例如

  • $S->aAd|aBe$
  • $A->c$
  • $B->b$

提取第一个产生式中的 a

  • $S->aS’$
  • $S’->Ad|Be$
  • $A->c$
  • $B->b$

改写产生式来推出决定

等读入了足够多的输入

获取足够信息后再做出正确的选择

LL(1)文法

在自顶向下分析法的过程中,可能遇到回溯,回溯会降低效率

我们可以使用预测分析技术来解决这个问题

S_文法

从文法开始符号出发,在每一步推导过程中根据当前句型的最左非终结符 A 和当前输入符号 a 选择正确的 A-产生式

为保证分析的确定性,选出的候选式必须是唯一的

S_文法 是 简单的确定性文法

每个产生式的右部都以终结符开始

同一非终结符的各个候选式的首终结符都不同

S_文法不包含空产生式

什么时候使用空产生式呢?

如果当前某非终结符 A 与当前输入符 a 不匹配时

若存在 $A->\epsilon$ 可以通过检查 a 是否可以出现在 A 的后面

来决定是否可以使用产生式 $A->\epsilon$ 若文法中无 $A->\epsilon$ 则应报错

非终结符的后继符号集

可能在某个句型中紧跟在 A 后边的终结符 a 的集合,记为 FOLLOW(A)
$$
FOLLOW(A)={ a|S=>^ \alpha Aa\beta, a∈V_T, \alpha , \beta ∈(V_T∪V_N)^ }
$$
如果 A 是某个句型的最右符号,则将结束符 $\$$ 添加到 FOLLOW(A) 中

产生式的可选集

产生式 $A->\beta$ 的可选集是指可以选用该产生式进行推导时对应的输入符号集合,记为 $SELECT(A->\beta)$

  • $SELECT(A->a\beta)={ a }$
  • $SELECT(A->\epsilon)=FOLLOW(A)$

q_文法

每个产生式的右部或为 $\epsilon$ 或以终结符开始

具有相同左部的产生式有不相交的可选集

串首终结符

串首第一个符号,并且是终结符