编译原理-词法分析

编译原理-词法分析

词法分析器

• 词法分析器: 把构成源程序的字符流翻译成记号(token)流，还完成和用户接口的一些任务
  其中:
  • 词法单元: 亦称单词, 编程语言中合法的字符串
  • 词法记号: 满足某种给定规则(模式)的词法单元
    示例: 对于词法记号NUM, 其词法单元可能有3.1, 10, 2.8E12等数字, 其"模式"即"认定为数字的字符串"

串和语言

• 字母表: 符号的有限集合. 示例: Σ = {0,1}
• 串: 符号的有穷序列. 示例: 0110,ε(长度为0的空串)
  运算:
  • 连接: xy, 其中sε = εs = s
  • 积: $ s^0 = \epsilon , s^i = s^{i-1}s(i>0) $
• 语言: 字母表上的一个串集. 示例: {ε, 0, 11, …}, {ε}, ∅
  运算:
  • 和: $ L \bigcup M = {s|s \in L 或 s \in M } $
  • 连接: $ LM = {st|s \in L 且 s \in M} $
  • 指数: $ L^0={ε}, L^i = L^{i-1}L $
  • 闭包: $ L^* = L^0\bigcup L^1\bigcup L^2\bigcup … $
  • 正闭包: $L^+ = L^1 \bigcup L^2 \bigcup ... 并且 L^* = L^0 \bigcup L^+$L+=L1⋃L2⋃...并且L∗=L0⋃L+

正规式(正则表达式)

• 正规式: 按照一定的定义规则, 由较简单的正规式构成, 每个正规式r表示一个语言L®
• 正规式是用于说明词法单元如何对应到词法记号的模式。与非形式化的描述相比，正规式更具形式化，更加精确
• 定义如下

正规式	定义的语言	备注
$\epsilon$ϵ	$\{\epsilon\}${ϵ}	以下定义均在字母表$\sum$∑中
a	{a}	$a \in \sum $
r | s	$L(r) \bigcup L(s)$L(r)⋃L(s)	r和s为正规式
rs	L®L(s)	L®L(s) = L(s)L®
$ r^* $	$ L®^* $	r为正规式

• 运算符优先级: * > 连接运算 > |
• 举例

