java实现的词法分析.docx

编译原理综合训练课程设计报告实验一：词法分析器一、 词法分析器程序的实验综述1.1 开发背景1.2 问题介绍1.3 词汇表二、 词法分析器程序的系统分析2.1 词法形式化描述2.2 单词种别定义2.3 状态转换图三、 词法分析器程序的系统设计 3.1 运行环境介绍3.2 关键算法流程图及文字解释3.3 用于处理注释的skip函数3.4 基于trie树的保留字搜索函数3.5 系统运行与调试四、 系统测评 设计系统界面设计数据结构收集材料运行并测试编辑代码了解系统功能 图0 系统开发流程图词法分析器程序一 词法分析器程序的实验综述1.1开发背景编译原理涉及词法分析，语法分析，语义分析及优化设计等各方面。词法分析阶段是编译过程的第一个阶段，是编译的基础。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用Lex等工具自动生成。从左到右逐个字符对构成源程序的字符串进行扫描，依据词法规则，识别出一个一个的标记（token），把源程序变为等价的标记串序列。执行词法分析的程序称为词法分析器，也称为扫描器。词法分析是所有分析优化的基础，涉及的知识较少，如状态转换图等，易于实现。本次实验使用java代码实现。1.2问题介绍 对某特定语言A ，构造其词法规则。A的内容如下：该语言的单词符号包括1. 保留字2. 运算符及界符3. 标识符（字母大小写不敏感），整型常数 1.3词汇表对于后文正则式中可能出现的符号定义如下，以便清晰地描述A语言的正则式符号说明a字母b数字c符号（不包括字母和数字）*闭包运算符|或运算符.连接运算符（可省略）空#结束符二 词法分析器程序的系统分析2.1词法形式化描述正则式意义举例a(a|b)*标识符或保留字Lex1， programb*常数12345c运算符或界符或非法字符+，*，（，）等2.2单词种别定义program1not8常数15.22begin2if9+16;23end3then10*17/24var4else11:=18/*25int5while12(19*/26and6do13)20or7标识符14,21对于标识符或保留字的推导对于常数的推导对于符号的推导2.3状态转换图其中：识别标识符或保留字识别常数识别加运算符识别乘运算符 识别赋值运算符识别大于等于运算符，大于运算符并加以区分识别小于等于运算符，不等于运算符，小于运算符并加以区分识别括号，逗号，点号，分号，等于号其余所有无法被此状态转换图识别的符号视为非法符号。三 词法分析器程序系统设计3.1 运行环境介绍词法分析器程序由一个java控制台程序实现，通过读入一个名为A.txt的文本文件中的测试代码来对其进行词法分析。开发环境：MyEclipse 8.5，jdk1.6系统流程图：3.2关键算法流程图及文字解释词法分析程序（Analysis函数）详细流程图如下：void analysis() throws ExceptionStringBuffer lexSegment=new StringBuffer();StringBuffer digitSegment=new StringBuffer();/char next;trywhile(true)program=in.readLine();if(program=null)if(line=0)System.out.println(文件为空，);break;elseSystem.out.println(文件已编译完成);break;elseline+;column=-1;lineLength=program.length()-1;while(column+lineLength)break;next=program.charAt(column);column-;constant.append( 数字,digitSegment.toString(),4,constant.binaryTeamLengthUsed);digitSegment.delete(0,digitSegment.length();continue;else if(now=A&now=z)now=Character.toLowerCase(now);lexSegment.append(now);if(columnreservedWordMaxLength)lex.append(标志符,lexSegment.toString(),3,lex.binaryTeamLengthUsed);lexSegment.delete(0,lexSegment.length();continue;*/else if(Character.isDigit(next)column+;while(Character.isDigit(next)lexSegment.append(next);column+;if(columnlineLength)break;next=program.charAt(column);column-;lex.append(标志符,lexSegment.toString(),4,lex.binaryTeamLengthUsed);lexSegment.delete(0,lexSegment.length();continue;else if(nextz)lex.append(标志符,lexSegment.toString(),5,lex.binaryTeamLengthUsed);lexSegment.delete(0,lexSegment.length();continue;else if(now.equals(+)signal.append(运算符,symbol0,1,signal.binaryTeamLengthUsed);isFinished=true;continue;else if(now.equals(*)signal.append(运算符,symbol1,1,signal.binaryTeamLengthUsed);isFinished=true;continue;else if(now.equals()signal.append(运算符,symbol2,1,signal.binaryTeamLengthUsed);isFinished=true;continue;else if(now.equals()signal.append(运算符,symbol3,1,signal.binaryTeamLengthUsed);isFinished=true;continue;else if(now.equals(,)signal.append(运算符,symbol4,1,signal.binaryTeamLengthUsed);isFinished=true;continue;else if(now.equals(.)signal.append(运算符,symbol5,1,signal.binaryTeamLengthUsed);isFinished=true;continue;else if(now.equals(:)column+;if(program.charAt(column)=)signal.append(运算符,symbol6,1,signal.binaryTeamLengthUsed);isFinished=true;continue;elseSystem.out.println(第+line+行出现非法字符:);column-;continue;else if(now.equals(;)signal.append(运算符,symbol7,1,signal.binaryTeamLengthUsed);isFinished=true;if(column=lineLength)isAnnotation=true;continue;else if(column+1=lineLength&program.charAt(column+1)=/)isAnnotation=true;continue;else if(column+1)column+;if(program.charAt(column)=)signal.append(运算符,symbol11,1,signal.binaryTeamLengthUsed);isFinished=true;continue;elsesignal.append(运算符,symbol8,1,signal.binaryTeamLengthUsed);column-;continue;else if(now.equals()signal.append(运算符,symbol13,1,signal.binaryTeamLengthUsed);isFinished=true;continue;elsesignal.append(运算符,symbol9,1,signal.binaryTeamLengthUsed);column-;continue;else if(now.equals(=)signal.append(运算符,symbol10,1,signal.binaryTeamLengthUsed);isFinished=true;continue;else if(now.equals(/)if(column+1=lineLength)next=program.charAt(column+1);elseSystem.out.println(第+line+行+第+column+列+出现非法字符+now+);continue;if(next.equals(/)column=lineLength;/isAnnotation=true;/System.out.println(注释);else if(next.equals(*)skip(this.in,this.line,this.column,this.lineLength,gram);/isAnnotation=true;/System.out.println(/*注释);elseSystem.out.println(第+line+行+第+column+列+出现非法字符+now+);if(isAnnotation=true)isAnnotation=false;else System.out.println(第+line+行缺少;);catch(IOException e)System.out.println(FileReadingError);函数分析：此函数用于进行词法分析，其中有多处对分号的检查，所以比较复杂，但是报错精确，处理速度也有一定的优化。其中在判定是否是保留字时使用了trie树这种数据结构，大大加快了搜索速度，将原来每次O(n*n)的时间复杂度提升为O（n*log(n)），极大地加快了搜索，当保留字数目较多时更能显示这种数据结构的优势，具体的trie树搜索算法将在后文中描述。3.3 用于处理注释的skip函数void skip(BufferedReader in,int line,int column,int lineLength,String program) throws ExceptionCharacter now;/program=in.readLine();while(true)/System.out.println(skip:+program);while(column+word.length()-1) /System.out.println(index); return true; if(word.charAt(hierarchy)=#) index=26; else if(word.charAt(hierarchy) “”= “”+“=”= “”+“空格”+“=”= = “”+“空格”+“=”+“=”，=和=“”+“=”+“=”，=和=3st7标识符3st72非法字符，以及25.去注释算法描述，如何正确处理如下形式的注释：/* this is a * comm. / ent */ 答：由skip函数来处理。当analysis判定读入的字符串是/*时，调用此函数，skip函数会从此行开始持续往后读入字符，直到出现结束标志*/。之后返回注释的结束行数及列数，继续词法分析。6.输入文件结束是如何处理的？ 答：当readLine函数读入的内容为空时，说明文件已输入结束。7.一行文本结束标志是如何识别，如何处理的？答：每次读入一行，当扫描字符的游标值等于行长度时，该行文本以结束。8.可以识别的输入文本的行数是否有限制？每行的长度是否有限制？为什么？答：文本行数无限制。因为是每次读入一行，所以行数的增加只是增加了循环的次数。每行的长度应小于String类型的最大长度，因为每次读入一行，存于一个String类型的变量中。9.如果输入文件是空文件，程序能否正确执行？答：可以，直接判定文件为空。结果如下：实验总结通过实际操作，我们体会到了数据结构在程序设计中的地位。同时也真正体会到词法分析器具体的工作流程。从开始拿到题目的不知所措，到后来泡图书馆查找各种资