Mercurial > hg > Applications > Grep

comparison regexParser/transition.h @ 167:3bf2c6d6d53e pairPro

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
move regexparser dir
author masa
date Sat, 19 Dec 2015 15:38:45 +0900
parents c/regexParser/transition.h@e2e717fbeb2f
children 313f1c176328
comparison
equal deleted inserted replaced
166:96854eba17e5 167:3bf2c6d6d53e
1 #include "bitVector.h"
2
3 typedef struct transition {
4 CharClassPtr condition;
5 BitVectorPtr nextState;
6 struct transition *next;
7 } Transition, *TransitionPtr;
8
9 typedef struct state {
10 BitVectorPtr bitState;
11 TransitionPtr transition;
12 struct state *next;
13 } State, *StatePtr;
14
15 StatePtr createState(BitVectorPtr bi, TransitionPtr ts, StatePtr next);
16 StatePtr appendState(StatePtr x, StatePtr y);
17 TransitionPtr createTransition(CharClassPtr cc ,BitVectorPtr state);
18 TransitionPtr appendTransition0(TransitionPtr curr,TransitionPtr next);
19 TransitionPtr appendTransition(TransitionPtr curr,TransitionPtr next);
20
21 /*
22 正規表現木を辿って transition のList をつくる
23 CharClass のかさなりを判定して重なりのない新しいCharClassをつくる
24 重なっている状態はbitvectorのorをとる
25 重なっている状態はそれぞれの状態について木をたどる
26
27 nextState == 0 は正規表現の末端を表す
28 nextState == 1 は受理状態を表す
29 正規表現のノードの番号 n に対応する 2^n のbitをセットした状態
30
31 | の場合は両方のListを結合する
32 + の場合は左のノードに * がある場合は右のリストも結合する
33 左のノードに*がない場合は、右のほうだけみる
34 * は直下のリストを使って、次の状態を自分自身にする
35 */