编译原理第三章 词法分析及词法分析程序

1、编译原理前后文无关文法和语言设计扫描器应注意的问题词法分析（3型）语法分析（2型）单词的(Class, Value)二元组表示标识符的长度限制和按“尽可能长”的识别策略超前搜索与回退, =, , 状态转换图设G=(VN,VT,P,S)是一右线性文法,令|VN|=K，1) 则所要构造的状态转换图共有K+1个状态.2) VN中的每个符号分别表示K个状态2.1) G的开始符S为初态状态3) 终止状态,用F(VN)标记F是新加(状态）节点右线性文法=状态转换图aA - aBABA - aAFaA -消除，重用上述规则AFotherA若A为起始符（GA）A产生式的消除SAXFabcotherYeSAXF

2、abcYeS - aA A - b|bX X - c|eYS - aAA - bX X - c|eY状态图=右线性文法文法G00-a1S-aA1-d1A-dA1-bA-b0-cS-c0-c2S-cB，2有出弧2-dB-d0132abcdd左线性文法=状态转换图设G=(VN,VT,P,S)是一左线性文法,令|VN|=K，1) 则所要构造的状态转换图共有K+1个状态.2) VN中的每个符号分别表示K个状态2.1) G的开始符S为终止状态3) 起始状态,用R(VN)标记R是新加(状态）节点左线性文法=状态转换图aA - BaBAA -的消除消除，重用上述规则RAother若A为起始符（GA）AA -

3、 aRAa不存在这种转换状态图=左线性文法文法G31 - aAa1 - 1dAAd3 -1bSAb2 - cBc3 - 2dSBd0132abcdd状态矩阵状态矩阵Bij=BSi, aj=Sk当前状态，扫视字符，语义动作，后续状态程序3-2识别无符号数的状态矩阵语义 动作中的返回值ICON、FCON分别为整型数、浮点型数的值；一般说来，无符号数具有形式dmdm-1d0.d-1d-nEdd 即dmdm-1d0d-1d-n*10(dd-n);程序3-3关于状态无符号数识别矩阵DFA的形式定义DFA: Deterministic Finite Automata 一个DFA M定义为M=(K, , f

4、, S0, Z)，其中1) K=状态i2) =字母表，即输入字符i3) f : K - K，f为函数，表示某状态接受某个字母所到达的状态，如：f(p,a) =q, p,qK, a 4) S0 K， S0为初态5) Z K，且Z ，Z为终态集合DFA例子0132abcdd左侧的状态图，在数学上称作DFA，其形式化定义为M=(K, , f, S0, Z)K=0 , 1 , 2 , 3 =a , b , c , d 源状态输入目的状态0a10C21d11b32d3f: S0=0Z=2 , 3 函数f的推广定义f f : K * - K，表示某状态接受一个字母串（而不是一个字母）所到达的状态，f的定义

5、依赖于f的定义， f递归定义如下：1） f(p, ) = p, if p K，即任意一状态p接受（串长为0）的输入，状态不变2） f(p, aw) = f( f(p,a), w), if p K, a , w * 函数f的推广定义f : 例子 对于x = adb, x *，那么从状态0可以迁移到的状态p可以这样求出：P = f(0, adb) = f(f(0,a), db) = f(1, db) = f(f(1,d), b) = f(1, b) = f(f(1,b), ) = f(3, ) = 30132abcdd因为从初态0接受输入字母串adb后，迁移到f(0,adb)= 3 Z，所以adb

