Mercurial > hg > Applications > Grep

annotate c/regexParser/subsetConstraction.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
96
b807383bcc43 add createBitVectorList.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 #include <stdio.h>
b807383bcc43 add createBitVectorList.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 #include <stdlib.h>
101
2cc097419169 fix print
masasann
parents: 100
diff changeset
3 #include <ctype.h>
117
166136236891 add header files
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 116
diff changeset
4 #include "subsetConstraction.h"
96
b807383bcc43 add createBitVectorList.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5
143
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
6 CharClassPtr charClassMerge(CharClassPtr src, CharClassPtr add) {
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
7 // 重なっているccの領域を分割する
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
8 // 必要ならばnextStateを重ねあわせる
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
9 // 変更があった場合は新しくリストを作って返す
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
10 if (src->type == 'a') {
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
11 if (add->type == 'a') {
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
12 if (src->cond.w.word[0] > add->cond.w.word[0]) {
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
13 // add のほうが小さいので小さい順のccをつくる
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
14 CharClassPtr left = charClassMerge(add->left.src);
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
15 return createCharClassWord(add->cond->w.word, left, add->right);
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
16 } else {
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
17
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
18 }
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
19 } else if (add->type == 'c') {
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
20 //
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
21 if (src->cond.w.word[0] < add->cond.range.begin) {
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
22
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
23 } else (src->cond->w.word[0] < add->end) {
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
24 } else if (src->type == 'c') {
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
25
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
26 }
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
27 }
32977f5a2ed0 add charClassMerge
masa
parents: 142
diff changeset
28
141
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
29 void printTransition(TransitionPtr ts) {
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
30 for (;;) {
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
31 printf("Input Condition : %c\n",ts->condition->cond->w->word);
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
32 printf("Next State : "); bitPrint(ts->nextState); printf("\n");
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
33 if (ts->next == NULL) break;
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
34 ts = ts->next;
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
35 }
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
36 }
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
37
142
de0f332d560c insert charClassMerge function
masa
parents: 141
diff changeset
38 TGValue generateTransition(NodePtr n,TransitionGenerator tg) {
141
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
39
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
40 if (n->tokenType == '+') {
142
de0f332d560c insert charClassMerge function
masa
parents: 141
diff changeset
41 TGValue tgv = generateTransition(n->left,tg);
de0f332d560c insert charClassMerge function
masa
parents: 141
diff changeset
42 if (tgv.asterisk) {
de0f332d560c insert charClassMerge function
masa
parents: 141
diff changeset
43 TGValue tgv1 = generateTransition(n->right,tg);
de0f332d560c insert charClassMerge function
masa
parents: 141
diff changeset
44 tgv.state |= tgv1.state;
de0f332d560c insert charClassMerge function
masa
parents: 141
diff changeset
45 return tgv;
de0f332d560c insert charClassMerge function
masa
parents: 141
diff changeset
46 }
de0f332d560c insert charClassMerge function
masa
parents: 141
diff changeset
47 tgv.state = n->right->nodeNumber;
de0f332d560c insert charClassMerge function
masa
parents: 141
diff changeset
48 return tgv;
141
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
49 } else if (n->tokenType == '|') {
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
50 tgv0 = generateTransition(n->left,tg);
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
51 tgv1 = generateTransition(n->right,tg);
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
52 tg->state->transition = appendTransition(tgv0->ts,tgv1->ts);
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
53 } else if (n->tokenType == '*') {
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
54 tgv0 = generateTransition(n->left,tg);
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
55 tgv0->asterisk = true;
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
56 } else {
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
57 tgv0 = (TGValuePtr)malloc(sizeof(TGValue));
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
58 BitVectorPtr bi = createBitVector(n);
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
59 tgv0->ts = createTransition(n->cc,bi);
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
60 tgv0->asterisk = false;
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
61 }
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
62
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
63 return tgv0;
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
64 }
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
65
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
66 StatePtr createStateList(NodePtr n) {
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
67 StatePtr s0 = NULL;
137
c292c67b3100 add generateTransitionList function
masa
parents: 117
diff changeset
68 if (n->left != NULL) {
141
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
69 s0 = createStateList(n->left);
137
c292c67b3100 add generateTransitionList function
masa
parents: 117
diff changeset
70 }
141
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
71
137
c292c67b3100 add generateTransitionList function
masa
parents: 117
diff changeset
72 if (n->tokenType == 'a') {
141
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
73 BitVectorPtr bi = createBitVector(n);
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
74 StatePtr s1 = createState(bi,0,0);
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
75 } else if (n->tokenType == '+' || n->tokenType == '|') {
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
76
104
3eb3cb5d581f implemented 'or' node translator
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 103
diff changeset
77 }
105
766fc2476f01 fix indent size
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 104
diff changeset
78
137
c292c67b3100 add generateTransitionList function
masa
parents: 117
diff changeset
79 if (n->right != NULL) {
141
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
80 s0 = createStateList(n->right);
104
3eb3cb5d581f implemented 'or' node translator
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 103
diff changeset
81 }
141
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
82 return s0;
104
3eb3cb5d581f implemented 'or' node translator
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 103
diff changeset
83 }
141
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
84
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
85 TransitionGeneratorPtr generateTransitionList(NodePtr n) {
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
86 TransitionGeneratorPtr tg = (TransitionGeneratorPtr)malloc(sizeof(TransitionGenerator));
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
87 int d = 0;
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
88 tg->state = createStateList(n);
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
89 generateTransition(n,tg);
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
90 return tg;
71f36a59cf6a add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 139
diff changeset
91 }