编译原理课程学习-词法分析

概念整理

相关资料来源：慕课哈工大编译原理课程

正则表达式

• 定义：用于描述正则语言更紧凑的表示方法，用符号为r表示
• 每个正则表达式 r定义（表示） 一个语言，记为L(r )。
• 运算：*、 连接、 | （优先级从高到低）

正则定义

• 就是给一个正则表达式RE取一个别名，就可以像字母表内的元素一样来使用

有穷自动机（FA）

• 定义：根据目前所处的状态和输入信息来决定后继行为的数学模型（类似电梯）

• 用M表示有穷自动机，某个串可以从初始状态到达最终状态则说该串被FA接收

• 由一个有穷自动机M接收的所有串构成的集合称为是
  该FA定义（或接收）的语言，记为L(M )

• 表示：转换图和转换表

  • 转换图：初始状态（start箭头指向）、终止状态（双圈）、带有标记的有向边、其他结点

    

  • 转换表：一个二维表，填写对应输入下的下一结点

• 分类：确定的有穷自动机（DFA）

  ​ 非确定的有穷自动机（NFA）

DFA

• 形式化定义M = ( S， Σ ， δ，s₀， F )
  S： 有穷状态集（就是结点）
  Σ： 输入字母表，即输入符号集合。 假设ε不是 Σ中的元素
  δ： 将S× Σ映射到S的转换函数。转换到的新状态唯一
  s₀： 开始状态 (或初始状态)， s₀∈ S
  F： 接收状态（或终止状态） 集合， F⊆ S

  ​

NFA

• 形式化定义M = ( S， Σ ， δ， s₀， F )
  S：有穷状态集
  Σ： 输入符号集合，即输入字母表。假设ε 不是Σ中的元素
  δ： 将S× Σ映射到2^S的转换函数。转换的新状态不唯一，用一个集合来表示
  s₀：开始状态 (或初始状态)， s₀∈ S
  F：接收状态（或终止状态）集合， F⊆ S

  

带有“ε-边”的NFA

• 形式化定义M = ( S， Σ ， δ， s₀， F )
  S：有穷状态集
  Σ： 输入符号集合，即输入字母表。假设ε不是Σ中的元素
  δ： 将S× (Σ∪ {ε})映射到2^S的转换函数。区别在于转换的条件可以是ε
  s₀：开始状态 (或初始状态)， s₀∈ S
  F：接收状态（或终止状态）集合， F⊆ S

ps:DNA和NFA是等价的，都能互相转换

​ 带有和不带有“ε-边”的NFA 也是等价的

概念区别总结

• 正则文法：3型文法，描述正则语言的规则 （推导式）
• 正则表达式：描述正则语言的简易形式 （*、 连接、 | 和元素连接的形式）
• FA:根据当前情况决定后继的数学模型 （转换图、转换表）

三者都是可以互相转换的

正则表达式到有穷自动机

NFA是比较直观也容易转化的，而DFA看起来比较复杂，但是对于计算机而言，确定的自动机处理起来才是比较舒服的。因此，从正则表达式到DFA，我们可以先从正则表达式到NFA，再从NFA到DFA

从正则表达式到NFA

转换原理

从NFA到DFA

若转换后的节点有多种情况，则可以将这个集合作为一个新的节点，再判断这个集合内的元素是否有可以转换的新结点

带有ε 边的NFA，在转换的过程中记住，ε 边可以不用转换直接到达下一个结点。

具体的过程可以看哈工大编译原理课程

视频介绍的方式还是比较直观的，其方法适合直接观察直接的转换。

如果需要真正的解题过程需要列出转换表，重新构造转换图。可以参考博文NFA到DFA

总结

词法分析部分的概念还是比较多的，重点在于理解每一个概念的基本定义，通过他们的联系串联起来就可以很好地记住。

词法分析的目的在于将字符流转换单词流，从而作为语法分析的输入，这一章的内容其实就是在说这一个步骤。