编译原理第三章词法分析.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时就认定它是一个关键字。如果不采用保留字的办法，就必须使用超前搜索技术。,由于把关键字作为保留字，故可以把关键字作为一类特殊标识符来处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中（此表叫做保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。,关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的）。例如，一个条件语句应写为IFi0i=1;而绝对不要写成IFi0i=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中的常数插入常数表，返回常数表指针。,intcode,value;start:strToken:=“”;/*置strToken为空串/GetChar();GetBC();If(isLetter()beginwhileIsLetter()orIsDigit()dobeginconcat();GetChar()end;Retract();code:=Reserve();If(code=0)thenbeginvalue:=Insertid(strToken);return($ID,value);endelseReturn(code,_),End;Elseif(isDigit()Beginwhile(IsDigit()beginConcat();GetChar();endRetract();value:=InsertConst(strToken);return($INT,value);EndElseif(ch=)return($ASSIGN,-);,elseif(ch=)return($ASSIGN,-);elseif(ch=+)return($PLUS,-);elseif(ch=*)beginGetChar();if(ch=*)return($POWER,-);Retract();return($STAR,-);endelseif(ch=;)return($SEMICOLON,-);elseif(ch=()return($LPAR,-);elseif(ch=)return($RPAR,-);elseif(ch=)return($LBRACE,-);elseif(ch=)return($RBRACE,-);elseProcError(),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个)终态结点。对于中的任何字，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于,则称可为DFAM所识别（读出或接受）。若M的初态结点同时又是终态结点，则空字可为M所识别（或接受）。DFAM所能识别的字的全体记为L(M)。,图3.5确定有限自动机状态转换图,3.3.3非确定有限自动机（NFA）,一个非确定有限自动机NFAM是一个五元式M=(S,S0,F)其中是一个有限集，它的每个元素称为一个状态。是一个有穷字母表，它的每个元素称为一个输入字符。是一个从S至S的子集的映照。即：S2sS0S，是一个非空初态集。FS，是一个终态集（可空）。,NFA状态转换图的特点,该图含有m个状态结点，每个结点可射出若干条箭弧射出和别的结点相连接，每条箭弧用中的一个字（不一定要不同的字而且可以是空字）作标记(称为输入字)，整张图至少含有一个初态结点以及若干个(可以是0个)终态结点。对于中的任何字a，若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字等于a，则称a可为(NFA)M所识别（读出或接受）。若M的初态结点同时又是终态结点，则空字可为M所识别（或接受）。(NFA)M所能识别的字的全体记为L(M)。,命题：DFA是NFA的特例，也就是说每一个NFAM存在一个DFAM，使L(M)=L(M)。证明：假设NFAM=,对其进行如下改造：从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的状态子集aIa=_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少的DFAM,使得L(M)=L(M)。状态等价定义：两个状态的等价（如s和t的两个不同的状态,称s和t等价）从状态s出发能读出字，同样从状态t出发也能读出；反过来从状态t出发也能读出字同样从状态s出发也能读出。如果DFAM的两个状态s和t不等价，则称这两个状态是可区别的。,化简（分割法）算法：基本思想：DFA的化简过程旨在的状态分割成一些不相交的子集（所谓相交在离散数学中已经学过，即这些子集这间不存在共同的部分），使得任何不同的两子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价。最后，在每个子集中选出一个代表，同时消去其它等价状态。分割法：把终态与非终态分开，分成两个子集，形成基本分划。显然，属于这两个不同子集的状态是可区别的。假定到某个时候已含m个子集，记I(1),I(2),I(m),并且属于不同子集的状态是可区别。检查中的每个I(i)看能否进一步分划。,一般地，若Ia(i)落入现行II中N个不同子集，则应将I(i)划分为N个不相交的组，使得每个组J的Ja都落入II的同一个子集，这样形成新的划分。重复上述过程，直至划分中所有的子集数不再增长为止。在每一个状态中选择一个代表作为新的状态,例3.6,3.4词法分析器的自动产生,略,作业:文法G:ICIN|CN;CA|B.Z;N0|1|2|9的状态转换图？文法G:ND|DN;D0|1|2|9的状态转换图？,