parse-regex 0.0.1

A recursive descent parser for regular expressions
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

pub type ParseResult = Result<RegEx, &'static str>;

#[derive(Eq, PartialEq, Debug)]
pub enum RegEx {
    Or(Box<RegEx>, Box<RegEx>),
    Sequence(Vec<Box<RegEx>>),
    Repetition(Box<RegEx>),
    Terminal(char),
}

pub struct RegExParser {
    s: String,
    pos: usize
}

impl RegExParser {
    pub fn new(s: String) -> RegExParser {
        RegExParser { s: s, pos: 0 }
    }

    pub fn parse(&mut self) -> ParseResult {
        self.regex()
    }

    fn regex(&mut self) -> ParseResult {
        let t1 = try!(self.term());
        if self.more() && self.peek() == '|' {
            self.consume('|').unwrap();
            let t2 = try!(self.term());
            Ok(RegEx::Or(Box::new(t1), Box::new(t2)))
        } else {
            Ok(t1)
        }
    }

    fn term(&mut self) -> ParseResult {
        let mut v = Vec::new();
        while self.more() && self.peek() != ')' && self.peek() != '|' {
            let f = try!(self.factor());
            v.push(Box::new(f));
        }
        Ok(RegEx::Sequence(v))
    }

    fn factor(&mut self) -> ParseResult {
        let b = try!(self.base());
        if self.more() && self.peek() == '*' {
            self.consume('*').unwrap();
            Ok(RegEx::Repetition(Box::new(b)))
        } else {
            Ok(b)
        }
    }

    fn base(&mut self) -> ParseResult {
        if self.peek() == '(' {
            self.consume('(').unwrap();
            let r = try!(self.regex());
            self.consume(')').unwrap();
            Ok(r)
        } else {
            Ok(RegEx::Terminal(self.next()))
        }
    }

    fn peek(&self) -> char {
        assert!(self.s.len() > self.pos);
        self.s.char_at(self.pos)
    }

    fn consume(&mut self, c: char) -> Result<(), String> {
        let p = self.peek();
        if p == c {
            self.pos += 1;
            Ok(())
        } else {
            Err(format!("Expected {} at position {} but got {}", c, self.pos, p))
        }
    }

    fn next(&mut self) -> char {
        let c = self.peek();
        self.consume(c).unwrap();
        c
    }

    fn more(&self) -> bool {
        self.s.len() > self.pos
    }
}

#[cfg(test)]
mod test {
    use parser::RegEx::{Or, Repetition, Sequence, Terminal};
    use parser::RegExParser;

    #[test]
    fn test_basic() {
        let mut p = RegExParser::new("".to_string());
        assert_eq!(p.parse(), Ok(Sequence(vec![])));

        let mut p = RegExParser::new("a".to_string());
        assert_eq!(p.parse(), Ok(Sequence(vec![Box::new(Terminal('a'))])));

        let mut p = RegExParser::new("a|b".to_string());
        assert_eq!(p.parse(), Ok(Or(Box::new(Sequence(vec![Box::new(Terminal('a'))])),
                                    Box::new(Sequence(vec![Box::new(Terminal('b'))])))));

        let mut p = RegExParser::new("a*".to_string());
        assert_eq!(p.parse(), Ok(Sequence(vec![Box::new(Repetition(Box::new(Terminal('a'))))])));

        let mut p = RegExParser::new("((a|b*)|a*)|aab".to_string());
        let res = Ok(Or(
            Box::new(Sequence(vec![Box::new(Or(
                Box::new(Sequence(
                    vec![Box::new(Or(Box::new(Sequence(vec![Box::new(Terminal('a'))])),
                                     Box::new(Sequence(
                                         vec![Box::new(Repetition(Box::new(Terminal('b'))))]))))])),
                Box::new(Sequence(vec![Box::new(Repetition(Box::new(Terminal('a'))))]))))])),
            Box::new(Sequence(vec![Box::new(Terminal('a')), Box::new(Terminal('a')),
                                   Box::new(Terminal('b'))]))));
        assert_eq!(p.parse(), res);
    }
}