编译原理

发表于 分类于 ， Waline：
本文字数： 6.1k 阅读时长 ≈ 6 分钟

词法分析

求自然语言对应的DFA

从状态转换入手，初始状态为：还没看到XXX，状态1：已经看到XXX。以此类推，手动做好状态回转。典型的例子是求出只包含偶数个0和偶数个1的DFA

求正则表达式对应DFA

用Thompsom构造法（简化版）转化为NFA

按照这三个部分一步步组合成NFA

用子集构造法将NFA转换为DFA

主要思想是把NFA中的状态组合成一个个状态集，然后重命名。所以NFA里的一个状态集就对应了转换后的DFA里的一个状态。

  1. 求初始状态：原来NFA的状态0只经过\(epsilon\)转换可达的状态集
  2. 从初始状态开始，对每个输入都尝试进行状态转换，可以转换到的状态又成为一个新的状态集（注意是转换后的，不一定包含出发的状态）
  3. 对于每次产生的新状态集都这样进行转换，最后没有新的状态集产生就停止。
  4. 对每个状态集重命名，那些包含原来的接收状态的状态集在转换后的DFA里也是接收状态

这里只有D是接收状态

Hopcroft算法最小化DFA的状态数

思路就是把等价的状态合并成一个。而判断等价状态，比如状态A和C，如果分别从A和C开始走，到达接收状态用的输入字符串都相同，那么状态A和C就是等价的。比如

这里状态A和C要走到接收状态F用的字符串都一样（比如输入babb，AC都能到达F），这里A和C就是等价状态。

具体算法过程是列一张表，初始的时候把非接受状态和接收状态分开（就是尽量把状态都看成等价的，所以开始只有两组），然后对于每个输入，将组里的那些可以走到其它组的状态拆出来（因为肯定不与当前组内状态等价了）。

语法分析

符号使用规定：

  1. 小写字母、特殊符号、数字和加粗的单词表示终结符Terminals（简记\(V\_T\)）

    如：a, -, 1, id

  2. 大写字母表示非终结符Non Terminals（简记\(V\_N\)）

    如：X, Y

  3. 希腊字母表示可能是终结符也可能是非终结符

    如：\(\alpha\), \(\gamma\)

求语言对应的CFG

CFG(Context Free Grammar)上下文无关文法

最基本的就是两个：

  1. \(\{wcw^R|w\in (a|b)^*\}\)，其中\(w^R\)表示w的逆序字符串，\((a|b)^*\)展开为(a|b)(a|b)...

    S → aSa | bSb | c

  2. \(\{a^nb^n|n\ge1 \}\)

    S → aSb | ab

然后就可以扩展：

  1. \(\{a^nb^mc^md^n|n\ge1,m\ge1 \}\)

    可以先把\(b^mc^m\)看成整体，记作A，由第一个基本例子就有：S → aSd | aAd （如果n可以为0，那么就直接是A）

    对于A，由第二个基本例子可得：A → bAc | bc （同样如果m可以为0，则最右边改为空）

  2. \(\{a^nb^nc^md^m|n\ge1,m\ge1 \}\)

    只用到了第二个基本例子，容易得到

    S → AB

    A → aAb | ab

    B → cBd | cd

非CFG的语言

  1. \(\{wcw|w\in (a|b)^*\}\)

    用于检查标识符先声明再使用

  2. \(\{a^nb^mc^nd^m|n\ge0,m\ge0 \}\)

    用于检查函数形参和实参个数相同

  3. \(\{a^nb^nc^n|n\ge0 \}\)

    （打字机打印下划线？）

LL(1)语法分析

这部分可以参考一个实例: LL(1)语法分析

消除左递归

原: \[ A{\rightarrow}A\alpha_1\ |\ A\alpha_2\ |\ ...\ |\ A\alpha_n\ |\ \beta_1\ |\ \beta_2\ |\ ...\ |\ \beta_n \]

