《编译原理与实现03第3章词法分析1》由会员分享，可在线阅读，更多相关《编译原理与实现03第3章词法分析1（44页珍藏版）》请在金锄头文库上搜索。
1、3.5 正则表达式,由于各种高级程序设计语言的单词形式基本上差不多，人们就希望能否构造一个自动生成系统，只要给出程序设计语言的各类单词描述以及识别出各类单词后应输出的结果，这种自动系统便能自动产生此程序设计语言的词法分析程序。词法分析程序自动生成系统的实现涉及正则表达式和有限自动机理论,假设有字母表=0，1，那么，字母表上的每个元素都是正则表达式，这样的正则表达式表示的语言只有一个句子。例如，0是一个正则表达式，表示的语言为0，该语言只有一个句子0。如果想表示更加复杂的语言，就必须使用运算符组成复杂的正则表达式，这一点很像用加减乘除运算符构造算术表达式。在正则表达式中，可使用的运算符有连接、选
2、择和重复。,例3.4，有正则表达式R1=1, R2=1, R3=0，所描述的语言分别为L1=1, L2=1,L3=0，求正则表达式R1.R2.R3、R1|R3R1描述的语言。解：根据正则表达式运算符的操作定义，可得如下结果：R1.R2.R3是一个正则表达式，描述的语言为110，该语言有一个句子110。R1|R3是一个正则表达式，描述的语言为1,0，该语言有两个句子1和0。R1是一个正则表达式，描述的语言为1n|n=0,1,2,.，该语言有无穷的句子，如1、11、11111等等。 标识符的正则表达式为： 标识符=字母字母|数字 而带有符号的实数的正则表达式为：数=（ |+|-）（数字.数字数字）
3、,3.5.1 正则表达式定义,设有两个正则表达式R1和R2，它们分别产生语言L1和L2，则正则表达式运算符的操作定义如下： 连接：R1.R2=xy|xL1， yL2选择：R1|R2= x|xL1或 xL2重复：R1=x|x L1*，L1*=L10L11L12,3.5.1 正则表达式定义,定义了运算符后，下面我们给出正则表达式的形式定义。,设是有穷字母表，在上的正则表达式及所描述的语言可递归定义如下：1.是一个表示空集的正则表达式。2.是一个正则表达式，它所表示的语言仅含一个空符号串，即3. a是一个正则表达式，a，它所表示的语言由符号a所组成a4.如果R1和R2是正则表达式，其表示的语言分别为
4、L1和L2，则 1) R1|R2或R1+R2是一个表示语言L1L2的正则表达式 2) R1.R2或R1R2是一个表示语言L1L2的正则表达式 3) R1或R1*是一个表示语言L1*的正则表达式 4) (R)表示的语言仍是L1的正则表达式，但调整优先权，使括号内的运算符优先权高于括号外的。5. 所有上的正则表达式可由上述4条规则构造出来。,注意：不要混淆和，正则表达式描述的语言只含一个空字符串，而表示的语言不含有任何字符串。,3.5.1 正则表达式定义,在正则表达式的运算符中，重复优先级高于连接，而连接高于选择，因此，(p) | (p) . (q)可写成p | pq , 但表达式(p|q).r中
5、的括号则不能去掉。,例3.5，设字母表=a,b，则a,b, 和都是上的正则表达式，所描述的语言为a、b、，求表达式ab、a|b和aa|ab|ba|bb定义的语言。解：根据正则表达式的形式定义，可得如下结果：表达式ab定义的语言为：ambn|m0,n0，表达式a|b定义的语言为：x|x a,b*，即字母a或b组成的任意长度字符串。 而表达式aa|ab|ba|bb表示的语言由字母a或b组成的所有偶长度字符串。,3.5.1 正则表达式定义,例3.6，设字母表=0，求表达式00与000|0定义的语言。解：表达式00定义的语言是0i|i1表达式000|0定义的语言是0i|i1,例3.6给出了两个不同的正
6、则表达式，但描述的语言却相同，这说明不同的正则表达式可描述相同的语言。如果两个正则表达式表示相同的语言，则称这两个表达式等价或相等。显然，例3.6的表达式00和000|0是等价的。,正则表达式的部分操作符满足结合律、交换律和分配律:即 (ab)c=a(bc) (a|b)|c=a(b|c) a|b=b|a a(b|c)=ab|ac注意：连接不满足交换律，即abba,3.5.2 正则文法与正则表达式的等价性,正则文法与正则表达式有等价性，即可以将正则文法转换成正则表达式。,例如，用正则文法表示标识符的文法规则如下：标识符= a|b|z |标识符a|标识符b|标识符z|标识符0|标识符1|标识符9而
7、采用正则表达式则为：标识符= (a|b|c|z)a|b|z|0|1|9 或简写成 标识符=字母字母|数字由此可见，正则表达式在描述语言时比正则文法更为简洁。,3.5.2 正则文法与正则表达式的等价性,例3.7，有正则文法如下，将其换成等价的正则表达式。S aSS aBB bCC aCC a解：,先用元符号“”和“”将文法改写成如下：S=aaBB =bCC = aa,然后按解方程组的方法可得：C=aaB= baaS=aabaa,最终转成正则表达式S=aabaa可以验证，它表示的语言与原来的正则文法描述的语言相同。,3.6 有穷自动机（FA）,有穷自动机不是一台具体的机器，而是一种具有离散输入与输
8、出系统的数学模型。在这种数学模型中有有限个状态，状态间存在着转换关系。系统可以处于有限个状态中的任意一个之中，系统的当前状态概括了有关过去输入的信息，这些信息对于确定系统在以后的输入上的行为是必需的。当系统处在某个状态之下读入一个字符时，会使系统所处的状态发生变化，从而形成状态转换。改变后的状态称为后继状态。在状态转换中，后继状态可能为一个，也可能为多个。有穷自动机分确定的和不确定的，所谓“确定的有穷自动机”是指在当前的状态下，输入一个符号，有穷自动机将转换到唯一的后继状态；而“不确定的有穷自动机”在当前状态下输入一个符号，可能有两种或两种以上可选择的后继状态。,3.6.1 确定的有穷自动机,
9、状态图就是一个确定的有穷自动机。 1、确定的有穷自动机定义一个确定的有穷自动机M（记作DFA M）是一个五元组： M=（ Q， ，q0，F，）其中：是一个字母表，它的每个元素称为一个输入符号 Q：是一个有穷的状态集合。 q0：q0Q，是唯一的初始状态。 F：FQ，称为终结状态集合。 ：状态转换函数，是一个QQ的单值映射。在确定的有穷自动机中，状态转换函数的具体形式如下：（q，a）=q 其中qQ，qQ，a,这是一个单值函数，表示在当前状态为q下，输入符号为a时，自动机将从状态q转换到下一个状态q，q称为q的后继状态。,3.6.1 确定的有穷自动机,2、确定的有穷自动机状态图,确定的有穷自动机M=
10、（ Q， ， q0，F，）可以用状态图来表示。状态图中的结点代表状态，用圆圈表示，它与自动机M中的状态集合Q相对应，其中包括初始状态q0和终结状态集合F，结束状态用双圈表示。状态间用有向弧线连接，连接弧上标记有符号，每条弧线对应一个状态转换函数，弧线上标记的符号集合就是字母表。,例3.8 设有穷自动机DFA M=（0，1，2，3，a,b,0,3,）(0,a)=1 (0,b)=2(1,a)=3 (1,b)=2(2,a)=1 (2,b)=3(3,a)=3 (3,b)=3画出该自动机对应的状态图。解：该自动机对应的状态图如图3.9所示。,a,b,3.6.1 确定的有穷自动机,3、确定的有穷自动机状态
11、转换矩阵图3.10 状态转换矩阵确定的有穷自动机M=（ Q， ， q0，F，）还可以用关系矩阵即状态转换矩阵来表示。矩阵中的第一列元素与自动机M中的状态集合Q一一对应，且初始状态q0是第一列的第一个元素，右上角标记*的元素对应终结状态。状态转换矩阵的第一行元素与子目标中的每个符号相对应。矩阵中的元素对应每个状态转换函数。如果有状态转换函数（q，a）=q，其中qQ，qQ，a，那么，就在矩阵中状态q对应的行和符号a对应的列单元中填入q。例3.5中的状态转换矩阵如图3.10所示。,3.6.1 确定的有穷自动机,4、确定的有穷自动机接受的语言,为了讲解确定的有穷自动机如何接受或识别字符串，首先，我们对
12、状态转换函数作补充定义： （q，at）= （ （q，a），t）其中a ， t *，即t是上的字符串例如,有(0,a)=1 且(1,b)=2， 则(0,ab)=（0，a），b）=(1,b)=2对一个确定的有穷自动机M=（ Q， q0，F，）以及某个字符串x（ x *），如果有(q0, x)=p，且pF，则字符串x就被该自动机M所接受。也就是从自动机开始状态开始，在读完全部输入串以后，自动机刚好到达终止状态，那么该输入串为该自动机所接受。从状态图上看，如果一个字符串能被自动机接受，那么从初始状态出发，则存在一条到达某一终结状态的路径，且组成这条路径的弧线上标记的符号连接起来正好就是字符串x。 一个
13、确定的有穷自动机M所接受的语言就是所能接受的输入串构成的集合，用L（M）表示，可定义为： L（M）=t | (q0, t) F，t *,3.6.1 确定的有穷自动机,例3.9，设计能接受偶数个0和偶数个1组成的串的有穷自动机，画出其状态图及状态转换矩阵并判别110101、11101能否被该自动机接受。解：首先设计能接受偶数个0和偶数个1组成的数字串的有穷自动机如下：M1=（S，A，B，C，0，1， S，S，） （S，0）=B （S，1）=A （A，0）=C （A，1）=S （B，0）=S （B，1）=C （C，0）=A （C，1）=B其状态图及状态转换矩阵分别如图3.11(a)(b)所示。,S
14、,A,B,C,1,1,0,1,0,0,1,0,图3.11(a),图3.11(a),下面判别110101、11101能否被该自动机接受：(S，110101)=(A，10101)=(S，101)=(B，101)=(C，01)=(A，1)= S(接受)(S，11101)=(A，1101)=(S，101)=(A，01)=(C，1)= B(拒绝),3.6.2 不确定的有穷自动机,不确定的有穷自动机与确定的有穷自动机的区别主要有两点：一是状态转换函数为多值函数，二是输入符号可允许为。1、不确定的有穷自动机定义一个不确定的有穷自动机NFA M是一个五元式M=（Q， ，q0，F，）其中：Q：有穷状态集 ：输入
15、字母表与空串组成的集合，输入可以是字母表中的字符，也可以是空串q0 ：开始状态q0QF：终止状态集FQ：状态转换函数，为Q* 到Q的子集的映射。不确定的有穷自动机同样可以用状态图和状态转换矩阵来表示，表示方法与确定的相同。,3.6.2 不确定的有穷自动机,2、不确定的有穷自动机接受的语言与确定的有穷自动机一样，为了判别一个字符串x能否被NFA接受，我们还需要对状态转换函数做补充定义：设(q, a)=p1,p2,pn，其中a ，q, p1,p2,pn Q1) (q, )= -closure(q)其中-closure(q)表示从状态q出发，沿着弧到达的后继状态集合以及再从这些后继状态沿着弧所能到达的所有状态集合。2) (q, at)=(p1, t)(p2, t) (pn, t) 其中a Vt , t *3) (q1, q2,qn,x) =(q1, x) (q2, x) (qi, x) 其中x * ，表示从不确定自动机的状态集出发，扫描字符串x后，所到达的状态集等于从当前状态集的每一个状态集出发，扫描字符串x后所到达的状态集之和。,
