- 语言中具有独立含义的最小语法单位是符号(单词),如标识符、无符号常数与界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。
- 词法规则可用3型文法(正规文法)或正规表达式描述,她产生的集合是语言规定的基本字符集∑(字母表)上的一个子集,称为正规集。
正规式和正规集:
对于字母表∑,其上的正规式及其表示的正规集可以递归定义如下:
1. ε(epsilon)是一个正规式,它表示集合 L(ε)={ε}。
2. 若a是Σ上的字符,则a是一个正规式。它所表示的正规集为{a}。
3. 若正规式 r 和 s 分别表示正规集L(r)和L(s),则:
a. r|s 是正规式,表示集合 L(r)∪L(s)。
b. r ·s 是正规式,表示集合L(r)L(s)。
c. r* 是正规式,表示集合(L(r))* 。
d. (r) 是正规式,表示集合 L(r)。
- 仅通过有限次地使用上述3个步骤定义的表达式才是Σ上的正规式,其中运算符“|”、“·”、“ * ”、分别表示为 或、连接、闭包。 在正规式的书写中,连接运算符 "·"可省略,运算的优先级从高到低顺序排序为“ * ”、“·”、“|”。
设∑={a,b},下表列出了∑上的一些正规式和相应的正规集。
正规式 | 正规集 |
---|---|
ab | 字符串 ab 构成的集合 |
a|b | 字符串 a、b 构成的集合 |
a* | 由 0 或多个 a 构成的字符串集合 |
(a|b)* | 所有字符 a 和 b 构成的串的集合 |
a(a|b)* | 以 a 为首字符的 a、b 字符串的集合 |
(a|b)*abb | 以 abb 结尾的 a、b 字符串的集合 |
文章评论