预处理：转换为字符串或字符

词法剖析

1. 基本功能

1.1 词法规定

• 语言因素：语法（语言的形容规定）、语义（语言的含意）

• 巴科斯 - 诺尔范式 BNF[元语言符号]

  • <>:
  • →(::=): 示意“定义为”或“由……组合成”
  • |:“或”

字符与字符串

• 字母表 Σ

• 符号串 ω: Σ* 中的元素

  • 符号串长度 |ω|
  • 前缀、真前缀
  • 后缀、真后缀
  • 子符号串（子串）

1.2 定义：正规式

递归定义: 构造方法

设∑为无限字母表，在∑上的正规式与正规集可递归定义如下

ε 和Ф是∑上的正规式，它们示意的正规集别离为 {ε} 和Ф

对任何 a∈∑, a 是∑上的正规式, 它的正规集为{a}

若 r,s 都是正规式 , 它们的正规集别离为 R 和 S , 则 (r|s)、(r·s)、(r) 也是正规式，它们别离示意的正规集是：R∪S,RS,R

无限次应用上述三条规定形成的表达式，称为∑上的正规式，仅
由这些正规式示意的汇合为正规集

正规式：汇合符号，正规集：汇合
正规式的运算

字母表→根本正则式→递归正则式
根本正则式: 字母自身

正规式：词法的示意办法
确定无限状态机：词法的识别方法