正规式	定义的语言
KaTeX parse error: Expected 'EOF', got '&' at position 6: (a &̲#124; b)(a &…	{aa, ab, ba, bb}
KaTeX parse error: Expected 'EOF', got '&' at position 6: (a &̲#124; b)^*	由a和b构成的所有串集

词法记号的识别

• 图形化:

正规式	状态转换图
$d \rightarrow a$d→a
$d \rightarrow ab$d→ab
KaTeX parse error: Expected 'EOF', got '&' at position 19: …rightarrow a &̲#124; b
$d \rightarrow a^*$d→a∗
$d \rightarrow a?$d→a?(a出现1次或0次)

• 举例:

正规式	状态转换图
$d \rightarrow a(a | b)^* $

有限自动机

• 识别器: 是一个程序，取串x作为输入，当x是语言的句子时，它回答“是”，否则回答“不是”
• 状态转换图即有限自动机, 可以作为识别器

确定的有限自动机(DFA)

• DFA是一个数学模型, 包括
  • 状态集合S
  • 输入字母表$\sum$∑
  • 转换函数$move: S \times \sum \rightarrow S$move:S×∑→S
  • 唯一的初态$s \in S$s∈S
  • 终态集合$F \subseteq S$F⊆S

不确定的有限自动机(NFA)

• NFA是一个数学模型, 包括
  • 状态集合S
  • 输入字母表$\sum$∑
  • 转换函数$move: S \times ( \sum \bigcup \{ \epsilon \}) \rightarrow S$move:S×(∑⋃{ϵ})→S (此处$\epsilon$ϵ理解为"未知")
  • 唯一的初态$s \in S$s∈S
  • 终态集合$F \subseteq S$F⊆S

DFA与NFA的对比

• 举例:

正规式	DFA	NFA
$ (a | b)^*ab $
状态转移表

1. NFA中允许$\epsilon$ϵ转换边, 即允许$\epsilon$ϵ的输入, 而DFA不允许
2. NFA中的move(s,a)可能是个多元集合, 而DFA中的move(s,a)最多一个元素
3. DFA:
   • 优点: 快速定位
   • 缺点: 字母表过大或大部分转换状态为空集时浪费空间
4. NFA:
   • 优点: 表较小
   • 缺点: 输入字符包括$\epsilon$ϵ, 一个状态对于某个字符，可能有多条输出边
5. NFA更贴近于人们对正规式的认识
6. DFA因为每次状态转换都是确定性的

DFA的构建

• 由自然语言描述构建
  方法:
  1. 列出所有可能的状态
  2. 从各个状态出发, 构造边及输入字符记号
• 由正规式构建
• 由正规式创建NFA再构建
  1. NFA构建
     NFA创建, 有如下框架:

正规式	NFA
$\epsilon$ϵ
a
s | t
st
s*

对于加括号的正规式(s), 使用N(s)作为其NFA
举例:

正规式	NFA
KaTeX parse error: Expected 'EOF', got '&' at position 6: (a &̲#124; b)^{*}ab

2. NFA转化为DFA(子集构造法)
   • 有限自动机理论: 设L为一个有不确定的有限自动机接受的集合，则存在一个接受L的确定的有限自动机
   • DFA的一个状态是NFA的一个状态集合, 即对于一个输入$a_1a_2...a_n$a1​a2​...an​ NFA可以到达所有状态为: $s_1, s_2, ..., s_k$s1​,s2​,...,sk​, 这些状态的集合为DFA的一个状态
   • 如上述的$ (a|b)^*ab $ 其NFA为
     则对于各种输入, 有如下集合:

集合名称	输入	状态
A	$\epsilon$ϵ	{0,1,2,4,7}
B	$a$a	{1,2,3,4,6,7,8}
C	$b$b	{1,2,4,5,6,7}
D	$b, a, b$b,a,b	{1,2,4,5,6,7,9}

依据上表列出状态转换表:

再画出转换图:

3. DFA化简

   • 通常由上述方法得来的DFA并非最简的

   • 状态的可区分性: 存在串w, 使得从状态s开始, 对w进行状态转换, 最终停在某个接受状态; 而对从t开始的状态转换停在了某个非接收状态
     **简言之, 对于两个状态, 若其对于所有相同的输入转换后有相同的接受状态, 则其为不可区分的, 否则可区分 **
     如上面的转换图 A与B可区分, A与C不可区分

   • 途径:

     • 根据状态是否可以区分，将状态划分成若干个集合，每个集合内的状态之间都不可区分，而任意两个集合中的元素都是可以互相区分的
     • 依据原始的DFA，在合并后的状态基础上，建立新的状态转换关系

   • 但是, 化简时DFA的状态转换函数必须是一个全函数(对于所有的输入都有对应的边，比如有a，b两个输入，那么每个状态必须有a，b两个出边，否则称之为部分函数)
     部分函数需要添加死状态变成全函数，死状态即是添加一个状态，使所有缺失的边都指向它，它自己的所有输出边也指向本身，如下图
     
     加上了死状态E
     但对于$(a|b)^*ab$(a∣b)∗ab, 无需加死状态

   • 化简$(a|b)^*ab$(a∣b)∗ab
     首先将接受状态和非接受状态分为两个部分
     {A, B, C}, {D}
     对于非接受状态，判断其转换函数
     move({A, B, C}, a} = {B}结果还是非接受状态
     move({A, B, C}, b} = {C, D}结果出现接受状态，而这种 改变是由于状态B造成，因此将B拆分出来
     {A, C}, {B}, {D}
     再重复以上过程
     move({A, C}, a} = {B}
     move({A, C}, b} = {C}
     发现A，C不存在例外了
     为格式化，我们将字母变成数字表示，将A,C合并
     其中0代表A, C, 1代表B, 2代表D

   • 最终:
     

至此, 词法分析完成!

参考链接:

https://blog.csdn.net/zp_icenow/article/details/82661407

个人博客:

https://qidianxuan.cn/2019/11/24/%E7%BC%96%E8%AF%91%E5%8E%9F%E7%90%86-%E8%AF%8D%E6%B3%95%E5%88%86%E6%9E%90/