Arya

第三章 词法分析 note
[+] 重新整理了一下笔记的方式,原先杂乱无章,还是决定用章节的方式来展示第三章 词法分析正则表达式此处的RE是正...
扫描右侧二维码阅读全文
28
2019/01

第三章 词法分析 note

[+] 重新整理了一下笔记的方式,原先杂乱无章,还是决定用章节的方式来展示

第三章 词法分析

正则表达式

Image3-2.png

Image3-3.png

此处的RE是正则表达式的缩写

例:令∑={a,b}

  • L(a|b)=L(a)UL(b)={a}U{b}={a,b}
  • L((a|b)(a|b))=L(a|b)L(a|b)={a,b}{a,b}={aa,ab,ba,bb}
  • L(a)=(L(a))={a}*={ε,a,aa,aaa……}
  • L((a|b))=L((a|b))={a,b}*={ε,a,b,aa,ab,ba,aba……}
  • L(a|a*b)={a,b,ab,aaab,aaab……}

Image3-4.png

Image3-5.png

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

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

正则定义

正则定义是具有如下形式的定义序列:
Image3-6.png

故正则定义是给一些RE命名,并在之后的RE中像使用字母表中的符号一样使用这些名字。

这里也举了一个简单的例子

  • C语言中标识符的正则定义
    digit->0|1|2|……|9
    letter_->A|B|C|……|Z|a|b|……|z|_
    id->letter_(letter_|digit)*
  • (整型或浮点型)无符号数的正则定义
    digit->0|1|2|……|9
    digits->digit digit*
    optionalFranction->.digits|ε
    optionalExponent->(E(+|-|ε)digit)|ε
    number->digits optionalFraction optionalExponent

所以number可表示为以下几种形式 :
2 2.15 2.15E+3 2.15E-3 2E-3

有穷自动机

  • 有穷自动机是对一类处理系统建立的数学模型
  • 这类系统具有一系列离散的输入输出信息有穷数目的内部状态(状态:概括了对过去输入信息处理的状况)
  • 系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后,系统内部状态也将发生变化

接下来举了一个FA的例子
Image3-7.png

Image3-8.png

FA定义(接收)的语言

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

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

FA的分类

FA分为两类:

  • 确定的FA(Deterministic finite automata,DFA)
  • 非确定的FA(Nondeterministic finite automata,NFA)

确定的有穷自动机(DFA)
DFA的表达式如下:

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

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

下面举了一个小例子

Image3-9.png

所以一个DFA既可以用转换图表示,也可以用转换表表示,二者之间的关系是等价的

非确定的有穷自动机(NFA)
NFA的表达式如下:

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

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

这里也举了一个例子
Image3-10.png

这里可以做一个小总结,从以上可以看出DFA的每个输入对状态产生结果都是互不相同的,而NFA则存在可以有不同输入得到同一结果

DFA和NFA的等价性

  • 对任何NFA N,存在识别同一语言的DFA D
  • 对任何DFA D,存在识别同一语言的NFA N

接下来又是一个小例子

Image3-11.png

带有"ε-边"的NFA
NFA的表达式如下:

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

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

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

Image3-13.png

DFA的算法实现

  • 输入:以文件结束符号eof结尾的字符串x。DFAD的开始状态s0,接收状态集F,转换函数move
  • 输出:如果D接收x,则回答"yes",否则回答"no"

接下来用伪代码实现了一个例子,输入串x

s=s0;
c=nextChar();
while(c!=eof){
    s=move(s,c);//move(s,c)表示从状态s出发,沿着标记为c的彼岸所能到达的状态
    c=nextChar();//nextChar()返回输入串x的下一个符号
}
if(s在F中)
    return "yes";
else
    return "no";

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

因为将RE直接转换为DFA很困难,所以我们一般先将RE转为NFA再转换为DFA
即:RE->NFA->DFA
Image3-14.png

Image3-15.png

接下来举了一个例子

Image3-16.png

从NFA到DFA的转化方法

这里举了两个例子

Image3-17.png

上面的正则表达式为

r=aa*bb*cc*

接下来举了一个稍微特殊的例子

带有"ε-边"的NFA到DFA的转换
Image3-18.png

上面的正则表达式为

r=0*1*2*

识别单词的DFA

  • C语言中标识符的正则定义
    digit->0|1|2|……|9
    letter_->A|B|C|……|Z|a|b|……|z|_
    id->letter_(letter_|digit)*

DFA图如下
Image3-19.png

  • (整型或浮点型)无符号数的正则定义
    digit->0|1|2|……|9
    digits->digit digit*
    optionalFranction->.digits|ε
    optionalExponent->(E(+|-|ε)digit)|ε
    number->digits optionalFraction optionalExponent

NFA图如下

Image3-20.png

再由NFA推出DFA

Image3-21.png

接下来将这三种进制整合到一个DFA图中

Image3-22.png

识别注释的DFA

Image3-23.png

识别token的DFA

Image3-24.png

这张图中并没有提到关键字这个非常重要的单词类型,事实上关键字是字母组成的串,所以我们可以使用识别标识符的方式来识别关键字,即,每当识别出一串字符串时,我们可以排查这串字符串是否在关键字表中,若在,则识别为关键字,反之则为标识符

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

  • 单词拼写错误,例如:
    int i=0x3G;
    float j=1.05e
  • 非法字符,例如:
    ~@

词法错误检测:
如果当前状态与当前输入符号在转换表对应项中的信息为空,则报错,调用错误处理程序

错误处理的方式
查找已扫描字符串中最后一个对应于某终态的字符

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

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

  • 从剩余的输入中不断删除字符,直到词法分析器能够在剩余输入的开头发现一个争取的字符为止
Last modification:January 28th, 2019 at 11:08 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment