第二章词法分析——模式..ppt

第二章 词法分析——模式 2.2 模式的形式化描述 正则表达式（正规式） 定义2.2 令Σ是一个有限字母表，则Σ上的正规式递归定义如下: 1. ε是正规式 2. 若a是Σ上的字符，则a是正规式 3. 若r和s分别是Σ上的正规式，那么 （a） r|s是正规式 （b） rs是正规式 （c） r*是正规式 （d）(r)是正规式 2.2 模式的形式化描述 正则语言（正规集） 令Σ是一个有限字母表，则Σ上的正则语言即Σ上的正则表达式所定义的语言。 1. ε是正规式，它表示集合L(ε) = {ε} 2. 若a是Σ上的字符，则a是正规式，它表示集合L(a) = {a} 3. 若正规式r和s分别表示集合L(r)和L(s)，则 （a） r|s是正规式，表示集合L(r)∪L(s)， （b） rs是正规式，表示集合L(r)L(s)， （c） r*是正规式，表示集合(L(r))*， （d）(r)是正规式，表示的集合仍然是L(r) 可用正则表达式描述的语言称为正则语言。 （表达能力） 2.2 模式的形式化描述 定义2.2说明： 运算的优先级与结合性 三种运算均具有左结合性质； 优先级从高到低：闭包、连接、或。 正规式中不必要的括号可以被省略。 例如：( a ) | ( ( ( b )* ) ( c ) )可以简化成 a | b* c。 正规式的等价 不同算术表达式可以表示同一个数，如3+5、5+3、2+6等均表示8。不同正规式也可以表示同一个正规集，即正规式与正规集之间是多对一的关系。 2.2 模式的形式化描述 定义2.3 若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P = Q。 [例2.4] 设字母表∑ = {a，b，c}，则∑上有： 正规式 正规集 a，b，c {a}，{b}，{c} a|b，b|a {a}∪{b}={a，b} a(a|b)* {a，aa，ab，aba，abb，aab，...}，a为首的ab串 ∑* {ε，a，b，c，aa，ab，ac，ba，bb，bc，...} [例2.5] 令 L(x) = {a，b}，L(y) = {c，d}， 则 L( x | y )={a，b，c，d} L( y | x )={a，b，c，d} 2.2 模式的形式化描述 利用正规式的等价性可以化简复杂的正规式。 正规式的等价性判定可以采用两种方法： 根据定义，证明不同的正规式表示同一集合（例2.5） 根据下述正规式的代数性质进行运算 记号的正规式表达 记号的说明 自然语言对模式的非形式化描述很不精确，而正规式可以严格地规定记号的模式，用正规式来表达记号： 记号 = 正规式 例如， id= ∑ (∑ | D )* 注：正规式就是说明记号的规则 2.2 模式的形式化描述 [例2.6] 记号relation、id和integer的正规式表示如下: Relation： | = | | | = | = id = (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z |A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z) (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z |A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z |0|1|2|3|4|5|6|7|8|9)* integer = (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* 返回 2.2 模式的形式化描述 简化正规式描述 正闭包 若r是表示L(r)的正规式，则r+是表示( L( r ) )+的正规式： r+ = r r* = r* r，r* = r+ | ε 例如： (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)* 化简为：(0|1|2|3|4|5|6|7|8|9)+ 可缺省 若r是正规式，则r?是表示L(r)∪{ε}的正规式： r?=r|ε 例如： E( + | - | ε ) 可改写为：E( + | - )? 2.2 模式的形式化描述 字符组 若