形式语言与编译提纲

发表于 Waline： 阅读次数：

自动机理论

DFA-NFA-RE

DFA 是五元组 \((Q,\Sigma,\delta,q_0,F)\)，分别表示状态，符号集，迁移函数，开始状态，接收状态集

DFA 扩展转移函数 \(\hat\delta:Q\times\Sigma^*\to Q\)

NFA 是五元组 \((Q,\Sigma,\delta,q_0,F)\)，其中 \(\delta:Q\times\Sigma\to2^Q\)

NFA 扩展转移函数 \(\hat\delta:Q\times\Sigma^*\to 2^Q\)

\(\mathrm \varepsilon\)-NFA 是五元组 \((Q,\Sigma,\delta,q_0,F)\)，其中 \(\delta:Q\times(\Sigma\cup\{\varepsilon\})\to2^Q\)

  • \(\mathrm \varepsilon\)-NFA 到 DFA：\(\mathrm{ECLOSE}(r)\) 与子集构造
  • NFA 到 DFA：（惰性）子集构造，\(O(n^32^n)\)
  • DFA 到 RE：消除状态得 GNFA，\(O(n^34^n)\)；证明：归纳法
  • RE 到 \(\varepsilon\)-NFA：\(O(n)\)

泵引理证正则：

存在 \(n\) 使得对任意 \(w\in L\)，若 \(|w|\ge n\)，我们能写成 \(w=xyz\)，其中 \(|xy|\le n\)，\(|y|\ge 1\)，且 \(\forall k\geq 0, xy^kz\in L\)

泵引理证非正则使用反证法，由上推论引出矛盾。或者

对于任意 \(n\) 存在串 \(w\in L\)，且 \(|w|\ge n\)，使得对任意书写 \(w=xyz\)，\(|xy|\leq n\)，\(|y|\ge 1\)，存在 \(k\ge 0\) 使 \(xy^k z\notin L\)