改写为: \[ A{\rightarrow}\beta_1A^{'}\ |\ \beta_2A^{'}\ |\ ...\ |\ \beta_nA^{'}\\ A^{'}{\rightarrow}\alpha_1A^{'}\ |\ \alpha_2A^{'}\ |\ ...\ |\ \alpha_nA^{'}\ |\ \varepsilon \]

提取左公因子

原: \[ A\rightarrow\alpha\beta_1\ |\ \alpha\beta_2\ |\ ...\ |\ \alpha\beta_n\ |\ \gamma \]

改写为: \[ A\rightarrow{\alpha}A^{'}\ |\ \gamma \\ A^{'}\rightarrow\beta_1\ |\ \beta_2\ |\ ...\ |\ \beta_n \]

LL(1)预测分析表

  1. 求First集

    First(A)表示可以由A推出的所有字符串的第一个字符集合

    1. 如果有A → \(aB\)，那么First(A)里就有a（记得符号约定，a是终结符）
    2. 如果有A → BC，那么还要加上First(B)，如果B可以推出\(\epsilon\)，那就还要加上First(C)，如果C也可以推出\(\epsilon\)。那么First里才要加上\(\epsilon\).

  2. 求Follow集

    1. 若\(S\)为开始符号，则\(FOLLOW(S)\)包含$ {$} $
    2. 若\(A{\rightarrow}{\alpha}B\)，则\(FOLLOW(A)\)也加到\(FOLLOW(B)\)里
    3. 若\(A{\rightarrow}{\alpha}B{\beta}\)，将\(FIRST({\beta})-\varepsilon\)加到\(FOLLOW(B)\)里。如果确实有\(\varepsilon{\in}FIRST(\beta)\)，则\(FOLLOW(A)\)也加到\(FOLLOW(B)\)里

  3. 求Select集

    对于一个产生式\(A\rightarrow \alpha\)，其\(SELECT(A\rightarrow \alpha)\)就是可以使用这个产生式进行推导的输入符号的集合。

    计算很简单，对于任意\(A\rightarrow \alpha\)：

    1. 如果\(\epsilon \notin FIRST(A)\)，则$SELECT(A)=FIRST(A) $
    2. 如果\(\epsilon \in FIRST(A)\)，则\[SELECT(A\rightarrow \alpha)=FIRST(A)-\epsilon + FOLLOW(A) \]

  4. 构造预测分析表

    分析表第一行为输入的符号(包括$), 第一列为非终结符, M[S, a]保存的是如果当前栈顶非终结符号为S而且输入为a时应该采用的产生式

    比如\[SELECT(A\rightarrow \alpha)=\{+, )\} \]，则预测分析表\(M\)中：$M[A, +]=M[A, )]=A$。

    上图里一格有两条产生式,说明有冲突,则不符合LL(1)

LL(1)分析过程

比如有预测分析表:

输入id+id*id的分析过程为:

  1. 当栈顶符号为非终结符时,去预测分析表里找相应的格子,应用产生式,比如上图里第一个划出来的那行(注意执行的动作写到了下一行)
  2. 当栈顶符号为终结符时,尝试跟输入进行匹配,比如上图里第二个划出来的行
  3. 最后栈空结束

LR(0)语法分析

