/
RegexInterpreter.java
153 lines (135 loc) · 5.55 KB
/
RegexInterpreter.java
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
package com.github.kmizu.jcombinator.showcase.regex;
import com.github.kmizu.jcombinator.ParseResult;
import com.github.kmizu.jcombinator.datatype.Function0;
import com.github.kmizu.jcombinator.datatype.Function1;
public class RegexInterpreter {
interface SuccessfullContinuation extends Function0<Boolean> {}
private static class ExpressionRewriter implements AstNode.RVisitor<AstNode.RExpression, Void> {
@Override
public AstNode.RExpression visitRGrouped(AstNode.RGrouped node, Void context) {
return new AstNode.RGrouped(node.getTarget().accept(this, context));
}
@Override
public AstNode.RExpression visitRString(AstNode.RString node, Void context) {
return node;
}
@Override
public AstNode.RExpression visitRAny(AstNode.RAny node, Void context) {
return node;
}
@Override
public AstNode.RExpression visitRChoice(AstNode.RChoice node, Void context) {
return new AstNode.RChoice(
node.getLhs().accept(this, context),
node.getRhs().accept(this, context)
);
}
@Override
public AstNode.RExpression visitRSequence(AstNode.RSequence node, Void context) {
return new AstNode.RSequence(
node.getLhs().accept(this, context),
node.getRhs().accept(this, context)
);
}
@Override
public AstNode.RExpression visitRRepeat0(AstNode.RRepeat0 node, Void context) {
return new AstNode.RRepeat0(
node.getTarget().accept(this, context)
);
}
@Override
public AstNode.RExpression visitRRepeat1(AstNode.RRepeat1 node, Void context) {
AstNode.RExpression target = node.getTarget().accept(this, context);
return new AstNode.RSequence(
target,
new AstNode.RRepeat0(target)
);
}
}
private static class ExpressionInterpreter implements AstNode.RVisitor<Boolean, SuccessfullContinuation> {
private String input;
private int cursor;
public ExpressionInterpreter(String input) {
this.input = input;
this.cursor = cursor;
}
@Override
public Boolean visitRGrouped(AstNode.RGrouped node, SuccessfullContinuation context) {
return node.getTarget().accept(this, context);
}
@Override
public Boolean visitRString(AstNode.RString node, SuccessfullContinuation context) {
String slice = input.substring(cursor);
if(slice.startsWith(node.getLiteral())) {
cursor += node.getLiteral().length();
return context.invoke();
} else {
return false;
}
}
@Override
public Boolean visitRAny(AstNode.RAny node, SuccessfullContinuation context) {
String slice = input.substring(cursor);
if(slice.length() > 0) {
cursor++;
return context.invoke();
} else {
return false;
}
}
@Override
public Boolean visitRChoice(AstNode.RChoice node, SuccessfullContinuation context) {
final int start = cursor;
boolean lhsMatched = node.getLhs().accept(this, context);
if(lhsMatched) {
return true;
} else {
cursor = start;
return node.getRhs().accept(this, context);
}
}
@Override
public Boolean visitRSequence(AstNode.RSequence node, SuccessfullContinuation context) {
return node.getLhs().accept(this, () ->
node.getRhs().accept(this, context)
);
}
@Override
public Boolean visitRRepeat0(AstNode.RRepeat0 node, SuccessfullContinuation context) {
Function1<Function0<Boolean>, Boolean>[] onSuccessRep = new Function1[1];
onSuccessRep[0] = (f) -> {
final int start = cursor;
final SuccessfullContinuation nf = () -> {
cursor = start;
return context.invoke() ? true : f.invoke();
};
return (node.getTarget().accept(
this,
() -> onSuccessRep[0].invoke(nf)
) ? true : nf.invoke());
};
return onSuccessRep[0].invoke(context);
}
@Override
public Boolean visitRRepeat1(AstNode.RRepeat1 node, SuccessfullContinuation context) {
throw new UnsupportedOperationException("ExpressionInterpreter#visit(AstNode.RRepeat1, SuccessfullContinuation)");
}
}
public boolean matches(String regex, String input) {
ParseResult<AstNode.RExpression> result = new RegexParser().expression().invoke(regex);
boolean[] matchResult = new boolean[1];
matchResult[0] = false;
result.onSuccess(e -> {
ExpressionRewriter rewriter = new ExpressionRewriter();
AstNode.RExpression newE = e.value().accept(rewriter, null);
ExpressionInterpreter interpreter = new ExpressionInterpreter(input);
matchResult[0] = newE.accept(interpreter, () -> true);
});
return matchResult[0];
}
public static void main(String[] args) {
RegexInterpreter i = new RegexInterpreter();
System.out.println(i.matches("a*aaa", "aaa"));
System.out.println(i.matches("(a*|xxx)y(bca)*(x|y)d", "xxxybcabcaxd"));
}
}