编译原理第三章 词法分析.pptVIP

把确定化的过程:不失一般性，设字母表只包含两个a和b，我们构造一张表:第62页，共111页，星期日，2025年，2月5日首先，置第1行第1列为?-closure({X})求出这一列的Ia，Ib；然后，检查这两个Ia，Ib，看它们是否已在表中的第一列中出现，把未曾出现的填入后面的空行的第1列上，求出每行第2，3列上的集合...重复上述过程，直到所有第2，3列子集全部出现在第一列为止。第63页，共111页，星期日，2025年，2月5日IIaIb{X,5,1}{5,3,1}{5,4,1}{5,3,1}{5,2,3,1,6,Y}{5,4,1}{5,4,1}{5,3,1}{5,2,4,1,6,Y}{5,2,3,1,6,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}{5,4,6,1,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,4,1,6,Y}{5,3,6,1,Y}{5,2,3,1,6,Y}{5,4,6,1,Y}XY?514236ab???ababab第64页，共111页，星期日，2025年，2月5日现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。这张表唯一刻划了一个确定的有限自动机M，它的初态是?-closure({X})，它的终态是含有原终态Y的子集。不难看出，这个DFAM与M’等价。第65页，共111页，星期日，2025年，2月5日Iab0121322153344655656340123546aabbbabaababab第66页，共111页，星期日，2025年，2月5日FA正规集正规式DFANFA正规文法3.3.13.3.23.3.33.3.4第67页，共111页，星期日，2025年，2月5日3.3.4正规文法与有限自动机的等价性对于正规文法G和有限自动机M，如果L(G)＝L(M)，则称G和M是等价的。关于正规文法和有限自动机的等价性，有以下结论：第68页，共111页，星期日，2025年，2月5日3.3.4正规文法与有限自动机的等价性定理：1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA)M，使得L(M)＝L(G)。2.对每一个FAM，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)＝L(GR)＝L(GL)。第69页，共111页，星期日，2025年，2月5日证明：1.对每一个右线性正规文法G或左线性正规文法G，都构造一个有限自动机（FA）M，使得L(M)＝L(G)。(1)设右线性正规文法G=VT,VN,S,P。将VN中的每一非终结符号视为状态符号，并增加一个新的终结状态符号f，f?VN。令M=VN∪{f},VT,?,S,{f}，其中状态转换函数?由以下规则定义：第70页，共111页，星期日，2025年，2月5日(a)若对某个A?VN及a?VT∪{?}，P中有产生式A→a，则令?(A,a)=f(b)对任意的A?VN及a?VT∪{?}，设P中左端为A，右端第一符号为a的所有产生式为：A→aA1|…|aAk（不包括A→a），则令?(A,a)={A1,…,Ak}。显然，上述M是一个NFA。第71页，共111页，星期日，2025年，2月5日对于右线性正规文法G，在Sw的最左推导过程中:利用A?aB一次就相当于在M中从状态A经过标记为a的箭弧到达状态B（包括a=?的情形）;在推导的最后，利用A?a一次则相当于在M中从状态A经过标记为a的箭弧到达终结状态f（包括a=?的情形）。综上，在正规文法G中，Sw的充要条件是：在M中，从状态S到状态f有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于w，这就是说，w?L(G)当且仅当w?L(M)，故L(G)＝L(M)。第72页，共111页，星期日，2025年，2月5日(2)设左线性正规文法G=VT,VN,S,P。将VN中的每一符号视为状态符号，并增加一个初始状态符号q0，q0?VN。令M=VN∪{q0},VT,?,q0,{S}，其中状态转换函数?由以下规则定义：(a)若对某个A?VN及a?VT∪{?}，若P中有产生式A?a，则令?(q0,a)=A(b)对任意的A?VN及a?VT∪{?}，若P中所有右端第一符号为A，第二个符号为a的产生式为：A1→Aa,…,Ak→Aa，