词法分析

回顾

正则表达式（RE）

每个正则表达式$r$定义（表示）一个语言，记为$L(r)$

• 一个正则语言可以对应多个正则文法

正则定义

给一些RE命名，并在之后的RE中像使用字母表中的符号一样使用这些名字

有穷自动机（FA）

• 组成
  • 输入带、读头、有穷控制器
• 表示
  • 转换图：初始状态、终止状态、有向边
  • 转换表
• FA接受的语言–$L(M)$：由一个有穷自动机$M$接受的所有串构成的集合
• 最长字串匹配原则
  • 由输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配
• 与正则表达式等价

确定的有穷自动机（DFA）

• $M=(S, \Sigma, \delta, s_0, F)$
  • (有穷状态集，输入字母表，转换函数，开始状态，接受状态)
• 容易实现

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

• $M=(S, \Sigma, \delta, s_0, F)$
• 直观

带$\varepsilon$的NFA

等价性

正则文法 $\Longleftrightarrow$ 正则表达式 $\Longleftrightarrow$ FA

转换

构造分析器时，真正实现模拟的是DFA，所以需要将正则表达式转换到DFA

(1) 根据RE构造NFA

(2) 从NFA到DFA的转换

• 子集构造法

词法分析阶段的错误处理

• 错误类型
  • 单词拼写错误、非法字符

错误检测

如果当前状态与当前输入符号在转换表对应项中的信息为空，而当前状态又不是终止状态，则调用错误处理程序

错误处理

查找已扫描字符串中最后一个对应于某终态的字符

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

错误恢复策略

• “恐慌模式”
  • 从剩余的输入中不断删除字符，知道词法分析器能够在剩余输入的开头发现一个正确的字符为止