手写Parser-Pratt Parser
解析是编译器将一系列标记转换为树表示的过程:
1 2 3 4 5
| Add Parser / \ "1 + 2 * 3" -------> 1 Mul / \ 2 3
|
Pratt Parser解析是手写解析最常用的技术之一。
优先级
如果我们给operator的设置优先级值。
对于不同级别的operator,因为*
的值更高,所以更倾向于把B和C保持在一起。表达式被解析为 A + (B * C)
。
1 2
| expr: A + B * C power: 3 3 5 5
|
如果表达式相同。我们可以调高 operator右边的power。
1 2
| expr: A + B + C power: 3 4 3 4
|
我们还可以在两端添加了零,因为没有运算符可以从两侧绑定
1 2
| expr: A + B + C power: 0 3 4 3 4 0
|
就语法树而言,第二个+更喜欢它的右边操作数,所以它倾向于抓住C。 当他这样做的时候,第一个+捕获了A和B,
1 2
| expr: (A + B) + C power: 0 3 4 0
|
构建 Pratt Parser
我们将解析基本原子是单字符数字的表达式,并使用标点符号表示运算符。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| public class Token { public static Token EOF = new Token(Type.EOF,(char)0); public Type type; public Character text;
public Token(Type type, Character text) { this.type = type; this.text = text; }
public boolean notEOF(){ return type != Type.EOF; }
@Override public String toString() { return "Token{" + "type=" + type + ", text=" + text + '}'; }
public static enum Type{ Atom,Operator,EOF } }
|
表达式的树结构定义如下,Expr分为Value和Composite两种类型。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| public class Expr { public Type type; public Expr[] exprs; public Character text; private Expr() { } public static Expr composite(Character text,Expr... exprs) { Expr expr = new Expr(); expr.type = Type.Composite; expr.exprs = exprs; expr.text = text; return expr; } public static Expr value(Character text) { Expr expr = new Expr(); expr.type = Type.Value; expr.text = text; return expr; }
@Override public String toString() { if(type.equals(Type.Value)){ return text.toString(); }else { StringBuilder sb = new StringBuilder(); sb.append("(").append(text); for (Expr expr: exprs) { sb.append(" ").append(expr.toString()); } sb.append(")"); return sb.toString(); } }
public static enum Type{ Value,Composite } }
|
通过lexer我们可以将字符串转为Token Stream。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| public class Lexer { LinkedList<Token> tokenList;
public Lexer(String expr) { tokenList = expr.codePoints().mapToObj(c -> (char) c) .filter(x -> !Character.isWhitespace(x)) .map(x -> { if ("0123456789".indexOf(x) != -1) { return new Token(Token.Type.Atom, x); } else { return new Token(Token.Type.Operator, x); } }) .collect(LinkedList::new, LinkedList::add, LinkedList::addAll); tokenList.add(Token.EOF); }
public Token next() { return tokenList.pop(); }
public Token peek() { return tokenList.peek(); } }
|
接下来,我们使用parser将Token stream转化为Expr。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
| public class Parser { private Lexer lexer; public Parser(Lexer lexer) { this.lexer = lexer; } public Expr expr(int min_bp) { Expr lhs = exprFirst(); Token token = null; while ((token = lexer.peek()).notEOF()) { if (token.type == Token.Type.Operator) { Pair<Integer, Integer> pair = infix_binding_power(token); if(pair == null){ throw new RuntimeException("unexpected token"+token); } if (pair.getLeft() < min_bp) { break; } lexer.next(); Expr rhs = expr(pair.getRight()); lhs = Expr.composite(token.text,lhs,rhs); } else { throw new RuntimeException("unexpected token"); } } return lhs; } private Expr exprFirst() { Expr expr = null; Token token = lexer.next(); if (token.type.equals(Token.Type.Atom)) { expr = Expr.value(token.text); } else { throw new RuntimeException("unexpected token"); } return expr; } static Map<Character, Pair<Integer, Integer>> infixBindingMap = new HashMap<>(); static { infixBindingMap.put('+', Pair.of(3, 4)); infixBindingMap.put('-', Pair.of(3, 4)); infixBindingMap.put('*', Pair.of(5, 6)); infixBindingMap.put('/', Pair.of(5, 6)); } private Pair<Integer, Integer> infix_binding_power(Token token) { Character op = token.text; return infixBindingMap.get(op); } }
|
测试一下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class ParserTest { @Test void testParser01(){ Parser parser = new Parser(new Lexer("1")); Assertions.assertEquals("1",parser.expr(0).toString()); } @Test void testParser02(){ Parser parser = new Parser(new Lexer("1 + 2 * 3 ")); Assertions.assertEquals("(+ 1 (* 2 3))",parser.expr(0).toString()); } @Test void testParser03(){ Parser parser = new Parser(new Lexer("1 + 2 * 3 * 4 + 5 ")); Assertions.assertEquals("(+ (+ 1 (* (* 2 3) 4)) 5)",parser.expr(0).toString()); } }
|
扩展Parser
右结合的operator
我们在二元operator中增加一个右结合的操作符=
。
1
| infixBindingMap.put('=', Pair.of(2, 1));
|
注意,运算符更倾向左侧,从而实现右结合。
1 2 3 4 5
| @Test void testParser04(){ Parser parser = new Parser(new Lexer("5 = 1 * 2 + 3 ")); Assertions.assertEquals("(= 5 (+ (* 1 2) 3))",parser.expr(0).toString()); }
|
一元operator
我们在operator中增加2个一元操作符+
,-
。
1 2 3 4 5 6 7 8 9 10 11 12
| static Map<Character, Pair<Integer, Integer>> prefixBindingMap = new HashMap<>(); static { prefixBindingMap.put('+', Pair.of(null, 7)); prefixBindingMap.put('-', Pair.of(null, 7)); }
private Pair<Integer, Integer> prefix_binding_power(Token token) { Character op = token.text; return prefixBindingMap.get(op); }
|
因为第一个Token可能是Atom或是一元操作符,修改exprFirst,增加一元操作符的处理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| private Expr exprFirst() { Expr expr = null; Token token = lexer.next(); if (token.type.equals(Token.Type.Atom)) { expr = Expr.value(token.text); } else if (token.type.equals(Token.Type.Operator)){ Pair<Integer,Integer> pair = prefix_binding_power(token); if(pair == null){ throw new RuntimeException("unexpected token"+token); } Expr rhs = expr(pair.getRight()); expr = Expr.composite(token.text,rhs); } else { throw new RuntimeException("unexpected token"+token); } return expr; }
|
后缀操作符
接下我们添加后缀一元操作符!
.先设置后缀操作符的优先级,这里后缀操作符的优先级高于前缀操作符。
1 2 3 4 5 6 7 8
| static Map<Character, Pair<Integer, Integer>> postfixBindingMap = new HashMap<>(); static { postfixBindingMap.put('!', Pair.of(9, null)); } private Pair<Integer, Integer> postfix_binding_power(Token token) { Character op = token.text; return postfixBindingMap.get(op); }
|
接下来添加优先级处理逻辑:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| public Expr expr(int min_bp) { Expr lhs = exprFirst(); Token token = null; while ((token = lexer.peek()).notEOF()) { if (token.type == Token.Type.Operator) { Pair<Integer,Integer> post= postfix_binding_power(token); if(post !=null){ if (post.getLeft() < min_bp) { break; } lexer.next(); lhs = Expr.composite(token.text, lhs); continue; } Pair<Integer, Integer> pair = infix_binding_power(token); if(pair == null){ throw new RuntimeException("unexpected token"+token); } if (pair.getLeft() < min_bp) { break; } lexer.next(); Expr rhs = expr(pair.getRight()); lhs = Expr.composite(token.text,lhs,rhs); } else { throw new RuntimeException("unexpected token:"+token); } } return lhs; }
|
括号表达式
在Parser中添加对"()"的处理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| private Expr exprFirst() { Expr expr = null; Token token = lexer.next(); if (token.type.equals(Token.Type.Atom)) { expr = Expr.value(token.text); } else if (token.type.equals(Token.Type.Operator)){ if(token.text.equals('(')){ expr = expr(0); Token rBracket = lexer.next(); Preconditions.checkArgument(rBracket.text.equals(')') && rBracket.type.equals(Token.Type.Operator)); return expr; } Pair<Integer,Integer> pair = prefix_binding_power(token); if(pair == null){ throw new RuntimeException("unexpected token"+token); } Expr rhs = expr(pair.getRight()); expr = Expr.composite(token.text,rhs); } else { throw new RuntimeException("unexpected token"+token); } return expr; } public Expr expr(int min_bp) { Expr lhs = exprFirst(); Token token = null; while ((token = lexer.peek()).notEOF()) { if (token.type == Token.Type.Operator) { Pair<Integer,Integer> post= postfix_binding_power(token); if(post !=null){ if (post.getLeft() < min_bp) { break; } lexer.next(); lhs = Expr.composite(token.text, lhs); continue; } Pair<Integer, Integer> pair = infix_binding_power(token); if(pair != null){ if (pair.getLeft() < min_bp) { break; } lexer.next(); Expr rhs = expr(pair.getRight()); lhs = Expr.composite(token.text,lhs,rhs); continue; } break;
} else { throw new RuntimeException("unexpected token:"+token); } } return lhs; }
|
其他
其他还可以支持的规则有:
本文代码见: github
参考资料