第3章词法分析3.1词法分析器的功能3.1.1单词的分类与表示&3.1.2词法分析器的输出二、单词的内部形式单词名称标识符无符号常数(整)无符号浮点数布尔常数字符串常数保留字分界符2、保留字和分界符采用一符一类例3.1语句ifcount>7thenresult:=3.14的单词符号序列3.1.3源程序的输入缓冲与预处理3.1.4词法分析阶段的错误处理3.1.5词法分析器的位置3.2单词的描述3.2.1正则文法例3.2标识符的文法或者定义为约定：用digit表示数字：0,1,2,…,9;用letter表示字母：A,B,…,Z,a,b,…,z<id><letter>|<id><digit>|<id><letter><letter>A|B|…|Z|a|b|…|z<digit>0|1|2|…|9例3.3无符号数的文法3.2.2正则表达式3.2.2正则表达式(续)—RE正则表达式中的运算优先级例子正规式举例正则表达式的缩写形式3.2.3正则表达式与正则文法的等价性根据正则文法构造等价的正则表达式根据正则文法构造等价的正则表达式根据正则文法构造等价的正则表达式根据正则文法构造等价的正则表达式根据正则文法构造等价的正则表达式根据正则文法构造等价的正则表达式将正则表达式转换成等价的正则文法将正则表达式转换成等价的正则文法将正则表达式转换成等价的正则文法例3.8a(a|b)*到正则文法的转换例3.9正则表达式到正则文法的转换例3.10标识符定义的转换高级语言词法的简单描述例3.7某简易语言的词法——正则定义式变换为正规文法3.2.4有穷状态自动机有穷自动机的物理模型确定的有穷自动机的形式定义DFA的表示转移矩阵从状态转换图看，从初态出发，沿任一条路径到达接受状态，这条路径上的弧上的标记符号连接起来构成的符号串被接受。如：ababDFAM接受的语言非确定的有穷自动机NFAMDFAM的模拟算法例3.11例3.113.2.5状态转换图例3.11对应的状态转换图3.2.6正则表达式转换为状态转换图3.2.6正则表达式转换为状态转换图ε|(0|1)01*|0+的状态转换图2024/10/33.3单词的识别3.3.1有穷状态自动机与单词识别的关系2024/10/33.3.1有穷状态自动机与单词识别的关系Install_id()首先检查符号表，如果在符号表中找到了当前识别出的单词，当它被标记为关键字时，install_id()返回0，当它被标记为程序变量时，返回指向相应符号表表项的指针。如果在符号表中没有找到当前标识出的单词，则将该单词作为程序变量填入符号表中，并返回指向新建表项的指针。Gettoken()以同样的方式在符号表中查找该单词，如果该单词是一个关键字，则返回该关键字的种别码，否则返回id。例3.14不同进制无符号整数的识别识别不同进制数的状态图识别不同进制数的状态图识别不同进制数的状态图识别不同进制数的状态图3.3.2单词识别的状态转换图表示2024/10/3利用状态转换图识别单词由正则文法构造状态转换图2024/10/32024/10/32024/10/33.3.3几种典型的单词识别问题3.3.4状态转换图的实现3.3.5词法分析程序的编写数据结构与子例程图3.15的状态转换图的实现算法elseif(isdigit(ch)){ch=getchar();while(isdigit(ch))ch=getchar();retract(1);token=copytoken();return(INT,install_num(token));}elseswitch(ch){case‘*’:ch=getchar();if(ch==‘*’)return(EXP,0);else{retract(1);return(MULTI,0);}break;case‘:’:ch=getchar();if(ch==‘=’)return(ASSIGN,0);else{retract(1);return(COLON,0);}break;case‘<’:ch=getchar();if(ch==‘=’)return(LE,0);elseif(ch==‘>’)return(NE,0);else{retract(1);return(LT,0);}break;case‘=’:return(EQ,0);break;case‘>’:ch=getchar();if(ch==‘=’)return(GE,0);else{retract(1);return(GT,0);}break;case‘+’:return(PLUS,0);break;case‘-’:return(MINUS,0);brea