1、实验一 词法分析设计实验一 词法分析设计一、实验目的通过本实验的编程实践，使学生了解词法分析的任务，掌握词法分析程序设计的原理和构造方法，使学生对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。二、实验内容用VC+/VB/JAVA语言实现对C语言子集的源程序进行词法分析。通过输入源程序从左到右对字符串进行扫描和分解，依次输出各个单词的内部编码及单词符号自身值；若遇到错误则显示“Error”，然后跳过错误部分继续显示 ；同时进行标识符登记符号表的管理。以下是实现词法分析设计的主要工作：（1）从源程序文件中读入字符。（2）统计行数和列数用于错误单词的定位。（3）删除空格类字
2、符，包括回车、制表符空格。（4）按拼写单词，并用（内码，属性）二元式表示。(属性值token的机内表示)（5）如果发现错误则报告出错（6）根据需要是否填写标识符表供以后各阶段使用。单词的基本分类：关键字：由程序语言定义的具有固定意义的标识符。也称为保留字例如 if、 for、while、printf ； 单词种别码为1。标识符：用以表示各种名字，如变量名、数组名、函数名；常数： 任何数值常数。如 125, 1,0.5,3.1416；运算符：+、-、*、/；关系运算符： 、=、；分界符： ；、，、（、）、；三、词法分析实验设计思想及算法 1、主程序设计考虑：程序的说明部分为各种表格和变量安排空间
3、。在具体实现时，将各类单词设计成结构和长度均相同的形式，较短的关键字后面补空。 k数组-关键字表，每个数组元素存放一个关键字（事先构造好关键字表）。s 数组-存放分界符表（可事先构造好分界符表）。为了简单起见，分界符、算术运算符和关系运算符都放在s表中（编程时，应建立算术运算符表和关系运算符表，并且各有类号），合并成一类。 id 和ci 数组分别存放标识符和常数。 instring 数组为输入源程序的单词缓存。 outtoken 记录为输出内部表示缓存。 还有一些为造表填表设置的变量。 主程序开始后，先以人工方式输入关键字，造k表；再输入分界符等造 p 表。 主程序的工作部分设计成便于调试的循
4、环结构。每个循环处理一个单词；接收键盘上送来的一个单词；调用词法分析过程；输出每个单词的内部码。例如，把每一单词设计成如下形式: (type,pointer)其中type指明单词的种类，例如：Pointer指向本单词存放处的开始位置。还有一些为造表填表设置的变量。 主程序开始后，先以人工方式输入关键字，造k表；再输入分界符等造 p 表。 主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；接收键盘上送来的一个单词；调用词法分析过程；输出每个单词的内部码。例如，把每一单词设计成如下形式: (type,pointer)其中type指明单词的种类，例如：Pointer指向本单词存放处的开
5、始位置。词法分析设计流程图2、词法分析过程考虑 根据输入单词的第一个字符（有时还需读第二个字符），判断单词类，产生类号：以字符k表示关键字；id表示标识符；ci表示常数；s 表示分界符。 对于标识符和常数，需分别与标识符表和常数表中已登记的元素相比较，如表中已有该元素，则记录其在表中的位置，如未出现过，将标识符按顺序填入数组 id 中，将常数变为二进制形式存入数组中 ci 中，并记录其在表中的位置。lexical 过程中嵌有两个小过程：一个名为 getchar，其功能为从 instring 中按顺序取出一个字符，并将其指针 pint 加 1 ；另一个名为 error，当出现错误时，调用这个过程
6、，输出错误编号。要求：所有识别出的单词都用两个字节的等长表示，称为内部码。第一个字节为 t ，第二个字节为 i 。 t 为单词的种类。关键字的 t=；分界符的 t=；算术运算符的 t=；关系运算符的 t=；无符号数的 t=；标识符的 t=。i 为该单词在各自表中的指针或内部码值。表 1 为关键字表；表 2 为分界符表；表 3 为算术运算符的 i 值；表 4 为关系运算符的 i 值。 取字符和统计字符行列位置子程序四、实验要求1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。2、将标识符填写的相应符号表须提供给编译程序的以后各阶段使用。3、根据测试数据进行测试。测试实例应包括以下三个
7、部分:全部合法的输入。各种组合的非法输入。由记号组成的句子。4、词法分析程序设计要求输出形式:例：输入VC+语言的实例程序：If i=0 then n+;a= 3b %);输出形式为：单词 二元序列 类 型 位置（行，列） （单词种别，单词属性）for (1,for ) 关键字 （1，1） i ( 6,i ) 标识符 （1，2）= ( 4，= ) 关系运算符 （1，3）0 ( 5，0 ) 常数 （1，4）then ( 1，then) 关键字 （1，5）n (6,n ) 标识符 （1，6）+ Error Error （1，7）； ( 2, ; ) 分界符 （1，8）a (6,a ) 标识符 （2
8、，1）= (4,= ) 关系运算符 （2，2）3b Error Error （2，4）% Error Error （2，4）) ( 2, ) ) 分界符 （2，5）； ( 2, ; ) 分界符 （2，6）五、实验步骤1、根据流程图编写出各个模块的源程序代码上机调试。2、 编制好源程序后，设计若干用例对系统进行全面的上机测试，并通过所设计的词法分析程序；直至能够得到完全满意的结果。3、书写实验报告 ；实验报告正文的内容：功能描述：该程序具有什么功能？程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图。 详细的算法描述（程序总体执行流程图）。给出软件的测试方法和测试结
9、果。实验总结 （设计的特点、不足、收获与体会）。六、源程序1、词法分析器操作类（Morp_Opertion.java）package MorphologyAnalysis;import java.util.ArrayList;public class Morp_Opertion private ArrayList keyTable = new ArrayList();/关键词表 private ArrayList delimiterTable = new ArrayList();/分界符表 private ArrayList identifierTable = new ArrayList();
10、/标识符表 private ArrayList constDigitTable = new ArrayList();/常数表 private final char letterTable = a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p ,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L ,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z;/字母表 private final char digitTable = 1,2,3,4,5,6,7,8,9,0;/数字表 private final char arithmeticTable =
11、 +,-,*,/;/算数运算符表 private final char relationTable = ;/关系运算符表 private char ch;/待判断的字符 private String token;/带判断的字符串 private int index = 0;/标志指针 private char strChar = new char1000;/存放单行的字符 private int rowLength = 0;/单行字符长度 private String result = new String();/存放分析结果 private String dataStrings = new
12、String1000005;/存放表格数据 private int arrarycount = 0;/存放表格行数 /* * return the result */ public String getResult() return result; /* * param result the result to set */ public void setResult(String result) this.result = result; /* * return the arrarycount */ public int getArrarycount() return arrarycount
13、; /* * param arrarycount the arrarycount to set */ public void setArrarycount(int arrarycount) this.arrarycount = arrarycount; public Morp_Opertion() this.result += 单词t二元序列tt类型tt位置（行，列）rn; /向关键词表、分界符表、标识符表、常数表插入数据 public void inKeyTable(String key) if (isKey(key) return; else keyTable.add(key); publ
14、ic void inDelimiterTable(String delimiter) if (isDelimiter(delimiter) return; else delimiterTable.add(delimiter); public void inIdentifierTable(String identifier) if (isIdentifier(identifier) return; else identifierTable.add(identifier); public void inConstDigitTable(String constDigit) if (isConstDi
15、git(constDigit) return; else constDigitTable.add(constDigit); /判断字符是否为字母 public boolean isLetter(String word) int N = 0; while (N letterTable.length) if (word.charAt(0) = letterTableN) return true; N+; return false; /判断字符是否为数字 public boolean isDigit(String word) int N = 0; while (N digitTable.length
16、) if (word.charAt(0) = digitTableN) return true; N+; return false; /判断字符串是否在关键词表 public boolean isKey(String word) int N = 0; while (N keyTable.size() if (word.equals(keyTable.get(N) return true; N+; return false; /判断字符串是否在分界符表 public boolean isDelimiter(String word) int N = 0; while (N delimiterTab
17、le.size() if (word.equals(delimiterTable.get(N) return true; N+; return false; /判断字符串是否在标识符表 public boolean isIdentifier(String word) int N = 0; while (N identifierTable.size() if (word.equals(identifierTable.get(N) return true; N+; return false; /判断字符串是否在常数表 public boolean isConstDigit(String word)
18、 int N = 0; while (N constDigitTable.size() if (word.equals(constDigitTable.get(N) return true; N+; return false; /判断字符是否为算数运算符 public boolean isArithmetic(String word) int N = 0; while (N arithmeticTable.length) if (word.charAt(0) = arithmeticTableN) return true; N+; return false; /判断字符是否为关系运算符 pub
19、lic boolean isRelation(String word) int N = 0; while (N relationTable.length) if (word.charAt(0) = relationTableN) return true; N+; return false; /清理分析器 public void cleanAnalysis() this.ch = ; this.index = 0; this.result = ; this.rowLength = 0; this.strChar = null; /获得非空白字符 public char getBC(char st
20、rChar) try while (strCharthis.index) = ) this.index+; this.index+; catch (ArrayIndexOutOfBoundsException e) return ; return strCharthis.index - 1; /链接字符串和字符 public String contact(String token, char ch) return token + String.valueOf(ch); /获得下一个字符 public char getNextChar(char strChar) if (this.index =
21、 this.rowLength-1) this.index+; return strCharthis.index - 1; else this.index+; return ; /回调一个字符 public void retract() this.index-; /单行分析 public String rowAnalysis(String row,int N) int M = 0; strChar = row.toCharArray(); rowLength = row.length(); while (index rowLength) this.token = ; this.ch = thi
22、s.getBC(strChar); if (this.isLetter(String.valueOf(this.ch) this.token = this.contact(this.token, this.ch); this.ch = this.getNextChar(this.strChar); while (isLetter(String.valueOf(this.ch) | isDigit(String.valueOf(this.ch) this.token = this.contact(this.token, this.ch); this.ch = this.getNextChar(t
23、his.strChar); this.retract(); if (this.isKey(token) this.result += this.token.toString() + t(1,+this.token.toString()+)tt + 关键词tt + ( + N + ,+ +M + ) + rn; this.getDataStrings()arrarycount0 = ; this.getDataStrings()arrarycount1 = this.token.toString(); this.getDataStrings()arrarycount2 = (1,+this.to
24、ken.toString()+); this.getDataStrings()arrarycount3 = 关键词; this.getDataStrings()arrarycount4 = ( + N + ,+ M + ); arrarycount+; else this.inIdentifierTable(token); this.result += this.token.toString() + t(6,+this.token.toString()+)tt + 标识符tt + ( + N + ,+ +M + ) + rn; this.getDataStrings()arrarycount0
25、 = ; this.getDataStrings()arrarycount1 = this.token.toString(); this.getDataStrings()arrarycount2 = (6,+this.token.toString()+); this.getDataStrings()arrarycount3 = 标识符; this.getDataStrings()arrarycount4 = ( + N + ,+ M + ); arrarycount+; this.token = ; else if (this.isDigit(String.valueOf(this.ch) t
26、his.token = this.contact(this.token, this.ch); this.ch = this.getNextChar(strChar); while (this.isDigit(String.valueOf(this.ch) this.token = this.contact(this.token, this.ch); this.ch = this.getNextChar(this.strChar); this.retract(); this.inConstDigitTable(token); this.result += this.token.toString(
27、) + t(5,+this.token.toString()+)tt + 常数tt + ( + N + ,+ +M + ) + rn; this.getDataStrings()arrarycount0 = ; this.getDataStrings()arrarycount1 = this.token.toString(); this.getDataStrings()arrarycount2 = (5,+this.token.toString()+); this.getDataStrings()arrarycount3 = 常数; this.getDataStrings()arrarycount4
