文档介绍：词法分析——正则表达式授课:胡静*2004年12月28日1编译原理状态转换图实例其中的假设条件是:,。把它们预先安排在一张表格中。,如果关键字、标识符和常数之间没有确定的运算符或界符做间隔,则必须至少用一个空白符做间隔。Date2编译原理状态转换图的实现ch:字符变量,存放最新读进的源程序字符strToken:字符数组,存放构成单词符号的字符串GetChar:子程序过程,将下一个输入字符读到ch中,搜索指示器前移一个字符位置。GetBC:子程序过程,检查ch中的字符是否为空白。如果是,则调用GetChar,直至ch中进入一个非空白字符。Concat:子程序过程,将ch中的字符连接到strToken之后。IsLetter和IsDigit:布尔函数过程,它们分别判断ch中的字符是否为字母和数字。Reserve:整型函数过程,对strToken中的字符串查找保留字表,若它是一个保留字则返回它的编码,否则返回0值。Retract:子程序过程,将搜索指示器回调一个字符位置,将ch置为空白字符Date3编译原理状态转换图的实现(续1)InsertId:整型函数过程,将strToken中的标识符插入符号表,返回符号表指针InsertConst:整型函数过程,将strToken中的常数插入常数表,返回常数表指针。关于出错处理的一些说明:如果后面还有状态图,出现在这个地方的代码应为:将搜索指示器回退一个位置,并令下一个状态图开始工作。如果后面没有其他的状态图,则出现在上述位置的代码应该进行真正的出错处理,报告源程序含有非法符号,并进行善后处理。Date4编译原理状态转换图的实现(续2)对于不含回路的分叉结点来说,可让它对应一个switch语句,或一组if…then…else语句 GetChar() if(IsLetter()){…状态j的对应程序段…} elseif(IsDigit()){…状态k的对应程序段…} elseif(ch==‘/’){…状态l的对应程序段…} else{…错误处理…}Date5编译原理状态转换图的实现(续3)对于含回路的状态结点来说,可让它对应一个由While语句和if语句构成的程序段 GetChar(); while(IsLetter()orIsDigit()) GetChar(); …状态j的对应程序段…Date6编译原理tokensIdentifiers:xy11elsen_i00Integers:21000-5005LFloatingpoint:-10Strings:“x”“Hesaid,\“Areyou?\””Comments:/**don’tchangethis**/Keywords:ifelsewhilebreakSymbols:+*{}++<<<[]>=Date7编译原理如何描述tokens我们可以使用正则表达式来描述程序设计语言中的tokens正则表达式(RE,RegularExpression)的定义如下:a ordinarycharacterstandsforitselfε theemptystringR|S eitherRorS(alternation),whereR,S=RERS RfollowedbyS(concatenation),whereR,S=RER* concatenationofaRERzeroormoretimes (R*=ε|R|RR|RRR|RRRR…)在实际形式中,会有优先级的限制,因此可以加入一些括号。Date8编译原理正规式的例子令={a,b},正规式正规集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a{,a,a,……任意个a的串}(ab){,a,b,aa,ab……所有由a和b组成的串}(ab)(aabb)(ab) {上所有含有两个相继的a或两个相继的b组成的串}Date9编译原理简单的例子正则表达式R描述的字符串的集合表示为L(R)L(R)=由R定义的“语言”L(abc)={abc}L(hello|goodbye)={hello,goodbye}L(1(0|1)*)=所有的非零二进制数我们可以用正则表达式来定义每种类型的tokenDate10编译原理