第三章-4-RE-DFA

知识

将正则表达式直接转换为DFA

• 我们可以将正则表达式转换为DFA（无需先创建NFA）。

• 首先，我们通过将给定的正则表达式与一个特殊符号#连接起来来扩充它。

  r ➔ （r） #增广正则表达式

• 然后，我们为这个扩展正则表达式创建一个语法树。

• 在这个语法树中，扩充正则表达式中的所有字母符号（加#和空字符串）都将位于叶子上，所有内部节点都将是该扩充正则表达式中的运算符。

• 然后每个字母符号（加#）都将被编号（位置编号）。

正则表达式➔ DFA

（a | b）*a➔ （a | b）*a#增广正则表达式

（a | b）*a#的语法树

• 每个符号都有编号（位置）

• 每个符号都在左边

• 内部节点是操作员

followpos

然后我们为位置（分配给叶子的位置）定义函数followpos。

followpos（i）——是一组位置，可以在增广正则表达式生成的字符串中跟随位置i。

例如，（a | b）*a#
        1  2   34
followpos（1）={1,2,3}
followpos（2）={1,2,3}
followpos（3）={4}
followpos（4）={}
//followpos只是为叶子定义的，而不是为内部节点定义的。

firstpos，lastpos，nullable

• 为了计算followpos，我们需要为语法树的节点（不仅仅是叶子）定义另外三个函数。

• firstpos（n）——由以n为根的子表达式生成的字符串的第一个符号的位置集。

• lastpos（n）——由以n为根的子表达式生成的字符串的最后一个符号的位置集。

• nullable（n）——如果空字符串是由以n为根的子表达式生成的字符串的成员，则为true。

否则就错了。

如何评估firstpos、lastpos和nullable

计算nullable和firstpos的规则

如何评估followpos

• 以下两条规则定义了函数：

1. 如果n是包含左子节点c1和右子节点c2的连接节点，i是lastpos（c1）中的一个位置，那么firstpos（c2）中的所有位置都在followpos（i）中。

2. 如果n是星型节点，i是lastpos（n）中的一个位置，那么firstpos（n）中的所有位置都在followpos（i）中。

• 如果已经为每个节点计算了firstpos和lastpos，则可以通过对语法树进行一次深度优先遍历来计算每个位置的followpos。

算法 (RE ➔ DFA)

最小化DFA的状态数

• 将状态集分为两组：

  • G1：接受状态集

  • G2：不接受状态集

• 对于每个新组G

  • 将G划分为子群，使状态s1和s2在同一个群中，如果

  • 对于所有输入符号a，状态s1和s2转换为同一组中的状态。

• 最小化DFA的开始状态是包含原始DFA的开始状态的组。

• 最小化DFA的接受状态是包含原始DFA接受状态的组。

词法分析器中的其他一些问题

• 词法分析器必须识别尽可能长的字符串。

  – 例如：标识符newval--n ne new v newva newval

• 单词的结尾是什么？是否有任何字符标志着单词的结束？

  – 它通常没有定义。

  – 如果令牌中的字符数是固定的，在这种情况下没有问题：+-–但是<➔ < 或<>（帕斯卡语）

  – 单词的结尾：标识符中不能包含字符。标识符可以标记单词的结尾。

  • 我们可能需要一个了望台

• 在序言中：p:-X是1。p:-X是1.5。

点后跟空格字符可以标记数字的结尾。

但如果情况并非如此，则必须将圆点视为数字的一部分。

• 跳过评论

  • 通常我们不会将评论作为标记返回。

  • 我们跳过一条注释，并将下一个单词（不是注释）返回给解析器。

  • 因此，注释只由词法分析器处理，并且注释不会使语言的语法复杂化。

• 符号表接口

  • 符号表包含有关令牌的信息（至少是标识符的词素）

  • 如何实现符号表，以及什么样的操作。

    • 哈希表——开放寻址、链接

    • 放入哈希表，从词素中查找标记的位置。

• 标记在文件中的位置（用于错误处理）。

例题

DFA

( a | b) * a #

