编译原理一

2019-06-17 本文已影响0人小屋的快乐

编译原理

正规式或NFA到DFA最小化
四元式DAG图的优化，根据要求写出优化结果翻译到目标代码
给你文法，给你句型，让你写出最左推导和最右推导，或者让你画出语法树，说出素短语，直接短语等（之类的东西）
给文法求firstvt lastvt first follow的过程

目标代码三种形式：绝对指令代码，可重定位指令代码，汇编指令代码。
编译程序开发技术：自编译，交叉编译，自展，移植

词法分析

子程序大纲：把词法分析作为语法分析的子程序

词法分析器设计方法

通常分为五种：保留字，标识符，常数，运算符，界符
词法分析单词的输入输出形式：输入源程序字符串，输出单词符号序列，通常是二元式：（单词种别，单词自身的值）
关于单词种别：保留字全体一种或者一字一种（更方便），标识符统一一种，常数可以归为一种，也可以按类型分类。运算符一符一种或一种。单词自身值：一符一种种就是值。
状态转换图：p11有标识符，无符号数和无符号整数的状态转换图。终态有*代表多余的字符回退。

简单词法分析器的示例

正规表达式和有限自动机

正规表达式与正规集：对于给定的字母表（segema），正规式和正规集递归定义如下：
1. $\varepsilon$ 和 $\Phi$ 都是 $\Sigma$ 上的正规式，它们所表示的正规集分别为{ $\varepsilon$ }和 $\Phi$ 。
2. 对任何一个a $\epsilon$ $\Sigma$ ，a是 $\Sigma$ 上的一个正规式，它所表示的正规集为｛a｝。
3. R和S是上的正规式，它所表示的正规集为L(R)和L(S)，则：
  1. R|S（或运算）是 $\Sigma$ 上的正规式，它所表示的正规集为L(R) $\cup$ L(S)
  2. R $\centerdot$ S.............L(R)L(S)
  3. (R)^*是 $\Sigma$ 上的正规式，他的正规集为(L(R))^*
  4. R..................L(R)(L就是语言)
4. 有限次使用上述规则得到 $\Sigma$ 上的正规式与正规集
关于上述规则的一系列说明：
- 运算顺序中，*（闭包）大于 $\centerdot$ ， $\centerdot$ 大于|
- 关于闭包运算 R⁰={ $\varepsilon$ }，并令R^*=R⁰ $\cup$ R¹ $\cup$ ......
- R⁺=RR^*，R⁺被称为R的正则闭包，不含 $\varepsilon$
- 正规式的正规集相等，正规式等价R=S，包括交换律：R|S=S|R，结合律：R|(S|T)=(R|S)|T；R(ST)=(RS)T，分配律（不赘述），同一律： $\varepsilon$ R=R $\varepsilon$ =R
- 简单就是L(R|S)=L(R) $\cup$ L(S)，其他同理

简单的举例： $\Sigma$ = { a,b }，求 $\Sigma$ 上正规式R = a(a|b)^*的正规集
方法：一层一层展开：L(a)L((a|b)^*)=L(a)(L(a|b))^*=L(a)(L(a) $\cup$ L(b))^*={a}({a} $\cup$ {b})^*={a}{a,b}^*={a}{ $\epsilon$ ,a,b,aa,ab,ba,bb,aaa,……}={a,aa,……}

判断正规式等价只需看正规集是否等价
有限自动机：更一般化的状态转换图，分为确定有限自动机DFA以及非有限自动机NFA。
DFA：是一个五元组Md = (S,,f,,Z}
- s是有限状态集，每个元素是一个状态
- $\Sigma$ 是有穷输入字母表，每个元素都是一个输入字符
- f是S $\times\Sigma$ 到S的单值映射，即f(s_i,a)=s_j,s_i,s_i $\epsilon$ S,a $\epsilon$ $\Sigma$
- s₀ $\epsilon$ S，是唯一的初态
- Z $\epsilon$ S，是一个终态集
NFA：也是五元组M_n=(S, $\Sigma$ ,f,Q,Z),S, $\Sigma$ ,Z与DFA意义相同，f是S $\times\Sigma$ ^*到S子集的映射（可以多值以及 $\varepsilon$ ），Q $\subset$ S，是一个非空初态集。
DFA到状态矩阵，很简单(这里不填了)，NFA一样，只不过填状态集，或者空集（NFA从初始态到终止态的通路，有向边上字符连接的串为FAM识别的语言，字符串集为L(M)，可以根据L(M)判断两个有限自动机是否等价)（DFA与NFA本质相同可以互相转化）

状态\字符	a	b
S₀	这里填的是S几（状态）
S₁
S₂

正规式到NFA的构造（根据这规则）

转换规则.jpg

例子：

转换例子.jpg

NFA确定化（到DFA）

解读例子

nfatodfa.jpg

方法：1. 先求初态 $\varepsilon$ 闭包（所有经 $\varepsilon$ 可达的都算, $\varepsilon$ 不限，因为一个 $\varepsilon$ 和多个一样），当然必须包括自己。之后求其经a,b可达状态集，（比如求a先到a之后再找新集合的 $\varepsilon$ 闭包得到新集合），重复之前操作，直到不再有新集合出现为止。

DFA的化简

这是例题： dfa.jpg

首先分为终态集和非终态集（包含原初态为初态，包含原终态为终态），之后经过a,b是否落在一个集合，不落则分开，经过多次重复得到最终结果。（得到新的状态转换矩阵，不可达用横杠代替）