只要能够通过正则表达式来表示单词的定义，词法分析器的设计就没有太大的困难。Java语言的正则表达式库能够在模式匹配后返回匹配的字符串中的一部分，本书将利用这一功能来实现词法分析器。例如，下面的字符串 http://javassist.org/ 与正则表达式 http://(.+)/ 匹配。Java语言能够获取与括号中的模式.+匹配的子字符串javassist.org。如果模式包含多个括号，各个括号内的子字符串都能被分别取得。 每一对左右括号都对应了与其包围的模式相匹配的子字符串。要利用这一功能设计词法分析器，首先要准备一个下面这样的正则表达式。 s*((//.*)|( pat1 )|( pat2 )| pat3 )? 其中，pat1是与整型字面量匹配的正则表达式，pat2与字符串字面量匹配，pat3则与标识符匹配。起始的s与空字符匹配，s*与0个及0个以上的空字符匹配。模式//.*匹配由//开始的任意长度的字符串，用于匹配代码注释。于是，上述正则表达式能匹配任意个空白符以及连在其后的注释、整型字面量、字符串字面量或标识符。又因为它最后以?结尾，所以仅由任意多个空白符组成的字符串也能与该模式匹配。 执行词法分析时，语言处理器将逐行读取源代码，从各行开头起检查内容是否与该正则表达式匹配，并在检查完成后获取与正则表达式括号内的模式相匹配的字符串。 左起第1个左括号对应的字符串与该括号对应的模式匹配，不包含字符串头部的空白符。如果匹配的字符串是一句注释，则对应于左起第2个左括号，从第3个左括号起对应的都是null。如果匹配的字符串是一个整型字面量，则对应于左起第3个左括号，第2个和第4个左括号与null对应。类似地，如果匹配的字符串是一个字符串字面量，则对应于左起第4个左括号，第2个和第3个左括号对应null。如果匹配的字符串是标识符，它将与第1个左括号对应，除此之外的左括号都与null对应。 只要像这样检查一下哪一个括号对应的不是null，就能知道行首出现的是哪种类型的单词。之后再继续用正则表达式匹配剩余部分，就能得到下一个单词。不断重复该过程，词法分析器就能获得由源代码分割而得的所有单词。 F 这么依赖正则表达式，会不会导致执行速度变慢呢？ C 手动设计匹配逻辑也是一样的，并不会有什么区别。 S 嗯，而且库中的实现经过了大量优化，肯定比自己手动设计性能更好嘛。 C 与完全手写的词法分析逻辑相比，至少错误会少很多。 A 是吗？只要字符串字面量的正则表达式没什么问题的话，这么说也没错吧。 代码清单3.3与代码清单3.4是一个实际的词法分析程序。Lexer类就是一个词法分析器。Lexer对象的构造函数接收一个java.io.Reader对象，它能根据需要逐行读取源代码，供执行词法分析。 正则表达式保存于regexPat字段。Java语言的字符串字面量中，反斜杠与双引号必须分别以\与"的形式转义。因此，字符串中将包含大量的反斜杠。 read与peek是Lexer中主要的两个方法。read方法可以从源代码头部开始逐一获取单词。调用read时将返回一个新的单词。 peek方法则用于预读。peek(i)将返回read方法即将返回的单词之后的第i个单词。如果参数i为0，则返回与read方法相同的结果。通过peek方法，词法分析器就能事先知道在调用read方法时将会获得什么单词。例如，peek(1)所返回的单词与调用read方法两次后返回的单词相同。 如果所有单词都已读取，read方法和peek方法都将返回Token.EOF。这是一个特殊的Token对象，用于表示程序结束。 F Lexer中不使用Iterator吗？ H 用next与hasNext方法来替代read也不错吧。 C 考虑到Lexer实际的使用方式，返回一个Token.EOF更加方便。不过如果能有hasNext也可以。 在词法分析后需要执行的是语法分析。对语法分析阶段的抽象语法树构造来说，peek方法必不可少。语法分析阶段将一边获取单词一边构造抽象语法树，在中途发现构造有误时，需要退回若干个单词，重新构造语法树，这称为回溯。为了支持回溯，语言处理器必须能够取消之前的几次read方法调用，并还原先前的结果。不过，如果要在实现Lexer类时解决这一问题，执行效率会受到影响，因此这里准备了peek方法。 peek方法可以事先获知之后将会取得的单词，以此避免撤销抽象语法树的构造。也就是说，当遇到分支路线时，不是先随意选取一条，在行不通时再原路返回改走另一条，而是先费一番周折，判断前路是否正确，在确信没有问题时才真正继续。 A 只要使用peek方法就能自由读取之后的单词，那还有必要使用read方法吗？ C 这关系到内存的占用量。read方法返回的单词不必一直保留，而peek方法必须保存所有返回的单词，内存消耗更大。 要使用peek方法，词法分析器需要在读取代码并获取单词后，将这些单词暂时保存在一个名为queue的ArrayList对象中。之后，peek与read方法会根据需要从中取值并返回。由read方法读取的单词会从queue中删除。 readLine方法是实际从每一行中读取单词的方法。由于正则表达式已经事先编译为Pattern对象，因此能调用matcher方法来获得一个用于实际检查匹配的Matcher对象。词法分析器一边通过region方法限定该对象检查匹配的范围，一边通过lookingAt方法在检查范围内进行正则表达式匹配。之后，词法分析器将使用group方法来获取与各个括号对应的子字符串。end方法用于取得匹配部分的结束位置，词法分析器将从那里开始继续执行下一次lookingAt方法调用，直至该代码行中不再含有单词。 代码清单3.3最后的NumToken、IdToken与StrToken类是Token类的子类。它们分别对应不同类型的单词。 C readLine与addToken是词法分析的核心部分，其他都只是起辅助作用，因此词法分析还是比较简单的。 H 我还以为您肯定会用工具来定义单词并自动生成词法分析器呢。 F 的确有JFlex（http://jflex.de）之类的工具。 C 如果要设计一个真正的语言处理器，最好是使用一些合适的工具。不过Stone语言非常简单，所以没这个必要。 代码清单3.3 词法分析器Lexer.java package stone; import java.io.IOException; import java.io.LineNumberReader; import java.io.Reader; import java.util.ArrayList; import java.util.regex.Matcher; import java.util.regex.Pattern; public class Lexer { public static String regexPat = "\s*((//.*)|([0-9]+)|("(\\"|\\\\|\\n|[^"])*")" + "|[A-Z_a-z][A-Z_a-z0-9]*|==|<=|>=|&&|\|\||\p{Punct})?"; private Pattern pattern = Pattern.compile(regexPat); private ArrayList<Token> queue = new ArrayList<Token>(); private boolean hasMore; private LineNumberReader reader; public Lexer(Reader r) { hasMore = true; reader = new LineNumberReader(r); } public Token read() throws ParseException { if (fillQueue(0)) return queue.remove(0); else return Token.EOF; } public Token peek(int i) throws ParseException { if (fillQueue(i)) return queue.get(i); else return Token.EOF; } private boolean fillQueue(int i) throws ParseException { while (i >= queue.size()) if (hasMore) readLine(); else return false; return true; } protected void readLine() throws ParseException { String line; try { line = reader.readLine(); } catch (IOException e) { throw new ParseException(e); } if (line == null) { hasMore = false; return; } int lineNo = reader.getLineNumber(); Matcher matcher = pattern.matcher(line); matcher.useTransparentBounds(true).useAnchoringBounds(false); int pos = 0; int endPos = line.length(); while (pos < endPos) { matcher.region(pos, endPos); if (matcher.lookingAt()) { addToken(lineNo, matcher); pos = matcher.end(); } else throw new ParseException("bad token at line " + lineNo); } queue.add(new IdToken(lineNo, Token.EOL)); } protected void addToken(int lineNo, Matcher matcher) { String m = matcher.group(1); if (m != null) // if not a space if (matcher.group(2) == null) { // if not a comment Token token; if (matcher.group(3) != null) token = new NumToken(lineNo, Integer.parseInt(m)); else if (matcher.group(4) != null) token = new StrToken(lineNo, toStringLiteral(m)); else token = new IdToken(lineNo, m); queue.add(token); } } protected String toStringLiteral(String s) { StringBuilder sb = new StringBuilder(); int len = s.length() - 1; for (int i = 1; i < len; i++) { char c = s.charAt(i); if (c == '\' && i + 1 < len) { int c2 = s.charAt(i + 1); if (c2 == '"' || c2 == '\') c = s.charAt(++i); else if (c2 == 'n') { ++i; c = 'n'; } } sb.append(c); } return sb.toString(); } protected static class NumToken extends Token { private int value; protected NumToken(int line, int v) { super(line); value = v; } public boolean isNumber() { return true; } public String getText() { return Integer.toString(value); } public int getNumber() { return value; } } protected static class IdToken extends Token { private String text; protected IdToken(int line, String id) { super(line); text = id; } public boolean isIdentifier() { return true; } public String getText() { return text; } } protected static class StrToken extends Token { private String literal; StrToken(int line, String str) { super(line); literal = str; } public boolean isString() { return true; } public String getText() { return literal; } } } 代码清单3.4 异常ParseException.java package stone; import java.io.IOException; public class ParseException extends Exception { public ParseException(Token t) { this("", t); } public ParseException(String msg, Token t) { super("syntax error around " + location(t) + ". " + msg); } private static String location(Token t) { if (t == Token.EOF) return "the last line"; else return """ + t.getText() + "" at line " + t.getLineNumber(); } public ParseException(IOException e) { super(e); } public ParseException(String msg) { super(msg); } }
