标识符的识别 多数语言的标识符是字母开头的“字母/数字”串， 而且在程序中标识符的出现后都跟着算符或界符。因此， 不难识别。 常数的识别 对于某些语言的常数的识别也需要使用超前搜索。 算符和界符的识别 对于诸如C++语言中的“++”、“--”，这种复 合成的算符，需要超前搜索
标识符的识别 多数语言的标识符是字母开头的“字母/数字”串， 而且在程序中标识符的出现后都跟着算符或界符。因此， 不难识别。 常数的识别 对于某些语言的常数的识别也需要使用超前搜索。 算符和界符的识别 对于诸如C++语言中的“+ +”、“- -”，这种复 合成的算符，需要超前搜索
42正规表达式与 运算符的优先顺序： 4.2.1正规式与> 先“*”，次“。” 最后“|” 正规 的子集U,V: 1 e ∑* 2、 任 积 UV={aβla∈U&B∈V} 3、 n次积 V=VV...V V0={E V的闭包 V*=Vo U V1 U V2 U... V的正则闭包 V+=VV* 这 些正 “*”读做 “闭包
正规式与正规集的递归定义： 1、ε和Φ都是字母表∑上的正规式，它们所表示的正规集分别为{ε}和Φ； 2、任何a∈∑，a是∑上的一个正规式，它所表示的正规集为{a}； 3、 正规式 正规集 正规式 正规集 U L(U) （U | V） L(U)∪L(V) V L(V) （U·V） L(U)L(V) (U)* L(U)*（闭包） 仅由有限次使用上述三步骤而得到的表达式才是∑上的正规式。仅由这 些正规式所表示的子集才是∑上的正规集。 运算符的优先顺序： 先“*”，次“·” ， 最后“|” “|”读 做“或” “·”读做 “连接” *” “闭包” ∑* 的子集 U , V： 积 UV ={αβ|α∈ U & β∈V } n次积 V = VVV… V V0 = {ε} V的闭包 V* = V0 U V1 U V2 U … V的正则闭包 V+ = V V*
若两个正规式表 例4-3：令∑={A,B,0,1},则： 示相同的正规集， 正规式 正规集 则认为二者等价， 记为U=V。例如： (AB)(AB01)* Σ上“标识符 b(ab)*=(ba)*b 体 (a b)*=(a*b*)* (01)(01)* ∑上“数”的全 例4-4：令∑={a,b},下面是∑上的正规式和相应的正规集： 正规式 正规集 ba* ∑上所有的以b为首，并且后跟任 意多个a的字，{b,ba,baa,baaa,… a(a b)* ∑上所有的以a为首的字 (a b)*(aa bb) (ab)* ∑上所有含有两个连续的a或者的字
例4-4：令∑＝{a，b}，下面是∑上的正规式和相应的正规集： 正规式 正规集 ba* ∑上所有的以b为首，并且后跟任 意多个a的字，{b, ba,baa,baaa,…} a(a|b)* ∑上所有的以a为首的字 (a|b)* (aa|bb) (a|b)* ∑上所有含有两个连续的a或者b的字 例4-3：令∑＝{A，B，0，1}，则： 正规式 正规集 (A|B)(A|B|0|1)* ∑上“标识符”的全 体 (0|1)(0|1)* ∑上“数”的全体 若两个正规式表 示相同的正规集， 则认为二者等价， 记为U=V。例如： b(ab)*=(ba)*b (a|b)*=(a*b *) *
令U、V和W均为正规式，显而易见，下列关系普遍成立： 1、UV=VU(交换律)； 2、U(WW)=(UV)W(结合律)； 3、U(WW)=(UV)W(结合律)； 4、U(VW)=UVUW(分配律) (V W)U=VU WU; 5、eU=Ue=U
令U、V和W均为正规式，显而易见，下列关系普遍成立： 1、U|V = V|U（交换律）； 2、U|(V|W) = (U|V)|W（结合律）； 3、U(VW) = (UV)W（结合律）； 4、U(V|W) = UV|UW（分配律） (V|W)U = VU|WU； 5、εU = Uε = U
4.2.2状态转换图 转换图：是一张有限方向图。在状态转换图中，结点代表 状态，用圆圈表示。状态之间用箭弧连接。箭弧上 的标记（字符）代表在射出结状态下可能出现的输 入字符或字符类。 状态转换图的功能：用于识别一定的字符串。 初态：一张转换图的启动条件，至少有一个，用圆圈表示。 终态：一张转换图的结束条件，至少有一个，用双圈表示。 *:表示多读进了一个字符
转换图：是一张有限方向图。在状态转换图中，结点代表 状态，用圆圈表示。状态之间用箭弧连接。箭弧上 的标记（字符）代表在射出结状态下可能出现的输 入字符或字符类。 状态转换图的功能:用于识别一定的字符串。 初态：一张转换图的启动条件，至少有一个,用圆圈表示。 终态：一张转换图的结束条件，至少有一个，用双圈表示。 * ：表示多读进了一个字符