输入缓冲

在实践中，很多情况需要我们至少向前看一个字符。比如我们只有读取到一个非字母或数字的字符之后才能确定达到了一个标识符的末尾，因此这个字符不是id的词素的一部分。在C语言中，像+、-、>、<、==这样的单字符运算符也可能是->、<=、>=、+=这类双字符运算符的开始字符。因此我们介绍一种双缓冲区方案，这种方案能够安全地处理向前看多个字符的问题。

缓冲区对和哨兵标记

CRE：缓冲区作用是防止”向前看”的过程中进行多次字符移动和覆盖。也就是要保证词素连续性。

每个缓冲区容量都是N个字符，通常N是一个磁盘块的大小，例如4096字节。我们可以使用系统读取命令一次将N个字符读入缓冲区而不是每个字符调用一次系统读取。如果剩余字符不足填满缓冲区，就使用特殊字符eof标记为结束。

程序为输入维护了两个指针：

1. lexemeBegin指针：指向词素的开始处。当前我们正试图确定这个词素的结尾。
2. forward指针：它一直向前扫描，直到发现某个模式被匹配为止。

让每个缓冲区在末尾包含一个哨兵(sentinal)标记，这个哨兵标记必须是一个在源程序中不会出现的特殊字符，一个自然的选择就是eof。（eof仍然可以用来标记整个输入的结尾，任何不是出现在缓冲区末尾的eof都表示到达了输入的结尾）

词法单元的规约

• 串和语言

字母表(alphabet)是一个有限的符号集合。例如字母表、数位等。（ASCII和Unicode也是字母表的例子）

串(string)是该字母表中符号的一个有穷序列。

语言(language)是给定字母表上一个任意的可数的串集合。（这个定义非常宽泛）

• 语言上的运算

运算	说明
L和M的并	常见的集合运算
L和M的连接	从L中任取一个串和M中任取一个串连接后得到的所有串的集合
L的Kleene闭包(L*)	将L连接0次或多次后得到的串集
L的正闭包(L+)	将L连接1次或多次后得到的串集

• 正则表达式

加入要描述C语言的所有合法标识符的集合，差不多就是L(L∪D)*所定义的语言（还应该包含下划线）。这种首先给出字母和数位集合的名字，然后使用并、连接、闭包这些运算来描述标识符，这种处理方法非常有用。因此人们常常使用一种称为正则表达式的表示方式来描述语言。

假定r和s都是正则表达式，分别表示语言L(r)和L(s)。那么：

1. (r)	(s)是一个正则表达式，表示语言L(r)∪L(s)。

2. (r)(s)是一个正则表达式，表示语言L(r)L(s)。
3. (r)*是一个正则表达式，表示语言(L(r))*。

优先级：

1. 一元运算符（”*“）具有最高优先级，并且是左结合的。
2. 连接具有次高优先级，也是左结合的。

3. ”	“的优先级最低，也是左结合的。

• 正则定义

正则定义：为了方便表示，我们可能希望给某些正则表达式命名，并在之后的正则表达式中像使用符号一样使用这些名字。

正则定义示例：
letter_ → A|B|C|..|Z|a|b|c|..|z|_（字母和下划线）
digit → 0|1|2|..|9（数字 ）
id → letter_ (letter_ | digit)*（C语言标识符 ）

• 正则表达式扩展

1. 一个或多个实例。单目后缀运算符+表示一个正则表达式及其语言的正闭包。
2. 零个或者一个实例。单目后缀运算符?意思是零个或者一个出现。

3. 字符类。a

   b

   c可以缩写为[abc]。a

   b

   ..

   z可以缩写为[a-z]。

（END）