文档介绍：: .
词法分析(1)---词法的串，成为语言的 句子 或字
比如：{abc,这就是一个语言， a} abc和 a就是句子。另外空集也是属于语言
连接：x是串，y是串，x和 y连接，结果就是 xy这个串。 假如 x是串， x^3
为 xxx。对于 x^n (n>=0),x^0ε =
语言的运算 (假定 L和 M是语言)：
1. L U M属于 = L{s|s或者 M}，例如：
L={1,2} M={3,4}那么 L U M = {1,2,3,4}
2. LM =属于 {st|sL且 t属于 M}，例如：L={a,b} M={1,2}那么 LM = {a1,a2,b1,b2} ML={1a,1b,2a,2b}
3. L^n = LLL...LLL个 L)，例如： (n
L={a,b}那么 L^3 = {aaa,aab,aba,abb,baa,bab,bbb,bba}
注意 n可以为 0，L^0 ε=} {
4. L* = L^0 U L^1 U L^2 U L^3 U ...
L*表示，语言 L中，所有的句子(串)以任意数目任意顺序组成的句子的集合，包
括 ε ，例如：
{a,b}*ε ,a,b,ab,ba,aab,aba,baa,bba,bab,abb,aaa,bbb...}= {
L*叫做 L的闭包
5. L+ = L^1 U L^2 U L^3 U...
L+表示，语言 L中，所有的句子(串)以任意数目任意顺序组成的句子的集合，但
是不包括 ε
L+中的句子和 L*中的句子相比少一个 ε
那么，我们通过上面的知识就可以表示一个标识符了，我们知道一般语言规定标
识符是由字母开头，后接若干个字母或数字，我们可以这样来表示： L={a-z A
-Z} N={0-9}，那么标识符就是 L(L U N)*
2)正规式
正规式又叫正规表达式，正规式是模式得一种规范的表达形式，正规式描述了一
个集合，这个集合是由串组成的，其实这个集合就是我们前面说过的语言，不过
这里大家喜欢使用正规集这个术语。正规式 r表示正规集 L(r)
正规式的运算：
，运算优先级最高， (r)*表示 (L(r))*，运算优先集合低于闭包， (r)(s)表示 (L(r))(L(s))
，运算优先集合最低， (r) | 表示(s) (L(r)) U (L(s))
例如：
a |表示集合 b (语言，正规集) {a,b}
(a | b)(a表示集合 | (b)语言，正规集 ) {aa,ab,ba,bb}
a*表示由一切 a字符组成的集合(语言，正规集)，包括 ε
(a |表示由 b) a,b组成的集合(语言，正规集)，包括 ε
等价的正规式：(a | b) = (b | a)
正规式的代数性质：
1. r|s = s|r
2. r|(s|t) = (r|s)|t
3. (rs)t = r(st)
4. r(s|t) = rs|rt
r = r
6. r** = r*
7. r* ε=)* (r|
注意，rs !=因为连接运算是有顺序的，记住并理解 sr 2个最基本的运算：a|
b表示{a,b}，ab表示{ab}
名字 ->正规式这种表示，来说明一个等价的代替，比如：
dight -> 0|1|2|3|4|5|6|7|8|9
这里，