写在前面
由于我对写解析器只有 阅读了几篇文章 的知识量, 因此水平并不是很高, 此文权当一次个人总结, 无法保证所涉及的知识点思路完全无误, 如有错误, 还请各位大佬指正
从一个正整数表达式开始
这篇文章围绕的仅仅是一个 正整数表达式, 而且它很简单, 不会出现括号嵌套等情况, 我们的目标只是把
10 * 5 + 1
解析为一个 Token 序列, 如下:
- [{ type: NUMBER, value: `10`},
- { type: OPERATOR, value: `*` },
- { type: NUMBER, value: `5` },
- { type: OPERATOR, value: `+` },
- { type: NUMBER, value: `1` }
- ]
我习惯从简单的开始, 那么我们先从一个最简单的只有个位数没有空格的式子开始:
1+1
最简单的思路
其实词法分析器要做的事本质上很简单: 对输入的字符串进行遍历, 分割成有意义的 Token
因此, 最简单的思路就是一个 for 循环:
- String expression = "1+1";
- for (char ch: expression.toCharArray()) {
- // 在这里进行处理
- }
所以我们定义一个 Scanner, 为了后续方便, 顺手实现个简单的单例吧:
- public class Scanner {
- private static volatile Scanner instance;
- public static Scanner getInstance() {
- if (Scanner.instance == null) {
- synchronized(Scanner.class) {
- if (Scanner.instance == null) {
- Scanner.instance = new Scanner();
- }
- }
- }
- return Scanner.instance;
- }
- private String expression;
- public Scanner from(String expression) {
- this.expression = expression;
- return this;
- }
- public void process() {
- for (char ch: expression.toCharArray()) {
- // 在这里进行处理
- }
- }
- public static void main(String...args) {
- Scanner scanner = Scanner.getInstance().from("1+1");
- scanner.process();
- }
- }
定义 Token 类型
在当前的 1+1 表达式中, 涉及到的 Token 不多, 只有数字操作符, 因此用一个枚举类即可表述:
- public enum Type {
- INIT,
- NUMBER,
- OPERATOR,
- UNKNOWN;
- public static Type of(char ch) {
- if ('0' <= ch && ch <= '9') {
- return NUMBER;
- }
- if ("+-*/".indexOf(ch) != -1) {
- return OPERATOR;
- }
- return UNKNOWN;
- }
- }
同时该枚举类承担辨识字符类型的工作:
- Type.of('1') // NUMBER
- Type.of('+') // OPERATOR
- Type.of('a') // UNKNOWN
定义 Token
- public class Token {
- // 一个 Token 的类型一旦确定, 就不可能再改变
- private final Type type;
- // 用以存储 Token 的值
- private final StringBuffer value;
- public Token(Type type) {
- this.type = type;
- this.value = new StringBuffer();
- }
- public void appendValue(char ch) {
- this.value.append(ch);
- }
- public String getValue() {
- return this.value.toString();
- }
- public Type getType() {
- return this.type;
- }
- @Override
- public String toString() {
- return String.format("{type: %s, value: `%s`}",
- this.getType().name(),
- this.getValue());
- }
- }
处理 1+1
- public class Scanner {
- // 省略...
- public void process() {
- for (char ch: expression.toCharArray()) {
- Type type = Type.of(ch);
- if (Type.UNKNOWN.equals(type)) {
- throw new RuntimeException(String.format("`%c` 并不属于期望的字符类型", ch));
- }
- Token token = new Token(type);
- token.appendValue(ch);
- System.out.println(token);
- }
- }
- public static void main(String...args) {
- Scanner scanner = new Scanner("1+1");
- scanner.process();
- }
- }
- /** 输出
- * {type: NUMBER, value: `1`}
- * {type: OPERATOR, value: `+`}
- * {type: NUMBER, value: `1`}
- */
现在来加点难度: 10+1
现在一个数字可能不止一位了, 那么我们该怎么办呢?
使用状态图:
- - [0 - 9] - -[ + |-|*|/ ]- -[ 0-9 ]-
- ---( NUMBER )--- ( OPERATOR )---( NUMBER )---/
具体的理论这里就不赘述了, 有兴趣可以自行查阅相关资料, 这里简单说一下怎么用:
现在我们来列个表, 看一下对于 10+1, 在状态上有什么变化:
字符 | 状态 | Token |
---|---|---|
NULL | INIT | NULL |
1 | NUMBER | {id: 0, type: NUMBER, value: 1} |
0 | NUMBER | {id: 0, type: NUMBER, value: } |
+ | OPERATOR | {id: 1, type: OPERATOR, value: +} |
1 | NUMBER | {id: 2, type: NUMBER, value: 1} |
可以看到, 在读到字符 1 和 0 时, 状态没有发生变化, 也就是说它们是一个整体(或是一个整体的一部分)
如果在 0 后面还有其他数字, 那么直到引起状态改变的字符出现之前, 这些字符就组成了整个 Token
同时, 我们还发现引入状态图后, 有个有意思的事:
从 初始状态 INIT 开始, 我们只允许后边是 NUMBER 类型;
NUMBER 后边允许 NUMBEROPERATOR 类型;
OPERATOR 后边允许 NUMBER 类型
除此之外的状态都是不合法的, 这也就是有时候解析类的包 (比如 fast-json) 会看到的 Invalid Character 错误的情况
所以我们需要改改代码, 同时为 Scanner 添加一个更新状态的方法:
- public class Scanner {
- // 省略
- private Token token;
- public void setToken(Token token) {
- this.token = token;
- }
- public void process() {
- // 初始化
- this.setToken(new Token(Type.INIT));
- for (char ch: expression.toCharArray()) {
- Type type = Type.of(ch);
- if (Type.UNKNOWN.equals(type)) {
- throw new RuntimeException(String.format("`%c` 并不属于期望的字符类型", ch));
- }
- // 根据当前 Token 的类型, 选择不同的判断分支
- switch (token.getType()) {
- case INIT:
- switch (type) {
- // 当前是初始状态, 遇到了数字, 切换状态
- case NUMBER:
- this.setToken(new Token(Type.NUMBER));
- this.token.appendValue(ch);
- break;
- default:
- throw new RuntimeException(String.format("Invalid Character: `%c`", ch));
- }
- break;
- case NUMBER:
- switch (type) {
- // 当前是数字状态, 遇到了数字, 追加字符
- case NUMBER:
- this.token.appendValue(ch);
- break;
- // 当前是数字状态, 遇到了操作符, 切换状态
- case OPERATOR:
- this.setToken(new Token(Type.OPERATOR));
- this.token.appendValue(ch);
- break;
- default:
- throw new RuntimeException(String.format("Invalid Character: `%c`", ch));
- }
- break;
- case OPERATOR:
- switch (type) {
- // 当前是操作符状态, 遇到了数字, 切换状态
- case NUMBER:
- this.setToken(new Token(Type.NUMBER));
- this.token.appendValue(ch);
- break;
- default:
- throw new RuntimeException(String.format("Invalid Character: `%c`", ch));
- }
- break;
- }
- System.out.println(token);
- }
- }
- }
- /** 输出
- * {type: NUMBER, value: `1`}
- * {type: NUMBER, value: `10`}
- * {type: OPERATOR, value: `+`}
- * {type: NUMBER, value: `1`}
- */
试着简化一下
我们刚才用了一个巨大无比的 switch 结构来描述状态图, 现在我们由内而外试着简化这个巨无霸
先从内部开始:
- switch (type) {
- // 当前是 ** 状态, 遇到了 ** , 执行 ** 操作
- case NUMBER:
- // ...
- break;
- case...
- default:
- throw new RuntimeException(String.format("Invalid Character: `%c`", ch));
- }
其实稍微归纳总结一下就能发现, 执行 ** 操作 这部分, 总的来说只有两种:
NewToken
对应着
- {
- token = new Token(Type.NUMBER);
- token.appendValue(ch);
- }
- AppendValue
对应着
- {
- token.appendValue(ch);
- }
现在我们再引入一个工具来帮助我们简化: 表驱动
其实从上面的对应关系不难发现, 我们可以用 HashMap 来简单模拟一个表, 帮助我们减少工作
在此之前, 我们需要把上述关系中的 {操作} 部分用一个接口来解耦:
- public interface Behavior {
- void apply(Token token, Type type, char ch);
- }
然后我们来定义一个枚举类 Behaviors 来表示操作类型:
- public enum Behaviors {
- NewToken,
- AppendValue;
- private static final Scanner scanner;
- private static final HashMap < Behaviors,
- Behavior > behaviorMap;
- static {
- scanner = Scanner.getInstance();
- behaviorMap = new HashMap < >();
- behaviorMap.put(Behaviors.NewToken, (token, type, ch) - >{
- token = new Token(type);
- token.appendValue(ch);
- scanner.setToken(token);
- });
- behaviorMap.put(Behaviors.AppendValue, (token, type, ch) - >{
- token.appendValue(ch);
- });
- }
- public void apply(Token token, Type type, char ch) {
- behaviorMap.get(this).apply(token, type, ch);
- }
- }
那么现在 执行 操作 这部分, 现在可以用 HashMap 来表述了:
- // 根据当前 Token 的类型, 选择不同的判断分支
- switch (token.getType()) {
- case INIT:
- HashMap<Type, Behaviros> behaviorsMap = new HashMap<>();
- // 当前是初始状态, 遇到了数字, 切换状态
- behaviorsMap.put(Type.NUMBER, Behaviors.NewToken);
- break;
- case NUMBER:
- HashMap<Type, Behaviros> behaviorsMap = new HashMap<>();
- // 当前是数字状态, 遇到了数字, 追加字符
- behaviorsMap.put(Type.NUMBER, Behaviors.AppendValue);
- // 当前是数字状态, 遇到了操作符, 切换状态
- behaviorsMap.put(Type.Operator, Behaviors.NewToken);
- break;
- case OPERATOR:
- HashMap<Type, Behaviros> behaviorsMap = new HashMap<>();
- // 当前是操作符状态, 遇到了数字, 切换状态
- behaviorsMap.put(Type.NUMBER, Behaviors.NewToken);
- break;
- }
既然是 Java , 那么让我们来让这部分看起来 OO 一些:
- public class BehaviorMap {
- private final HashMap < Type,
- Behaviors > map;
- public BehaviorMap() {
- this.map = new HashMap();
- }
- public BehaviorMap at(Type type, Behaviors behaviors) {
- this.map.put(type, behaviors);
- return this;
- }
- public BehaviorsTable done() {
- return BehaviorsTable.getInstance();
- }
- }
现在再来看看:
- // 根据当前 Token 的类型, 选择不同的判断分支
- switch (token.getType()) {
- case INIT:
- BehaviorMap map = new BehaviorMap();
- map
- // 当前是初始状态, 遇到了数字, 切换状态
- .at(Type.NUMBER, Behaviors.NewToken);
- break;
- case NUMBER:
- BehaviorMap map = new BehaviorMap();
- map
- // 当前是数字状态, 遇到了数字, 追加字符
- .at(Type.NUMBER, Behaviors.AppendValue);
- // 当前是数字状态, 遇到了操作符, 切换状态
- .at(Type.Operator, Behaviors.NewToken);
- break;
- case OPERATOR:
- BehaviorMap map = new BehaviorMap();
- map
- // 当前是操作符状态, 遇到了数字, 切换状态
- .at(Type.NUMBER, Behaviors.NewToken);
- break;
- }
简化外部
现在我们可以看到表驱动对于消除判断分支的威力了, 那么我们可以用同样的方法将外部 switch 也消除掉:
- public class BehaviorsTable {
- private static volatile BehaviorsTable instance;
- public static BehaviorsTable getInstance() {
- if (BehaviorsTable.instance == null) {
- synchronized(BehaviorsTable.class) {
- if (BehaviorsTable.instance == null) {
- BehaviorsTable.instance = new BehaviorsTable();
- }
- }
- }
- return BehaviorsTable.instance;
- }
- private final HashMap < Type,
- BehaviorMap > map;
- public BehaviorsTable() {
- this.map = new HashMap < >();
- }
- public BehaviorMap register(Type type) {
- BehaviorMap behaviorMap = new BehaviorMap();
- this.map.put(type, behaviorMap);
- return behaviorMap;
- }
- }
现在整个巨大的 switch 结构我们就可以简化为:
- BehaviorsTable
- .getInstance()
- .register(Type.INIT)
- .at(Type.NUMBER, Behaviors.NewToken)
- .done()
- .register(Type.NUMBER)
- .at(Type.NUMBER, Behaviors.AppendValue)
- .at(Type.OPERATOR, Behaviors.NewToken)
- .done()
- .register(Type.OPERATOR)
- .at(Type.NUMBER, Behaviors.NewToken)
- .done();
现在 process 方法我们就可以简化为:
- public void process() {
- this.setToken(new Token(Type.INIT));
- for (char ch : expression.toCharArray()) {
- Type type = Type.of(ch);
- if (Type.UNKNOWN.equals(type)) {
- throw new RuntimeException(String.format("`%c` 并不属于期望的字符类型", ch));
- }
- BehaviorsTable
- .getInstance()
- // 根据当前 Token 类型获取对应的处理对策
- .get(this.token.getType())
- // 获取当前字符所属的处理行为
- .is(type)
- .apply(type, ch);
- System.out.println(token);
- }
- }
我们在源码里做了一些改动, 请参考文章底部全部代码
让我们测试一下
- public static void main(String...args) {
- Scanner scanner = Scanner.getInstance();
- scanner.from("10+1").process();
- /**
- * {type: NUMBER, value: `1`}
- * {type: NUMBER, value: `10`}
- * {type: NUMBER, value: `+`}
- * {type: NUMBER, value: `1`}
- */
- scanner.from("10 +1").process();
- /**
- * {type: NUMBER, value: `1`}
- * {type: NUMBER, value: `10`}
- * Exception in thread "main" java.lang.RuntimeException: ` ` 并不属于期望的字符类型
- */
- scanner.from("10++1").process();
- /**
- * {type: NUMBER, value: `1`}
- * {type: NUMBER, value: `10`}
- * {type: OPERATOR, value: `+`}
- * Exception in thread "main" java.lang.RuntimeException: Invalid Character: `+` for Token `OPERATOR`
- */
- }
现在看起来一切正常, 但是别忘了 Scanner 的工作是将输入的字符串分割为 Token 序列, 因此我们需要让 process 方法返回处理后的 LinkedList<Token> 序列
为此我们需要将每次新生成的 Token 保存下来:
- public class Scanner {
- private LinkedList<Token> tokens;
- private Token token;
- public void addToken(Token token) {
- this.token = token;
- this.tokens.add(token);
- }
- public LinkedList<Token> process() {
- this.setToken(new Token(Type.INIT));
- for (char ch : expression.toCharArray()) {
- Type type = Type.of(ch);
- if (Type.UNKNOWN.equals(type)) {
- throw new RuntimeException(String.format("`%c` 并不属于期望的字符类型", ch));
- }
- BehaviorsTable
- .getInstance()
- .get(this.token.getType())
- .is(type)
- .apply(type, ch);
- }
- return this.tokens;
- }
- public static void main(String ... args) {
- Scanner scanner = Scanner.getInstance().from("10*5+1");
- LinkedList<Token> tokens = scanner.process();
- for (Token token : tokens) {
- System.out.println(token);
- }
- }
- }
记得将 Behaviors 初始化部分中 NewToken 里的行为修改一下:
- behaviorMap.put(Behaviors.NewToken, (token, type, ch) - >{
- token = new Token(type);
- token.appendValue(ch);
- //scanner.setToken(token);
- scanner.addToken(token);
- });
现在再看看结果:
- {type: NUMBER, value: `10`}
- {type: OPERATOR, value: `*`}
- {type: NUMBER, value: `5`}
- {type: OPERATOR, value: `+`}
- {type: NUMBER, value: `1`}
看起来一切都如我们所愿! 现在离最初的目标只剩下空格的处理了, 得益于我们抽象了行为 Behaviors, 我们只需要在 Type 中注册空格, 然后为 BehaviorsTable 注册各种类型下对空格的处理就行了:
- public enum Type {
- SPACE;
- public Tpye of(char ch) {
- if (' ' == ch) return SPACE;
- }
- }
- public enum Behaviors {
- Continue;
- static {
- behaviorMap
- .put(Behaviors.Continue, (token, type, ch) -> {
- // 留空就行了
- })
- }
- }
- public class Scanner {
- static {
- BehaviorsTable
- .getInstance()
- .register(Type.INIT)
- .at(Type.NUMBER, Behaviors.NewToken)
- .at(Type.SPACE, Behaviors.Continue)
- .done()
- .register(Type.NUMBER)
- .at(Type.NUMBER, Behaviors.AppendValue)
- .at(Type.OPERATOR, Behaviors.NewToken)
- .at(Type.SPACE, Behaviors.Continue)
- .done()
- .register(Type.OPERATOR)
- .at(Type.NUMBER, Behaviors.NewToken)
- .at(Type.SPACE, Behaviors.Continue)
- .done();
- }
- }
还缺什么呢
我们现在完成的扫描器实际上无法识别出 1 1 + 0 是个错误的表达式, 它会解析出如下序列:
- {type: NUMBER, value: 11}
- {type: OPERATOR, value: +}
- {type: NUMBER, value: 0}
我个人希望这部分工作往上层放, 由消化 Token 序列的调用者通过模式匹配的方式去验证, 不过这样的话, Type.SPACE 的处理就不能随意 Continue 了, 有兴趣的话看官可以自行尝试一下 : P
全部代码
一个小尝试, 就不传 Github 了, 直接放这儿吧 (其实就是懒...
- Scanner.java public class Scanner {
- private static volatile Scanner instance;
- public static Scanner getInstance() {
- if (Scanner.instance == null) {
- synchronized(Scanner.class) {
- if (Scanner.instance == null) {
- Scanner.instance = new Scanner();
- }
- }
- }
- return Scanner.instance;
- }
- static {
- // 注册行为表
- BehaviorsTable.getInstance()
- // 注册 INIT 状态的行为表
- .register(Type.INIT).at(Type.NUMBER, Behaviors.NewToken).at(Type.SPACE, Behaviors.Continue).done().register(Type.NUMBER).at(Type.NUMBER, Behaviors.AppendValue).at(Type.OPERATOR, Behaviors.NewToken).at(Type.SPACE, Behaviors.Continue).done().register(Type.OPERATOR).at(Type.NUMBER, Behaviors.NewToken).at(Type.SPACE, Behaviors.Continue).done();
- }
- private String expression;
- private LinkedList < Token > tokens;
- private Token token;
- public Scanner from(String expression) {
- this.expression = expression;
- this.tokens = new LinkedList < >();
- return this;
- }
- public void setToken(Token token) {
- this.token = token;
- }
- public Token getToken() {
- return token;
- }
- public LinkedList < Token > process() {
- this.setToken(new Token(Type.INIT));
- for (char ch: expression.toCharArray()) {
- Type type = Type.of(ch);
- if (Type.UNKNOWN.equals(type)) {
- throw new RuntimeException(String.format("`%c` 并不属于期望的字符类型", ch));
- }
- BehaviorsTable.getInstance()
- // 获取当前 Token 类型所适用的行为表
- .get(this.token.getType())
- // 获取当前字符所适用的行为
- .is(type).apply(type, ch);
- }
- return this.tokens;
- }
- public void addToken(Token token) {
- // 更新一下当前 Token
- this.token = token;
- this.tokens.add(token);
- }
- public static void main(String...args) {
- Scanner scanner = Scanner.getInstance().from("10 * 5+1");
- LinkedList < Token > tokens = scanner.process();
- for (Token token: tokens) {
- System.out.println(token);
- }
- }
- }
- Type.java
- // Token 类型枚举
- public enum Type {
- INIT,
- // 初始化时使用
- SPACE,
- // 空格
- NUMBER,
- // 数字
- OPERATOR,
- // 操作符
- UNKNOWN; // 未知类型
- public static Type of(char ch) {
- if (' ' == ch) {
- return SPACE;
- }
- if ('0' <= ch && ch <= '9') {
- return NUMBER;
- }
- if ("+-*/".indexOf(ch) != -1) {
- return OPERATOR;
- }
- return UNKNOWN;
- }
- }
- Token.java public class Token {
- // 一个 Token 的类型一旦确定, 就不可能再改变
- private final Type type;
- // 用以存储 Token 的值
- private final StringBuffer value;
- public Token(Type type) {
- this.type = type;
- this.value = new StringBuffer();
- }
- // 向 value 中追加字符
- public void appendValue(char ch) {
- this.value.append(ch);
- }
- public String getValue() {
- return this.value.toString();
- }
- public Type getType() {
- return this.type;
- }@Override public String toString() {
- return String.format("{type: %s, value: `%s`}", this.getType().name(), this.getValue());
- }
- }
- Behavior.java public interface Behavior {
- /**
- * 将行为抽象出来
- * @param token 当前的 token
- * @param type 读入字符的类型
- * @param ch 读入的字符
- */
- void apply(Token token, Type type, char ch);
- }
- Behaviors.java
- // 预设行为
- public enum Behaviors {
- NewToken,
- // 新建一个指定类型的 Token, 将当前字符保存到新 Token
- AppendValue,
- // 将当前字符追加到当前 Token 的值中
- Continue,
- // 跳过当前字符
- InvalidCharacter; // 当前 Token 类型所不期望的字符类型, 会抛出一个异常
- // 持有一个引用就不用老是调用 getInstance()
- private static final Scanner scanner;
- // 为预设行为指定行为内容
- private static final HashMap < Behaviors,
- Behavior > behaviorMap;
- static {
- scanner = Scanner.getInstance();
- behaviorMap = new HashMap < >();
- // 指定 NewToken, 行为逻辑参见枚举值说明
- behaviorMap.put(Behaviors.NewToken, (token, type, ch) - >{
- token = new Token(type);
- token.appendValue(ch);
- scanner.addToken(token);
- });
- // 指定 AppendValue, 行为逻辑参见枚举值说明
- behaviorMap.put(Behaviors.AppendValue, (token, type, ch) - >{
- token.appendValue(ch);
- });
- // 指定 Continue, 行为逻辑参见枚举值说明
- behaviorMap.put(Behaviors.Continue, (token, type, ch) - >{});
- // 指定 InvalidCharacter, 行为逻辑参见枚举值说明
- behaviorMap.put(Behaviors.InvalidCharacter, (token, type, ch) - >{
- throw new RuntimeException(String.format("Invalid Character: `%c` for Token `%s`", ch, token.getType().name()));
- });
- }
- public void apply(Type type, char ch) {
- // 获取预设行为
- behaviorMap.get(this)
- // 向行为中传递当前 Token, 当前字符类型, 当前字符
- .apply(scanner.getToken(), type, ch);
- }
- }
- BehaviorsMap.java
- // 保存某一字符类需要执行何种预设行为的映射关系
- public class BehaviorsMap {
- private final HashMap < Type,
- Behaviors > map;
- public BehaviorsMap() {
- this.map = new HashMap();
- }
- /**
- * 注册指定类型所需的预设行为
- * @param type 指定类型
- * @param behaviors 指定所需的预设行为
- */
- public BehaviorsMap at(Type type, Behaviors behaviors) {
- this.map.put(type, behaviors);
- return this;
- }
- // 注册完后回退操作域到 BehaviorsTable
- public BehaviorsTable done() {
- return BehaviorsTable.getInstance();
- }
- // 获取指定类型的预设行为
- public Behaviors is(Type type) {
- Behaviors behaviors = this.map.get(type);
- if (behaviors == null) {
- // 如果没有注册, 那么使用 InvalidCharacter 预设行为, 因为出现了非预期的字符类型
- behaviors = Behaviors.InvalidCharacter;
- }
- return behaviors;
- }
- }
- BehaviorsTable.java
- // 行为表
- public class BehaviorsTable {
- private static volatile BehaviorsTable instance;
- public static BehaviorsTable getInstance() {
- if (BehaviorsTable.instance == null) {
- synchronized(BehaviorsTable.class) {
- if (BehaviorsTable.instance == null) {
- BehaviorsTable.instance = new BehaviorsTable();
- }
- }
- }
- return BehaviorsTable.instance;
- }
- private final HashMap < Type,
- BehaviorMap > map;
- public BehaviorsTable() {
- this.map = new HashMap < >();
- }
- // 注册指定当前类型, 返回一个空的 BehaviorsMap 来注册预设行为
- public BehaviorsMap register(Type type) {
- BehaviorsMap behaviorsMap = new BehaviorsMap();
- this.map.put(type, behaviorsMap);
- return behaviorsMap;
- }
- // 获取指定当前类型的 BehaviorsMap
- public BehaviorsMap get(Type type) {
- return this.map.get(type);
- }
- }
来源: https://segmentfault.com/a/1190000013236830