ステートマシンに変換された正規表現の短い例は?

StackOverflow https://stackoverflow.com/questions/525004

  •  22-08-2019
  •  | 
  •  

質問

Stack Overflow ポッドキャスト #36 (http://blog.stackoverflow.com/2009/01/podcast-36/）、次のような意見が表明されました。ステート マシンのセットアップがいかに簡単かを理解すれば、二度と正規表現を不適切に使用しようとすることはなくなります。

いろいろ検索してみました。学術論文やその他の複雑な例をいくつか見つけましたが、このプロセスを理解するのに役立つ簡単な例を見つけたいと思っています。私は正規表現をたくさん使用していますが、二度と正規表現を「不適切に」使用しないようにしたいと思っています。

役に立ちましたか？

解決

確かに、あなたが本当にどのようにするREの仕事を理解するために、より複雑な例が必要になりますが。以下のREを考えてみます：

^[A-Za-z][A-Za-z0-9_]*$

は（アルファで始まる必要があり、どれも含まない、以下の英数字とundescore任意の数の文字を有することができる）は、典型的な識別子です。次の擬似コードは、これは有限状態機械で行うことができる方法を示しています。

state = FIRSTCHAR
for char in all_chars_in(string):
    if state == FIRSTCHAR:
            if char is not in the set "A-Z" or "a-z":
                error "Invalid first character"
            state = SUBSEQUENTCHARS
            next char
    if state == SUBSEQUENTCHARS:
            if char is not in the set "A-Z" or "a-z" or "0-9" or "_":
                error "Invalid subsequent character"
            state = SUBSEQUENTCHARS
            next char
私が言ったように、

さて、これは非常に単純な例です。それは、バックトラック（全体ではなく、ラインの）ライン内に一致すると簡単にRE構文によって処理されるステートマシンの他のより難解な機能、貪欲/最短一致マッチを行う方法を示していない。

RESは非常に強力である理由

です。ワンライナーREは、何ができるかを行うために必要な実際の有限状態マシンコードは、通常は非常に長く複雑である。

あなたができる最善のことは、特定の簡単な言語のためのいくつかのlex / yaccの（または同等の）コードのコピーを取得し、それが生成するコードを参照してくださいです。それはかなりありません（それは、人間が読むことを想定していないので、それはする必要はありません、彼らはLEX / yaccのコードを見ていることになっている）が、それはあなたに彼らがどのように動作するかについてのより良いアイデアを与える可能性があります。

他のヒント

どのようなパターンにPythonのあまり知られていないre.DEBUGフラグを使用するには、このを見て助けるためにかなり便利な方法：

>>> re.compile(r'<([A-Z][A-Z0-9]*)\b[^>]*>(.*?)</\1>', re.DEBUG)
literal 60
subpattern 1
  in
    range (65, 90)
  max_repeat 0 65535
    in
      range (65, 90)
      range (48, 57)
at at_boundary
max_repeat 0 65535
  not_literal 62
literal 62
subpattern 2
  min_repeat 0 65535
    any None
literal 60
literal 47
groupref 1
literal 62

「リテラル」と「範囲」の後の数字は、それらが一致することになっている。

ASCII文字の整数値を参照してください。

その場で自分自身を作ろう！

<のhref = "のhttp：//osteele.com/tools/reanimator/ ???" rel = "nofollowをnoreferrer">のhttp：//osteele.com/tools/reanimator/ ??? の

有限状態マシン

これは本当に素敵なのFSMとして正規表現を視覚化するツールを一緒に入れています。それはあなたが現実世界の正規表現エンジンで見つける構文の一部をサポートしていますが、起こっている正確に理解するために、確かに十分ではありません。

質問は「状態と遷移条件をどのように選択すればよいですか?」、それとも「Foo で抽象ステート マシンを実装するにはどうすればよいですか?」ですか?

状態と移行条件はどのように選択すればよいですか?

私は通常、かなり単純な問題に FSM を使用し、直感的に選択します。で 正規表現に関する別の質問に対する私の答え, 、私は解析問題を次のいずれかであると考えただけです。 Inside または outside タグのペアを作成し、そこからの遷移を書き出します (実装をクリーンに保つために開始状態と終了状態を指定します)。

Foo で抽象ステート マシンを実装するにはどうすればよいですか?