green – firstpos
blue – lastpos
然后我们可以计算followpos
followpos(1) = {1,2,3}
followpos(2) = {1,2,3}
followpos(3) = {4}
followpos(4) = {}

• 计算跟随位置之后，我们就可以为正则表达式创建DFA了。

followpos(1)={1,2,3} followpos(2)={1,2,3} followpos(3)={4} followpos(4)={}
S0=firstpos(root)={1,2,3}
↓ mark S0
a: followpos(1) ∪ followpos(3)={1,2,3,4}=S1 move(S0,a)=S1
b: followpos(2)={1,2,3}=S0 move(S0,b)=S0 
↓ mark S1
a: followpos(1) ∪ followpos(3)={1,2,3,4}=S1 move(S1,a)=S1
b: followpos(2)={1,2,3}=S0 move(S1,b)=S0
start state: S0
accepting states: {S1}

最小化DFA

因此，最小化DFA（具有最小状态）

课堂练习

请计算firstpos、lastpos、followpos，然后转换为DFA

followpos(1)={2} followpos(2)={3,4} 
followpos(3)={3,4} followpos(4)={}
S0=firstpos(root)={1,2}
↓ mark S0
a: followpos(1)={2}=S1 move(S0,a)=S1
b: followpos(2)={3,4}=S2 move(S0,b)=S2 
↓ mark S1
b: followpos(2)={3,4}=S2 move(S1,b)=S2 
↓ mark S2
c: followpos(3)={3,4}=S2 move(S2,c)=S2
start state: S0
accepting states: {S2}

最小化DFA

最小化DFA，列出状态转换表

答案

所以，最小DFA

用两种方法为以下正则表达式构造DFA

• 用两种方法为以下正则表达式构造DFA：

1. a（a | b）*（b）|∈)

2. a（a | b）*a（a | b）a

• 第一种方法是使用汤普森算法构造NFA，然后使用子集构造算法从NFA构造DFA。

• 第二种方法是直接从正则表达式构造DFA。

• 最小化DFA的状态。

作业

一、直接构造法构造正则表达式的DFA，并且最小化DFA。

一、直接构造法构造这四个正则表达式的DFA，并且最小化DFA。

a) (a | b)*
b) (a* | b*)*
c) ((e | a)b*)* 
d) (a | b)*abb(a | b)*

参考答案

a

a) (a | b)*

firstpos(root) = {1, 2, 3} = A
δ(A, a) = followpos(1) = { 1, 2, 3 } = A
δ(A, b) = followpos(1) = { 1, 2, 3 } = A

b

b) (a* | b*)*

firstpos(root) = {1, 2, 3} = A
δ(A, a) = followpos(1) = { 1, 2, 3 } = A
δ(A, b) = followpos(1) = { 1, 2, 3 } = A

c

c) ((e | a)b*)*

firstpos(root) = {1, 2, 3} = A
δ(A, a) = followpos(1) = { 1, 2, 3 } = A
δ(A, b) = followpos(1) = { 1, 2, 3 } = A

d

d) (a | b)*abb(a | b)*

firstpos(root) = {1, 2, 3} = A
δ(A, a) = followpos(1)∪followpos(3) = { 1, 2, 3, 4 } = B
δ(A, b) = followpos(2) = A
δ(B, a) = followpos(1)∪followpos(3) = B
δ(B, b) = followpos(2)∪followpos(4) = { 1, 2, 3, 5 } = C
δ(C, a) = followpos(1)∪followpos(3) = B
δ(C, b) = followpos(2)∪followpos(5) = { 1, 2, 3, 6, 7, 8} = D
δ(D, a) = followpos(1)∪followpos(3)∪followpos(6) = { 1, 2, 3, 4, 6, 7, 8 } = E
δ(D, b) = followpos(2)∪followpos(7) = D
δ(E, a) = followpos(1)∪followpos(3)∪followpos(6) = E
δ(E, b) = followpos(2)∪followpos(4)∪followpos(7) = { 1, 2, 3, 5, 6, 7, 8 } = F
δ(F, a) = followpos(1)∪followpos(3)∪followpos(6) = E
δ(A, b) = followpos(2)∪followpos(7) = D