手写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
参考资料