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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
package bjc.utils.parserutils.pratt;
import bjc.utils.data.ITree;
import bjc.utils.funcutils.NumberUtils;
import bjc.utils.parserutils.ParserException;
import java.util.HashMap;
import java.util.Map;
/**
* A configurable Pratt parser for expressions.
*
* @author EVE
*
* @param <K>
* The key type for the tokens.
*
* @param <V>
* The value type for the tokens.
*
* @param <C>
* The state type of the parser.
*
*
*/
public class PrattParser<K, V, C> {
private final LeftCommand<K, V, C> DEFAULT_LEFT_COMMAND = new DefaultLeftCommand<>();
private final NullCommand<K, V, C> DEFAULT_NULL_COMMAND = new DefaultNullCommand<>();
private Map<K, LeftCommand<K, V, C>> leftCommands;
private Map<K, NullCommand<K, V, C>> nullCommands;
/**
* Create a new Pratt parser.
*
* @param terminal
* The terminal symbol.
*/
public PrattParser() {
leftCommands = new HashMap<>();
nullCommands = new HashMap<>();
}
/**
* Parse an expression.
*
* @param precedence
* The initial precedence for the expression.
*
* @param tokens
* The tokens for the expression.
*
* @param state
* The state of the parser.
*
* @return The expression as an AST.
*
* @throws ParserException
* If something goes wrong during parsing.
*/
public ITree<Token<K, V>> parseExpression(int precedence, TokenStream<K, V> tokens, C state)
throws ParserException {
if(precedence < 0) {
throw new IllegalArgumentException("Precedence must be greater than zero");
}
Token<K, V> initToken = tokens.current();
tokens.next();
ITree<Token<K, V>> ast = nullCommands.getOrDefault(initToken.getKey(), DEFAULT_NULL_COMMAND)
.nullDenotation(initToken, new ParserContext<>(tokens, this, state));
int rightPrec = Integer.MAX_VALUE;
while(true) {
Token<K, V> tok = tokens.current();
K key = tok.getKey();
LeftCommand<K, V, C> command = leftCommands.getOrDefault(key, DEFAULT_LEFT_COMMAND);
int leftBind = command.leftBinding();
if(NumberUtils.between(precedence, rightPrec, leftBind)) {
tokens.next();
ast = command.leftDenote(ast, tok, new ParserContext<>(tokens, this, state));
rightPrec = command.nextBinding();
} else {
break;
}
}
return ast;
}
/**
* Add a non-initial command to this parser.
*
* @param marker
* The key that marks the command.
*
* @param comm
* The command.
*/
public void addNonInitialCommand(K marker, LeftCommand<K, V, C> comm) {
leftCommands.put(marker, comm);
}
/**
* Add a initial command to this parser.
*
* @param marker
* The key that marks the command.
*
* @param comm
* The command.
*/
public void addInitialCommand(K marker, NullCommand<K, V, C> comm) {
nullCommands.put(marker, comm);
}
}
|
