本文介绍正则表达式相关的基本概念,包括正则表达式定义、有穷自动机、DFA、NFA等。


正则表达式(Regular Expression,RE)是一种用来描述正则语言的更紧凑的表示方法


正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式 r定义(表示)一个语言,记为L(r)。这个语言也是根据r 的子表达式所表示的语言递归定义的

正则表达式的定义

ε是一个RE,L(ε) = {ε}

如果 a∈∑,则a是一个RE,L(a) = {a}

假设 r和 s都是 RE,表示的语言分别是 L(r)和L(s),则

运算的优先级:*、连接、|

例:

令 ∑ = {a, b},则

例:C语言无符号整数的RE

  • 十进制整数的RE

    (1|...|9)(0|...|9) * |0

  • 八进制整数的RE

    0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7) *

  • 十六进制整数的RE

    0x(0|1|...|9|a|...| f |A|…|F)(0|...|9|a|...| f |A|…|F) *

正则语言

可以用RE定义的语言叫做正则语言(regular language)或正则集合(regular set)

RE的代数定律

正则文法与正则表达式等价

  • 对任何正则文法 G,存在定义同一语言的正则表达式 r
  • 对任何正则表达式 r,存在生成同一语言的正则文法 G

正则定义(Regular Definition)

正则定义是具有如下形式的定义序列:

d1→r1

d2→r2

dn→rn

其中:

  • 每个di都是一个新符号,它们都不在字母表 Σ中,而且各不相同
  • 每个ri是字母表 Σ∪{d1 ,d2 , … ,di-1}上的正则表达式

给一些RE命名,并在之后的RE中像使用字母表中的符号一样使用这些名字

例1:C语言中标识符的正则定义

digit → 0|1|2|…|9

letter → A|B|…|Z|a|b|…|z|

id → letter(letter|digit) *

例2:(整型或浮点型)无符号数的正则定义

digit → 0|1|2|…|9

digits → digit digit *

optionalFraction → .digits|ε

optionalExponent → (E(+|-|ε)digits)|ε

number→ digits optionalFraction optionalExponent

2 2.15 2.15E+3 2.15E-3 2.15E3 2E-3

有穷自动机

有穷自动机 (Finite Automata,FA)由两位神经物理学家MeCuloch和Pitts于1948年首先提出,是对一类处理系统建立的数学模型

这类系统具有一系列离散的输入输出信息和有穷数目的内部状态(状态:概括了对过去输入信息处理的状况)

系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后,系统的内部状态也将发生改变

FA的典型例子:电梯控制装置

输入:顾客的乘梯需求(所要到达的层号)

状态:电梯所处的层数+运动方向

电梯控制装置并不需要记住先前全部的服务要求,只需要知道电梯当前所处的状态以及还没有满足的所有服务请求

FA模型

  • 输入带(input tape):用来存放输入符号串
  • 读头(head):从左向右逐个读取输入符号,不能修改(只读)、不能往返移动
  • 有穷控制器(finite control):具有有穷个状态数,根据当前的状态和当前输入符号控制转入下一状态

FA的表示

转换图 (Transition Graph)

  • 结点:FA的状态
  • 初始状态(开始状态):只有一个,由start箭头指向
  • 终止状态(接收状态):可以有多个,用双圈表示
  • 带标记的有向边:如果对于输入a,存在一个从状态p到状态q的转换,就在p、q之间画一条有向边,并标记上a

FA定义(接收)的语言

  • 给定输入串x,如果存在一个对应于串x的从初始状态到某个终止状态的转换序列,则称串x被该FA接收
  • 由一个有穷自动机M接收的所有串构成的集合称为是该FA定义(或接收)的语言,记为L(M)

L(M) =所有以abb结尾的字母表{a, b}上的串的集合

最长子串匹配原则(Longest String Matching Principle)

当输入串的多个前缀与一个或多个模式匹配时,总是选择最长的前缀进行匹配

在到达某个终态之后,只要输入带上还有符号,DFA就继续前进,以便寻找尽可能长的匹配

FA的分类

  • 确定的FA (Deterministic finite automata, DFA)
  • 非确定的FA (Nondeterministic finite automata, NFA)
确定的有穷自动机 (DFA)

M = (S,Σ ,δ,s0,F)

  • S:有穷状态集
  • Σ:输入字母表,即输入符号集合。假设ε不是 Σ中的元素
  • δ:将S×Σ映射到S的转换函数。 ∀s∈S, a∈Σ, δ(s,a)表示从状态s出发,沿着标记为a的边所能到达的状态。
  • s0:开始状态 (或初始状态),s0∈ S
  • F:接收状态(或终止状态)集合,F⊆ S

例:一个DFA

M = (S,Σ ,δ,s0,F)

可以用转换表表示DFA

非确定的有穷自动机(NFA)

M = (S,Σ ,δ,s0,F)

  • S:有穷状态集
  • Σ:输入符号集合,即输入字母表。假设ε 不是Σ中的元素
  • δ:将S×Σ映射到2S的转换函数。∀s∈S, a∈Σ, δ(s,a)表示从状态s出发,沿着标记为a的边所能到达的状态集合
  • s0:开始状态 (或初始状态),s0∈ S
  • F:接收状态(或终止状态)集合,F⊆ S

