编译原理复习笔记 第三章

编译原理第三章

3-1 正则表达式

1. 由较小的表达式递归定义，正则表达式定义的语言r-L（r)
2. 可以表示大部分语言
3. 十进制整数的RE：(1|…|9)(0|…|9)|0
   八进制整数的RE：0(1|…|7)(0|…|7)
   十六进制整数的RE：0x(1|…|9|a|…|f|A|…|F)(0|…|9|a|…|f|A|…|F)*
4. 正则文法与正则表达式等价

3-2 正则定义

1. 正则定义的定义
2. C语言标识符的正则定义：
   digit→0|1|2|…|9
   letter_→A|B|…|Z|a|b|…|z|_
   id→letter_(letter_|digit)*
3. 无符号数的正则定义
   digit
   digits
   选择小数
   选择指数
   number

3-3 有穷自动机

1. FA模型
   
2. FA接收语言
3. 最长子串匹配原则：到达某个状态时，只要输入带还有符号，FA就继续前进，以便寻找最长的匹配。

3-4 有穷自动机分类

1. 分类（1）DFA （2）NFA

2. DFA 的定义：
   
   不含有 “ 空状态 ”

3. DFA / NFA等价

4. 正则文法 / 正则表达式 / 有穷自动机 等价

5. 带有“空边”的NFA

6. DFA的算法实现
   

3-5 从正则表达式到有穷自动机

1. NFA更加直观，DFA计算机更好操作
2. RE→DFA：RE→NFA→DFA
3. RE→NFA：分解正则表达式

3-6 从NFA到DFA

1. “DFA的状态是NFA状态的集合的子集”，可以利用NFA的转换表来得到集合
2. 注意判断初始状态和终止状态
3. 子集构造法
   

3-7 识别单词的DFA

2. 识别无符号数


3. 识别各进制无符号整数的DFA

4.