myregexp/parser.cpp at master · kohn/myregexp · GitHub

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
#include "Parser.h"
#include "ParseTreeNode.h"
#include <stack>
#include <string>
#include <assert.h>
#include <list>


ParseTreeNode* Parser::parse(std::string s){
    int len = s.length();
    return parse_whole_tree(s, 0, len, len);
}

ParseTreeNode* Parser::parse_whole_tree(std::string s, int start, int end, int &new_pos){
    int pos = end;
    ParseTreeNode* last_node = NULL;
    last_node = parse_one_node(s, start, pos, pos);
    while(pos>start){
        switch (get_next_op(s, pos)) {
            case CAT: {
                last_node = new CatNode(parse_one_node(s, start, pos, pos), last_node);
                break;
            }
            case UNION: {
                last_node = new UnionNode(parse_whole_tree(s, start, pos, pos), last_node);
                break;
            }
        }
    }
    new_pos = start;
    return last_node;
}

ParseTreeNode* Parser::parse_one_node(std::string s, int start, int end, int &new_pos){
    int pos = end;

    if(pos <= start)
        return NULL;

    switch (s[pos-1]) {
    case '*': {
        ParseTreeNode* new_node = new StarNode(parse_one_node(s, start, pos-1, pos));
        new_pos = pos;
        return new_node;
    }
    case '?': {
        ParseTreeNode* new_node = new ExistNode(parse_one_node(s, start, pos-1, pos));
        new_pos = pos;
        return new_node;
    }
    case '.': {
        ParseTreeNode* new_node = new DotNode();
        new_pos = pos-1;
        return new_node;
    }
    case '+': { // a+ => aa*
        ParseTreeNode* next_node = parse_one_node(s, start, pos-1, pos);
        ParseTreeNode* star_node = new StarNode(next_node);
        ParseTreeNode* cat_node = new CatNode(next_node, star_node);
        new_pos = pos;
        return cat_node;
    }
    case ')': {
        // find corresponding(the outmost) '('
        int i;
        for(i=start; i<end; i++){
            if(s[i] == '(')
                break;
        }

        // parenthesis mismatch
        if(i == end)
            return NULL;

        new_pos = i;
        return parse_whole_tree(s, i+1, end-1, pos);
    }
    case '(': {
        // parenthesis mismatch
        return NULL;
    }
    case ']': {
        int i;
        // find the outmost '['
        for(i=start; i<end; i++){
            if(s[i] == '[')
                break;
        }

        if(i == end)
            return NULL;

        new_pos = i;
        return parse_bracket_node(s, i+1, end-1);
    }
    case '[': {
        // bracket mismatch
        return NULL;
    }
    default:{
        // characters cases
        new_pos = pos - 1;
        return new CharNode(s[pos-1]);
    }
    }
}

ParseTreeNode* Parser::parse_bracket_node(std::string s, int start, int end){
    if(start >= end)
        return NULL;

    ParseTreeNode* root = new CharNode(s[end-1]);
    for(int i=end-2; i>=start; i--){
        ParseTreeNode* char_node = new CharNode(s[i]);
        root = new UnionNode(char_node, root);
    }
    return root;
}


OP Parser::get_next_op(std::string s, int &pos){
    if(s[pos-1] == '|'){
        pos = pos-1;
        return UNION;
    }
    else
        return CAT;
}