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
use crate::earley_parse::{CFG, ASTNode, nt, tr};
fn regex_cfg() -> CFG{
let mut g = CFG::new("UNION");
// union
g.add_rule("UNION", vec![nt("UNION"), tr('|'), nt("CONCAT")]);
g.add_rule("UNION", vec![nt("CONCAT")]);
// concatenation
g.add_rule("CONCAT", vec![nt("CONCAT"), nt("Q")]);
g.add_rule("CONCAT", vec![nt("Q")]);
// one or zero
g.add_rule("Q", vec![nt("PLUS"), tr('?')]);
g.add_rule("Q", vec![nt("PLUS")]);
// one or more
g.add_rule("PLUS", vec![nt("STAR"), tr('+')]);
g.add_rule("PLUS", vec![nt("STAR")]);
// zero or more
g.add_rule("STAR", vec![nt("EXPR"), tr('*')]);
g.add_rule("STAR", vec![nt("EXPR")]);
// parenthesis
g.add_rule("EXPR", vec![tr('('), nt("UNION"), tr(')')]);
g.add_rule("EXPR", vec![nt("CHAR")]);
// literals
g.add_rule("CHAR", vec![nt("DIGIT")]);
g.add_rule("CHAR", vec![nt("LETTER")]);
g.add_rule("CHAR", vec![nt("WHITESPACE")]);
g.add_rule("CHAR", vec![nt("NON-DIGIT")]);
g.add_rule("CHAR", vec![nt("NON-LETTER")]);
g.add_rule("CHAR", vec![nt("NON-WHITESPACE")]);
g.add_rule("CHAR", vec![nt("SPECIAL")]);
g.add_rule("CHAR", vec![nt("LITERAL-DOT")]);
g.add_rule("CHAR", vec![tr('.')]);
for c in ' '..='~' {
match c {
| '|' | '*' | '(' | ')' | '+' | '?' | '\\' =>
g.add_rule("SPECIAL", vec![tr('\\'), tr(c)]),
| '.' =>
g.add_rule("LITERAL-DOT", vec![tr('\\'), tr(c)]),
| _ =>
g.add_rule("CHAR", vec![tr(c)])
};
}
g.add_rule("CHAR", vec![tr('\t')]);
// any digit, letter, or whitespace literal
g.add_rule("DIGIT", vec![tr('\\'), tr('d')]);
g.add_rule("LETTER", vec![tr('\\'), tr('s')]);
g.add_rule("WHITESPACE", vec![tr('\\'), tr('w')]);
// negations of the above
g.add_rule("NON-DIGIT", vec![tr('\\'), tr('D')]);
g.add_rule("NON-LETTER", vec![tr('\\'), tr('S')]);
g.add_rule("NON-WHITESPACE", vec![tr('\\'), tr('W')]);
return g;
}
pub fn parse_regex(regex: &str) -> Option<ASTNode> {
let g: CFG = regex_cfg();
return g.parse(regex);
}