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を結合する
  + の場合は左のノードに * がある場合は右のリストも結合する
  左のノードに*がない場合は、右のほうだけみる
  * は直下のリストを使って、次の状態を自分自身にする
 */