例:一个NFA

M = (S,Σ ,δ,s0,F)


如果转换函数没有给出对应于某个状态-输入对的信息,就把Ø放入相应的表项中

DFA和NFA的等价性
  • 对任何非确定的有穷自动机N ,存在定义同一语言的确定的有穷自动机D
  • 对任何确定的有穷自动机D ,存在定义同一语言的非确定的有穷自动机N
  • DFA和NFA可以识别相同的语言

    状态1:串以a结尾

    状态2:串以ab结尾

    状态3:串以abb结尾

    r = (a|b) * abb

    正则文法⇔正则表达式⇔FA

带有"ε-边"的NFA

M = (S,Σ ,δ,s0,F)

  • S:有穷状态集
  • Σ:输入符号集合,即输入字母表。假设ε不是Σ中的元素
  • δ:将S×(Σ∪{ε})映射到2S的转换函数。∀s∈S, a∈Σ∪{ε}, δ(s,a)表示从状态s出发,沿着标记为a的边所能到达的状态集合
  • s0:开始状态 (或初始状态),s0∈ S
  • F:接收状态(或终止状态)集合,F⊆ S


带有和不带有"ε-边"的NFA 的等价性




DFA的算法实现
  • 输入:以文件结束符eof结尾的字符串x。DFA D 的开始状态s0,接收状态集 F,转换函数move。
  • 输出:如果 D接收 x,则回答"yes",否则回答"no"。
  • 方法:将下述算法应用于输入串 x。

    s = s0;
    c = nextChar();
    while(c! = eof){
    s = move (s , c) ;
    c = nextChar () ;

    if (s在F中)
    return"yes";
    else
    return "no";

    • 函数nextChar()返回输入串x的下一个符号
    • 函数move(s, c)表示从状态s出发,沿着标记为c的边所能到达的状态

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

根据RE 构造NFA

ε对应的NFA

字母表Σ中符号a对应的NFA

r = r1r2对应的NFA

r = r1 |r2对应的NFA

r = (r1) * 对应的NFA

例:r=(a|b) * abb 对应的NFA

从NFA到DFA的转换

例1:




DFA的每个状态都是一个由NFA中的状态构成的集合,即NFA状态集合的一个子集

例2:从带有ε-边的NFA到DFA的转换




子集构造法(subset construction)

  • 输入:NFA N
  • 输出:接收同样语言的DFA D
  • 方法:一开始,ε-closure (s0)是Dstates 中的唯一状态,且它未加标记;
  while(在Dstates中有一个未标记状态T){ 
    给T加上标记;
    for(每个输入符号a){
        U = ε-closure(move(T, a));
        if (U不在Dstates中) 
            将U加入到Dstates中,且不加标记;
        Dtran[T, a]=U ; 
    } 
  }
操作 描述
ε-closure (s) 能够从NFA的状态s开始只通过ε转换到达的NFA状态集合
ε-closure (T) 能够从T 中的某个NFA状态 s开始只通过ε转换到达的NFA状态集合,即Us∈T ε-closure (s)
move(T , a) 能够从T 中的某个状态 s出发通过标号为a的转换到达的NFA状态的集合
计算 ε-closure (T)
将T的所有状态压入stack中;
将ε-closure (T)初始化为 T ;
while(stack非空){
    将栈顶元素 t 给弹出栈中;
    for(每个满足如下条件的u :从t出发有一个标号为ε的转换到达状态u)
        if (u不在ε-closure (T)中){
            将u加入到ε-closure (T)中;
            将u压入栈中; 
        } 
    }

识别单词的DFA

识别标识符的DFA

标识符的正则定义

digit → 0|1|2|…|9

letter → A|B|…|Z|a|b|…|z|

id → letter(letter|digit) *

识别无符号数的DFA

digit → 0|1|2|…|9
digits → digit digit *
optionalFraction → .digits|ε
optionalExponent → (E(+|-|ε)digits)|ε
number → digits optionalFraction optionalExponent


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

DEC → (1|...|9)(0|...|9) * |0

OCT → 0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7) *

HEX → 0x(0|1|...|9|a|...|f|A|…|F)(0|...|9|a|...|f |A|…|F) *

结合各进制:

识别注释的DFA

识别Token的DFA

词法分析阶段的错误处理

词法分析阶段可检测错误的类型

  • 单词拼写错误

    例:int i = 0x3G; float j =1.05e;

  • 非法字符

    例:~ @

词法错误检测

如果当前状态与当前输入符号在转换表对应项中的信息为空,而当前状态又不是终止状态,则调用错误处理程序

错误处理

查找已扫描字符串中最后一个对应于某终态的字符

  • 如果找到了,将该字符与其前面的字符识别成一个单词。然后将输入指针退回到该字符,扫描器重新回到初始状态,继续识别下一个单词
  • 如果没找到,则确定出错,采用错误恢复策略

错误恢复策略

最简单的错误恢复策略:"恐慌模式 (panic mode)"恢复,即:

从剩余的输入中不断删除字符,直到词法分析器能够在剩余输入的开头发现一个正确的字符为止

最后修改日期:2020年5月23日

留言

撰写回覆或留言