実装言語が次のような構造をサポートしている場合 cさんの switch ステートメントを実行したら、現在の状態をオンにして入力を処理し、次にどのアクションや遷移が実行されるかを確認します。

それなし switch- のような構造、または何らかの形で欠陥がある場合、 if スタイルの分岐。 うーん。

すべてを 1 か所にまとめて書きました c 私がリンクした例は次のようになります。

token_t token;
state_t state=BEGIN_STATE;
do {
   switch ( state.getValue() ) {
   case BEGIN_STATE;
      state=OUT_STATE;
      break;
   case OUT_STATE:
      switch ( token.getValue() ) {
         case CODE_TOKEN:
            state = IN_STATE;
            output(token.string());
            break;
         case NEWLINE_TOKEN;
            output("<break>");
            output(token.string());
            break;
         ...
      }
      break;
   ...
   }
} while (state != END_STATE);

これはかなり面倒なので、通常はリッピングします state ケースを別の機能に分割します。

私は誰かがより良い例を持っていると確信しているが、あなた可能性<のhref = "http://haacked.com/archive/2009/01/14/named-formats-redux.aspx" のrel = "nofollowをnoreferrer" > / <（そこにはいくつかのより多くの正規表現の例と、前のポストは私が考えるにもあります。）同じことをやって、正規表現の例とステートマシンを持っているフィル・ハークに、でこの記事をチェックP>

そのページの "HenriFormatter" をチェックします。

私はあなたが既に読んだ学術論文わかりませんが、本当に有限状態マシンを実装する方法を理解することは難しいことではありません。そこにいくつかの興味深い数学があるが、アイデアを実際に理解することは非常に簡単です。 FSMを理解する最も簡単な方法は、（実際には、これは私がここに記述しないことを、正式な定義のほとんどを含んで）入力および出力を介して行われます。 「状態」は、本質的にだけ発生したと特定のポイントから発生することができ、入力および出力のセットを記述している。

有限状態マシンは、ダイアグラムを経由して理解するのが最も簡単です。たとえばます：

http://img6.imageshack.us/img6/7571/mathfinitestatemachinedco3 .GIFする

このすべてを言っているあなたは、いくつかの状態Q0（その隣のスタートシンボルと1）で始まる場合は、他の州に行くことができるということです。各状態は円です。各矢印は（あなたがそれを見てどのように応じて）入力または出力を表しています。有限状態機械を考えるための別の方法は、「有効」または「許容される」の入力に関するものです。特定の有限状態機械は不可能である特定の出力文字列があります。これは、あなたが式を「一致」することができるようになります。

今、あなたはQ0から開始とします。さて、あなたの入力0場合は、状態Q1に移動します。ただし、入力1場合は、状態Q2に移動します。あなたは、入力/出力の矢印上のシンボルで、これを見ることができます。

あなたはQ0から始まり言うと、この入力を取得してみましょう。

0、1、0、1、1、1

これは、あなたが（Q0のための入力は、あなただけが起動していない）の状態を経たことを意味し

Q 0 - > Q1 - > Q0 - > Q1 - > Q0 - > Q2 - > Q3 - > Q3

それは意味がない場合は、

指で絵をトレースします。 Q3は、入力0と1の両方のために戻って自分自身に行くことに注意してください。

「あなたは、状態Q0にある場合、あなたはQ2に1人の行くを見たら、あなたはQ1に0、外出先を参照してくださいが、」このすべてを言うために別の方法でありますあなたは、各状態のため、これらの条件を作る場合、あなたはほとんどあなたのステートマシンを定義して行われています。あなたがしなければならない状態変数を持っているし、その後に入力をポンピングする方法、それはそこにあるものは基本的である。

[OK]を、なぜこの重要なに関するジョエルのステートメントがありますか？さて、「それらすべてを支配するためにONE TRUE正規表現に」構築する修正維持、あるいは他の人が戻ってきて、理解するためにすることは非常に難しく、また、困難な場合があります。また、いくつかのケースでは、より効率的です。

もちろん、ステートマシンは、他の多くの用途があります。これはいくつかの小さな方法でお役に立てば幸いです。私は理論に入る気にしませんでしたが、FSMのに関するいくつかの興味深い証拠があり、注意します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top