04词法分析

null第五章 词法分析第五章 词法分析概 述概 述编译程序需要在单词级别上来分析和翻译源程序，所以首先要识别出单词。 词法分析的任务是： 从左至右扫描源程序的字符串，按照词法 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf （正则文法规则）识别出一个个正确的单词，并转换成该单词相应的二元式（种别码、属性值）交给语法分析使用。 因此，词法分析是编译的基础。执行词法分析的程序称为词法分析器。两种 词法 分析 程序两种 词法 分析 程序不包括处理说明部分：仅读单词并转换成属性字，而不把单词的全部属性都识别出来。 包括处理说明部分：把单词的全部属性都识别出来 本章叙述的词法分析程序是处理了说明部分的词法分析程序，也即一个源程序经过词法分析程序分析处理后，将被改造成为由属性字组成的不含有静态说明部分的中间程序词法分析的两种处理结构词法分析的两种处理结构（1）把词法分析工作单独作为一趟词法分析是主程序 输入流是用高级语言编写的由字符组成的源程序，输出流是由属性字组成的与源程序等价的程序，称之为用第一级中间语言写的程序，简称L1程序。把词法分析工作单独作为一趟的好处把词法分析工作单独作为一趟的好处可使整个编译程序的结构更简洁、清晰和条理化： 词法分析比语法分析要简单得多，可用更有效的特殊 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 和工具进行出理。有些语言的词法分析工作比较别扭，如FORTRAN这种受书写格式限制的语言，识别其单词符号便甚为曲折和费时，把词法分析作为一趟独立出来就有利于集中力量考虑这些枝节问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 。null增强编译程序的可移植 在同一个语言的不同实现中，或多或少会涉及到与设备有关的特征，如采用ASCII还是其它的字符编码，可置于词法分析程序中解决而不会影响编译程序其它成分的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 。 编译程序的效率会得到改进 编译程序的大部分时间是花费在扫描字符以把单词符号分离出来，若把词法分析独立出来，则可采用专门的读字符和分离单词的技术可提高编译速度，而且可建立词法分析程序的自动构造工具 这并不意味着必须要把词法分析工作单独作为一趟把词法分析工作作为子程序把词法分析工作作为子程序 每当语法分析器需要一个单词符号时就调用词法分析子程序。每一次调用，词法分析器就从输入串中识别出一个单词符号交给语法分析器。 语法分析是主程序 由于后一种方式不需要在内存中构造和保存中间文件而常常被采用。实验一 词法分析实验一 词法分析实验目的： 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 估计实验时间： 课余准备15小时 上机二次4小时； 完成实验 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 5小时。 null如源程序为C语言。输入如下一段： main() { int a=-5,b=4,j; if(a>=b) j=a-b; else j=b-a; }要求输出如图： （2，”main”） （5，”（”） （5，”）”） （5，”{”） （1，”int”） （2，”a”） （4，”=”） （3，”-5”） （5，”,”） （2，”b”） （4，”=”） （3，”4”） （5，”,”） （2，”j”） （5，”;”） （1，”if”） （5，”（”） （2，”a”） （4，”>=”） （2，”b”） （5，”）”） （2，”j”） （4，”=”） （2，”a”） （4，”-”） （2，”b”） （5，”;”） （1，”else”） （2，”j”） （4，”=”） （2，”b”） （4，”-”） （2，”a”） （5，”;”） （5，”}”）一、识别各种单词符号一、识别各种单词符号程序语言的单词符号一般分为五种： 关键字（保留字/基本字）if、while、begin… 标识符：常量名、变量名… 常数：34、56.78、true、‘a’、… 运算符：+、-、*、/、〈、and、or、…. 界限符：， ； （ ） { } /*… 识别单词：掌握单词的构成规则很重要 标识符的识别：字母|下划线+(字母/数字/下划线) 关键字的识别：与标识符相同，最后查表 常数的识别 界符和算符的识别 单词的构成规则用状态转换图表示单词的构成规则用状态转换图表示大多数程序设计语言的单词符号都可以用转换图来识别null状态转换图的实现：使用一个switch case 语句：每条分支对应一个case语句段词法分析器的输出形式词法分析器的输出形式词法分析器输出的单词符号常常表示为二元式：（单词种别，单词符号的属性值） 单词种别通常用整数编码，如1代表关键字，2代表标识符等 关键字可视其全体为一种，也可以一字一种。采用一字一种得分法实际处理起来较为方便。 标识符一般统归为一种 常数按类型（整、实、布尔等）分种 运算符可采用一符一种的方法。 界符一般一符一种的分法。本实验采用一类符号一种别码二、 超前搜索方法二、 超前搜索方法词法分析时，常常会用到超前搜索方法。 如当前待分析字符串为“a>+”，当前字符为“>”，此时，分析器倒底是将其分析为大于关系运算符还是大于等于关系运算符呢？ 显然，只有知道下一个字符是什么才能下结论。于是分析器读入下一个字符’+’，这时可知应将’>’解释为大于运算符。但此时，超前读了一个字符’+’，所以要回退一个字符，词法分析器才能正常运行。又比如：‘+’分析为正号还是加法符号三、预处理三、预处理预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。由一个预处理子程序来完成。词法分析器的设计词法分析器的设计设计方法： 写出该语言的词法规则。 把词法规则转换为相应的状态转换图。 把各转换图的初态连在一起，构成识别该语言的自动机 设计扫描器 把扫描器作为语法分析的一个过程，当语法分析需要一个单词时，就调用扫描器。 扫描器从初态出发，当识别一个单词后便进入终态，送出二元式取单词程序框图取单词程序框图开始读标识符是字母掠过空格和回车符查保留字表是否查到换成属性字结束是数字是特殊符号error取数换成属性字换成属性字换成属性字YNYYYNNNnullvoid main() { if ((fp=fopen(“example.c”,“r”))==NULL) /*只读方式打开一个文件*/ printf("error"); else { cbuffer = fgetc(fp); /*fgetc( )函数：从磁盘文件读取一个字符*/ while (cbuffer!=EOF) { if(cbuffer==‘ ’||cbuffer==‘\n’) /*掠过空格和回车符*/ cbuffer=fgetc(fp); else if(isalpha(cbuffer)) cbuffer=alphaprocess(cbuffer); else if (isdigit(cbuffer)) cbuffer=digitprocess(cbuffer); else cbuffer=otherprocess(cbuffer); } } }nullchar alphaprocess(char buffer) { int atype; /*保留字数组中的位置*/ int i=-1; char alphatp[20]; while ((isalpha(buffer))||(isdigit(buffer))||buffer=='_') { alphatp[++i]=buffer; } /*读一个完整的单词放入alphatp数组中*/ alphatp[i+1]='\0'; atype=search(alphatp,1);/*对此单词调用search函数判断类型*/ if(atype!=0) { printf("%s, (1,%d)\n",alphatp,atype-1); id=1; } else { printf("(%s ,2)\n",alphatp); id=2; } }nullFILE *fp; char cbuffer; char *key[8]={"if","else","for","while","do","return","break","continue"}; int atype,id=4; int search(char searchchar[ ],int wordtype) /*判断单词是保留字还是标识符*/ { int i=0; int p; switch (wordtype) { case 1:for (i=0;i<=7;i++) { if (strcmp(key[i],searchchar)==0) { p=i+1; break; } /*是保留字则p为非0且不重复的整数*/ else p=0; /*不是保留字则用于返回的p=0*/ } return(p); } }nullchar digitprocess(char buffer) { int i=-1; char digittp[20]; while ((isdigit(buffer))) { digittp[++i]=buffer; buffer=fgetc(fp); } digittp[i+1]='\0'; printf("(%s ,3)\n",digittp); id=3; return(buffer); }nullchar otherprocess(char buffer) { char ch[20]; ch[0]=buffer; ch[1]='\0'; if(ch[0]==','||ch[0]==';'||ch[0]=='{'||ch[0]=='}'||ch[0]=='('||ch[0]==')') { printf("(%s ,5)\n",ch); buffer=fgetc(fp); id=4; return(buffer);} if(ch[0]=='*'||ch[0]=='/') { printf("(%s ,4)\n",ch); buffer=fgetc(fp); id=4; return(buffer); } }nullif(ch[0]=='='||ch[0]=='!'||ch[0]=='<'||ch[0]=='>') { buffer=fgetc(fp); if(buffer=='=') { ch[1]=buffer; ch[2]='\0'; printf("(%s ,4)\n",ch); } else { printf("(%s ,4)\n",ch); id=4; return(buffer); } buffer=fgetc(fp); id=4; return(buffer); }nullif(ch[0]=='+'||ch[0]=='-') { if(id==4) /*在当前符号以前是运算符，则此时为正负号*/ { buffer=fgetc(fp); ch[1]=buffer; ch[2]='\0'; printf("(%s ,3)\n",ch); id=3; buffer=fgetc(fp); return(buffer); } ch[1]='\0'; printf("(%s ,4)\n",ch); buffer=fgetc(fp); id=4; return(buffer); }5.5 词法分析器的自动生成5.5 词法分析器的自动生成一般来说，在各种不同的高级程序设计语言中，单词的总体结构基本相同，从而人们总希望对所有的高级程序设计语言设计一个词法分析程序的自动生成程序（生产器）。只要给出某种高级语言的单词描述，便能经过这样的自动生成程序自动产生相应的词法分析程序，这就是词法分析程序的自动生成问题 这里只介绍一个词法分析程序的生成程序— Lex LexLex是一种描述词法分析程序的语言，它由一组正则表达式以及与之相伴的代码(动作)组成，每个动作指出相应的正则表达式所要完成的任务,也即当按该正则表达式识别出某单词后应执行的操作。 一个Lex程序被编译后所得的结果程序(记为L),其作用就如同一个有效自动机一样，可用来识别和产生单词符号。 结果程序L含有一张状态转换矩阵和一个控制程序。 null LEX编译系统的作用一 Lex源程序一 Lex源程序辅助定义 ﹪﹪ 转换规则 ﹪﹪ 代码null 辅助定义 辅助定义部分由以下形式的一串Lex语句组成D1→R1 D2→R2 …… Dn→RnRi(i=1,2,…,n) 是一个正则表达式, Di是代表此正则表达式Ri的名字, 并限定Ri =Vt∪(D1, D2,…, Di-1) Di一般用小写英文字母串表示标识符的辅助定义 letter→A︱…︱Z︱a︱…︱z ident →letter(letter︱digit)* 例:整常数的辅助定义 digit→0︱1︱…︱9 integer →digit(digit)* 与文法一致null也称识别规则,由下列形式的一串Lex语句组成P1｛A1｝ P2｛A2｝ …… Pm｛Am｝ Pi(i=1,2,…m)是定义在Vt∪(D1, D2,…, Dn)上的正则表达式,称为词型,它描述了单词的形式. Ai (i=1,2,…m)是一个动作,每个动作是一个可以执行的代码序列,并用｛｝括起来,它指出在识别出词型为Pi的单词后,词法分析器应采取的动作 转换规则nulldigit(digit)* 例 整常数的转换规则｛ val:=int(id); return(16);return(val)｝求整型值,并执行有关子程序,查填常量表等函数int(id)是求数字串id的数值，子程序return 及其参数与整个转换规则的统一要求有关。二、Lex编译程序二、Lex编译程序将源程序翻译成语法分析程序的程序过程转换规则(Pi)状态转换图(NFA)状态转换矩阵简化(NFA→DFA)词法分析程序三 词法分析程序三 词法分析程序Lex源程序经Lex编译程序编译后得到的Lex目标程序叫词法分析程序 工作过程 Lex目标程序(L)逐一扫描输入串的每个字符，寻找一个最长的子串匹配某个Pi，把该子串截下来放在一个缓冲区TOKEN中 然后L就调用动作子程序Ai,当Ai完成后，L就把得到的单词符号交给词法分析程序 当L重新被调用时,就从输入串中继上次截出的位置之后识别下一个单词符号 .null匹配时有两种： 输入串找不到任何词型Pi与之相匹配L应报告输入串有错误 输入串可以匹配若干个不同的Pi以Lex程序中出现在最前面的Pi为准null 与每个词型Pi相应的动作Ai的基本组成成分是“返回”Pi定义的单词属性”。对于大多数单词，词法分析程序返回的属性就是该单词的内部编码。但是诸如常数、标识符、字符串常数单词，除了返回内部编码以外，还要分别返回常数的值、标识符本身和字符串在串表中的起始位置和长度。另外，必须把保留字从标识符中区别出，这可以通过查找预先设置的保留字表来实现。