[编译原理与设计] 2 词法分析编译原理计算机科学

预处理：转换为字符串或字符
词法分析 1. 基本功能 1.1 词法规则

语言要素：语法（语言的描述规则）、语义（语言的含义）
巴科斯-诺尔范式BNF[元语言符号]
- <>:
- →(::=):表示“定义为”或“由……组合成”
- |: “或”

字符与字符串

字母表Σ
符号串ω: Σ*中的元素
- 符号串长度|ω|
- 前缀、真前缀
- 后缀、真后缀
- 子符号串（子串）

1.2 定义：正规式
递归定义: 构造方法

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

ε和Ф是∑上的正规式，它们表示的正规集分别为{ε}和Ф
对任何a∈∑, a是∑上的正规式,它的正规集为{a}
若r,s都是正规式 , 它们的正规集分别为R和S , 则(r|s)、(r·s)、(r)也是正规式，它们分别表示的正规集是：R∪S,RS,R
有限次使用上述三条规则构成的表达式，称为∑上的正规式，仅
由这些正规式表示的集合为正规集

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