Chapter-3-词法自动化.

1北京航空航天大学计算机学院编译自动化技术2北京航空航天大学计算机学院编译自动化技术•词法分析的自动化•语法分析的自动化•其它自动化技术–编译优化3北京航空航天大学计算机学院第三章:词法分析1词法分析的功能2词法分析程序的设计与实现－－状态图3词法分析程序的自动生成－－有穷自动机4北京航空航天大学计算机学院第三章:词法分析3.1词法分析的功能－－识别单词，返回单词的类别和值3.2词法分析程序的设计与实现－－状态图：有穷自动机的非形式表示－－－正则文法和状态图3.3词法分析程序的自动生成－－正则表达式和有穷自动机5北京航空航天大学计算机学院八月十五日夜湓亭望月白居易昔年八月十五夜曲江池畔杏园边今年八月十五夜湓浦沙头水馆前西北望乡何处是东南见月几回圆昨风一吹无人会今夜清光似往年6北京航空航天大学计算机学院八月十五日夜湓亭望月白居易昔年八月十五夜，曲江池畔杏园边。今年八月十五夜，湓浦沙头水馆前。西北望乡何处是，东南见月几回圆。昨风一吹无人会，今夜清光似往年。7北京航空航天大学计算机学院八月十五日夜湓亭望月白居易昔年八月十五夜，曲江池畔杏园边。今年八月十五夜，湓浦沙头水馆前。西北望乡何处是，东南见月几回圆。昨风一吹无人会，今夜清光似往年。词法分析：断词，并给出词性（分类）语法分析：断句，并给出句的结构、分类8北京航空航天大学计算机学院程序intmain()‘\n’{intcount=read();‘\n’//ifnumberofentriesreadisgreaterthan1‘\n’//thensort()andcompact()‘\n’if(count1){sort();compact();}‘\n’if(count==0)‘\n’count“nosalesforthismonth\n”;‘\n’elsewrite();‘\n’return;‘\n’}9北京航空航天大学计算机学院程序intmain(){intcount=read();//ifnumberofentriesreadisgreaterthan1//thensort()andcompact()if(count1){sort();compact();}if(count==0)count“nosalesforthismonth\n”;elsewrite();return;}10北京航空航天大学计算机学院内容3.1词法分析程序的功能及实现方案3.2单词的种类及词法分析程序的输出形式3.3正则文法和状态图3.4词法分析程序的设计与实现3.5正则表达式与有穷自动机3.6词法分析程序的自动生成器11北京航空航天大学计算机学院3.1词法分析程序的功能及实现方案词法分析程序的功能词法分析：根据词法规则识别及组合单词，进行词法检查。删去空格字符和注释。对数字常数完成数字字符串到二进制数值的转换。12北京航空航天大学计算机学院实现方案：基本上有两种1.词法分析单独作为一遍2.词法分析程序作为单独的子程序S.P.(字符串)词法分析S.P.(符号串)语法分析第一遍第二遍单词串优点:结构清晰、各遍功能单一缺点：效率低S.P.(字符串)词法分析程序语法分析程序取单词单词优点:效率高13北京航空航天大学计算机学院3.2单词的种类及词法分析程序的输出形式单词的种类1.保留字：begin、end、for、do...2.标识符：由用户定义，表示各种名字的字符串3.常数：无符号数、布尔常数、字符串常数等4.分界符：+、-、*、/、...14北京航空航天大学计算机学院词法分析程序的输出形式-----单词的内部形式几种常用的单词内部形式：1、按单词种类分类2、保留字和分界符采用一符一类3、标识符和常数的单词值又为指示字（指针值）单词类别单词值表示单词的种类，可用整数编码或记忆符表示不同的单词不同的值整型58保留字“for”15北京航空航天大学计算机学院单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数保留字分界符类别编码1234567单词值内部字符串整数值数值0或1内部字符串保留字或内部编码分界符或内部编码1、按单词种类分类类别编码单词值16北京航空航天大学计算机学院2、保留字和分界符采用一符一类单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数BEGINENDFORDO………:+*,(类别编码123456789…….20212223…….单词值内部字符串整数值数值0或1内部字符串----…..------17北京航空航天大学计算机学院内容3.1词法分析程序的功能及实现方案3.2单词的种类及词法分析程序的输出形式3.3正则文法和状态图3.4词法分析程序的设计与实现3.5正则表达式与有穷自动机3.6词法分析程序的自动生成器18北京航空航天大学计算机学院3.3正则文法和状态图•状态图的画法（根据文法画出状态图）例如：正则文法Z::=U0|V1U::=Z1|1V::=Z0|0左线性文法。该文法所定义的语言为：L(G[Z])={Bn|n0},其中B={01,10}19北京航空航天大学计算机学院左线性文法的状态图的画法：1.令G的每个非终结符都是一个状态；2.设一个开始状态S；3.若Q::=T,Q∈Vn,T∈Vt,则：QST4.若Q::=RT,Q、R∈Vn,T∈Vt,则：QRT5.按自动机方法，可加上开始状态和终止状态标志。例：正则文法Z::=U0|V1U::=Z1|1V::=Z0|020北京航空航天大学计算机学院例如：正则文法Z::=U0|V1U::=Z1|1V::=Z0|0其状态图为：ZSUV111000Start1.每个非终结符设一个状态；2.设一个开始状态S；3.若Q::=T,Q∈Vn,T∈Vt,4.若Q::=RT,Q、R∈Vn,T∈Vt,5.加上开始状态和终止状态标志21北京航空航天大学计算机学院•识别算法利用状态图可按如下步骤分析和识别字符串x：1、置初始状态为当前状态，从x的最左字符开始，重复步骤2，直到x右端为止。2、扫描x的下一个字符，在当前状态所射出的弧中找出标记有该字符的弧，并沿此弧过渡到下一个状态；如果找不到标有该字符的弧，那么x不是句子，过程到此结束；如果扫描的是x的最右端字符，并从当前状态出发沿着标有该字符的弧过渡到下一个状态为终止状态Z，则x是句子。例：x=0110和10111SUVZ1100022北京航空航天大学计算机学院•问题：1、上述分析过程是属于自底向上分析？还是自顶向下分析？2、怎样确定句柄？1SUVZ110001001UZVZZ=|=V1=|=Z01=|=U001=|=100123北京航空航天大学计算机学院3.4词法分析程序的设计与实现词法规则状态图词法分析程序24北京航空航天大学计算机学院3.4.1文法及其状态图语言的单词符号标识符保留字(标识符的子集）无符号整数单分界符+*：，（）双分界符:=两点说明：1.空格的作用2.实数的表示25北京航空航天大学计算机学院•文法：1.标识符::=字母|标识符字母|标识符数字2.无符号整数::=数字|无符号整数数字3.单字符分界符::=:|+|*|,|(|)4.双字符分界符::=冒号=5.冒号::=:标识符S标出口非字母数字字母字母、数字无符号整数S数出口非数字数字数字单字符分界符S单界出口其他字符+*，（）双字符分界符S冒号：双界=出口其他字符非=26北京航空航天大学计算机学院标识符无符号整数单字符分界符双字符分界符S标非字母数字字母字母、数字数非数字数字数字单界其他字符+*，（）出口冒号其他字符：双界=非=出错其他读字符查保留字表返回S27北京航空航天大学计算机学院读字符TOKEN:=’’:出错组合标识符:R查保留字表输出标识符:组数:R输出常数输出单分界符:读字符:输出’:=’:R输出’:’读字符:读去注释:YYN输出保留字YN出口NYYNNNNYYNYY转入口R输出’/’N是空字符？是字母？是保留字？是数字？是单分界符？是冒号？是斜竖？是’=’？是’*’？入口见教材28北京航空航天大学计算机学院3.4.2状态图的实现——构造词法分析程序1.单词及内部表示2.词法分析程序需要引用的公共（全局）变量和过程3.词法分析程序算法29北京航空航天大学计算机学院1.单词及内部表示:保留字和分界符采用一符一类单词名称BEGINENDFORDOIFTHENELSE标识符常数(整):+*,():=类别编码12345678910111213141516记忆符BEGINSYENDSYFORSYDOSYIFSYTHENSYELSESYIDSYINTSYCOLONSYPLUSSYSTARSYCOMSYLPARSYRPARSYASSIGNSY单词值-------内部字符串整数值-------30北京航空航天大学计算机学院2.词法分析程序需要引用的公共（全局）变量和过程名称CHARTOKENGETCHARGETNBCCATISLETTER和ISDIGITUNGETCHRESERVEATOIERROR类别字符变量字符数组读字符过程过程过程布尔函数过程布尔函数函数过程功能存放当前读入的字符存放单词字符串读字符到CHAR,移动指针反复调用GETCHAR,直至CHAR进入一个非空白字符CHAR与TOKEN连接判断读字符指针后退一个字符判断TOKEN中的字符串是保留字,还是标识符字符串到数字的转换出错处理31北京航空航天大学计算机学院3、词法分析程序算法START:TOKEN:=‘‘;/*置TOKEN为空串*/GETCHAR;GETNBC;CASECHAROF‘A’..’Z’:BEGINWHILEISLETTERORISDIGETDOBEGINCAT;GETCHAREND;UNGETCH;C:=RESERVE;/*返回0，为标识符*/IFC=0THENRETURN(‘IDSY’:TOKEN)ELSERETURN(C,-)/*C为保留字编码*/END;‘0’..’9’:BEGINWHILEDIGITDOBEGINCAT;GETCHAREND;UNGETCH;RETURN(‘INTSY’,ATOI)END;‘+’:RETURN(‘PLUSSY’,-);S标非字母数字字母字母、数字数非数字数字数字单界其他字符+*，（）出口冒号其他字符：双界=非=出错其他32北京航空航天大学计算机学院‘*’:RETURN(‘STARSY’,-);‘,’:RETURN(‘COMMASY’,-);‘(’:RETURN(‘LPARSY’,-);‘)’:RETURN(‘RPARSY’,-);‘:’:BEGINGETCHAR;ifCHAR=‘=‘THENRETURN(‘ASSIGNSY’,-);UNGETCH;RETURN(‘COLONSY’,-);ENDENDOFCASE;ERROR;GOTOSTART;练习：用C语言实现上述算法。S标非字母数字字母字母、数字数非数字数字数字单界其他字符+*，（）出口冒号其他字符：双界=非=出错其他33北京航空航天大学计算机学院intgetsym()/*返回类别编码*、{clearToken();while(isSpace()||isNewline()||isTab())getchar();/*读取字符，跳过空格、换行和Tab*/if(isLetter())/*判断当前字符是否是一个字母*/{while(isLetter()||isDigit())/*将字符拼接成字符串*/{catToken();getchar();}retract();/*指针后退一个字符*/intresultValue=reserver();/*resultValue是查找保留字的返回值*/if(resultValue==0)symbol=IDSY;/*resultValue=0，token中的字符串为标识符*/elsesymbol=resultValue;/*否则token中的字符串为保留字*/}elseif(isDigit())/*判断当前字符是否是一个数字*/{while