词法分析的主要任务

从左向右逐行扫描源程序的字符，识别出各个单词，确定单词的类型。

将识别出的单词转换成统一的机内表示——词法单元（token）形式。

token：<种别码，属性值>

字母表

字母表 $\Sigma$ 是一个有穷符号集合

• 符号：字母、数字、标点符号、...

字母表上的运算

• 字母表 $\Sigma_1$ 和 $\Sigma_2$ 的乘积(product)
• 字母表 $\Sigma$ 的 n 次幂(power)
• 字母表 $\Sigma$ 的正闭包(positive closure)
• 字母表 $\Sigma$ 的克林闭包(Kleene closure)

串 String

设 $\Sigma$ 是一个字母表，$\forall x\in \Sigma^*$ ，x 称为是 $\Sigma$ 上的一个串

串是字母表中符号的一个有穷序列

串 s 的长度，记作 $|s|$，是指 s 中符号的个数

空串是长度为 0 的串，用 $\varepsilon$ (epsilon) 表示

串上的运算——连接