从整体上看, 词法分析是编译器前段的第一个部分, 它的任务是完成从字符流到记号流的转换.
字符流 : 其实就是源代码. 那么什么是记号流, 记号其实是一种数据结构, 方便编译器后期对代码进行有效处理而产生的, 比如在java 中, 这就是记号(Token).
1 public class Token {2 public static enum Type{3 Id, If, Else, While, For, LP, RP4 };5 6 private Type type;7 private String value;8 }
实现方案至少有两种
1. 手工编码
2. 词法分析器的生成器
先看手工编码, 为了方便代码生成, 我们可以先生成所需要识别程序代码的状态转移图. 大概就长成这个样子 :
图里面有几点需要提一下 : 首先是 0 号状态 (开始状态) : 最明显的标志是有一个箭头从外指向它... 然后是2, 4, 6号状态, 他们由两个同心圆组成, 表示接受状态, 也就是说此时这个Token已经生成并且可以返回了(比如6号状态), 仔细看的话你会发先他们的右上角都有一个 * 的符号, 这说明在这个位置有一个回滚操作, 比如 你从输入流中读入了 i f 进去了状态5, 那么你只有在读入一个字母 (可以是空格), 你才能知道这边是if 而不会是 ifx 但是这个空格你是没有处理过的, 所以你必须把这个空格回滚到输入流中...
另外一点, 其实这个转移图可以改进, 我们会发现 程序的关键字 其实可以认为是标识符的一部分, 都是字母或者下划线开头, 字母下划线数字跟在后面, 所以更好的做法是先统一把关键字识别为标识符, 等到真正构造Token的时候在对它进行细化...
下面是一个小练习 :
我的代码实现...
1 package font; 2 3 public class Token { 4 public static enum Type{ 5 IF, ID, NUM 6 }; 7 8 private Type type; 9 private String value;10 private int line;11 private int pos;12 13 public Token(Type type, String value, int line, int pos) {14 if(type == Type.ID && value.equals("if")){15 this.type = Type.IF;16 }else {17 this.type = type;18 this.value = value;19 }20 21 this.line = line;22 this.pos = pos - value.length();23 }24 25 26 @Override27 public String toString() {28 return type + "("+ value +")" + "("+ line + ", " + pos +")";29 }30 } 1 package font; 2 3 import java.io.IOException; 4 import java.io.Reader; 5 import java.util.ArrayList; 6 7 public class Lexer { 8 Reader reader; 9 char[] buffer = new char[256];10 int length;11 int curPos = 0;12 StringBuilder sb = new StringBuilder();13 int line = 1;14 int pos = 1;15 ArrayList tokens = new ArrayList<>();16 boolean EOF = false;17 18 public Lexer(Reader reader) throws IOException {19 this.reader = reader;20 length = reader.read(buffer, 0, 256);21 }22 23 public void lex() throws IOException {24 char ch;25 while(true) {26 eatSpace();27 ch = buffer[curPos];28 if (isNumber(ch)) {29 sb.append(ch);30 pos++;31 while (isNumber(ch = buffer[++curPos])) {32 sb.append(ch);33 pos++;34 }35 tokens.add(new Token(Token.Type.NUM, sb.toString(), line, pos));36 sb = new StringBuilder();37 } else if (isIdentifier(ch)) {38 sb.append(ch);39 pos++;40 while (isIdentifier(ch = buffer[++curPos])) {41 sb.append(ch);42 pos++;43 }44 tokens.add(new Token(Token.Type.ID, sb.toString(), line, pos));45 sb = new StringBuilder();46 } else if (EOF) {47 return;48 } else {49 System.exit(110);50 }51 }52 }53 54 public void eatSpace(){55 char ch;56 while(Character.isWhitespace(ch = buffer[curPos++]) || ch == '\0'){57 if(ch == '\n'){58 line++;59 pos = 1;60 }else if(ch == '\0'){61 EOF = true;62 break;63 } else{64 pos++;65 }66 }67 curPos--;68 }69 70 public boolean isIdentifier(char ch){71 return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || isNumber(ch);72 }73 74 public boolean isNumber(char ch){75 return ch >= '0' && ch <= '9';76 }77 78 public void print(){79 for(Token each : tokens){80 System.out.println(each);81 }82 }83 } package font;import java.io.*;public class Test { public static void main(String[] args) throws IOException { File fh = new File("/Users/zhangzhimin/test.c"); Lexer lexer = new Lexer(new BufferedReader(new FileReader(fh))); lexer.lex(); lexer.print(); }} 输出结果 :
