《第4章 词法分析(6学时)》由会员分享，可在线阅读，更多相关《第4章 词法分析(6学时)（55页珍藏版）》请在金锄头文库上搜索。
1、第四章 词法分析,4.1 词法分析程序的设计,词法分析（lexical analysis）功能：逐个读入源程序字符，输出“单词符号” ，供语法分析使用。主要任务：读源程序，产生单词符号其他任务：滤掉空格，跳过注释、换行符追踪换行标志，复制出错源程序宏展开，,单词符号,一般可分为下列五种：基本字（关键字）：begin, end, if, while标识符：各种名称，如常量名、变量名、过程名常数（量）：25, 3.1415, TRUE, “ABC”等运算符：如 + - * / ” 或 “-”标出终态用双圈 或 “+”标出矩阵列标题：输出符号（VT） 行标题：状态若f( Ki , a ) = Kj，
2、则Ki和a的交汇处是 Kj初态用“=” 标出 或 默认第一行（表格左端）终态用“1”标出（表格右端）非终态用“0”标出（表格右端）,例：参见上例的DFA，分别用状态图和矩阵表示。,确定的有穷自动机(DFA),3. DFA可以接受的句子（符号串）：若t*，且存在f(S,t)= = P，P终态集，则t为该DFA可以接受的句子。即：从初态S到某终态结点P的道路上，所有弧上的标记符连接而成字符串t，t为该DFA可以接受的句子。,例：参见上例的DFA状态图，判断下列句子能否被接受：abbabaababbaaa,DFA M 能够接受的句子的全体记为 L(M) !,确定的有穷自动机(DFA),4. DFA的
3、确定性：f: KK 是一个单值函数即 对任何状态K，当输入字符a时，下一状态唯一。上例的有穷状态机就是DFA,DFA M=（K，f，S，Z）的行为模拟程序：K:=S；c:=getchar;while (ceof)K:=f(K,c);c:=getchar;if (K in Z) return (yes);elsereturn (no);,DFA的行为模拟程序,返回,不确定的有穷自动机(NFA),1. 定义：一个NFA是一个五元组 M=(K , ,f ,S ,Z ) K：有穷的状态集 ：有穷的字母表（即输入字符的集合） f：转换函数 K*K+ 上的映像（K+ 表示K的子集） S：初态集（初态不唯一
4、） Z：终态集,例：NFA M=(0,1,2,3,4 , a,b , f ,0 ,2,4)f：f(0,a)=0,3f(0,b)=0,1f(1,b)=2f(2,a)=2f(2,b)=2f(3,a)=4f(4,a)=4f(4,b)=4,2. NFA的“直观”表示：状态图（状态转换图）每个状态用结点表示若f( Ki , a ) = Kj，则初态用“=” 或 “-”标出终态用双圈 或 “+”标出矩阵?,举例：参见上例的NFA，分别用状态图和矩阵表示。,不确定的有穷自动机(NFA),3. NFA可以接受的句子（符号串）：(同DFA)若t*，且存在f(S,t)= = P，P终态集，则t为该NFA可以接受的
5、句子。,例：参见上例的NFA状态图，判断下列句子能否被接受：aaabaababbaababab,NFA M 能够接受的句子的全体记为 L(M)对于每个NFA M 存在一个DFA M，使得L(M)= L(M) !,不确定的有穷自动机(NFA), 可以被 NFA M 能够接受的两种情况： M的某结点既是初态，又是终态 存在一条从初态到终态的道路,4. NFA的不确定性：对于状态K，当输入字符a时，下一状态不一定唯一。5. NFA的确定化：对每个NFA M 一定存在一个DFA M，使得L(M)=L(M)即：对每个NFA M存在着与之等价的DFA M 。注：与某一NFA等价的DFA不唯一。,不确定的有
6、穷自动机(NFA),返回,NFADFA（子集法）,（一）基本运算：状态集合I的闭包：表示为-closure(I)状态集I中的任何状态S经任意条弧而能到达的状态的集合。 注：状态集I的任何状态S都属于-closure(I)状态集合I的a弧转换：表示为move(I,a)定义为状态集合J，其中J是所有那些可从I的某一状态经过一条a弧而到达的状态的全体。定义 Ia = -closure(J)举例：参见P58 图4.4，求：-closure(0)move(0,a)move(0,b)-closure(1)move(2,a)move(2,b)move(0,1,2,4,7,a)-closure(1,3)move(0,1,2,4,7,b),
