2.2词法记号的描述与识别 2.2.1串和语言 字母表：符号的有限集合，例：∑={0,1} 串：符号的有穷序列，例：0110,8 -语言：字母表上的一个串集 {ε，0,00,000，…}，{8}，⑦ 句子：属于语言的串 串的运算 -连接（积） xy,SE=ES=S 幂 s为e,s为s-1s(i>0)
2.2 词法记号的描述与识别 2.2.1 串和语言 – 字母表：符号的有限集合， 例： = { 0, 1} – 串：符号的有穷序列，例：0110, – 语言：字母表上的一个串集 {, 0, 00, 000, …}, {}, – 句子：属于语言的串 • 串的运算 – 连接（积） xy，s = s = s –幂 s 0为，s i为s i-1 s（i > 0）
2.2词法记号的描述与识别 ·语言的运算 -并： LUM={s|s∈L或S∈M} 连接： LM={st|S∈L且t∈ 幂： L0是{ε}，L是L-1L 闭包： L*=L0UO2U... 一正闭包： L+=LIOL20... 例 L:{A,B,,Z,4,b,,z},D:{0,1,,9} LUD,LD,L,L,LLD)",D
2.2 词法记号的描述与识别 • 语言的运算 –并： L M = {s | s L 或 s M } –连接： LM = {st | s L 且 t M} – 幂： L0是{}，Li是Li-1L –闭包： L = L0 L1 L2 … – 正闭包： L+ = L1 L2 … • 例 L: { A, B, …, Z, a, b, …, z }, D: { 0, 1, …, 9 } L D, LD, L6 , L* , L(L D ) * , D+
2.2词法记号的描述与识别 2.2.2正规式 正规式用来表示简单的语言，叫做正规集 正规式 定义的语言 备注 {ε a {a} a∈∑ (r)|(s) L(rUL(s) 和s是正规式 (r)(s) L(r)L(s) 和s是正规式 () (L(r)) 是正规式 (r) L(r) r是正规式 (@)(b))1(c)可以写成ab1c
2.2 词法记号的描述与识别 2.2.2 正规式 正规式用来表示简单的语言，叫做正规集 正规式 定义的语言 备注 {} a {a} a (r) | (s) L(r)∪L(s) r和s是正规式 (r)(s) L(r)L(s) r和s是正规式 (r) * (L(r))* r是正规式 (r) L(r) r是正规式 ((a) (b) * )| (c)可以写成ab* | c
2.2词法记号的描述与识别 正规式的例子∑={a,b -a b {a,b} -(a b)(a b) {aa,ab,ba,bby aa ab ba bb {aa,ab,ba,bby a' 由字母构成的所有串集 -(ab) 由a和b构成的所有串集 复杂的例子 (00|111((01110)(00111)*(01110)))* 句子：01001101000010000010111001
2.2 词法记号的描述与识别 • 正规式的例子 = {a, b} – a | b {a, b} – (a | b) (a | b ) {aa, ab, ba, bb} – aa | ab | ba | bb {aa, ab, ba, bb} – a * 由字母a构成的所有串集 – (a | b) * 由a和b构成的所有串集 • 复杂的例子 ( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：01001101000010000010111001
2.2词法记号的描述与识别 2.2.3正规定义 对正规式命名，使表示简洁 d1→r 2→r2 dn→ -各个d的名字都不同 每个r都是ΣU{d1,d2,,d1上的正规式
2.2 词法记号的描述与识别 2.2.3 正规定义 – 对正规式命名，使表示简洁 d1 → r1 d2 → r2 . . . dn → rn –各个di的名字都不同 –每个ri都是 {d1 , d2 , …, di-1 }上的正规式