tk's blog
  • tk's blog Read Me
  • 算法相关
    • 数据结构
      • 【集训整理】 旋转treap模板
      • 二叉树及相关数据结构的java语言实现
      • 快乐树0x01:AVL树的java实现
      • 快乐树0x02 线段树实现(c++)
      • 链表的Java语言实现
    • 算法
      • DP的背包问题小结-java语言描述
      • 【集训整理】2-SAT问题 模板题
      • 【集训整理】Tarjan算法 模板题
      • 【集训整理】差分约束 模板题
      • 【集训整理】最近公共祖先LCA 模板题
      • 二分查找与二分答案-java实现
      • 动态规划-java语言练习一:暴力DP
      • 快速幂
      • 状态压缩DP-java描述
      • 差分
      • 乘法逆元
    • 题解
      • CFRound-GoodBye2022题解
  • java相关
    • Java与算法竞赛——注意事项摘录
    • java面向对象简要总结 一
    • java面向对象简要总结 三
    • java面向对象简要总结 二
  • 后端相关
    • Linux-Crontab命令
    • Spring Data JPA 使用方法
    • Spring集成Artemis实现JSM的异步消息传递
    • Spring使用自定义配置项
    • MIT6.824分布式系统Lab1.MapReduce笔记
    • MIT6.824分布式系统Lab2-Raft-A笔记
    • MIT6.824分布式系统Lab2-Raft-B笔记
  • 杂谈
    • 杂谈-关于2021
  • 杂项
    • c语言 scanf的返回值
    • 系统设计
  • 计科基础
    • 编译原理
      • 编译原理:词法分析笔记
    • CSAPP 第二章笔记
    • 计算机组成原理笔记
    • CSAPP Lab1. Datalab
    • CSAPP Lab2 Bomblab
  • C++每日一题
    • C++每日一题 Day 1 肥宅水
    • C++每日一题 Day 2 数字反转
    • C++每日一题 Day 3 理五的凡尔赛风气
    • C++每日一题 Day 4 我喜欢这个数
    • C++每日一题 Day 5 数字楼梯
    • C++每日一题 Day 6 插火把
    • C++每日一题 Day 7 贪吃蛇
    • C++每日一题 Day 8 蒙德最强战力
    • C++每日一题 Day 9 璃月七星选举
    • C每日一题 Day 2 肥宅水
    • C每日一题 Day 3 理五的凡尔赛风气
    • C语言每日一题 Day 1 荧妹好感队
由 GitBook 提供支持
在本页
  • 定义
  • 单词
  • 正则表达式
  • 有限状态自动机
  • NFA的确定化
  • 三个重要的操作(概念):
  • 确定化的步骤
  • NFA确定化实例:
  1. 计科基础
  2. 编译原理

编译原理:词法分析笔记


定义

词法分析是将源程序从左至右,逐个字符地扫描,然后产生一个个的单词符号,将源程序转换成单词符号。之后就可以根据单词符号做后续的分析。

单词

单词符号分为5类:

  1. 标识符,如变量、数组、函数等,如length,nextch等;

  2. 基本字,也叫保留字,如if,while等等;

  3. 常数,如3.1415926;

  4. 运算符,如+,-,*, /, >=, !, ==, &&等;

  5. 界符,如;,(.),:等。

表示方法:

识别出的单词应该用二元式来表示,以便后续处理:(单词类别,单词属性)

e.g.(标识符的编码,标识符的名称“i”)

正则表达式

设正则表达式r表示语言L(r),则L(r)就是根据r的规则递归地定义的。

正则表达式简介书面地规定了一门语言。

归纳步骤:

  • (r) | (s):可选 r 或 s;

  • (r)(s):连接r和s;

  • (r)*:称为Kleene闭包,也就是将L连接0次或多次后得到的串集;

  • (r):括号不影响其所表示的语言。

e.g.

(a | b)* == (a*b*)*,都表示由任意个a和b组成的串,如空串ε、a、ab、ba、baba等。

有限状态自动机

有限状态自动机用具体程序的方式实现了正则表达式的匹配。

有限状态机有一系列有限状态的集合和一些从一个状态通往另一个状态的边,其中一个状态是初态,某些状态是终态。

有限状态自动机分为两类:

  1. 不确定的有限状态自动机,英文简写NFA。其对边上的标号没有限制,可以以空串ε作为标号,一个符号也可以标记离开同一个状态的多条边(可以有多个同标号的出边,所谓不确定具体去哪个状态)。

  2. 确定的有限状态自动机,DFA,有且仅有一条以某符号为标号的离开该状态的边。

DFA是NFA的一个特例,它没有对输入ε的转换动作,且对于状态s和输入符号a,有且只有一条标号为a的边离开s。

DFA的例子:

NFA的确定化

由于NFA在转移时具有不同的可能性,所以在具体实现的运行时往往效率较低,因此需要一种方法将NFA转化为确定的DFA。

三个重要的操作(概念):

  • 状态集的空闭包集合(ε-闭包):

若I是一个状态集合,其空闭包集合就是I中从任意元素出发经过任意条ε弧(标号为ε的边)能到达的状态的集合,记为ε-closure(I);

  • 状态集的a弧转换:

I中的任意状态经过一条a弧能到达的所有状态的集合,记为move(I,a);

  • 状态集的a弧转换的闭包Ia:

就是状态集I的a弧转换的ε闭包,即

Ia=ε−closure(move(I,a))I_a = ε-closure(move(I,a))Ia​=ε−closure(move(I,a))

确定化的步骤

第一步:规则转换

将NFA转换成标准形式:

第二步:状态合并

为了确定化DFA,我们需要从初态开始,根据ε-闭包将闭包内的状态合并为一个新的状态,然后根据*(输入的字符)弧转换引出新的状态,直到全部状态都已转换完成。

实例:原来的NFA:

首先求初状态的ε-闭包,即{i,1,2},作为初始集合S;

求出S的a弧、b弧转换的ε-闭包,即Ia、Ib,得到新状态A、B:

A = {1,2,3},B={1,2,4}

以此类推,求出新状态的的a弧、b弧转换的ε-闭包,直至不再产生新状态(新集合)为止。一般做法是列出列为I、Ia、Ib的表格,每个新状态开一行;每个产生的新集合(状态)都要再去求Ia和Ib,直到不产生新状态(产生表的新行)为止。接下来只需要根据表合并新状态,然后构造DFA即可。

这样就完成了NFA到DFA的等价转化。其中产生新状态和求*弧转换的表,称为Dtran表。

NFA确定化实例:

NFA:

列表:

合并状态:

上一页编译原理下一页CSAPP 第二章笔记

最后更新于2年前

NFA的例子:

img
img

根据表构造DFA:

参考:

编译原理学习笔记-3:词法分析(一)基本过程、正规式和有限自动机 - 腾讯云开发者社区-腾讯云 (tencent.com)
mgcuH.png