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

第三章 词法分析,3.1 对于词法分析器的要求 3.2 词法分析器的设计 3.3 正规表达式与有限自动机 3.4 词法分析器的自动产生,3.1 对于词法分析器的要求,词法分析的功能和输出形式： 词法分析器的功能是接收输入源程序，输出单词符号。 单词符号分五种：关键字；标识符；常数；运算符；界符。 词法分析器所输出的单词符号常常表示成如下的二元式： (单词种别，单词符号的属性值),单词种别： 本书假定关键字、运算符和界符都是一符一种，标示符单列一种，常数按类型分种。 单词符号的属性信息： 属性信息（值）是指单词符号的特性或特征值。本书仅给出标示符、常量的属性信息，即存放它们的符号表表项的指针。,例子：,While (i=j) i-; 经词法分析器处理后的结果为： =,- ,3.2 词法分析器的设计,3.2.1 输入、预处理,输入： 源程序。 输入缓冲区： 存放输入串。 预处理子程序： 对输入串进行预处理，其主要工作是去掉注释行，合并空白符等。 扫描缓冲区： 存放整理好的符号串。 扫描器： 不断地从扫描缓冲区读入字符串，并进行识别。,扫描器设计,扫描缓冲区分为两部分： 基本缓冲区和补充缓冲区，如果基本缓冲区不够，则要求输入串一定在补充缓冲区内结束，所以高级语言的符号串长度有限制。,搜索指示器,起点指示器,扫描缓冲区,3.2.2 超前搜索,超前搜索： 由于符号串需要结合后面的符号明确语义，所以需要向前读取多个符号后，判断其含义，这种向前读取符号的机制称为超前搜索。 超前搜索应用： 关键字识别 标示符的识别 常数的识别 算符和界符识别,例子：While (i=j) i-;,3.2.3 状态转换图,状态转换图定义： 转换图是一张有限方向图。在状态转换图中，结点代表状态，用圆圈表示。状态之间用箭弧连结。箭弧上的标记（字符）代表在射出结点（即箭弧始结点）状态下可能出现的输入字符或字符类。,(a)一个简单转换图,简单语言符号表,转换规则： 关键字（如IF、WHILE等）都是“保留字”。所谓保留字的意思是，用户不得使用它们作为自己定义的标识符。例如，下面的写法是绝对禁止的： IF（5）=X 因为，我们的分析器在识别出IF时就认定它是一个关键字。如果不采用保留字的办法，就必须使用超前搜索技术。,由于把关键字作为保留字，故可以把关键字作为一类特殊标识符来处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中（此表叫做保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。,关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的）。例如，一个条件语句应写为 IF i0 i=1; 而绝对不要写成 IFi0 i=1; 因为对于后者，我们的分析无条件地将IFi看成一个标识符。,3.2.4 状态转换图的实现,算法主要思想： 让每个状态结点对应一小段程序。 对不含回路的分支结点，可以对应一个switch或一组if 语句。 对含回路的状态结点，可以对应一个while语句和if语句。 终态结点对应一个return(code,value)语句。,Ch-字符变量，存放最新读进的源程序字符。 strToken-字符数组，存放构成单词符号的字符串。 GetChar-子程序过程，将下一输入字符读到ch中，搜索指示器前移一字符位置。 GetBC-子程序过程，检查ch中的字符是否为空白。若是，则调用GetChar直至ch中进入一个非空白字符。 Concat-子程序过程，将ch中的字符连接到strToken之后。例如，假定，strToken原来的值为“AB”,而ch中存放着C,经调用Concat后，strToken的值就变为“ABC”.,IsLetter和IsDigit-布尔函数过程，它们分别判断ch中的字符是否为字母和数字。 Reserve-整型函数过程，对strToken中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返回0值（假定0不是保留字的编码）。 Retract-子程序过程，将搜索指示器回调一个字符位置，将ch置为空白字符。 InsertId-整型函数过程，将strToken中的标识符插入符号表，返回符号表指针。 InsertConst-整型函数过程，将strToken中的常数插入常数表，返回常数表指针。,int code, value; start: strToken : =“ ”; /*置strToken为空串/ GetChar( ); GetBC( ); If(isLetter() begin while IsLetter() or IsDigit() do begin concat(); GetChar() end; Retract(); code:=Reserve(); If (code=0) then begin value:=Insertid(strToken); return ($ID,value); end else Return(code, _),End; Else if (isDigit() Begin while (IsDigit() begin Concat();GetChar(); end Retract(); value:=InsertConst(strToken); return($INT,value); End Else if (ch= =) return ($ASSIGN,-);,else if (ch= =) return ($ASSIGN,-); else if (ch= +) return ($PLUS,-); else if (ch= *) begin GetChar(); if (ch=*) return ($POWER,-); Retract(); return($STAR,-); end else if (ch= ;) return ($SEMICOLON,-); else if (ch= () return ($LPAR,-); else if (ch= ) return ($RPAR,-); else if (ch= ) return ($LBRACE,-); else if (ch= ) return ($RBRACE,-); else ProcError(),3.3正规表达式与有限自动机,3.3.1正规式与正规集 3.3.2确定有限自动机(DFA) 3.3.3非确定有限自动机(NFA) 3.3.4正规文法与有限自动机的等价性 3.3.5 正规式与有限自动机的等价性 3.3.6 确定有限自动机的化简,3.3.1正规式与正规集,正规式和正规集的递归定义： 和都是在上的正规式，它们所表示的正规集分别为和； 任何a，a是上的一个正规式，它所表示的正规集为a； 假定U和V都是上的正规式，它们所表示的正规集分别记为L(U)和L(V)，那么，(U|V)、(UV)和(U)也都是正规式，它们所表示的正规集分别为L(U)L(V)、L(U)L(V)（连接积）和(L(U)（闭包）。 仅由有限次使用上述三步骤而得到的表达式才是上的正规式。仅由这些正规式所表示的字集才是上的正规集。,例3.1：令=a,b，下面是上的正规式和相应的正规集。,正规式的四则运算： U|V=V|U（交换律）； U|(V|W)=(U|V)|W(结合律)； U(VW)=(UV)W(结合律)； U(V|W)=UV|UW(分配律) (V|W)U=VU|WU； U=U=U,3.3.2 确定有限自动机（DFA）,一个确定有限自动机(DFA)M是一个五元式 M=（S,s0,F） 其中： S是一个有限集，它的每个元素称为一个状态。 是一个有穷字母表，它的每个元素称为一个输入字符。 是一个从S至S的单值部分映射。(s,a）=s意味着：当现行状态为s、输入字符为a时，将转换到下一状态s.我们称s为s的一个后继状态。 s0S，是唯一的初态。 FS，是一个终态集（可空）。,例如：DFA的M=(0,1,2,3,a,b, ,0,3),DFA状态转换图的特点： 含有m个状态和n个输入字符，那么，这个图含有m个状态结点，每个结点顶多有n条箭弧射出和别的结点相连接，每条箭弧用中的一个不同输入字符作标记，整张图含有唯一的一个初态结点和若干个(可以是0个)终态结点。 对于中的任何字，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于,则称可为DFA M所识别（读出或接受）。若M的初态结点同时又是终态结点，则空字可为M所识别（或接受）。DFA M所能识别的字的全体记为L(M)。,图 3.5 确定有限自动机状态转换图,3.3.3 非确定有限自动机（NFA）,一个非确定有限自动机NFA M是一个五元式 M=(S,S0,F) 其中 是一个有限集，它的每个元素称为一个状态。 是一个有穷字母表，它的每个元素称为一个输入字符。 是一个从S至S的子集的映照。即 ：S2s S0S，是一个非空初态集。 FS，是一个终态集（可空）。,NFA状态转换图的特点,该图含有m个状态结点，每个结点可射出若干条箭弧射出和别的结点相连接，每条箭弧用中的一个字（不一定要不同的字而且可以是空字）作标记(称为输入字)，整张图至少含有一个初态结点以及若干个(可以是0个)终态结点。 对于中的任何字a，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于a，则称a可为(NFA)M所识别（读出或接受）。若M的初态结点同时又是终态结点，则空字可为M所识别（或接受）。(NFA)M所能识别的字的全体记为L(M)。,命题：DFA是NFA的特例，也就是说每一个NFA M存在一个DFA M，使L(M)=L(M)。 证明： 假设NFA M=,对其进行如下改造： 从X到S0中任意状态结点连一条箭弧，从F中任意状态结点连一条箭弧到Y。从而形成一个新的NFA，记为M，它只有一个初态X和一个终态Y。 对M的状态转换图进一步实行下列替换，其中k是新引进的状态。显然，L（M）=L（M）。即，这两个NFA是等价的。,(b)整数识别,将M进一步变换为DFA,方法如下： 定义1： I状态子集的闭包_CLOSURE(I)为 若qI，则q_CLOSURE(I) 若qI，那么从q出发经任意条弧而能到达的任何状态q都属于_CLOSURE(I)； 定义2： I的状态子集 a Ia=_CLOSURE(J) J是那些可从I中的某一状态结点出发经过一条a弧(跳过a弧前任意条弧)而到达的状态结点的全体。,子集法： 构造一张表,表头分别为I,a1,a2,，ak，其中I列的第一行为_CLOSURE(X)。 在第一行，对_CLOSURE(X)分别求Iai=_CLOSURE(J)，并填入相应的列中。 如果Iai为新的子集，则把其填入I列的下一行，依次类推。 对从第二行开始，继续执行2）3）直到没有新的子集出现。,例3.3,a,3.3.4正规文法与有限自动机的等价性,略,3.3.5 正规式与有限自动机的等价性,略,3.3.6 确定有限自动机的化简,一个确定有限自动机M的化简是指： 寻找一个状态数比M少的DFA M,使得L(M)=L(M)。 状态等价定义： 两个状态的等价（如s和t的两个不同的状态,称s和t等价）从状态s出发能读出字，同样从状态t出发也能读出；反过来从状态t出发也能读出字同样从状态s出发也能读出。如果DFA M的两个状态s和t不等价，则称这两个状态是可区别的。,化简（分割法）算法： 基本思想：DFA的化简过程旨在的状态分割成一些不相交的子集（所谓相交在离散数学中已经学过，即这些子集这间不存在共同的部分），使得任何不同的两子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价。最后，在每个子集中选出一个代表，同时消去其它等价状态。 分割法： 把终态与非终态分开，分成两个子集，形成基本分划。显然，属于这两个不同子集的状态是可区别的。 假定到某个时候已含m个子