正则语言的封闭运算：交并补、连接反向、闭包

  • 交 \(L\cap L'\)：状态对
  • 并 \(L\cap L\)：揉起来
  • 补 \(L^C\)：DFA 改变接收状态拒绝状态
  • 连接 \(LL'\)：正则表达式连接
  • 逆 \(L^R\)：DFA 反向
  • 幂 \(L^k\)：\(k\) 个表达式连接
  • 闭包 \(L^*\)：表达式的闭包

DFA 最小化：区分状态等价类填 \(n\times(n-1)\) 的下三角表

DFA 等价性：放在一起填表，区分开始状态是不是等价

PDA-CFG-CFL

CFG 是四元组 \(G=(V,T,\mathscr P,S)\)，分别是变元集，终结符集，产生式集，开始符号

产生式惯用法

  • 变元：字母表开头大写字母 A，B，C
  • 终结符：字母表开头小写字母 a，b，c
  • 符号（终结符或变元）：字母表结束大写字母 X，Y，Z
  • 终结符串：字母表结束小写字母 w，x，y，z
  • 符号串：\(\alpha\)，\(\beta\)，\(\gamma\)

直接推导 \(\alpha A\beta\Rightarrow \alpha\gamma\beta \iff A\to\gamma\)

连续推导 \(\alpha A\beta\stackrel{*}{\Rightarrow} \alpha\gamma\beta \iff A\Rightarrow\cdots\Rightarrow \gamma\)

多于一次的推导 \(\alpha A\beta\stackrel{+}{\Rightarrow} \alpha\gamma\beta\)

最左推导 \(\stackrel{lm}{\Rightarrow}\)，最右推导 \(\stackrel{rm}{\Rightarrow}\)

句型：从开始符号推导的任意串

句子：从开始符号推导的终结符串

规约：序列 \(\alpha_1,\cdots,\alpha_n\)，其中 \(\alpha_1=w\)，\(\alpha_n=S\)，\(\alpha_i\Leftarrow \alpha_{i+1}\)

歧义文法：该文法存在一个串是多个语法树的产物；该文法存在一个串存在两个不同最左推导

固有歧义的：语言的每个文法均是歧义的

CFG 化简：

  • 消除 \(\varepsilon\)-产生式：删去可空变元，重写产生式，若出现无用符号则消除
  • 消除单位产生式：对于单位产生式推导的序列，以最后的产生式（组）替代单位产生式的产生式变元（检查所有变元序对）
  • 无用符号（先消无产出后消不可达）
    • 无产出的变元：推导不出终结符串（无候选式、死循环）
    • 不可达符号：不出现在任意句型中的符号

乔姆斯基范式：每个产生式右侧仅有两个变元或一个终结符

PDA 是七元组 \((Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)\)，分别为状态集，输入字母集，栈字母集，迁移函数 \(\delta:Q\times(\Sigma\cup \{\varepsilon\})\to 2^{Q\times \Gamma*}\)，初始状态，开始符号，终结状态集

PDA 的移动 \((p,\gamma)\in \delta(q,a,X)\)：状态 \(q\) 移动到 \(p\)，消耗输入符号 \(a\)，使用 \(\gamma\) 替代 \(X\) 作为新栈顶

PDA 图示边标记格式：输入符号，弹出符号/压入符号串

瞬时描述 ID：\((q,w,\alpha)\)，当前状态，剩余串和栈内容

迁移：ID \(I\) 在一次移动变为 ID \(J\)，记为 \(I\vdash J\)

定理 6.5 与 6.6：串里看不见的符号不影响迁移

终结状态定义语言，空栈定义语言可互相模拟

确定性 PDA：至多存在一个迁移（可以是 \(\varepsilon\)-迁移）

  • CFG 到 PDA：仅三个状态，迁移模拟移入，\(\varepsilon\)-迁移模拟规约
  • PDA 到 CFG

编译原理

源语言、实现语言、目标语言

宿主机器、目标机器

词法分析、语法分析、语义分析、代码优化、代码生成

源程序、中间表示、目标代码

词法分析（<种属，值>）：关键字一符一种、全体一种

语法分析

自上而下语法分析

LL(1) 文法：无二义性，无回溯（无左递归，无左公因子，候选式 FIRST 不相交，若候选首符含空则其 FIRST 交 FOLLOW 为空）

LL(1) 分析：从左到右扫描，最左推导，向前查看一个

消除左递归：对非终结符排序，对每个终结符看前面的终结符，将代带入前面终结符的候选，消除直接左递归（\(E\to E\alpha\ |\ \beta\) 到 \(E\to \beta E'\)；\(E'\to \alpha E'\ |\ \varepsilon\)）

FIRST(\(\alpha\))：串 \(\alpha\) 能推导出来的串的最左侧终结符（或空符）集合

求解 FIRST 迭代法：首先构造非终结符 FIRST，然后根据串构造

FOLLOW(A)：所有句型中符号 A 右侧的终结符（或结束符）

求解 FOLLOW：先求 FIRST，后遍历产生式

提左公因子：加变元消去公因子

递归下降语法分析：每个变元构造一个过程

构造预测分析表 M[A, a]，对于每一个产生式 \(A\to\alpha\)：

  • 对任意 \(a\in\mathrm{FIRST}(\alpha)\)，M[A, a]\(= A\to\alpha\)
  • 若 \(\varepsilon\in \mathrm{FIRST}(\alpha)\)，M[A, b]\(= A\to\alpha\)，\(b\in\mathrm{FOLLOW}(A)\)

错误处理：

  • 栈顶终结符与输入不匹配：弹出
  • M[A, b] == null：Sync

预测分析表的使用：状态栈和剩余字符串

自下而上的分析

短语：有 \(S\stackrel{*}\Rightarrow \alpha A\delta\)，且 \(A\stackrel{+}{\Rightarrow} \beta\)，则 \(\beta\) 是句型 \(\alpha\beta\delta\) 相对于规则 \(A\to\beta\) 的短语

直接短语：若 \(A{\Rightarrow} \beta\)，则 \(\beta\) 是句型 \(\alpha\beta\delta\) 相对于规则 \(A\to\beta\) 的直接短语

句柄：句型的最左直接短语

规范规约（最左规约）：最右推导的逆过程

LR(0) 文法：项目集不包含冲突项目

增广文法：在 \(G\) 中增加 \(S'\to S\)

活前缀 NFA：初态 \(S'\to\bullet S\)，从状态 \(X\to \cdots X_{i-1}\bullet X_{i}\cdots\) 到 \(X\to \cdots X_i\bullet X_{i+1}\cdots\) 有 \(X_i\) 弧；到状态 \(X_i\to\bullet \beta\) 有 \(\varepsilon\) 弧

直接构造活前缀 DFA：初态 \(p_0=\mathrm{CLOSURE(\{[S'\to\bullet S]\})}\)，\(q\) 的 \(X\) 迁移到 \(p\) 当且仅当 \(p=\mathrm{CLOSURE(\{[A\to\alpha X\bullet \eta]\ |\ [A\to\alpha\bullet X\eta]\in q\})}\)

构造 LR(1) 分析表：使用活前缀 DFA，ACTION 为终结符迁移动作（点不在最后 shift / 点在最后 reduce），GOTO 为针对变元迁移动作（当 reduce 时使用）

SLR(1) 分析表：使用 FOLLOW 来加强规约的能力，则 SLR(1) 文法为对于所有项目集，移进项目与规约项目 FOLLOW 不相交的；重新定义项目使其带有 1 个终结符

LR 分析表使用：状态栈、符号栈和剩余字符串

语义分析

属性文法

综合属性、继承属性；S-属性文法：仅有综合属性（自下而上）

属性方程，过程调用

中间表示

后缀式，图表示，三地址（四元式、三元式）

翻译

声明的翻译

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
VarD:	TYP L			{
							typfill($2.dtype, $1.dtype);
						}
	;

L	:	id Dim, L		{
							typlink($2.dtype, $$.dtype);
						}
	|	id Dim			{
							typlink($1.dtype, $$.dtype);
						}
	;

Dim	:	[num] Dim		{}
	|	%empty			{}
	;
	
Proc:	M Pdef			{}
	;

M	:	%empty			{}
	;

Pdef:	Pdef; Pdef		{}
	|	procid
	;

嵌套过程声明：mktab(father) 建表，addwidth(tab,name,typr,offset) 填表，fillwidth(tab, width) 填表长，enterproc(tab, name, chtab) 建子表登记

函数调用的翻译

1
2
3
4
5
6
7
8
9
10
11
S	:	procid '(' args ')'	{
								for (auto arg : $3.q) {
									emit(par, arg, _, _);
								}
								emit(call, entry(procid), $3.q.size(), _);
							}
	;

args:	args, E				{ $1.q.push(E.place); $$.q = $1.q; }
	|	E					{ $$.q = queue<void*>(); q.push(E.place); }
	；

数组引用的翻译

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
E	:	L	{
				// and much more
			}
	;

L	:	EList ']'		{
							
						}
	|	id				{
							
						}
	;

EList	:	EList',' E	{
							
						}
		|	id '[' E	{
							
						}
		;

&A[i,j]=base+((i-l_1)*(u_2-l_2)+j-l_2)*w \[ \begin{align} base - C + (\cdots(((i_1)d_2+i_2)d_3+i_3)d_4\cdots)d_n + i_n \nonumber\newline l_k\le i_k\le u_k\nonumber\\ d_k = u_l-l_k\nonumber\\ C=((\cdots(((l_1)d_2+l_2)d_3+l_3)d_4\cdots)d_n+l_n)w\nonumber \end{align} \] 布尔表达式的翻译

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
E	:	E_1 or M E_2	{
							backpatch($$.falselist, M.quad);
							$$.truelist = merge($1.truelist, $4.truelist);
							$$.falselist = $4.falselist;
						}
	|	E_1 and M E_2	{
							backpatch($$.truelist, M.quad);
							$$.falselist = merge($1.falselist, $4.falselist);
							$$.truelist = $4.truelist;
						}
	|	not E_1			{
							$$.falselist = $2.truelist;
							$$.truelist = $2.falselist;
						}
	|	'(' E_1 ')'		{
							$$.falselist = $2.falselist;
							$$.truelist = $2.truelist;
						}
	|	id_1 rop id_2	{
							$$.truelist = makelist(nextquad);
							emit($2.jop, $1.place, $3.place, NULL);
							$$.falselist = makelist(nextquad);
							emit(j, NULL, NULL, NULL);
						}
	|	id				{
							$$.truelist = makelist(nextquad);
							emit(jnz, $1.place, NULL, NULL);
							$$.falselist = makelist(nextquad);
							emit(j, NULL, NULL, NULL);
						}
	;
	
M	:	%empty			{
							$$.quad = nextquad;
						}
	;

控制语句的翻译

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Contr	: 	if E then		{
								bp($2.tc, nxq);
								$$.chain = $2.fc;
							}
		;

Stmts	:	Contr Stmts		{ $$.chain = merg($1.chain, $2.chain); }
		|	ConEl Stmts		{ $$.chain = merg($1.chain, $2.chain); }
		|	A				{ $$.chain = 0; }
		|	Wd Stmts		{
								bp($2.chain, $1.quad);
								Gen(j, _, _, $1.quad);
								$$.chain = $1.chain;
							}
        |	begin L end		{ $$.chain = $2.chain; }
        ;
	
ConEl	:	Contr Stmts else{
                                q = nxq; Gen(j, , , 0);
                                bp($1.chain ,nxq);
                                $$.chain = merge($2.chain, q);
                            }
        ;
	
W		:	while			{ $$.quad = nxq; }
Wd		:	W E do			{
                                bp($2.tc, nxq);
                                $$.chain = $2.fc;
                                $$.quad = $1.quad;
                            }
        ;
    
L		:	Stmts			{ $$.chain = $1.chain; }
		|	Ls Stmts		{ $$.chain = $2.chain; }

Ls		:	L ';'			{ bp($1.chain, nxq); }
		;

符号表

名字、类型（整、实、双精、布尔、字符、复、标号、指针等）、种属、变量地址长度、标号标志位置、形式参数标志；

局部变量（包括形式参数）占用的存储空间、返回结果类型、局部过程名及符号表指针、嵌套外层过程

内情向量表

Dim，base，Type/w， C，\(l_i\)，\(u_i\)，\(d_i=u_i-l_i\)

运行时空间组织

offset chain content
100 形参
99 ……形参
98 参数个数
97 访问链
96 fp 控制链
95 返回地址
94 局部变量
93 ……局部变量
92 超长数据
91 sp 超长数据

函数 <ip, ep> 作为参数，ip 代码入口，ep 实参求值的过程的活动记录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
program c;
    procedure p(procedure a);
        begin
        	a;
        end;
    procedure q;
        var x:integer;
        procedure r;
        begin
            writeln(x);
        end;
    begin
        x:=2;
        p(r);
    end;
begin
	q;
end.

认为过程 r 的调用者是过程 q，则在 p 使用 r 时走 l_r-l_p+1 层访问链

Display 表：过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址