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

词法剖析

1. 基本功能

1.1 词法规定

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

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

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

字符与字符串

• 字母表

• 符号串: *中的元素

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

1.2 定义：正规式

递归定义: 构造方法

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

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

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

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

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

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

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

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