Mercurial > hg > Applications > Grep
annotate regexParser/transition.h @ 169:313f1c176328 pairPro
implement mergeTransition
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Sat, 19 Dec 2015 19:06:35 +0900 |
parents | 3bf2c6d6d53e |
children | 540fc12871d9 |
rev | line source |
---|---|
116
66c633575b53
remove error and warning
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
112
diff
changeset
|
1 #include "bitVector.h" |
66c633575b53
remove error and warning
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
112
diff
changeset
|
2 |
110 | 3 typedef struct transition { |
4 CharClassPtr condition; | |
5 struct transition *next; | |
116
66c633575b53
remove error and warning
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
112
diff
changeset
|
6 } Transition, *TransitionPtr; |
110 | 7 |
8 typedef struct state { | |
9 TransitionPtr transition; | |
10 struct state *next; | |
116
66c633575b53
remove error and warning
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
112
diff
changeset
|
11 } State, *StatePtr; |
140
84a2a5209d3a
change some variable name
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
116
diff
changeset
|
12 |
141
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
140
diff
changeset
|
13 StatePtr createState(BitVectorPtr bi, TransitionPtr ts, StatePtr next); |
71f36a59cf6a
add appendState
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
140
diff
changeset
|
14 StatePtr appendState(StatePtr x, StatePtr y); |
169
313f1c176328
implement mergeTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
167
diff
changeset
|
15 TransitionPtr createTransition(CharClassPtr cc); |
140
84a2a5209d3a
change some variable name
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
116
diff
changeset
|
16 TransitionPtr appendTransition0(TransitionPtr curr,TransitionPtr next); |
84a2a5209d3a
change some variable name
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
116
diff
changeset
|
17 TransitionPtr appendTransition(TransitionPtr curr,TransitionPtr next); |
84a2a5209d3a
change some variable name
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
116
diff
changeset
|
18 |
110 | 19 /* |
20 正規表現木を辿って transition のList をつくる | |
112
ec485345daf9
some function use static
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
110
diff
changeset
|
21 CharClass のかさなりを判定して重なりのない新しいCharClassをつくる |
110 | 22 重なっている状態はbitvectorのorをとる |
23 重なっている状態はそれぞれの状態について木をたどる | |
112
ec485345daf9
some function use static
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
110
diff
changeset
|
24 |
110 | 25 nextState == 0 は正規表現の末端を表す |
26 nextState == 1 は受理状態を表す | |
27 正規表現のノードの番号 n に対応する 2^n のbitをセットした状態 | |
112
ec485345daf9
some function use static
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
110
diff
changeset
|
28 |
110 | 29 | の場合は両方のListを結合する |
30 + の場合は左のノードに * がある場合は右のリストも結合する | |
112
ec485345daf9
some function use static
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
110
diff
changeset
|
31 左のノードに*がない場合は、右のほうだけみる |
110 | 32 * は直下のリストを使って、次の状態を自分自身にする |
33 */ |