第三章-词法分析学习教案

《第三章-词法分析学习教案》由会员分享，可在线阅读，更多相关《第三章-词法分析学习教案（114页珍藏版）》请在装配图网上搜索。

1、会计学1第三章第三章-词法词法(cf)分析分析第一页，共114页。2022-6-62词法分析器的手工构造1正规表达式2有限自动机3词法分析器的自动生成4第1页/共114页第二页，共114页。2022-6-63第2页/共114页第三页，共114页。第3页/共114页第四页，共114页。2022-6-65第4页/共114页第五页，共114页。2022-6-66n字符串n输出是单词符号（token）的内部中间表示n过程是扫描输入的字符流，按词法规则识别出单词第5页/共114页第六页，共114页。2022-6-67n变量n常见的类型有整型、实型、布尔型、文字型等n如，100、3.14159、TRUE

2、、examplen运算符，用于表示操作n如，+、-、*、/ 等n界符，用于区分各种不同的语法单位n如，“,”、“;”、“(”、“)”、“/*”、“*/” 等第6页/共114页第七页，共114页。种(y zhn)处理n关键字、运算符和界符由语言定义，个数是固定的n种别的整数编码可唯一确定该单词，无须属性值n标识符常作为一种(y zhn)来处理，常数则可按类型分种n需用属性值来区分不同单词的特征n这些特征信息存放于相关的符号表项或常数表项中单词种别：用整数编码2022-6-68第7页/共114页第八页，共114页。2022-6-69nn第8页/共114页第九页，共114页。2022-6-610n器

3、在需要单词符号时调用n词法分析器和语法分析器作为两个并发(bngf)的过程通过pipe通信第9页/共114页第十页，共114页。第10页/共114页第十一页，共114页。ntabn大多数PL，空白是有意义的nFORTRAN和Algol60，空白可以加在任何地方提高可读性2022-6-612第11页/共114页第十二页，共114页。n缓冲区也有用处n关键字n保留字：用户不能使用关键字作为标识符nPL/l 的关键字不是保留字，词法分析器要区分2022-6-613第12页/共114页第十三页，共114页。2022-6-614第13页/共114页第十四页，共114页。n如，空格、跳格、回车和换行符只是

4、在文字常数中有意义n注解的出现对程序的功能也无任何意义n为了方便识别工作，编辑性字符和注解应事先删除n有些PL将一个(y )或相继多个空格用作单词之间的界符n此时应事先将相继多个空格合并为一个(y )空格n预处理即在识别开始前，删去输入缓冲区中的无用字符2022-6-615第14页/共114页第十五页，共114页。n前搜索其终点n若单词被半区边界截断，则再装入N个字符到另半区n单词的长度 N，故语言(yyn)通常限制标识符和常数的长度2022-6-616第15页/共114页第十六页，共114页。2022-6-617第16页/共114页第十七页，共114页。2022-6-618预处理子程序扫描缓

5、冲区扫描器输入缓冲区输入列表单词符号第17页/共114页第十八页，共114页。2022-6-619DO99K n必须(bx)超前搜索至第一个界符,或.才能确定单词的种别第18页/共114页第十九页，共114页。n如C+，Java中，+，+=，-，=等2022-6-620第19页/共114页第二十页，共114页。2022-6-621态）01字母2其它字母或数字*第20页/共114页第二十一页，共114页。2022-6-62201字母2其它字母或数字*转换状态初态终态输入字符第21页/共114页第二十二页，共114页。2022-6-623第22页/共114页第二十三页，共114页。2022-6-6

6、24第23页/共114页第二十四页，共114页。2022-6-625nn每个状态结点对应一段程序n不含回路的分叉(fn ch)结点对应switch或if-else语句n含回路的状态结点对应while和if构成的程序段第24页/共114页第二十五页，共114页。2022-6-626第25页/共114页第二十六页，共114页。第26页/共114页第二十七页，共114页。第27页/共114页第二十八页，共114页。第28页/共114页第二十九页，共114页。2022-6-630第29页/共114页第三十页，共114页。第30页/共114页第三十一页，共114页。第31页/共114页第三十二页，共11

7、4页。第32页/共114页第三十三页，共114页。第33页/共114页第三十四页，共114页。n其中：描述词法的形式规则(guz)是 正规式正规文法n描述转换图的形式工具是 有限自动机n形式化也使得可以用数学方法保证结果的正确性自动(zdng)自动(zdng)第34页/共114页第三十五页，共114页。2022-6-636正规式与正规集1DFA和NFA2正规文法3等价性证明4第35页/共114页第三十六页，共114页。n正规式是一种比文法更为(n wi)简单、高效的方法2022-6-637第36页/共114页第三十七页，共114页。2022-6-638第37页/共114页第三十八页，共114页

