Mercurial > hg > Applications > Grep
view regexParser/transition.h @ 176:c092dd0e1ae0 pairPro
implement appendState() and serchState()
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Wed, 23 Dec 2015 15:41:27 +0900 |
parents | 3be0fbcd4b52 |
children | 8de9a33f6ae5 |
line wrap: on
line source
#include "bitVector.h" typedef struct transition { CharClassPtr condition; struct transition *next; } Transition, *TransitionPtr; typedef struct state { BitVector bitState; TransitionPtr transition; NodePtr nextNode; struct state *next; } State, *StatePtr; StatePtr createState(StatePtr state,BitVector bi); StatePtr appendState(StatePtr x,StatePtr y); TransitionPtr createTransition(CharClassPtr cc, BitVectorPtr state); TransitionPtr appendTransition0(TransitionPtr curr,TransitionPtr next); TransitionPtr appendTransition(TransitionPtr curr,TransitionPtr next); /* 正規表現木を辿って transition のList をつくる CharClass のかさなりを判定して重なりのない新しいCharClassをつくる 重なっている状態はbitvectorのorをとる 重なっている状態はそれぞれの状態について木をたどる nextState == 0 は正規表現の末端を表す nextState == 1 は受理状態を表す 正規表現のノードの番号 n に対応する 2^n のbitをセットした状態 | の場合は両方のListを結合する + の場合は左のノードに * がある場合は右のリストも結合する 左のノードに*がない場合は、右のほうだけみる * は直下のリストを使って、次の状態を自分自身にする */