Mercurial > hg > Applications > Grep

annotate c/regexParser/regexParser.cc @ 143:32977f5a2ed0 pairPro

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add charClassMerge
author masa
date Fri, 11 Dec 2015 15:04:58 +0900
parents de0f332d560c
children d8a4922eceae
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 #include <stdlib.h>
89
50a146c05192 add NodeNumber in Regex Parser tree
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
2 #include <stdio.h>
122
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 121
diff changeset
3 #include <string.h>
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 121
diff changeset
4 #include <ctype.h>
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 #include "regexParser.h"
115
ca30f8334741 rename createRegexParser.cc to regexParser.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 112
diff changeset
6 #include "error.h"
ca30f8334741 rename createRegexParser.cc to regexParser.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 112
diff changeset
7
112
ec485345daf9 some function use static
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 108
diff changeset
8 static NodePtr charClass(RegexInfoPtr);
ec485345daf9 some function use static
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 108
diff changeset
9 static void token(RegexInfoPtr);
ec485345daf9 some function use static
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 108
diff changeset
10 static NodePtr regexAtom(RegexInfoPtr);
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 NodePtr regex(RegexInfoPtr);
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 /**
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 * Create a node of regex parse tree.
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 * tokenType
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 * regexPosition(state)
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 * stateTransitionTable
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 */
112
ec485345daf9 some function use static
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 108
diff changeset
19
118
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 116
diff changeset
20 static
116
66c633575b53 remove error and warning
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 115
diff changeset
21 NodePtr allocateNode() {
129
b930be74a16e remove word.h
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 128
diff changeset
22 NodePtr n = NEW(Node);
125
4d6ac69801ad fix createNode
Nozomi
parents: 122
diff changeset
23 n->cc = NULL;
4d6ac69801ad fix createNode
Nozomi
parents: 122
diff changeset
24 n->left = NULL;
4d6ac69801ad fix createNode
Nozomi
parents: 122
diff changeset
25 n->right = NULL;
116
66c633575b53 remove error and warning
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 115
diff changeset
26 return n;
66c633575b53 remove error and warning
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 115
diff changeset
27 }
66c633575b53 remove error and warning
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 115
diff changeset
28
112
ec485345daf9 some function use static
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 108
diff changeset
29 static
126
639b0b437ebf remove error (do not work)
masa
parents: 125
diff changeset
30 CharClassPtr createCharClassWord(RegexInfoPtr ri) {
125
4d6ac69801ad fix createNode
Nozomi
parents: 122
diff changeset
31 CharClassPtr cc = NEW(CharClass);
4d6ac69801ad fix createNode
Nozomi
parents: 122
diff changeset
32 cc->type = 'a';
142
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
33 cc->cond.w.word = ri->tokenValue;
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
34 cc->cond.w.length = ri->ptr - ri->tokenValue;
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
35 cc->nextState.bitContainer = 0;
134
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
36 token(ri);
126
639b0b437ebf remove error (do not work)
masa
parents: 125
diff changeset
37
639b0b437ebf remove error (do not work)
masa
parents: 125
diff changeset
38 return cc;
125
4d6ac69801ad fix createNode
Nozomi
parents: 122
diff changeset
39 }
4d6ac69801ad fix createNode
Nozomi
parents: 122
diff changeset
40
4d6ac69801ad fix createNode
Nozomi
parents: 122
diff changeset
41 static
134
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
42 NodePtr createNode(RegexInfoPtr ri,unsigned char type,CharClassPtr cc, NodePtr left, NodePtr right) {
116
66c633575b53 remove error and warning
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 115
diff changeset
43 NodePtr n = allocateNode();
108
70069d4647a0 implement malloc error checking
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 104
diff changeset
44
125
4d6ac69801ad fix createNode
Nozomi
parents: 122
diff changeset
45 n->tokenType = type;
134
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
46 n->cc = cc;
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 n->left = left;
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 n->right = right;
120
5d29b6a1b50f include Word in Node
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 118
diff changeset
49 n->nodeNumber = ri->nodeNumber;
5d29b6a1b50f include Word in Node
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 118
diff changeset
50 ri->nodeNumber++;
89
50a146c05192 add NodeNumber in Regex Parser tree
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
51
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 return n;
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 }
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
54
143
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
55 CharClassPtr charClassMerge(CharClassPtr cc, unsigned char begin, unsigned char end, CharClassPtr next) {
142
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
56 if (src->type == 'a') {
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
57 if (add->type == 'a') {
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
58 if (src->cond.w.word[0] > add->cond.w.word[0]) {
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
59 // add のほうが小さいので小さい順のccをつくる
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
60 CharClassPtr left = charClassMerge(add->left.src);
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
61 return createCharClassWord(add->cond->w.word, left, add->right);
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
62 } else {
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
63
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
64 }
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
65 } else if (add->type == 'c') {
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
66 //
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
67 if (src->cond.w.word[0] < add->cond.range.begin) {
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
68
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
69 } else (src->cond->w.word[0] < add->end) {
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
70 } else if (src->type == 'c') {
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
71
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
72 }
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
73 }
125
4d6ac69801ad fix createNode
Nozomi
parents: 122
diff changeset
74
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 // <charClass> ::= '['<literal>'-'<literal>']'
112
ec485345daf9 some function use static
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 108
diff changeset
76 static
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 NodePtr charClass(RegexInfoPtr ri) {
125
4d6ac69801ad fix createNode
Nozomi
parents: 122
diff changeset
78 CharClassPtr cc = NEW(CharClass);
135
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
79 NodePtr n = createNode(ri,'c',cc,0,0);
126
639b0b437ebf remove error (do not work)
masa
parents: 125
diff changeset
80 cc->type = 'r';
142
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
81 cc->nextState.bitContainer = 0;
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
82 RangeListPtr rangeList = &cc->cond.range;
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
83 rangeList->begin = ri->ptr;
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
84 rangeList->end = ri->ptr;
130
7925e9abb078 add or flag
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 129
diff changeset
85
135
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
86 for (ri->ptr++; *ri->ptr && *ri->ptr != ']'; ri->ptr++) {
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
87 if (*ri->ptr == '-') {
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
88 rangeList->end = ri->ptr + 1;
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
89 ri->ptr++;
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
90 continue;
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
91 }
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
92 if (ri->ptr[0] == 0 || ri->ptr[0] == ']') break;
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
93 if (ri->ptr[0] == rangeList->end[0] + 1) {
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
94 rangeList->end = ri->ptr;
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
95 continue;
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
96 }
126
639b0b437ebf remove error (do not work)
masa
parents: 125
diff changeset
97 rangeList->next = NEW(RangeList);
125
4d6ac69801ad fix createNode
Nozomi
parents: 122
diff changeset
98 rangeList = rangeList->next;
135
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
99 rangeList->begin = ri->ptr;
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
100 rangeList->end = ri->ptr;
125
4d6ac69801ad fix createNode
Nozomi
parents: 122
diff changeset
101 rangeList->next = NULL;
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 }
142
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
103 // TODO literal support
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
104 // merge rangeList here
135
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
105 if (*ri->ptr) ri->ptr++;
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
106 token(ri);
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 return n;
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 }
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
109
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
110 // <literal> ::= [a-z][A-Z][0-9]
112
ec485345daf9 some function use static
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 108
diff changeset
111 static
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 NodePtr literal(RegexInfoPtr ri) {
134
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
113 CharClassPtr cc = createCharClassWord(ri);
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
114 NodePtr n = createNode(ri,'a',cc,0,0);
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
115 return n;
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
116 }
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
117
133
ccc673449351 Look ahead '*'
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 132
diff changeset
118 static
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 void token(RegexInfoPtr ri) {
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
120 while (ri->ptr[0] != '\0') {
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
121 if (ri->ptr[0] == '('){
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
122 ri->ptr++;
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
123 ri->tokenType = '(';
118
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 116
diff changeset
124 ri->tokenValue = NULL;
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
125 return;
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
126 } else if (ri->ptr[0] == ')') {
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 ri->ptr++;
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 ri->tokenType = ')';
118
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 116
diff changeset
129 ri->tokenValue = ri->ptr;
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
130 return;
135
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
131 } else if (ri->ptr[0] == ']') {
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
132 ri->ptr++;
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
133 ri->tokenType = ']';
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
134 ri->tokenValue = ri->ptr;
e1a262ec75f0 impl charclass
masa
parents: 134
diff changeset
135 return;
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
136 } else if (ri->ptr[0] == '|'){
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
137 ri->ptr++;
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
138 ri->tokenType = '|';
118
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 116
diff changeset
139 ri->tokenValue = NULL;
133
ccc673449351 Look ahead '*'
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 132
diff changeset
140 ri->orNum++;
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
141 return;
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
142 } else if (ri->ptr[0] == '*'){
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
143 ri->ptr++;
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
144 ri->tokenType = '*';
118
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 116
diff changeset
145 ri->tokenValue = NULL;
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
146 return;
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
147 } else if (ri->ptr[0] == '\\'){
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
148 // need more proccesing
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
149 /*
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
150 \277
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
151 \0xa5
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
152 \[
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
153 \\
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
154 \utf-8 etc...
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
155 */
142
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
156 } else if (ri->ptr[0] == '[') {
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
157 ri->ptr++;
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
158 ri->tokenType = 'c';
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
159 ri->tokenValue = ri->ptr;
de0f332d560c insert charClassMerge function
masa
parents: 136
diff changeset
160 return;
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
161 } else {
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
162 ri->tokenType = 'a';
118
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 116
diff changeset
163 ri->tokenValue = ri->ptr;
134
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
164 if (isalnum(ri->ptr[0])) {
122
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 121
diff changeset
165 ri->ptr++;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 121
diff changeset
166 }
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
167 return;
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
168 }
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
169 }
134
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
170 ri->tokenType = 0;
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
171 ri->tokenValue = NULL;
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
172 return;
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
173 }
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
174
130
7925e9abb078 add or flag
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 129
diff changeset
175 // <regexAtom> ::= <literal>|<charClass>|<group>
112
ec485345daf9 some function use static
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 108
diff changeset
176 static
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
177 NodePtr regexAtom(RegexInfoPtr ri) {
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
178
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
179 NodePtr n = NULL;
124
masa
parents: 122
diff changeset
180 if (ri->tokenType == 'c') n = charClass(ri);
134
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
181 else if (ri->tokenType == 'a') n = literal(ri);
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
182 else if (ri->tokenType == '(') {
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
183 n = regex(ri);
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
184 if (ri->tokenType != ')') {
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
185 // error
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
186 }
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
187 token(ri);
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
188 }
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
189 if (ri->tokenType == '*') {
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
190 n = createNode(ri,'*',0,n,0);
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
191 token(ri);
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
192 }
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
193
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
194 return n;
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
195 }
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
196
133
ccc673449351 Look ahead '*'
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 132
diff changeset
197 // <regex> ::= <regexAtom> | <regexAtom>'*'<regex> | <regexAtom>'|'<regex> | <regexAtom><regexAtom>'*' | <regexAtom><regex>
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
198 NodePtr regex(RegexInfoPtr ri) {
134
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
199 token(ri);
128
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 127
diff changeset
200 NodePtr n = regexAtom(ri);
134
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
201 while (ri->tokenType) {
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
202 if (ri->tokenType == '*') {
134
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
203 n = createNode(ri,'*',0,n,0);
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
204 token(ri);
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
205 return n;
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
206 } else if (ri->tokenType == '|') {
134
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
207 n = createNode(ri,'|',0,n,0);
133
ccc673449351 Look ahead '*'
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 132
diff changeset
208 NodePtr n1 = regex(ri);
134
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
209 n->right = n1;
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
210 } else if (ri->tokenType == ')') {
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
211 return n;
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
212 } else {
134
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
213 n = createNode(ri,'+',0,n,0);
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
214 NodePtr n1 = regexAtom(ri);
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
215 n->right = n1;
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
216 }
134
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
217 }
dbafc753078e fix concatination & selection & grouping
masa
parents: 133
diff changeset
218 return n;
82
1d9bbf922bb6 add createRegexTree.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
219 }