view 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
line wrap: on
line source

#include "bitVector.h"

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

typedef struct state {
    TransitionPtr transition;
    struct state *next;
} State, *StatePtr;

StatePtr createState(BitVectorPtr bi, TransitionPtr ts, StatePtr next);
StatePtr appendState(StatePtr x, StatePtr y);
TransitionPtr createTransition(CharClassPtr cc);
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を結合する
  + の場合は左のノードに * がある場合は右のリストも結合する
  左のノードに*がない場合は、右のほうだけみる
  * は直下のリストを使って、次の状態を自分自身にする
 */