03-词法分析（字符串-＞单词序列）

词法分析（字符串->单词序列）

掌握：给出正规式，能描述出正规集。NFA确定化，DFA最小化，正规式、正规文法、有穷自动机之间的互相转换

单词的描述工具

3型文法（正规文法）

右线性：右部唯一非终结符在最右面

左线性：左部唯一非终结符在最左面

不允许既有右线性又有左线性的文法

正规集：正规文法对应的句子集合，即语言

正规式（正则表达式）

正规集描述的数学工具，正规式描述的集合就是正规集

• 优先级（高-低）：$*>·>|$，且左结合，闭包看作方幂，连接看作乘，或看作加
• （）只是改变运算优先级

正规式与正规文法的互相转换

正规式转换为正规文法

直到产生式右部最多有一个终结符

• $xy$ $A\longrightarrow xB$、$B\longrightarrow y$
• $x*y$ $A\longrightarrow xA$、$A\longrightarrow y$
• $x|y$ $A\longrightarrow x$、$A\longrightarrow y$

正规文法转换伟正规式

先将左部一样的写到一起，消除终结符，直到只剩下一个起始符号（注意带入时并不是可以消除产生式，若带入后的产生式是不可到达的才能删除）

• $A\longrightarrow xB$、$B\longrightarrow y$ $A=xy$
• $A\longrightarrow xA|y$ $A=x*y$
• $A\longrightarrow x$、$A\longrightarrow y$ $A=x|y$

有穷自动机

DFA（确定有穷自动机）

确定：一个状态面临同一输入符号，有确定的下一个状态，即相同输入符号弧只有一条

• 五元组
  • 状态集：所有状态
  • 输入符号表：弧上
  • 转换函数集：有向弧，合并时是逗号分隔，并非竖线
    • $f(当前状态，输入符号)=变换后状态$
    • 不允许输入符号是$\epsilon$
    • 一个输入符号只有一种状态
  • 唯一初态：箭头指向的状态
  • 终态集：双圈状态
• 矩阵表示
  • 行是输入符号
  • 列是状态
    • 起始状态一般第一行
    • 最后一列是区别终态和非终态用的标记位
  • 表内是当前状态对应输入符号转换后的状态

NFA（不确定有穷自动机）

不确定：一个状态面临同一输入符号，有多个下一个状态，即相同输入符号弧只有多条

• 五元组

  • 状态集：所有状态
  • 输入符号表：弧上
  • 转换函数集：有向弧，合并时是逗号分隔，并非竖线
    • $f(当前状态，输入符号)=变换后状态集$，若变换后状态集是空集，表示没有射出该输入符号的弧
    • 允许输入符号是$\epsilon$
    • 同一输入符号可以到达多个状态
  • 初态集：箭头指向的状态
    • 允许有多个起始状态
  • 终态集：双圈状态

• 矩阵表示

  • 行是输入符号
  • 列是状态
    • 起始状态一般第一行
    • 最后一列是区别终态和非终态用的标记位
    • 表内是当前状态对应输入符号转换后的状态

NFA确定化

运算规则

• $\epsilon$闭包：$\epsilon -closure(状态集)$=状态集中的每个元素经过任意$\epsilon$弧到达的状态集合（注意默认自己到自己有一条$\epsilon$弧，所以当前状态集也会在到达状态集中）
• a弧转换：$moce(状态集,输入符号)$=从状态集出发经过一条输入符号弧到达的状态集

步骤

1. 唯一初态：将NFA的初始状态集，做$\epsilon$闭包运算得到的集合，作为DFA的初始状态
2. 转换函数和其他状态：构造NFA矩阵，反复对已经出现的状态集合，先做a弧转换得到集合后，再对该集合做$\epsilon$闭包，得到新状态集合（集合中有NFA终止状态则该集合是DFA终止状态），直到不出现新状态为止
3. 根据矩阵画出转换图

DFA最小化

理论支持

同一语言的DFA可能不同，但最小DFA是唯一的

1. 删除多余状态：不可到达状态、不可终止状态
2. 合并等价状态（不能删除转换函数）
   • 一致性条件：同是非终态或同是终态
   • 蔓延性条件：对每一个相同的输入符号，到达的状态是一样的

分割法（找不等价状态）

1. 根据一致性条件对所有状态进行分组：终态和非终态分组
2. 对同一组的状态使用蔓延性条件检查：当到达状态集中出现不等价状态，逆推这组状态部分不等价，就分隔，反复分隔，直到不能分隔，若还有非单个元素的集合，则该集合中的状态等价
   • 当某些状态没有射出要检查的弧时
     • 增加弧射到死状态
     • 死状态面临任何输入符号时都到自己
     • 死状态属于非终态
     • 算法结束后将死状态删除

正规式与NFA互相转换

正规式转换NFA

1. 引入两个状态，x起始状态，y终止状态
2. 弧上是正规式
3. 根据三条规则将规则分解，直到每条弧上只有一个输入符号

NFA转换正规式

1. 增加一个状态x射出$\epsilon$所有的起始状态
2. 增加一个状态y被所有的终止状态射入$\epsilon$弧
3. 根据这三条规则将原来的所有状态消除，只剩下x和y，弧上的就是正规式

正规文法与NFA互相转换

正规文法转换NFA

1. 文法每个非终结符都对应NFA的一个状态（起始符号就是起始状态）
2. 文法终结符对应NFA输入符号
3. 新增加一个终止状态Z
4. NFA转换函数由这两条规则转换
   • $A\longrightarrow a$：$f(A,a)=Z$，即A状态射出a弧到终态
   • $A\longrightarrow aB$：$f(A,a)=B$，即A状态射出a弧到B

DFA转换正规文法

1. 自动机的状态对应文法的非终结符
2. 自动机起始状态对应文法起始符号
3. 自动机的输入符号（字母表）对应文法的终结符
4. 文法转换函数由这两条规则转换
   • $f(A,a)=B$：$A\longrightarrow aB$，即A状态射出a弧到B
   • 对于终态Z，增加$Z \longrightarrow\epsilon$