Question

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

Answer 1

语言
正则表达：

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

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

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

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

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

例：对于FA

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

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

例：

以上两种自动机都可以用正则表达式 来表示。
事实上， 正则表达式与有穷自动机是等价的 。

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

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

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

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

例：

记数字为 ，字母为 ，那么标识符的正则表达式为：

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

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

记：
数字
数字串
小数部分
指数部分
数

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

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

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