8、。2022-6-639第38页/共114页第三十九页，共114页。第39页/共114页第四十页，共114页。n2022-6-641第40页/共114页第四十一页，共114页。2022-6-642连接(linji)对 | 是可分配的 是连接(linji)的恒等元素性性 质质描描 述述A|B=B|A| 是可交换的A|(B|C)=(A|B)|C| 是可结合的A(BC)=(AB)C连接是可结合的A(B|C)=AB|AC(A|B)C=AC|BC连接对 | 是可分配的 A = AA = A 是连接的恒等元素 A* = (A | )*和之间的关系A*=A*幂的等价性第41页/共114页第四十二页，共114页

9、。2022-6-643第42页/共114页第四十三页，共114页。 x , x n令 x = x1x2xk 有 xi L(A*) = (L(A)*n于是有 xi (L(A)mi （mi 0, i =1, 2, k)n则 x = x1x2xk (L(A)m1 (L(A)m2 (L(A)mk n = (L(A) m1+ m2 + + mkn令 m = m1 + m2 + mk , 有 x (L(A)m (L(A)*n故有 L(A*)*) L(A*)第43页/共114页第四十四页，共114页。2022-6-645 s a到后继状态sn从转换图来看，相当于nS0 S 为唯一的初态nF S 为终态集（可

10、空）ssa第44页/共114页第四十五页，共114页。2022-6-646第45页/共114页第四十六页，共114页。2022-6-64701a3b2aaa,bbbv 状态(zhungti)转换图第46页/共114页第四十七页，共114页。2022-6-648第47页/共114页第四十八页，共114页。2022-6-649nDFA M所识别的字的全体记为L(M)。第48页/共114页第四十九页，共114页。2022-6-650v 是DFA吗？接受(jishu)什么样的字符串？第49页/共114页第五十页，共114页。v 带符号的自然数第50页/共114页第五十一页，共114页。v 浮点数第51

11、页/共114页第五十二页，共114页。第52页/共114页第五十三页，共114页。n只能用唯一的初始状态将它们连接在一起2022-6-654第53页/共114页第五十四页，共114页。2022-6-655第54页/共114页第五十五页，共114页。2022-6-656第55页/共114页第五十六页，共114页。2022-6-657第56页/共114页第五十七页，共114页。2022-6-658第57页/共114页第五十八页，共114页。2022-6-659第58页/共114页第五十九页，共114页。2022-6-660第59页/共114页第六十页，共114页。2022-6-661aabbb32

12、10第60页/共114页第六十一页，共114页。2022-6-662第61页/共114页第六十二页，共114页。2022-6-663态结点的通路，则空字可为M所接受。第62页/共114页第六十三页，共114页。2022-6-664第63页/共114页第六十四页，共114页。2022-6-665第64页/共114页第六十五页，共114页。2022-6-666第65页/共114页第六十六页，共114页。2022-6-667第66页/共114页第六十七页，共114页。第67页/共114页第六十八页，共114页。第68页/共114页第六十九页，共114页。第69页/共114页第七十页，共114页。第7

13、0页/共114页第七十一页，共114页。行（有算法）？n下一步：等价性证明和构造（转换）算法第71页/共114页第七十二页，共114页。2022-6-673第72页/共114页第七十三页，共114页。2022-6-674第73页/共114页第七十四页，共114页。析器n若能消除NFA的非确定性，将其转换为DFA，则容易实现2022-6-675第74页/共114页第七十五页，共114页。nNFA : S * 2Sn需证明，NFA M存在一个DFA M使L(M)=L(M)2022-6-676* , 2S S第75页/共114页第七十六页，共114页。n反复使用图示的替换(t hun)n直至每条有向

14、边上n标记为 或单个字符n显然，L(M) = L(M)2022-6-677第76页/共114页第七十七页，共114页。达状态集2,3,4，即状态n观察NFA M：可能有 边，也可能有相同标记的边n要构造DFA M，必须合并这两种边到达的状态2022-6-678第77页/共114页第七十八页，共114页。n设 I S，a , 定义 Ia = _closure ( J )nq I，从 q 出发经 a 边可达的q J2022-6-679第78页/共114页第七十九页，共114页。2022-6-680第79页/共114页第八十页，共114页。n则 将Si, Ia 或 Si, Ib 填入 Sk+, I,

15、 （k表示第一个空行）；i+；返回步骤(bzhu)2n否则算法终止2022-6-681第80页/共114页第八十一页，共114页。2022-6-682ISIaaIbbX, 5, 105, 3, 11 5, 4, 125, 3, 115, 3, 1, 2, 6, Y3 5, 4, 125, 4, 125, 3, 11 5, 4, 1, 2, 6, Y55, 3, 1, 2, 6, Y35, 3, 1, 2, 6, Y3 5, 4, 1, 6, Y45, 4, 1, 6, Y45, 3, 1, 6, Y6 5, 4, 1, 2, 6, Y55, 4, 1, 2, 6, Y55, 3, 1, 6,

16、Y6 5, 4, 1, 2, 6, Y55, 3, 1, 6, Y65, 3, 1, 2, 6, Y3 5, 4, 1, 6, Y4第81页/共114页第八十二页，共114页。第82页/共114页第八十三页，共114页。2022-6-684第83页/共114页第八十四页，共114页。n显然，三个NFA分别接受的正规集为, 和an归纳假设：设r,如果r中的运算符数目为k，则存在一个FA M，使得 L(M)=L(r)n当r中有k+1个运算符时，r有三种可能：r = r1| r2, r = r1 r2 或 r = r1*； r1和r2 中的运算符数目=k. 根据归纳假设，对r1和r2存在FAM1和M

17、2使得L(M1)=L(r1)L(M2)=L(r2)2022-6-685第84页/共114页第八十五页，共114页。并从f1引出(yn ch)转换至q2n显然，有L(M) = L(M1) L(M2) = L(r1) L(r2) = L(r)n对于r = r1*, 构造 M 为n显然，有L(M) = L(M1)* = L(r1)* = L(r)2022-6-686第85页/共114页第八十六页，共114页。2022-6-687接受正规式a的NFA接受正规式的NFA假设接受正规式r的NFA如下接受正规式rs的NFA接受正规式r|s的NFA接受正规式r*的NFA第86页/共114页第八十七页，共114

18、页。2022-6-688第87页/共114页第八十八页，共114页。2022-6-689第88页/共114页第八十九页，共114页。第89页/共114页第九十页，共114页。第90页/共114页第九十一页，共114页。n(wnf)GR造NFA M，并证明L(M)=L(GR)n对左线性文法(wnf)GL构造NFA M，并证明L(M)=L(GL)n对DFA M构造右线性文法(wnf)GR，并证明L(GR) =L(M)n对DFA M构造左线性文法(wnf)GL，并证明L(GL) =L(M)2022-6-692第91页/共114页第九十二页，共114页。2022-6-693第92页/共114页第九十三

19、页，共114页。n(A, a) = A1,A2, Akn容易证明，该NFA M所识别的语言L(M) = L(GR)2022-6-694第93页/共114页第九十四页，共114页。n若AVN, 且a VT, 使A1 Aa, A2 Aa,Ak Aan则令(A, a) = A1,A2, Ak2022-6-695第94页/共114页第九十五页，共114页。2022-6-696第95页/共114页第九十六页，共114页。| 1D (D为无用产生式）n从GR中构造NFA MnM = (A, B, C, D, F, 0, 1, , A, F)2022-6-697第96页/共114页第九十七页，共114页。1

20、2.B 0 | C013.D 1 | C1| D0 | D1| B0第97页/共114页第九十八页，共114页。2022-6-699RG第98页/共114页第九十九页，共114页。2022-6-6100tw终态；n反之，若从t出发能读出某个字w而停于终态，则从s出发也能读出同样的w而停于终态。第99页/共114页第一百页，共114页。2022-6-6101v 状态的可区分关系vs, t SM, s t, 若s，t不等价，则s，t是可区分的v 据 关系，对SM可进行等价划分v SM = S1S2 Sn, SiSj = , | Si | 1v 容易看出, s, t Si, s t, 而 s Si,

21、 t Sj, s与 t 是可区分的v 等价划分是最大划分，即这样划分 n 为最小v 每个等价集中元素可读出相同的w而终止，故可合并(hbng)为一个状态v 最小化算法: 从 SM中寻找 S1, S2,Sn, 使得SiSj = , s, t Si, s t第100页/共114页第一百零一页，共114页。2022-6-6102第101页/共114页第一百零二页，共114页。2022-6-6103第102页/共114页第一百零三页，共114页。2022-6-6104第103页/共114页第一百零四页，共114页。第104页/共114页第一百零五页，共114页。2022-6-6106解：（1）根据正规

22、(zhnggu)式，得到NFA如右图（2）确定(qudng)化IIaIb11,211,21,21,31,31,21,41,41,21（3）最小化，上面的DFA已经是最小的DFA重命名状态后得到DFA如下第105页/共114页第一百零六页，共114页。定识别(shbi)单词后的动作2022-6-6107第106页/共114页第一百零七页，共114页。2022-6-6108第107页/共114页第一百零八页，共114页。2022-6-6109LEX编译程序LEX源程序词法分析器L正规式动作状态转换表控制程序词法分析器L输入串单词符号串第108页/共114页第一百零九页，共114页。2022-6-6110n将M改造(gizo)为等价的DFA，必要时化简DFA第109页/共114页第一百一十页，共114页。第110页/共114页第一百一十一页，共114页。第111页/共114页第一百一十二页，共114页。2022-6-6113第112页/共114页第一百一十三页，共114页。第113页/共114页第一百一十四页，共114页。