编译原理
- 正规式或NFA到DFA最小化
- 四元式DAG图的优化，根据要求写出优化结果翻译到目标代码
- 给你文法，给你句型，让你写出最左推导和最右推导，或者让你画出语法树，说出素短语，直接短语等（之类的东西）
- 给文法求firstvt lastvt first follow的过程
- 目标代码三种形式：绝对指令代码，可重定位指令代码，汇编指令代码。
- 编译程序开发技术：自编译，交叉编译，自展，移植
词法分析
子程序大纲：把词法分析作为语法分析的子程序
词法分析器设计方法
- 通常分为五种：保留字，标识符，常数，运算符，界符
- 词法分析单词的输入输出形式：输入源程序字符串，输出单词符号序列，通常是二元式：（单词种别，单词自身的值）
- 关于单词种别：保留字全体一种或者一字一种（更方便），标识符统一一种，常数可以归为一种，也可以按类型分类。运算符一符一种或一种。单词自身值：一符一种种就是值。
- 状态转换图：p11有标识符，无符号数和无符号整数的状态转换图。终态有*代表多余的字符回退。
简单词法分析器的示例
正规表达式和有限自动机
- 正规表达式与正规集：对于给定的字母表（segema），正规式和正规集递归定义如下：
-
和
都是
上的正规式，它们所表示的正规集分别为{
- 对任何一个a
- R和S是
- R|S（或运算）是
L(S)
- R
S.............L(R)L(S)
- (R)*是
- R..................L(R)(L就是语言)
- R|S（或运算）是
- 有限次使用上述规则 得到
-
- 关于上述规则的一系列说明：
- 运算顺序中，*（闭包）大于
- 关于闭包运算 R0={
- R+=RR*，R+被称为R的正则闭包，不含
- 正规式的正规集相等，正规式等价R=S，包括交换律：R|S=S|R，结合律：R|(S|T)=(R|S)|T；R(ST)=(RS)T，分配律（不赘述），同一律：
- 简单就是L(R|S)=L(R)
- 运算顺序中，*（闭包）大于
简单的举例：
方法：一层一层展开：L(a)L((a|b)*)=L(a)(L(a|b))*=L(a)(L(a),a,b,aa,ab,ba,bb,aaa,……}={a,aa,……}
- 判断正规式等价只需看正规集是否等价
- 有限自动机：更一般化的状态转换图，分为确定有限自动机DFA以及非有限自动机NFA。
- DFA：是一个五元组Md = (S,
,Z}
- s是有限状态集，每个元素是一个状态
-
- f是S
到S的单值映射，即f(si,a)=sj,si,si
- s0
- Z
- NFA：也是五元组Mn=(S,
S，是一个非空初态集。
- DFA到状态矩阵，很简单(这里不填了)，NFA一样，只不过填状态集，或者空集（NFA从初始态到终止态的通路，有向边上字符连接的串为FAM识别的语言，字符串集为L(M)，可以根据L(M)判断两个有限自动机是否等价)（DFA与NFA本质相同可以互相转化）
| 状态\字符 | a | b |
|---|---|---|
| S0 | 这里填的是S几（状态） | |
| S1 | ||
| S2 |
-
正规式到NFA的构造（根据这规则）
转换规则.jpg
例子：
转换例子.jpg
- NFA确定化（到DFA）
解读例子
nfatodfa.jpg
方法：1. 先求初态闭包（所有经
可达的都算,
不限，因为一个
和多个一样），当然必须包括自己。之后求其经a,b可达状态集，（比如求a先到a之后再找新集合的
闭包得到新集合），重复之前操作，直到不再有新集合出现为止。
- DFA的化简
这是例题：dfa.jpg
- 首先分为终态集和非终态集（包含原初态为初态，包含原终态为终态），之后经过a,b是否 落在一个集合，不落则分开，经过多次重复得到最终结果。（得到新的状态转换矩阵，不可达用横杠代替）