6、为DFA所识别 DFA所识别的语言令M 为一DFA，我们：定义L(M)=x | f(S0, x) Z, x *L(M)称为DFA M所识别的语言有定理：L(M) = L(G)，其中M为一DFA，G为一正规文法DFA关键特征状态迁移映射f是入射函数即f(x) f(y) 蕴含 x y即对任意状态结点p，其出弧上的字母各不相同且不为从状态图角度，如出现下述情况的状态结点，则不是DFA（而是NFA）PQNaaQ NPQP QWhy?NFA的形式定义一个NFA M定义为M=(K, , f, S0, Z)，除f外其余成员与DFA相同，f定义为 f : K - (K)，其中(K)为集合K的幂集合，即有 |(

7、K)|=2|K|f 表示某状态接受某个字母所到达的状态集合，如：f(p,a) =q,m p,q,mK, a 映射f的推广定义ff : (K) * - (K)，表示某状态集合接受一个字母串（而不是一个字母）所到达的状态集合，f递归定义如下(依赖于f)：f(p, ) = pf(p,a) =p1, p2,. if f(p,a)=p1,p2, if f(p,a) = f(p,aw) = f(f(p,a), w)其中，p,p1,p2 K, a , w *属于什么？NFA所识别的语言令N 为一NFA，我们：定义L(N)=x | f(S0, x) Z , x *L(N)称为NFA N所识别的语言有定理：L(

8、N) = L(M) = L(G)，其中N为一NFA，M为一DFA，G为一正规文法NFA例子 写状态迁移表fSABCabaaa,bba为什么是NFA源状态输入目的状态集合-SaA,CAaA,CAbA,BBaABbCCx 对每状态结点，按出弧上的字母写出状态迁移表C行可以不填f : K - (K)NFA例子 接受串源状态输入目的状态集合-SaA,CAaA,CAbA,BBaABbCCx f : K - (K)当前状态 余留输入 后续状态 选择状态 S ababb A,C A or C ?注意，NFA识别输入符号串时有一个试探过程，为了能走到终态，往往要走许多弯路（带回溯），这影响了NFA的效率。解决

9、办法？NFA与DFA的等价性定理3.1 对于字母表上的任一NFA N，必存在与M等价的DFA M，使L(N)=L(M) 有了该定理，为提高NFA识别字符串的效率提供了tips：将NFA转换为DFA，即NFA的确定化基本idea:DFA的 f : K - KNFA的f : K - (K)，将其改造为 f : (K) - (K)，并证明f是入射函数 且f接收的串与f接收的串相同例子S0S1abba,bq0q2a,babq1b带有动作的NFA例子 a b c S0 S0 S1, S2 S1 S1, S3 S2 S2 S3 S3 bS0S1S3aS2cb带有动作的NFA-闭包-closure(S0)=

10、S0, S1, S2, S3f(S, ) = -closure(S)f(S,wa) = -closure( f(f(S,w),a) )f(q, )通常不等于f(q, )f(S0, ) f(S0, )带有动作的NFA的确定化1) 令K=-closure(S0)(给出M的初态q0)2) 对于K中任一尚未标记的状态qi=Si1,Si2,Sim，Sik K，作2.1)标记qi2.2)对于每个a ，置T=f(Si1,Si2,Sim,a)qj= -closure(T)2.3) 若qj不在K中，则将qj作为一个未加标记的状态添加到K中，且把状态转移添加到M。3)重复进行步骤2)，直到K中不再含有未标记的状态

11、为止，对于由此构造的K ，我们把那些至少含有一个Z中的元素的qi作为M的终态。S0S1S3aS2cbbDFA状态数最小化可区分状态ABa1a2ana1a2状态A,B被某一输入串w=a1a2.an所区分，指1）从其中一个状态出发读入w，到达终态，2）而从另一个状态出发进入非终态可区分状态的递归定义在一个DFA中，状态A与状态B可区分：1）A是终止状态，B是非终止状态或 B是终止状态，A是非终止状态2）对于字母a，有f(A,a)=C, f(B,a)=D2.1) C与D可区分2.2) C=NULL 且 D NULL且D可达终态或 C NULL且C可达终态 且 D=NULLDFA状态数最小化-例子S0

