view c/regexParser/transition.h @ 110:a3adc5c24e19 pairPro

start branch
author masa
date Fri, 20 Nov 2015 21:02:00 +0900
parents
children ec485345daf9
line wrap: on
line source

typedef struct transition {
    CharClassPtr condition;
    BitVectorPtr nextState;
    struct transition *next;
} Transition, TransitionPtr;


typedef struct state {
    TransitionPtr transition;
    struct state *next;
} State; StatePtr;
/*
  正規表現木を辿って transition のList をつくる
  HcarClass のかさなりを判定して重なりのない新しいCharClassをつくる
  重なっている状態はbitvectorのorをとる
  重なっている状態はそれぞれの状態について木をたどる
  
  nextState == 0 は正規表現の末端を表す
  nextState == 1 は受理状態を表す
  正規表現のノードの番号 n に対応する 2^n のbitをセットした状態
  
  
  | の場合は両方のListを結合する
  + の場合は左のノードに * がある場合は右のリストも結合する
  左のノードにあすたがない場合は、右のほうだけみる
  * は直下のリストを使って、次の状態を自分自身にする
 */