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
122
123
124
125
126
127
128
129
|
package bjc.utils.parserutils;
import java.util.Deque;
import java.util.LinkedList;
import java.util.function.Function;
import java.util.function.Predicate;
import bjc.data.IHolder;
import bjc.data.IPair;
import bjc.data.ITree;
import bjc.data.Identity;
import bjc.data.Pair;
import bjc.funcdata.IList;
/**
* Creates a parse tree from a postfix expression.
*
* @author ben
*
*/
public class TreeConstructor {
/**
* Alias interface for special operator types.
*
* @param <TokenType>
* The token type of the tree.
*/
public interface QueueFlattener<TokenType>
extends Function<Deque<ITree<TokenType>>, ITree<TokenType>> {
/*
* Alias
*/
}
/* Alias for constructor state. */
static final class ConstructorState<TokenType>
extends Pair<Deque<ITree<TokenType>>, ITree<TokenType>> {
public ConstructorState(final Deque<ITree<TokenType>> left,
final ITree<TokenType> right) {
super(left, right);
}
public ConstructorState(
final IPair<Deque<ITree<TokenType>>, ITree<TokenType>> par) {
super(par.getLeft(), par.getRight());
}
}
/**
* Construct a tree from a list of tokens in postfix notation.
*
* Only binary operators are accepted.
*
* @param <TokenType>
* The elements of the parse tree.
*
* @param tokens
* The list of tokens to build a tree from.
*
* @param isOperator
* The predicate to use to determine if something is a
* operator.
*
* @return A AST from the expression.
*/
public static <TokenType> ITree<TokenType> constructTree(
final IList<TokenType> tokens, final Predicate<TokenType> isOperator) {
/* Construct a tree with no special operators */
return constructTree(tokens, isOperator, op -> false, null);
}
/**
* Construct a tree from a list of tokens in postfix notation.
*
* Only binary operators are accepted by default. Use the last two parameters to
* handle non-binary operators.
*
* @param <TokenType>
* The elements of the parse tree.
*
* @param tokens
* The list of tokens to build a tree from.
*
* @param isOperator
* The predicate to use to determine if something
* is a operator.
*
* @param isSpecialOperator
* The predicate to use to determine if an operator
* needs special handling.
*
* @param handleSpecialOperator
* The function to use to handle special case
* operators.
*
* @return A AST from the expression.
*
*/
public static <TokenType> ITree<TokenType> constructTree(
final IList<TokenType> tokens, final Predicate<TokenType> isOperator,
final Predicate<TokenType> isSpecialOperator,
final Function<TokenType, QueueFlattener<TokenType>> handleSpecialOperator) {
/*
* Make sure our parameters are valid
*/
if (tokens == null)
throw new NullPointerException("Tokens must not be null");
else if (isOperator == null)
throw new NullPointerException("Operator predicate must not be null");
else if (isSpecialOperator == null)
throw new NullPointerException(
"Special operator determiner must not be null");
final ConstructorState<TokenType> cstate
= new ConstructorState<>(new LinkedList<>(), null);
/* Here is the state for the tree construction */
final IHolder<ConstructorState<TokenType>> initialState = new Identity<>(cstate);
/* Transform each of the tokens */
final TokenTransformer<TokenType> trans = new TokenTransformer<>(initialState,
isOperator, isSpecialOperator, handleSpecialOperator);
tokens.forEach(trans);
/* Grab the tree from the state */
return initialState.unwrap(ConstructorState::getRight);
}
}
|
