《《编译原理》课程简介 (12).pdf》由会员分享，可在线阅读，更多相关《《编译原理》课程简介 (12).pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编译原理 C O M P I L A T I O N P RIN C IP LE第三章 词法分析3.3.1 正规式与有限自动机3.3.1 正规式与有限自动机一、基本概念二、确定有穷状态自动机（DFA）三、非确定有穷状态自动机（NFA）四、正规式和有限自动机的等价性五、DFA的化简3.3.1 正规式与有限自动机p1.字母表：元素的非空有限集合。如=A,B,Op2.字符：字母表的一个元素称为一个字符（符号）p3.上的字：上字符的有穷序列；例：=a,b,cp4.空字：不含任何字符的字 一、基本概念3.3.1 正规式与有限自动机p5.字的长度：|p6.上字的全体：*p7.字的连接：字与字的连接记为 p
2、8.字的方幂：字的n次连接称为的n次方幂,记为n,特别地0=一、基本概念3.3.1 正规式与有限自动机p9.字的集合A与B的乘积：记作 AB=|AB,其中A,Bp10.*子集的方幂：A=,A1=A,An=AAA=An-1Ap11.*子集的正则闭包：A+=A1A2p12.*子集的闭包：A=A0A1A2=A0A+=A+一、基本概念3.3.1 正规式与有限自动机:正规式与正规集正规集是字母表上的一个特殊字集，通常我们借助正规式来描述它。关于正规式与正规集的定义是递归的。l1.和都是上的正规式，它们所表示的正规集分别为和l2.任何a,a是上的正规式，它所表示的正规式为al3.假定u和v是正规式，它们所
3、代表的正规集分别是L(u)和L(v)，则u|v,uv,u*都是上的正规式，它们所表示的正规集分别为L(u)L(v),L(u)L(v),L(u)*仅由有限次使用上述三步而定义的表达式才是上的正规式，仅由这些正规式所表示的字集才是上的正规集3.3.1 正规式与有限自动机:正规式与正规集u优先级递增：|(或)，（连接），*（对正规式而言），*（对正规集而言）u例1.=0,1 则正规式有 0，1，1*，(101)*，正规集有0，1，1*，101*，u若两个正规式所表示的正规集相同，则认为二者等价 3.3.1 正规式与有限自动机:正规式的性质u1.交换律：u|v=v|u 证：L(u|v)=L(u)L(v)=L(v)L(u)=L(v|u)因此，u|v=v|uu2结合律：(u|v)|w=u|(v|w),(uv)w=u(vw)u3分配律：u(v|w)=uv|uw,(u|v)w=uw|vwu4 u=u=u证：L(u)=L()L(u)=L(u)0 L(u)=L(u)|编译原理谢 谢Thanks