求LR(0)项集族

  1. 增广文法:比如原本开始符号位为S,就添加一条S' → S

  2. 求闭包Clousure:

    LR(0)项目:比如产生式A → XY就对应三个项目

    \(A\rightarrow \cdot XY\), \(A\rightarrow X\cdot Y\), \(A\rightarrow XY\cdot\)

    而\(A\rightarrow \epsilon\)只有一个项目\(A\rightarrow \cdot\)

    对于当前项目集里的每个\(A\rightarrow \alpha\cdot B \beta\),如果B有产生式\(B\rightarrow \eta\),那么就把\(B\rightarrow \eta\)加入到当前项目集,最后没有可以加入的就停止.

    现在初始项目集\(I_0\),只有一项\(S'\rightarrow \cdot S\),比如有文法里有产生式S → A,那就把\(S\rightarrow \cdot A\)加进来,如果还有A → B,那就还要把\(A\rightarrow \cdot B\)加进来,以此类推.最后没有可以加的就结束了\(I_0\)的求解求出了这个初始项目的闭包就是\(I_0\)

  3. 求转移GOTO:

    比如现在\(I_0\)里有\(A\rightarrow \cdot BC\),那么就有一条转移(转移上面标注B),转移的目标项目集里有\(A\rightarrow B\cdot C\),本项目集里其它也可以用B转移的也填到目标项目集里.然后还要对目标项目集里的各项目求闭包Closure,这才形成新项目集\(I_1\).

    如果一个项目集里有$S' S\(,那么这个项目集可以通过\)转移到acc,也就是接受

LR(0)语法分析过程

上面求出来的项集族里每个项目集都可以看成一个状态,而且带有状态转换,称为LR(0)自动机,比如:

有了自动机就可以进行LR(0)语法分析.

对于输入id*id的分析过程为

符号列表示从状态0转移到当前栈顶状态需要的符号序列

看上图中第一个划出来的行,当前输入为id,因为状态0可以通过id转换到状态5,所以移入id,状态栈中添加状态5.

看上图中第第二个划出来的行,当前输入为*,但是状态5中没有*的转移,但是可以通过F → id进行规约,于是从符号列弹出一个id,换成F,状态栈弹出一个状态5(弹出的符号个数和状态个数相同),此时栈顶为状态0,而状态0对于F可以转移到状态3,于是又将状态3压入状态栈,所以现在状态栈为03

最后遇到$,acc结束

LR(0)语法分析表

先给原来文法里的产生式编号:比如只有E → E + T | T,那么1号就是E → E + T,2号就是E→ T,以此类推.

记\(s_i\)为转移到状态i,\(r_j\)为使用j号产生式进行规约,acc为接受,空白为报错

观察上面求出来的自动机:

  1. 对于状态转移的

    比如i号状态有个\(A\rightarrow \alpha\cdot a\beta\)(注意命名约定,a是终结符),然后用a转移到了j号状态,那么ACTION[i,a] = \(s_j\)

    如果是用非终结符进行转移,比如\(A\rightarrow\alpha\cdot B\beta\)(根据命名约定,B是非终结符),i号状态通过B转移到了j号状态,那么GOTO[i,B]=j

  2. 对于项目集里的归约

    比如i号状态里有\(A\rightarrow\alpha\cdot\)(命名规则,\(\alpha\)可能终结也可能非终结),这条产生式的编号为j,并且A不是S',那么对每个非终结符(包括$)\(V_T\),设置ACTION[i,\(V_T\)]=\(r_j\)(也就是对应分析表里ACTION一行全部填j)

    如果有\(S' \rightarrow S\cdot\),那么ACTION[i,$] = acc

如果最后得到的分析表中一格有两个动作,那么就是冲突,就不符合LR(0)

比如上图中存在移入-归约冲突

SLR(1)语法分析

SLR(1)可以简称为SLR

求项集族,分析表都于上面LR(0)过程类似,不同之处在于:对于归约的动作变严格了

原本是如果\(A\rightarrow\alpha\cdot\),就对所有终结符都设置ACTION[i,\(V_T\)] = \(r_j\)

而现在需要限制只对FOLLOW(A)中的终结符设置此ACTION()目的是为了减少冲突的发生

如果最后分析表中仍然有冲突,那就不符合SLR(1)(注意也称为SLR)

LR(1)语法分析

LR(1)可以简称LR

当初就是因为不知道简称,一直搞不明白这几个有什么区别

为了进一步减少冲突,LR(1)进一步使得应用归约的条件更严格

LR(1)引入一个搜索符(lookahead,也称为展望符,向前看符号),只有搜索符离的终结符才可以归约,具体规则:

  1. 不同以往的闭包:对于项目[A → \(\alpha \cdot B \beta\),a],如果有B → \(\eta\),则先求出First(\(\beta a\)),对于First(\(\beta a\))里得每个终结符b,把[B → \(\cdot \eta\), b]加到当前项目集里.比如First(\(\beta a\))有a和b,可以把[B → \(\cdot \eta\), a/b]加到当前项目集里(方括号也可以省掉)
  2. 略有不同得GOTO:对于项目[A → \(\alpha \cdot B \beta\),a],可以通过B进行转移,转移后的目标项目集里应该是[A → \(\alpha B \cdot\beta\),a],相比以前就是多加了个搜索符,注意转移前后搜索相同.

求LR(1)分析表

首先求LR(1)项集族

类似于LR(0),但又有点不同.初始项目为[S' → \(\cdot\)S,$],这个$就是一个搜索符.下面来求\(I_0\)(也就是这个项目的闭包):

首先要跟[A → \(\alpha \cdot B \beta\),a]一一对应,这里对应A是S', B是S,\(\alpha\)和\(\beta\)都是\(epsilon\),a是$,于是计算First(\(\beta a\)),这里就是First($)=$,然后看B的产生式并把相应的项目加进来.

求出项集族后再画分析表,跟前面的不同之处在于:

对于项目[A → \(\alpha \cdot\),a/b],只有a和b设为归约,也就是ACTION[i,a] = ACTION[i,b] = \(r_j\)(j是产生式编号)

LALR(1)语法分析

LALR(1)通常简称LALR

上面LR(1)让归约更少了,但是状态(项目集)很多,某些项目集之间得差别仅仅在于后面得搜索符不同,这样的项目叫做同心项,比如:

图里同颜色圈出的就是同心项

LALR就是把这些同心项进行合并,也就是搜索符取并集,然后各种转移转移都迁移到合并之后的状态上

比如:

就可以合并为

中间代码生成

求三地址码

1
2
3
// 地址从100开始,其中A1,A2,A3都产生10条指令
if(a < b || c <d && c < f) A1; else A2;
while(a < b) A3;
1
2
3
4
5
6
7
8
9
10
11
12
13
100 if a < b goto 106
101 goto 102
102 if c < d goto 104
103 goto 117
104 if e < f goto 106
105 goto 117
106~115 A1.code
116 goto 127
117~126 A2.code			// 注意这后面没有goto
127 if a < b goto 129	
128 goto
129~138 A3.code
139 goto 127
1
n = f(a[i]);
1
2
3
4
5
t1 = i * 4
t2 = a[t1]
param t2
t3 = call f, 1		// 一个参数
n = t3

零散

  1. LL(1)和LR(1)何时采用产生式A→\(\alpha\)

    LL(1)再看到First(\(\alpha\))后,而LR(1)在识别出整个\(\alpha\)后,再向后看一个搜索符

参考

[1] 编译原理第2版 (本科教学版)

相关文章