资源描述
编译原理和技术,大连理工软件学院胡彦huyan.ssdut,本讲纲要,回顾重点：FIRST集、FOLLOW集自上而下分析实现递归函数法非递归的预测分析方法,FOLLOW集计算,文法,SBAABS|dBaA|bS|c,初始状态：,FOLLOW(S)=FOLLOW(A)=FOLLOW(B)=,FIRST(B)=a,b,cFIRST(A)=a,b,c,dFIRST(S)=a,b,c,FOLLOW集计算,文法,SBAABS|dBaA|bS|c,第1步：FOLLOW(S)-$,FOLLOW(S)=$FOLLOW(A)=FOLLOW(B)=,FIRST(B)=a,b,cFIRST(A)=a,b,c,dFIRST(S)=a,b,c,FOLLOW集计算,文法,SBAABS|dBaA|bS|c,第1步：FOLLOW(S)-$,FOLLOW(S)=$FOLLOW(A)=FOLLOW(B)=a,b,c,d,第2步：FOLLOW(B)+=FIRST(A)FOLLOW(B)+=FIRST(S),FIRST(B)=a,b,cFIRST(A)=a,b,c,dFIRST(S)=a,b,c,FOLLOW集计算,文法,SBAABS|dBaA|bS|c,第1步：FOLLOW(S)正规式DFA化简,1、叙述正规式(00|11)(01|10)(00|11)(01|10)(00|11)描述的语言。答案：所有由偶数个0和偶数个1构成的串。分析：该正规式的一个重要特点是，它是两个字符一组来考虑的。正规式(00|11)表示的串的长度是偶数，每两个字符一组的话，不是00就是11。再看正规式(01|10)(00|11)(01|10)，它表示的串由01或10开始，中间有若干组00或11，最后出现01或10。这样的串仍然由偶数个0和偶数个1构成，只不过第一组是01或10的话，那么一定还要有一组01或10才能保证它们的偶数性。显然，正规式(01|10)(00|11)(01|10)(00|11)表示的串也仍然是由偶数个0和偶数个1构成。这样，可以判断题目所给的正规式表示的语言的每个句子都是由偶数个0和偶数个1构成。,11000011010011000011100110,反过来还需要考虑，任何由偶数个0和偶数个1构成的串是否都在这个语言中。这实际上是问，每个这样的串，其结构是否都符合正规式(00|11)(01|10)(00|11)(01|10)(00|11)所做的刻划。我们可以这样叙述由偶数个0和偶数个1构成的串，从左向右，每两个字符一组地考察，它1，由若干个（强调一下，可以是零个）00或11开始（这由正规式(00|11)描述）；2一旦出现一个01或10，那么经过若干个00或11后，一定会出现一个01或10。这第二个01或10的后面可能还有若干个00或11，一直到串的结束，或者到再次出现01或10为止。如果串没有结束的话，就是重复出现这里所描述的结构（所以这由(01|10)(00|11)(01|10)(00|11)描述）。因此正规式(00|11)(01|10)(00|11)(01|10)(00|11)描述的是偶数个0和偶数个1构成的串。,11000011010011000011100110,思考题,奇数个0和奇数个1的串用正规式怎么表示？奇数个0和偶数个1的串呢？偶数个0和奇数个1构成的串有是怎么用正规式表示呢？,2、写出语言“所有相邻数字都不相同的非空数字串”的正规定义。答案：no_0-89no_0-7(8|no_0-88)(no_0-88)(no_0-8|)|no_0-8no_0-6(7|no_0-77)(no_0-77)(no_0-7|)|no_0-7no_0-5(6|no_0-66)(no_0-66)(no_0-6|)|no_0-6no_0-4(5|no_0-55)(no_0-55)(no_0-5|)|no_0-5no_0-3(4|no_0-44)(no_0-44)(no_0-4|)|no_0-4no_0-2(3|no_0-33)(no_0-33)(no_0-3|)|no_0-3no_0-1(2|no_0-22)(no_0-22)(no_0-2|)|no_0-2no_0(1|no_0-11)(no_0-11)(no_0-1|)|no_0-1answer(0|no_00)(no_00)(no_0|)|no_0,3、将下图的DFA极小化。,1、加入死状态2、合并不可区分状态,先把状态集分成非接受状态集0,1,2,3,5和接受状态集4这两个子集。1集合4不能再分解，我们看集合0,1,2,3,5。move(0,1,2,3,5,a)=1,2,5move(0,1,2,3,5,b)=3,4,5由于b转换的结果3,4,5不是最初划分的某个集合的子集，因此0,1,2,3,5需要再分，由于状态1和状态2的b转换都到状态4。因此状态集合的进一步划分是：1,2，0,3,5和42由于move(1,2,a)=2,5move(1,2,b)=4move(0,3,5,a)=1,5move(0,3,5,b)=3,5显然1,2和0,3,5需要再分，分别分成：1和2以及0,3和53由于move(0,3,a)=1move(0,3,b)=3因此不需要再分。这样状态0和状态3合并成一个状态，我们取0为代表，再删去死状态5，就得到该题的结果。,正确做法！,最初的划分是0,1,2,3和4。1状态集合的进一步划分是：1,2，0,3和42忽略了死状态的影响，会认为它们都不需要再分,错误做法！,1、直接合并不可区分状态,E,LL(1)文法的自上而下的非递归分析方法理解,深度优先构造分析树,ETEE+TE|TFTT*FT|F(E)|id,输入：id*id,E,T,E,E,T,E,F,T,E,T,E,F,T,id,E,T,E,F,T,id,E,T,E,F,T,id,*,T,F,E,T,E,F,T,id,*,T,F,E,T,E,F,T,id,*,T,F,id,E,T,E,F,T,id,*,T,F,id,E,T,E,F,T,id,*,T,F,id,E,T,E,F,T,id,*,T,F,id,2.7(d)2.12(a),
展开阅读全文