Mercurial > hg > Applications > Grep

comparison c/regexParser/createRegexTree.cc @ 89:50a146c05192

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add NodeNumber in Regex Parser tree
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Fri, 23 Oct 2015 17:20:54 +0900
parents aef2546cd130
children 912d7bd51f38
comparison
equal deleted inserted replaced
88:7809fb223dc9 89:50a146c05192
1 #include <stdlib.h> 1 #include <stdlib.h>
2 #include <stdio.h>
2 #include "regexParser.h" 3 #include "regexParser.h"
3 4
4 NodePtr createNode(unsigned char,NodePtr,NodePtr); 5 NodePtr createNode(RegexInfoPtr,unsigned char,NodePtr,NodePtr);
5 NodePtr charClass(RegexInfoPtr); 6 NodePtr charClass(RegexInfoPtr);
6 NodePtr group(RegexInfoPtr); 7 NodePtr group(RegexInfoPtr);
7 void token(RegexInfoPtr); 8 void token(RegexInfoPtr);
8 NodePtr regexAtom(RegexInfoPtr); 9 NodePtr regexAtom(RegexInfoPtr);
9 NodePtr regex(RegexInfoPtr); 10 NodePtr regex(RegexInfoPtr);
12 * Create a node of regex parse tree. 13 * Create a node of regex parse tree.
13 * tokenType 14 * tokenType
14 * regexPosition(state) 15 * regexPosition(state)
15 * stateTransitionTable 16 * stateTransitionTable
16 */ 17 */
17 NodePtr createNode(unsigned char character, NodePtr left, NodePtr right) { 18 NodePtr createNode(RegexInfoPtr ri,unsigned char character, NodePtr left, NodePtr right) {
18 NodePtr n = (NodePtr)malloc(sizeof(Node)); 19 NodePtr n = (NodePtr)malloc(sizeof(Node));
20 n->tokenType = ri->tokenType;
19 n->self = n; 21 n->self = n;
20 n->Value.character = character; 22 n->Value.character = character;
21 n->left = left; 23 n->left = left;
22 n->right = right; 24 n->right = right;
25
26 if (ri->tokenType == 'a') {
27 static int number = 1;
28 n->nodeNumber = number;
29 number++;
30 ri->tokenType = 0;
31 }
23 return n; 32 return n;
24 } 33 }
25 34
26 // <charClass> ::= '['<literal>'-'<literal>']' 35 // <charClass> ::= '['<literal>'-'<literal>']'
27 NodePtr charClass(RegexInfoPtr ri) { 36 NodePtr charClass(RegexInfoPtr ri) {
37 } 46 }
38 47
39 // <literal> ::= [a-z][A-Z][0-9] 48 // <literal> ::= [a-z][A-Z][0-9]
40 NodePtr literal(RegexInfoPtr ri) { 49 NodePtr literal(RegexInfoPtr ri) {
41 unsigned char *top = ri->ptr; 50 unsigned char *top = ri->ptr;
42 NodePtr n = createNode(ri->ptr[0],0,0); 51 NodePtr n = createNode(ri,ri->ptr[0],0,0);
43 ri->ptr++; 52 ri->ptr++;
44 return n; 53 return n;
45 } 54 }
46 55
47 // <group> ::= '('<regex>')' 56 // <group> ::= '('<regex>')'
97 ri->tokenType = 'a'; 106 ri->tokenType = 'a';
98 ri->tokenValue = ri->ptr[0]; 107 ri->tokenValue = ri->ptr[0];
99 return; 108 return;
100 } 109 }
101 } 110 }
102
103 ri->tokenType = 0; 111 ri->tokenType = 0;
104 ri->tokenValue = 0; 112 ri->tokenValue = 0;
105 return; 113 return;
106 } 114 }
107 115
121 NodePtr regex(RegexInfoPtr ri) { 129 NodePtr regex(RegexInfoPtr ri) {
122 NodePtr n = regexAtom(ri); 130 NodePtr n = regexAtom(ri);
123 while (ri->ptr[0]) { 131 while (ri->ptr[0]) {
124 token(ri); 132 token(ri);
125 if (ri->tokenType == '*') { 133 if (ri->tokenType == '*') {
126 n = createNode('*',n,0); 134 n = createNode(ri,'*',n,0);
127 } else if (ri->tokenType == '|') { 135 } else if (ri->tokenType == '|') {
128 NodePtr n1 = regex(ri); 136 NodePtr n1 = regex(ri);
129 n = createNode('|',n,n1); 137 n = createNode(ri,'|',n,n1);
130 } else if (ri->tokenType == ')') { 138 } else if (ri->tokenType == ')') {
131 return n; 139 return n;
132 } else { 140 } else {
133 NodePtr n1 = regex(ri); 141 NodePtr n1 = regex(ri);
134 n = createNode('+',n,n1); 142 n = createNode(ri,'+',n,n1);
135 } 143 }
136 } return n; 144 } return n;
137 } 145 }
138 146