清华大学：《编译原理》课程教学资源（PPT课件）第三章 词法分析

定义（正规式和它所表示的正规集）： 设字母表为∑，辅助字母表={Φ，8，，·， *,(,)}。 1。ε和Φ都是∑上的正规式，它们所表示的正 规集分别为{8}和{}：

定义（正规式和它所表示的正规集）： 设字母表为，辅助字母表`={，，，•， ，(，)}。 1。 和都是上的正规式，它们所表示的正 规集分别为{}和{ }；

2。任何a∈∑，a是∑上的一个正规式，它所表 示的正规集为{a; 3。假定e和e都是∑上的正规式，它们所表示 的正规集分别为L(e)和L(e2),那么，(e), e1e2,ee2,e1*也都是正规式，它们所表示的 正规集分别为L(e),L(eUL(e2),L(e)L(e2) 和(L(e)*。 4。仅由有限次使用上述三步骤而定义的表达 式才是Σ上的正规式，仅由这些正规式所表 示的集合才是Σ上的正规集

2。任何a ，a是上的一个正规式，它所表 示的正规集为{a}； 3。假定e1和e2都是上的正规式，它们所表示 的正规集分别为L(e1 )和L(e2 )，那么，(e1 ), e1 e2 , e1•e2 , e1 也都是正规式,它们所表示的 正规集分别为L(e1 ), L(e1 )L(e2 ), L(e1 )L(e2 ) 和(L(e1 )) 。 4。仅由有限次使用上述三步骤而定义的表达 式才是上的正规式，仅由这些正规式所表 示的集合才是上的正规集

正规式中的符号 其中的“”读为“或”（也有使用“+”代 替“|”的)；“。”读为“连接”；“*” 读为“闭包”（即，任意有限次的自重复连 接)。在不致混淆时，括号可省去，但规定 算符的优先顺序为“*”、“。”、“” 连接符“。”一般可省略不写。“*” 、 和“”都是左结合的

正规式中的符号 其中的“”读为“或”（也有使用“+”代 替 “” 的）；“• ”读为“连接”；“” 读为“闭包”（即，任意有限次的自重复连 接）。在不致混淆时，括号可省去，但规定 算符的优先顺序为“”、“• ”、“” 。 连接符“• ”一般可省略不写。“”、“• ” 和“” 都是左结合的

例子 令={a,b},∑上的正规式和相应的正规集的例 子有： 正规式 正规集 a (a) alb {a,b} ab (ab) (ab)(a b) aa ab,ba bb {8,a,a,..任意个a的 串}

例子 令={a，b}， 上的正规式和相应的正规集的例 子有： 正规式 正规集 a {a} ab {a,b} ab {ab} (ab)(ab) {aa,ab,ba,bb} a  { ,a,a, ……任意个a的 串}

正规式 正规集 (ab)* {s ,a,b,aa ab ..所有由a 和b组成的串} (ab)*(aabb(ab)*{Σ*上所有含有两个相继 的a或两个相继的b组成 的串}

正规式 正规集 (ab) { ,a,b,aa,ab ……所有由a 和b组成的串} (ab) (aabb)(ab) { 上所有含有两个相继 的a或两个相继的b组成 的串}