形式语言与编译提纲
自动机理论
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 | VarD: TYP L { |
嵌套过程声明:mktab(father)
建表,addwidth(tab,name,typr,offset)
填表,fillwidth(tab, width)
填表长,enterproc(tab, name, chtab)
建子表登记
函数调用的翻译
1 | S : procid '(' args ')' { |
数组引用的翻译
1 | E : L { |
&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 | E : E_1 or M E_2 { |
控制语句的翻译
1 | Contr : if E then { |
符号表
名字、类型(整、实、双精、布尔、字符、复、标号、指针等)、种属、变量地址长度、标号标志位置、形式参数标志;
局部变量(包括形式参数)占用的存储空间、返回结果类型、局部过程名及符号表指针、嵌套外层过程
内情向量表
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 | program c; |
认为过程 r
的调用者是过程 q
,则在
p
使用 r
时走 l_r-l_p+1
层访问链
Display 表:过程的嵌套层次显示表,记录该过程的各外层过程的最新活动记录的起始地址