编译原理

2020/1/201南开大学软件学院李忠伟2主楼[e-mail]2020/1/202第三章2020/1/203词法分析器的设计方法状态转换图正规表达式与有限自动机2020/1/2043.1词法分析器的设计方法词法分析器：执行词法分析的程序。是编译器中唯一与源程序打交道的部分。任务：从左到右、逐个字符地对源程序进行扫描，产生一个个单词符号。过滤掉程序中的无用成分，如注释、空格、回车等。处理与具体平台有关的输入，如文件结束符的不同表示等。调用符号表管理器或者出错处理器，进行相关的处理。进行宏展开等工作。2020/1/205词法分析器的输入/输出输入：源程序。输出：单词符号。单词符号的种类：关键字（保留字、基本字）—如if,then,while,do,for等。标识符—表示各种名字，如变量名，数组名和过程名。常数—各种类型的常数。运算符—+,-,*,/,,,=等。界符—逗号、分号、括号、空白等。2020/1/206词法分析器的输入/输出输出的单词符号表示形式：（单词种别，单词自身的值）单词种别：通常用整数编码表示如果一个种别只有一个单词符号，那么种别编码就代表该单词符号。如果一个种别有多个单词符号，则对于每个单词符号，必须给出种别编码和自身的值。关键字、运算符和界符，都可以是1个符号对应1个种别，也可以是1类对应一个种别。标识符自身的值可以表示为按机器字节划分的内部码。常数按类型分种，其值可表示为标准的二进制形式。2020/1/207例3.1对于C语言中的语句while(i=j)i--;输出的单词符号串为：while,-(,-id,指向i的符号表项的指针=,-id,指向j的符号表项的指针),-id,指向i的符号表项的指针--,-;,-2020/1/208词法处理器的处理结构把词法分析程序作为主程序，将词法分析作为独立的一遍来完成。优点：结构简单清晰，增加了编译系统的可移植性。字符串形式的源程序字符词法分析器符号表单词符号串程序单词2020/1/209把词法分析程序作为语法分析程序调用的子程序。进行语法分析时，每当需要一个单词时便调用词法分析程序。字符串形式的源程序字符词法分析器语法分析器符号表单词取下一单词2020/1/2010输入与预处理设定一个输入缓冲区。输入串放在输入缓冲区中。增加预处理子程序。去除无用的空白、回车等编辑性字符以及注释部分；每一次对一串订场的输入字符进行预处理，并将处理的结果装入一个指定的缓冲区（扫描缓冲区）。设定一个扫描缓冲区扫描缓冲区进行扫描时一般用到两个指示器：一个指向当前正在识别的单词的开始位置（单词的首字符）；一个用于向后搜索单词的终点。2020/1/2011例如：将扫描缓冲区分成两个半区：(1)每个半区容纳120个字符；(2)半区可以互补使用；(3)标识符和常数的长度不大于120个字符。2020/1/2012词法分析器的结构2020/1/20133.2状态转换图状态转换图是一张有限个结点的有向图。结点代表状态，用圆圈表示；状态之间用有向的箭头连接，箭头上的标记（字符）表示在当前状态下，如果出现（输入）该标记，将从当前状态跳转到下一个状态。状态是有限的，其中有一个是初态，至少有一个终态（用双圈表示）。2020/1/2014*0127·2356数字数字数字数字E＋或－数字数字其它数字其它其它E4识别无符号数的状态转换图：2020/1/2015一个状态转换图可用于识别（接受）一定的字符串。在状态转换图中，到达单词符号的终态时即可得到相应的单词编码。到达终态时多读入了一个符号，识别出该单词后再将多读入的那个符号退回。在终态上以*作为标识。每个状态都对应一小段程序。对于不含回路的分支状态，可对应一个switch()语句或一组if-else语句。对于含回路的状态，可对应一个while语句。2020/1/2016状态i对应的switch语句：s=getchar();switch(s){case'a':…case'z':…;/*实现状态j功能的语句*/case'0':…case'9':…;/*实现状态k功能的语句*/}jki数字字母2020/1/2017状态i对应的while语句：getchar();while(letter()||digit())getchar();……;//实现状态j功能的语句ij字母或数字其它2020/1/2018右线性文法状态转换图在将文法非终结符作为结点的基础上，增加一个额外的结点；文法中的开始符号为初态结点编号，新增额外的结点作为终态结点，单独编号；对每一个形如AaB的产生式，都有一条弧线从结点A指向B，并用符号a标记该弧线；对每一个形如Aa的产生式，都有一条弧线从结点A指向终态结点，并以符号a标记该弧线。例3.2已知文法G[S]=({S,A,B},{a,b},S,P1)，其中P1={SaA,AaA,AbB,Ab,BbB,Bb}画出文法的状态转换图。2020/1/2019助记符单词符号种别编码助记符内码值while1while—if2if—else3else—switch4switch—case5case—标识符6idid在符号表中位置常数7numnum在常数表中位置+8+—−9−—*10*—=11relopLE11relopLT==11relopEQ=12=—；13；—2020/1/202001*2开始空白字母字母或数字非字母数字34数字数字*非数字返回(id,id在符号表中位置)或返回(保留字,-)返回(num,num在常数表中位置)5＋67－*89101112131415＜＝*其它＝＝其它*；其它*返回(+,-)返回(－,-)返回(*,-)返回(relop,LE)返回(relop,LT)返回(relop,EQ)返回(＝,-)返回(;,-)非法字符错C语言子集上的词法分析的状态转换图2020/1/2021识别C语言子集的词法分析器引进一组变量和过程character:字符变量，存放最新读入的源程序字符。token:字符数组,存放构成单词符号的字符串。getbe():若character中字符为空，则调用getchar(),直至character为非空。concatenation():将token中字符串与character中字符连接作为token中新字符串。letter()和digit():判断character中的字符是否为字母和数字的布尔函数，若是则返回true，否则返回false。reserve():按token数组中的字符串查保留字表，若是保留字则返回其编码，否则返回0。retract():扫描指针回退一个字符，同时将character置为空白。buildlist():将标识符登录到符号表或将常数登录到常数表。error():进行出错处理。2020/1/2022token='';//对token数组初始化s=getchar();getbe();//滤除空格switch(s){case'a':…case'z':while(letter()‖digit()){concatenation();//将当前读入字符送入token数组getchar();}2020/1/2023retract();/*扫描指针回退一个字符*/c=reserve();if(c==0){buildlist();/*将标识符登录到符号表*/return(id,id在符号表中的入口指针);}elsereturn(保留字码,null);break;case'0':case'1':…case'9':while(digit()){concatenation();getchar();}retract();2020/1/2024buildlist();/*将常数登录到常数表中*/return(num,num的常数表入口指针);break;case'+':return('+'，null);break;case‘-':return(‘-'，null);break;case'*':return('*'，null);break;case'':getchar();if(character=='=')return(relop,LE);else{retract();return(relop,LT);}break;2020/1/2025case'=':getchar();if(character=='=')return(relop,EQ);else{retract();return('=',_);}break;case';':return(';',-);break;default:error();}2020/1/20263.3正规表达式与有限自动机概念回顾设是一个有穷字母表，它的每个元素称为一个符号。上的一个符号串是指由中的符号所构成的有穷序列。不包含符号的序列称为空字，记为。用*表示上的所有符号串的全体，空字也包括在其中。例如：若={a,b},则*={,a,b,aa,ab,bb,aaa,…}。2020/1/2027*的子集U和V中的（连接）积定义为:UV={∣U&V}集合UV中的符号串是由U和V的符号串连接而成的。一般UVVU，但（UV)W=U(VW)。V自身的n次（连接）积记为：Vn=VV…V(n个V)规定V0={}.闭包和正则闭包令V*=V0V1V2…，称V*是V的闭包。记V+=VV*,称V+是V的正则包。2020/1/2028正规式和正规集正规文法是3型文法，是描述正规集的文法，可用于描述程序设计语言的词法部分。正规集是一个集合，可以有穷也可以无穷。是正规文法产生的语言，可以通过正规式来形式化。正规式也叫正规表达式，是一种形式化表示法，它可以表示单词符号的结构，从而精确定义单词符号集。是表示正规集的方法。一个集合是为正规集，当且仅当它能用正规式表示。2020/1/2029例如：标识符是以字母开头的字母数字串。若用letter表示字母，用digit表示数字,则标识符可表示为:letter(letter|digit)*其中*表示零次或多次引用。则有：letter(letter|digit)*为标识符的正规式，该正规式表示的集合为标识符的正规集。2020/1/2030ε和Ф为字母表Σ上的正规式，它们表示的正规集分别为{ε}和Ф。对任一a∈Σ,a是Σ上的正规式，它表示的正规集为{a}。若R和S是Σ上的正规式,它们表示的正规集为L(R)和L(S)：R|S是Σ上的正规式，它表示的正规集为L(R)∪L(S)；R·S是Σ上的正规式，它表示的正规集为L(R)L(S);(R)*是Σ上的正规式，它表示的正规集为(L(R))*；仅由有限次使用以上3条规则得到的表示式是Σ上的正规式,它表示的集合是Σ上正规集。正规式和正规集的递归定义2020/1/2031几点说明Σ上的一个字指的是由Σ中字符构成的一个有穷序列。不包含任何字符的序列称为空字ε。Σ*表示Σ上所有字的全体,包括空字ε。如,若Σ={a,b}则Σ*={ε,a,b,aa,ab,ba,bb,aaa,…}Ф表示不含任何元素的空集{}。ε、{}和{ε}的区别：ε表示不包含任何字符的序列,它是正规集中的一个元素；{}表示不含任何字的集合,它是一个空的正规集；{ε}表示由空字组成的集合。2020/1/2032使用括号可改变运算符的运算次序。如果规定了运算优先关系，则可在不混淆情况下省去括号。对于正规式R和S，若它们表示的正规集L(R)=L(S),则称R和S等价，记为R=S。正规式具有下列性质：(1)交换律：R|S=S|R(2)结合律：R|(S|T)=(R|S)|T,R(ST)=(RS)T(3)分配律：R(S|T)=RS|RT,(R|S)T=RT|ST(4)同一律：ε