【编译原理】第三章：词法分析

一、正则表达式（RE）

语言L=\{a\}\{a,b\}^*(\{\epsilon\}\cup (\{.,\_\}\{a,b\}\{a,b\}^*))
正则表达：r = a(a|b)^*(\epsilon|(.|\_)(a|b)(a|b)^*)

正则表达式可以由较小的正则表达式递归构建。每个正则表达式r定一个语言记作L(r)。

正则表达式优先级为：克林闭包>连接>或。

二、正则定义

简单来说就是重定义。
例如：
letter -> 字母
number -> 数
\d -> 整数

三、有穷自动机（FA）

系统根据当前状态与当前的输入信息决定后继行为。
每当处理完当前输入后，状态也发生改变。

1. FA的表示

FA的表示

2. FA定义的语言

如果给定输入串x，如果存在对于该串从初始状态到某个终止状态的转换序列，则该串被该FA接收。

例：对于FA


FA定义的语言

abbaabb是被接收的，而abbaaba则不被接收。

  • 由一个有穷自动机M接收的所有串构成的集合被称为该FA定义的语言，记作L(M)。

  • 最长匹配：输入有多个前缀匹配时，会选择最长的前缀进行匹配。

四、有穷自动机的分类

  • 确定的FA（DFA）
  • 非确定的FA（NFA）

重点：转换表；
一个有穷自动机可以由转换表表示。

1. DFA

DFA
DFA例子

2. NFA

NFA
NFA例子

3. DFA与NFA的等价性

  • 对于任何NFA，存在识别同一语言的DFA
  • 对于任何DFA，存在识别同一语言的NFA

例：


DFA与NFA的转换

以上两种自动机都可以用正则表达式r=(a|b)^*abb来表示。
事实上，正则表达式与有穷自动机是等价的。

4. 含有空边的NFA

含有空边的NFA

5. DFA的算法实现

从人的角度看，NFA比DFA更加直观；但对于程序来说，DFA比NFA容易实现。

五、从正则表达式RE到有穷自动机FA

直接从RE转换到DFA是比较困难的，所以一般通过NFA作为中介。


转换

1. 从RE到NFA

从RE到NFA

2. 从NFA到DFA

DFA中的每个状态都是NFA中状态集合的一个子集。


从NFA到DFA

即，先写出NFA的转换表，再通过新的状态构建出DFA。

2.1 从带有空边的NFA转换为DFA

例：r=0^*1^*2^*

带有空边的NFA到DFA

3. 子集构造法

子集构造法

六、识别单词的DFA

1. 标识符

记数字为digit，字母为letter\_，那么标识符的正则表达式为：
r=letter\_(letter\_|digit)^*

这个正则表达式转换为NFA，表示如下：


标识符的NFA表示

这个NFA同时也是一个DFA，所以不用再进行转换。

2. 无符号数

记：
数字digit \rightarrow 0|1|...|9
数字串digits \rightarrow digit\ digit^*
小数部分optionalFraction \rightarrow .digits|\epsilon
指数部分optionalExponent \rightarrow (E(+|-|\epsilon)digits)|\epsilon
数number \rightarrow digits\ optionalFraction\ optionalExponent

即一个数由一个数字串+可选的小数部分+可选的指数部分构成。
转换为NFA，表示如下：


无符号数的NFA表示

通过子集构造法，将NFA转换为DFA：


无符号数的DFA表示

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

可以表示10进制、8进制、16进制的DFA：


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

4. 识别注释的DFA

识别注释的DFA

5. 词法分析阶段的错误处理

  • 单词拼写错误
  • 非法字符
  • 错误恢复
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容