12、S1S3S2babbaaabS4ab复习一个DFA M=(K, , f, S0, Z)，函数f : K - K表示某状态Ki接受某字母a后，到达状态Kj的转换。一个NFA M=(K, , f, S0, Z)，函数f : K - (K)表示某状态Ki接受某字母a后，到达状态集合K1, , Kj的转换。 一个带动作的NFA M=(K, , f, S0, Z)，函数 f : K - (K)表示某状态Ki接受某字母a或空串后，到达状态集合K1, , Kj的转换。试描述下述文法所产生的语言的特点GS=(VN=S, , , VT=AZ, az, 09, P, S), 其中P= S S，S S，S ， A，

13、 z， 0， 9 上述正规文法产生的语言的特点是由字母开头，后接0个或多个字母和(或)数字的符号串即标识符的定义如果使用型如 字母(字母|数字)* 的式子来表示上述符号串构成的集合，那么这样的式子就称为正规表达式(正则式，Regular Expression)，相应的符号串集合则称为该表达式对应的正规集。正规表达式及正规集的定义正规式 正规集1. 空集2. 3. a，a a4. (r)(s) Lr Ls(r)|(s) Lr Ls(r)* Lr* r=(r)|() Lr (r)+=(r)(r)*) Lr+算符优先级与正规式化简 算符优先级从高到低依次为 (), , *,+, , | 如( (r)

14、 ( (s)* ) ) | ( r )，可化简为 r s*|r 又因为连接符通常可省略不写， 再化简为rs*|r正规式与正规集的例子=a,b正规式与正规集的多对一关系给定一个正规式，它唯一确定一个正规集；反之不然。即一个正规集可由多个不同的正规式表示。我们称两个正规式等价，当且仅当它们所描述的正规集相同。例如a|b与b|a, (a|b)*与 (b|a)*等等正规式的基本等价公理A1. r|s=s|rA2. r|r=rA3. r|=r A4. (r|s)|t=r|(s|t)A5. (rs)t=r(st) A6. r(s|t)=rs|rtA7. (s|t)r=sr|trA8. r = r = A9

15、. r = r =rA10. r*=(|r)*=|rr* 由正规文法构造正规式1/4使用正规式描述下述右线性文法产生的语言S aS | bS aS | bS | c (或S (a|b)S | c )S abS | c 总结出规律: S S | 对应的正规式是 *由正规文法构造正规式2/4使用正规式描述下述左线性文法产生的语言S Sa | bS Sa | Sb | c (或S S(a|b) | c )S Sab | c 总结出规律: S S | 对应的正规式是 *由正规文法构造正规式3/4如果将“ | ”用 “ + ”替换，“ ” 用 “ = ” 替换，那么可以将产生式转换为方程的形式，于是对上

16、述两个规律，我们得到论断：论断3.1 方程X= X + （对应S S | ），有解 X= *论断3.2 方程X= X + （对应 S S | ），有解 X= *由正规文法构造正规式4/4于是，对文法GS SaS | bA | b AaS 我们可以将所有产生式的运算符“ | ”用 “ + ”替换，“ ” 用 “ = ” 替换，再以我们习掼的线性方程组求解方法来求解S对应的正规式。例子1) SaS|bA|b, AaS2) SaA, AbA|aB|b, BaA3) SbS|aA, AaA|bB, BaA|bC|b, CbS|aA练习1) SaS|bA|c, AbS2) SaA, AaA|bB|c, BcS由正规式构造FAThompson法S0SfS0S0Sfa当n=0r=r=r=a根据正规式所含运算符个数n递归给出。r= r1|r2r1S01r2S02s0Sf不再是初态不再是终态Sf1Sf2r=r1r2r1S01Sf1r2S02Sf2r=r*S01Sf1sSf例子与练习例子：1）a(b|aa)*b2）( (0*|1) (1*0) )*练习：1） ab|c*2） (b|aa|ac|aaa|aac)*综合练习1对文法GS=