词法分析器实现过程（java和c++实现） |
您所在的位置：网站首页 › java词法分析器dfa › 词法分析器实现过程（java和c++实现） |
词法分析器实现过程（java和c++实现）
|
词法分析器是编译原理的一个实验，本文将会详细给出实现的具体步骤，利用java进行示例讲解，源码（包含java和c++两种实现方式）可在 https://download.csdn.net/download/qq_40121502/10926516 下载。 一、 实验目的设计、编写一个词法分析程序，加深对词法分析原理的理解。 二、 实验原理词法分析是从左向右一个字符、一个字符地读入源程序，扫描每行源程序的符号，依据词法规则，识别单词。执行词法分析的程序称为词法分析器，将给定的程序通过词法分析器，识别出一个个单词符号。单词符号常采用统一的二元式表示：（单词种别码，单词符号自身的值），单词种别码是语法分析所需要的信息，而单词符号自身属性值是编译其他阶段需要的信息。 三、 实验内容（1）程序利用C++或Java或其他编程语言，给出其词法的产生式（词法部分也可以用regular expression），包含数学运算表达式，赋值，函数调用，控制流语句（分支或循环），类型声明等基本元素。 （2）词法实验部分要求写出该语言的词法分析程序。要求识别出词法分析单元，给出词法单元的分类，按照不同类别填入相应的表中，表中给出词法单元在源程序中的位置。 四、 实验方法（1）词法的产生式（或regular expression）转换成NFA （2）NFA确定化为DFA （3）DFA最小化 （4）根据最小化后的DFA写出词法分析程序。 （5）使用选定的编程语言写几个测试用例文件作为输入，测试词法分析程序是否正确。 五、 实验设计（1）关键字： “char”,“int”,“float”,“double”,“final”,“if”,“else”,“while”,“do”,“for”,“break”,“continue”,”void”,”return” （2）运算符：=、==、>、=、letter( letter )* letter->[a-z] 按照RE—>NFA—>DFA—>最小化DFA的顺序，过程如图所示： 本实验设计了十个运算符，分别为：=、==、>、=、 ( = | == | > | < | >= | NFA—>DFA—>最小化DFA的顺序，过程如图所示： 本实验设计的界限符有：( ) [ ]{ } , : ; 界限符表达式为： delimiter -> ( ( | ) | [ | ] | { | } | , | : | ; )* 从RE—>NFA—>DFA—>最小化DFA的顺序，过程如图所示： 用字母、数字、下划线的连接用来表示变量名、过程名等的单词称为标识符（不能以数字开头、不与关键字重名、不包含$、#等无法识别的字符）。 标识符的正规表达式为： ID ->( letter | _ ) ( letter | digit | _ )* letter->[a-zA-Z] digit->[0-9] 按照RE—>NFA—>DFA—>最小化DFA的顺序，过程如图所示： 将整数，浮点数归并后分为无符号数和有符号数。 因为有符号数，除了开始有符号外，之后的判断与无符号数是一致的。所以在这里只针对无符号数的正规表达式构造NFA和DFA。 无符号数正规表达式： NUM -> digits op_fra op_exp 其中： digits -> d(d)* d -> [0-9] op_fra-> .digits | ε op_exp -> ( E (+|-| ε) digits) | ε 将上述表达式整合得无符号数NUM的正规表达式为： NUM->d(d)|d(d).d(d)|d(d)(E(+|-|ε)d(d))|d(d).d(d)E(+|-|ε)d(d) d -> [0-9] 按照RE—>NFA—>DFA—>最小化DFA的顺序，过程如图所示： （1）使用ArrayList来存放从文件内读取进来的每个单词（符号）。 （2）自定义类Pair，相当于键值对，用于存放单词种别码和对应的单词，包含一个Integer类型的key和一个String类型的value。 （3）使用ArrayList来存放词法分析的结果。 八、实现代码 1.定义关键字首先定义了一系列关键字及其对应的种别码，用于表示词法分析的结果。 // 单词种别码, 1-17为关键字种别码 public static final int CHAR = 1; public static final int SHORT = 2; public static final int INT = 3; public static final int LONG = 4; public static final int FLOAT = 5; public static final int DOUBLE = 6; public static final int FINAL = 7; public static final int STATIC = 8; public static final int IF = 9; public static final int ELSE = 10; public static final int WHILE = 11; public static final int DO = 12; public static final int FOR = 13; public static final int BREAK = 14; public static final int CONTINUE = 15; public static final int VOID = 16; public static final int RETURN = 17; // 20为标识符种别码 public static final int ID = 20; // 30为常量种别码 public static final int NUM = 30; // 31-40为运算符种别码 public static final int AS = 31; // = public static final int EQ = 32; // == public static final int GT = 33; // > public static final int LT = 34; // = public static final int LE = 36; // InputStream is = new FileInputStream(filepath); String line; // 用来保存每行读取的内容 BufferedReader reader = new BufferedReader(new InputStreamReader(is)); line = reader.readLine(); // 读取第一行 while (line != null) { // 如果 line 为空说明读完了 sb.append(line); // 将读到的内容添加到 buffer 中 sb.append("\n"); // 添加换行符 line = reader.readLine(); // 读取下一行 } reader.close(); is.close(); fileStr = sb.toString(); } catch (IOException e) { e.printStackTrace(); } System.out.println("文件内容如下：\n" + fileStr); 单词分割采用循环读取的方式将输入的内容进行读取分析 getFirstChar()：去除字符串开头的空格和换行符，找到第一个有效字符的位置 getWord()：使用正则表达式进行匹配，获取一个单词 当文件读取结束时将抛出IndexOutOfBoundsException异常，捕获这个异常，在catch块中进行后续的词法分析。 int begin = 0, end = 0; //分别表示单词的第一个和最后一个字符位置 ArrayList arrayList = new ArrayList(); try { do { begin = getFirstChar(fileStr, begin); String word = getWord(fileStr, begin); end = begin + word.length() - 1; // 单词最后一个字符在原字符串的位置 if (word.equals("")) { break; } if (!(word.equals(blank) || word.equals(newLine))) { arrayList.add(word); } begin = end + 1; } while (true); } catch (IndexOutOfBoundsException e) { // 文件读取结束 // 词法分析 } /** * 去除字符串开头的空格和换行符，找到第一个有效字符的位置 * @param str 目标字符串 * @param begin 开始位置 * @return 第一个有效字符在字符串中的位置 */ public static int getFirstChar(String str, int begin) { while (true) { if (str.charAt(begin) != ' ' && str.charAt(begin) != '\n' ) { return begin; } begin++; } } /** * 获取一个单词 * @param str 目标字符串 * @param begin 查找的开始位置 * @return 单词 */ public static String getWord(String str, int begin) { String regEx = "\\s+|\\n|\\+|-|\\*|/|=|\\(|\\)|\\[|]|\\{|}|,|:|;"; // 正则 Pattern p = Pattern.compile(regEx); Matcher m = p.matcher(str); int end; if (m.find(begin)) { end = m.start(); } else { return ""; } if (begin == end) { return String.valueOf(str.charAt(begin)); } return str.substring(begin, end); } 3.词法分析将分割好的单词和最开始定义的一系列关键字进行比对匹配，每个单词的分析结果由Pair类进行保存，Pair类仅代表键值对的形式，键为单词种别码，值为该单词。 Pair类定义如下： public static class Pair { Integer key; String value; Pair(Integer key, String value) { this.key = key; this.value = value; } }词法分析函数：根据单词的长度进行分析比对 // 词法分析函数 public static ArrayList analyse(ArrayList arrayList) { ArrayList result = new ArrayList(); for (int i = 0; i if (arrayList.get(i).equals("=")) { // 运算符"=" if (arrayList.get(i+1).equals("=")) { // 若后面跟的是"="，则是运算符"==" result.add(new Pair(EQ, arrayList.get(i) + arrayList.get(++i))); } else { // 否则是运算符"=" result.add(new Pair(AS, arrayList.get(i))); } } else if (arrayList.get(i).equals(">")) { // 运算符">" if (arrayList.get(i+1).equals("=")) { // 若后面跟的是"="，则是运算符">=" result.add(new Pair(GE, arrayList.get(i) + arrayList.get(++i))); } else { // 否则是运算符">" result.add(new Pair(GT, arrayList.get(i))); } } else if (arrayList.get(i).equals(" |
【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |