《chapter-3-词法自动化》由会员分享，可在线阅读，更多相关《chapter-3-词法自动化（112页珍藏版）》请在金锄头文库上搜索。
1、编译自动化技术,编译自动化技术,词法分析的自动化 语法分析的自动化 其它自动化技术 编译优化,第三章:词法分析,1 词法分析的功能 2 词法分析程序的设计与实现 状态图 3 词法分析程序的自动生成 有穷自动机,第三章:词法分析,3.1 词法分析的功能识别单词，返回单词的类别和值 3.2 词法分析程序的设计与实现 状态图：有穷自动机的非形式表示 正则文法和状态图 3.3 词法分析程序的自动生成 正则表达式和有穷自动机,八月十五日夜湓亭望月 白居易昔年八月十五夜曲江池畔杏园边今年八月十五夜湓浦沙头水馆前西北望乡何处是东南见月几回圆昨风一吹无人会今夜清光似往年,八月十五日夜湓亭望月 白居易 昔年八月
2、十五夜，曲江池畔杏园边。 今年八月十五夜，湓浦沙头水馆前。 西北望乡何处是，东南见月几回圆。 昨风一吹无人会，今夜清光似往年。,八月十五日夜湓亭望月 白居易 昔年八月十五夜，曲江池畔杏园边。 今年八月十五夜，湓浦沙头水馆前。 西北望乡何处是，东南见月几回圆。 昨风一吹无人会，今夜清光似往年。,词法分析：断词，并给出词性（分类） 语法分析：断句，并给出句的结构、分类,程序,int main( ) n int count=read( ); n /if number of entries read is greater than 1 n /then sort( ) and compact( ) n
3、if (count 1) sort( ); compact( ); n if (count =0) n count 1) sort( ); compact( ); if (count =0)count 0 , 其中 B= 01,10,左线性文法的状态图的画法：,1. 令G的每个非终结符都是一个状态；,2. 设一个开始状态S；,5. 按自动机方法，可加上开始状态和终止状态标志。,例：正则文法Z:= U0 |V1U :=Z1 |1V :=Z0 | 0,例如：正则文法Z:= U0 |V1U :=Z1 |1V :=Z0 | 0其状态图为：,Z,S,U,V,1,1,0,0,每个非终结符设一个状态； 设一
4、个开始状态S； 若Q:=T, Q Vn,T Vt, 若Q:=RT, Q、RVn,T Vt, 加上开始状态和终止状态标志,识别算法,利用状态图可按如下步骤分析和识别字符串x： 1、置初始状态为当前状态，从x的最左字符开始，重复步骤2，直到x右端为止。 2、扫描x的下一个字符，在当前状态所射出的弧中找出标记有该字符的弧，并沿此弧过渡到下一个状态；如果找不到标有该字符的弧，那么x不是句子，过程到此结束；如果扫描的是x的最右端字符，并从当前状态出发沿着标有该字符的弧过渡到下一个状态为终止状态Z，则x是句子。 例：x=0110 和1011,问题：,1、上述分析过程是属于自底向上分析？还是自顶向下分析？
5、2、怎样确定句柄？,3.4 词法分析程序的设计与实现,词法规则 状态图 词法分析程序,3.4.1 文法及其状态图,语言的单词符号标识符保留字(标识符的子集）无符号整数单分界符 + * ：，（ ）双分界符 :=,两点说明：1. 空格的作用 2. 实数的表示,文法：1. := 字母 | 字母 | 数字2. :=数字 | 数字3. := : | + | * | , | ( | )4. := =5. := :,标识符,无符号整数,单字符分界符,双字符分界符,见教材,3.4.2 状态图的实现构造词法分析程序,1. 单词及内部表示,2. 词法分析程序需要引用的公共（全局）变量和过程,3. 词法分析程序算法
6、,1.单词及内部表示: 保留字和分界符采用一符一类,单词名称BEGIN END FOR DO IF THEN ELSE 标识符 常数(整) : + * , ( ) :=,类别编码1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16,记忆符BEGINSY ENDSY FORSY DOSY IFSY THENSY ELSESY IDSY INTSY COLONSY PLUSSY STARSY COMSY LPARSY RPARSY ASSIGNSY,单词值- - - - - - - 内部字符串 整数值 - - - - - - -,2.词法分析程序需要引用的公共（全局）变量和
7、过程,名称CHARTOKENGETCHARGETNBCCATISLETTER 和 ISDIGITUNGETCHRESERVEATOIERROR,类别字符变量 字符数组 读字符过程 过程过程 布尔函数 过程 布尔函数函数 过程,功能存放当前读入的字符 存放单词字符串 读字符到CHAR,移动指针 反复调用GETCHAR, 直至CHAR进入一个非空白字符 CHAR与TOKEN连接 判断 读字符指针后退一个字符 判断TOKEN中的字符串 是保留字, 还是标识符 字符串到数字的转换 出错处理,3、词法分析程序算法,START: TOKEN := ; /*置TOKEN为空串*/GETCHAR; GETNB
8、C;CASE CHAR OFAZ: BEGINWHILE ISLETTER OR ISDIGET DOBEGIN CAT; GETCHAR END;UNGETCH;C:= RESERVE; /* 返回0，为标识符 */IF C=0 THEN RETURN(IDSY: TOKEN)ELSE RETURN (C,-) /*C为保留字编码*/END;09: BEGINWHILE DIGIT DOBEGIN CAT; GETCHAR END;UNGETCH;RETURN (INTSY,ATOI) END; + : RETURN(PLUSSY,-) ;,* : RETURN(STARSY,-) ; ,
9、: RETURN(COMMASY,-) ; ( : RETURN(LPARSY,-) ; ) : RETURN(RPARSY,-) ; : : BEGINGETCHAR;if CHAR= THEN RETURN(ASSIGNSY,-) ;UNGETCH;RETURN(COLONSY,-) ;END END OF CASE; ERROR; GOTO START;练习：用C语言实现上述算法。,int getsym() /*返回类别编码*、 clearToken();while(isSpace()|isNewline()|isTab() getchar(); /*读取字符，跳过空格、换行和Tab*/
10、if(isLetter() /*判断当前字符是否是一个字母*/while(isLetter()|isDigit() /*将字符拼接成字符串*/ catToken(); getchar();retract(); /*指针后退一个字符*/int resultValue = reserver(); /*resultValue是查找保留字的返回值*/if(resultValue=0) symbol= IDSY; /*resultValue=0，token中的字符串为标识符*/else symbol= resultValue; /*否则token中的字符串为保留字*/else if(isDigit() /*判断当前字符是否是一个数字*/while(isDigit() /*将字符拼接成整数*/ catToken(); getchar();retract();num= transNum(token)； /*将token中的字符串转换成整数*/symbol= INTSY; /*此时识别的单词是整数*/ 。,见教材,第三章作业1：P56 1,2,(4?),内 容,3.1 词法分析程序的功能及实现方案,3.2 单词的种类及词法分析程序的输出形式,3.3 正则文法和状态图,3.4 词法分析程序的设计与实现,3.5 正则表达式与有穷自动机,
