(57)【要約】【課題】  正規表現コンパイラと文字列照合機からなる正規表現エンジンには、低速なＮＦＡエンジンと、高速なＤＦＡエンジンの２種類が存在する。シングルバイト文字セット用には高速なＤＦＡエンジンが存在するが、マルチバイト文字セット用には低速なＮＦＡエンジンが実存するのみであった。【解決手段】  本発明は、マルチバイト文字セット用に書かれた正規表現を、ＤＦＡへの変換が容易な構造に変換する方法を提供し、結果としてマルチバイト文字セット用ＤＦＡ正規表現エンジンを得るものである。  本発明は、正規表現中に現れる任意文字を表す記号に対しては、バイト長毎に分岐するＮＦＡ構造を割り当て、正規表現中に現れる文字クラスを表す記号列に対しては、バイト毎の決定性分解を実現するＮＦＡ構造を割り当てる。この翻訳規則と従来の方法をあわせて適用し、正規表現に対応するＮＦＡ構造を得、ＮＦＡ構造から既知の手続きによってＤＦＡ遷移表を得る。得られたＤＦＡ遷移表は後段階のＤＦＡ用文字列照合機と接続される。【選択図】図１
2007102744.tif 000002
【特許請求の範囲】
【請求項１】
マルチバイト文字セット上の正規表現に対し非決定性有限状態機械（ＮＦＡ）を対応させる正規表現コンパイラ構成方法であって、任意文字を表す記号に対して文字を構成する符号長毎のシーケンスを受理する２方向以上に分岐した分枝でバイト単位でラベル付けられた状態遷移機械を対応させ、文字クラスを表す記号列に対して文字を構成する符号長毎のシーケンスを受理する２方向以上に分岐した分枝でそれぞれの分枝が決定性分解に基づきバイト単位でラベル付けられた非決定性状態遷移機械を対応させる方法。
【請求項２】
マルチバイト文字セット上の正規表現に対し非決定性有限状態機械（ＮＦＡ）を対応させる正規表現コンパイラ構成方法であって、任意文字を表す記号に対して文字を構成する符号長毎のシーケンスを受理する２方向以上に分岐した分枝でバイト単位でラベル付けられた状態遷移機械を対応させ、文字クラスを表す記号列に対して、文字を構成する符号長毎のシーケンスを受理する２方向以上に分岐した分枝でそれぞれの分枝が決定性分解に基づきバイト単位でラベル付けられた非決定性状態遷移機械を対応させる方法を利用したＮＦＡ正規表現コンパイラ。
【請求項３】
請求項１の方法をＮＦＡ用文字列照合方法とあわせて用いるものであって、結果としてマルチバイト文字セット用ＮＦＡ正規表現エンジンを実現する方法。
【請求項４】
請求項１の方法を後段階の非決定性有限状態機械（ＮＦＡ）を決定性有限状態機械（ＤＦＡ）に変換する処理とあわせて使用し、得られたＤＦＡ遷移表を、ＤＦＡ用文字列照合機が参照する状態遷移機械として用いるものであって、結果としてマルチバイト文字セット用ＤＦＡ正規表現エンジンを実現する方法。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、正規表現エンジン構成方法のうち、マルチバイト文字セット用正規表現コンパイラ構成方法及び正規表現コンパイラプログラムに関するものである。
【背景技術】
【０００２】  マルチバイト文字セットは、２５６文字を超える文字集合を扱うために用いられる文字符号法であり、表現する文字によって符号長が異なるという特徴を持つ。マルチバイト文字セットの代表的なものに、Ｓｈｉｆｔ＿ＪＩＳやＥＵＣ−ＪＰやＵＴＦ−８がある。【０００３】  マルチバイト文字セットは、符号化し得る文字数がシングルバイト文字セットの２５６文字に比較して多い。その大きさはそれぞれのマルチバイト文字セットによってまちまちであるが、約１万字を表現し得るもの（Ｓｈｉｆｔ＿ＪＩＳ）、約２万字を表現し得るもの（ＥＵＣ−ＪＰ）、約４２億字を表現し得るもの（ＵＴＦ−８）と、シングルバイト文字セットとの差は甚大である。この文字空間の大きさは、実用上のメリットをもたらすと共に、検索速度の低下というデメリットも同時にもたらしてきた。【０００４】  正規表現は、プログラミング言語処理及び文字列検索に広範に用いられる文字列集合の表記法である。正規表現は、プログラミング言語処理の応用においては、コンパイラの字句解析部において、字句の文字の並びを指定するために用いられる。また、正規表現は、全文テキスト検索の応用において、一般的な表記法を提供し、検索対象となる複数文字列の指定や、複雑なパターンの指定のために用いられる。【０００５】  正規表現エンジンとは、正規表現を変換して有限状態機械を構築する正規表現コンパイラと、得られた有限状態機械を用いて入力文字列との文字列照合を行うプログラムの組である。正規表現エンジンには、これを構成する正規表現コンパイラが非決定性有限状態機械（ＮＦＡ）を利用するＮＦＡエンジンと、決定性有限状態機械（ＤＦＡ）を利用するＤＦＡエンジンがある（非特許文献１）。【０００６】  文字列検索及びパターン検索に、正規表現からコンパイルされたＤＦＡ表引きを利用すると、パターンの複雑さに依存しない速度が得られるため、極めて高速な動作がもたらされることに加えて、最大一致文字列を検出できるため、均質で統制のとれた結果が得られる（非特許文献３）。【０００７】  既存技術の正規表現エンジンとしては、シングルバイト文字セット用のものに高速なＤＦＡ表引きに依るものが既に得られているが（非特許文献２）、マルチバイト文字セット用には低速なＮＦＡ構造のバックトラッキングに頼るしかないのが実情であった。【０００８】  いっぽう、文字列検索や字句解析の多国語対応に目を転じると、高度な文字列処理のために、文字コードの変換を伴う例（特許文献１）があるものの、マルチバイト文字セットによりエンコードされた文字列をそのまま扱う仕組みは希少であった。また、テキストデータの変換を伴うもの（特許文献２）があるものの、テキストデータを保持したままで検索を行えるシステムは少なかった。
【特許文献１】特開２００４−２５８７５９公報
【特許文献２】特開２００４−２２０２４６公報
【非特許文献１】Ｊｅｆｆｒｅｙ  Ｅ．Ｆ．Ｆｒｉｅｄｌ著，田和  勝  訳  「『詳説  正規表現  第２版」オライリー・ジャパン２００３年発行
【非特許文献２】Ａ．Ｖ．エイホ，Ｒ．セシィ，Ｊ．Ｄ．ウルマン共著，原田  賢一  訳，  「コンパイラＩ」サイエンス社１９９０年発行
【非特許文献３】守屋  悦朗「形式言語とオートマトン」サイエンス社２００１年発行
【発明の開示】
【発明が解決しようとする課題】
【０００９】  正規表現は極めて広い応用範囲を持つものの、正規表現エンジンは、シングルバイト文字セット用に開発されたものを起源とし、マルチバイト文字セット用の正規表現エンジンの開発は最近になるまで行われなかった。いっぽうコンパイラの字句解析機は、正規表現によって記述方法が規則化されて多大な労力の低減をもたらし、また、文字列検索、複数文字列検索、パターン検索を正規表現の形式により統合した一般的で強力なツールは、逐次のプログラミング作業の労力を軽減し、今日のインターネット上での検索システムが展開するための一翼を担っている。【００１０】  正規表現をマルチバイト拡張する際に生じる困難は、実用上の配慮から正規表現の文法に加えられた「任意文字記号」と、「文字クラス記号列」の拡張に起因する。任意文字記号は本来、文字列の照合時に任意の１文字にマッチングするべきのものであるが、シングルバイト文字セット用の正規表現エンジンでは、任意の１バイトにマッチングしてしまう。これをマルチバイト文字セットに改良しようとすると、文字空間が広大なために、既知の方法では、速度上の効率が損なわれるか、膨大な記憶領域を必要とするものになる。文字クラス記号列は、複数の文字の内の任意の１文字に適合するマッチングするべきものであり、前述の問題と同じ困難を生じせしめる。【００１１】  本発明は上記の問題を鑑みてなされたもので、正規表現をマルチバイト文字セットに対応させ、しかも効率の低下を招かない正規表現エンジン構成方法およびプログラムを提供するものである。
【課題を解決するための手段】
【００１２】  この発明は、マルチバイト文字セット上の正規表現を、ＮＦＡ構造に与えられたラベルがすべて１バイト長の符号を持つＮＦＡ構造に変換し、既知のＮＦＡ・ＤＦＡ変換機とあわせることによって、結果として正規表現をコンパクトで高速性の高い決定性有限状態機械（ＤＦＡ）に変換する方法を実現するものである。【００１３】  本発明は、正規表現のコンパイルの過程に手を加え、ＤＦＡ遷移表の構築を容易ならしめる非決定性有限状態機械（ＮＦＡ）を生成し、得られたＮＦＡ構造に対して既存の手法を適用することによって、最終的にＤＦＡ遷移表を出力する正規表現コンパイラを構築する。この正規表現コンパイラによって、マルチバイト文字セット用の正規表現エンジンであって、高速なＤＦＡ表引きによる文字列照合を行うものが構成でき、課題が解決される。【００１４】  本発明は、従来型のマルチバイト文字セット用の正規表現コンパイラが、ＮＦＡ構造に２バイト以上の符号長を持つラベルを付与していたのを改め、ＮＦＡ構造に対してちょうど１バイトの符号長を持つラベルを付与するようにＮＦＡ構造の生成過程を改良する。この改良を行うために、正規表現中に現れる任意文字記号及び文字クラス記号列から生成されるＮＦＡ構造を変更する。【００１５】  任意文字記号は通常、ドット「．」で表される正規表現のメタ記号であり、文字列照合時に任意の文字にマッチすると解釈する。従来のシングルバイト文字セット用正規表現コンパイラでは、任意文字記号に対して、単一辺であってラベルに１バイト長符号の全体集合のビットセットを持つもの与えていた。また、従来のマルチバイト文字セット用正規表現コンパイラでは、任意文字記号に対して、単一辺であってラベルに仮の記号を持つものを与え、後の文字列照合機で任意のバイト長の任意の文字にマッチさせる工夫を施していた。【００１６】  本発明ではこの方法を改め、任意文字記号に対して、符号長毎のバイト列を受理する２方向以上に分岐した分枝であってバイト単位でラベル付けされたＮＦＡ構造（図４）を対応させる。このＮＦＡ構造は文字セットの最大符号長によって異なり、最大符号長が１である場合、すなわちシングルバイト文字セットの場合（図４：１）には既知の方法と一致する。最大符号長が２の場合（図４：２）、最大符号長が３の場合（図４：３）、最大符号長が４の場合（図４：４）は、任意文字記号に対してマルチバイト文字セット用に拡張されたＮＦＡ構造を提供する。【００１７】  文字クラス記号列は通常、角括弧「［」と「］」で全体を囲まれた記号列であり、開括弧「［」の直後にサーカムフレックス記号「＾」を伴うか否かで、否定文字クラスか肯定文字クラスであるかを決定する。肯定文字クラスの場合は角括弧内の記号列によって列挙される文字集合に属する任意の文字にマッチすると解釈し、否定文字クラスの場合は角括弧内の記号列によって列挙される文字集合に属さない任意の文字にマッチすると解釈する。【００１８】  従来のシングルバイト文字セット用正規表現エンジンでは、文字クラス記号列に対して、文字集合を表現するビットセットを与えていた。従来のマルチバイト文字セット用正規表現エンジンでは、文字クラス記号列に対して、符号長に２バイト���以上を要するビットセットか、文字クラス記号列そのものに近い形を持った仮の表現を与えていた。【００１９】  本発明ではこの方法を改め、文字クラス記号列に対しては、２方向以上に分岐した分枝であって、それぞれの分枝がバイト長毎の符号列を受理し、かつ決定性分解に基づくバイト単位でラベル付けられたＮＦＡ構造を対応させる（図５）。このＮＦＡ構造は文字セットの最大符号長によって異なり、シングルバイト文字セットの場合（図５：１）に既知の方法と一致する。最大符号長が２の場合（図５：２）、最大符号長が３の場合（図５：３）、最大符号長が４の場合（図５：４）は、文字クラス記号列に対してマルチバイト文字セット用に拡張されたＮＦＡ構造を提供する。【００２０】  各バイト長の符号列受理のために用いる構造は、文字集合を１バイト長符号を要素とする正規集合と捉え直したときに、その正規集合の決定性分解を実現するＮＦＡ構造とする。【００２１】  特定の符号長の正規集合は、いつでも決定性分解を持つ。例えば、符号長が２の場合に、正規集合をζとすると、その決定性分解は、（数１）の形に書くことができる。特に、Ｂ（０）を１バイト符号の符号集合で、基底集合Ｓ（２，２）に等しいものにすることができる。
【数１】
2007102744.tif 000003
【００２２】  符号長がｍの場合は、正規集合をξとすると、その決定性分解は、符号長がｍ−１の正規集合の決定性分解を利用して、（数２）の形に書くことができる。
【数２】
2007102744.tif 000004
【００２３】  特にβ（０）を基底集合のｍ−１バイト長の連接、Ｓ（２，ｍ）・Ｓ（３，ｍ）・・・Ｓ（ｍ，ｍ）にすることができる。【００２４】  これらの改良を施した正規表現コンパイラによって、対象とする文字列の基づく文字セットが、シングルバイト文字セットであるか、マルチバイト文字セットであるかのいずれであるかによらず、すべてのラベルが１バイト長であるようなＮＦＡ構造が得られる。【００２５】  従来から、２バイト以上の符号長のラベルの付いたＮＦＡ構造から実用的な大きさのＤＦＡ遷移表を得ることは困難であったが、この困難は、ＤＦＡ遷移表がその符号長で区別し得る符号数に比例した記憶領域を必要とすることに起因する。ＤＦＡ遷移表とは縦方向にＤＦＡ状態、横方向にその符号長で表現し得るすべての符号が並んだものであるからである。【００２６】  １バイト符号長のラベルを持つＮＦＡ構造からは実用的な大きさのＤＦＡ遷移表が得られる。これらの処理は標準的で既知のものであり（非特許文献２）、本発明の施すＮＦＡ構造に対する改良は既知の方法でＤＦＡ遷移表に変換できる範囲内で行われるものである。【００２７】  ＮＦＡ構造は、イプシロン閉包処理（図１：７）及び部分集合構成処理（図１：８）によってＤＦＡ表に変換する。イプシロン閉包処理は、何も入力が与えられなくても起こる遷移を予めまとめておく処理で、ＮＦＡ構造のそれぞれの状態に対して、イプシロンラベルのついた辺による遷移先を収集することにより実現する（非特許文献２）。部分集合構成処理は、特定の入力が与えられた時に起こる遷移先を集めるもので、ＮＦＡ構造のそれぞれの状態に対して、特定のラベルのついた辺を任意のラベルについて収集することによって実現する（非特許文献２）。なお、ＤＦＡ表の大きさを小さくするために、ＤＦＡ状態数最適化処理（図１：９）を行ってもよい。【００２８】  ＮＦＡ正規表現エンジンは、正規表現コンパイラとＮＦＡ文字列照合機を主要部分とし、正規表現と入力文字列を入力とし中間結果としてのＮＦＡ構造を利用して文字列照合を行い照合結果を出力するプログラム群により構成する。【００２９】  ＤＦＡ正規表現エンジンは、正規表現コンパイラとＮＦＡ・ＤＦＡ変換機とＤＦＡ用文字列照合機を主要部分とし、正規表現と入力文字列を入力とし中間結果としてのＤＦＡ表を利用して文字列照合を行い照合結果を出力するプログラム群により構成する。
【発明の効果】
【００３０】  この発明により、従来のシングルバイト文字セット用に書かれた正規表現エンジンを、マルチバイト文字セット用に改良することが可能になる。改良された正規表現エンジンは、決定性有限状態機械（ＤＦＡ）による高速性を保持しているため、正規表現を使ったプログラムのマルチバイト化及び高速化が可能になる。【００３１】  本発明によって、予備インデックス生成を伴わない全文日本語検索エンジンであって、複数字句検索機能や高度なパターンマッチングの機能を有するものの高速化が可能になる。【００３２】  また、外国語や複数のマルチバイト文字セットに対して同一のプログラムの適用が可能となるため、複数のプラットフォームの上で統一され、多国語対応し、なおかつ速度上の効率の保障された文字列検索及び字句解析ツールが得られる。【００３３】  プログラミング言語の字句解析機に本発明を適用すると、今まで手作業の混在していたプログラミング言語のコンパイラやインタープリタの多国語対応や複数の文字符号化法への対応が自動化される。【００３４】  本発明による正規表現エンジンは、高速性を保ちつつも記憶領域にかける負担が少ないため、低ＣＰＵクロックで搭載するメモリの比較的小さいモバイル情報機器への適用が可能になる。
【発明を実施するための最良の形態】
【００３５】  正規表現コンパイラは（図１：２）、再帰下降型構文解析法により実現する。再帰下降型構文解析機を、文法流れ図（図２及び図３）に対応した形のいくつかの手続きから構成する。【００３６】「正規表現」は、複数の「和項」が記号「｜」を間にはさんで連なったものである（図版２：１）。「和項」は１つでも良く、その場合には記号「｜」は用いられないものとする。「和項」は、１つ又は複数の「積項」の連なりであり、間にはさみ込まれる記号はない（図２：２）。【００３７】「積項」は、「任意文字記号」であるか「文字クラス記号列」であるか、「文字」であるか、丸括弧「（」と「）」によってはさまれた、より小さな単位の「正規表現」であるのいずれかであるとし、その後にクリーネ閉包演算子「＊」、または正閉包演算子「＋」、あるいはオプション演算子「？」を伴っても良いものとする（図２：３）。【００３８】  「任意文字記号」は、ドット記号「．」であるとする（図２：４）。【００３９】  「文字クラス記号列」は、開角括弧記号「［」で始まり、「文字クラス内部」が続き、閉角括弧記号「］」で終わるか、もしくは開ブラケット記号「［」で始まり、サーカムフレックス記号「＾」が続き、さらに「文字クラス内部」が続き、閉角括弧記号「］」で終わるかのいずれかとする（図２：５）。【００４０】「文字クラス内部」は、任意の個数の「文字」か、文字範囲指定の連結とする。ここで文字範囲指定とは、「文字」と「文字」がハイフン「−」で連結されたものとする（図２：６）。【００４１】「文字」は、コンピュータ上で扱うことのできるいずれかの文字符号である。マルチバイト文字セットに対しては、符号長により文字を数種類に分類し、「１バイト文字」、「２バイト文字」、「３バイト文字」あるいは「４バイト文字」のいずれかであるとする（図３：１）。【００４２】  「１バイト文字」は、基底集合Ｓ（１，１）に含まれるいずれかの符号であるとする（図３：２）。「２バイト文字」は、基底集合Ｓ（２，１）に含まれるいずれかの符号の後に基底集合Ｓ（２，２）に含まれるいずれかの符号が続いたものとする（図３：３）。「３バイト文字は、基底集合Ｓ（３，１）に含まれるいずれかの符号の後に基底集合Ｓ（３，２）に含まれるいずれかの符号が続き、さらに基底集合Ｓ（３，３）に含まれるいずれかの符号が続いたものとする（図３：４）。「４バイト文字」は、基底集合Ｓ（４，１）に含まれるいずれかの符号の後に基底集合Ｓ（４，２）に含まれるいずれかの符号が続き、さらに基底集合Ｓ（４，３）に含まれるいずれかの符号が続き、最後に基底集合Ｓ（４，４）に含まれるいずれかの符号が続いたものとする（図３：５）。【００４３】正規表現（図１：１）は、入力文字列（図１：４及び図１：１１）と同じ文字符号化方式により符号化されている必要がある。もし両者が異なる場合は、あらかじめ正規表現の符号化方式を、入力文字列の符号化方式にあわせておく。【００４４】  符号集合を扱うために、ビットセットを用いる。ビットセットは、符号集合と要素符号の包含関係を１あるいは０で表現して符号の順に並べたビット列をコンピュータのビット順序に従ってパックしたものである。ビットセットを用いると��最大要素数が２５６の符号集合を、３２バイトを用いて表現することができる。【００４５】  基底集合は、マルチバイト文字セットの文字を符号長ごとに分類して各バイトを構成する集合をビットセットによって表現したものである。Ｌａｔｉｎ−１は最大符号長が１のシングルバイト文字セットであり、基底集合Ｓ（１，１）が文字セットを構成するすべての符号を包含する（図１８：１）。Ｓｈｉｆｔ＿ＪＩＳは最大符号長が２のマルチバイト文字セットであり、基底集合Ｓ（１，１）及びＳ（２，１）及びＳ（２，２）により文字を構成する符号が分類される（図１８：２）。ＥＵＣ−ＪＰは最大符号長が３のマルチバイト文字セットであり、基底集合Ｓ（１，１）及びＳ（２，１）・Ｓ（２，２）及びＳ（３，１）・Ｓ（３，２）・Ｓ（３，３）により文字を構成する符号が分類される（図１８：３）。ＵＴＦ−８は現在定義されている範囲において最大符号長が４のマルチバイト文字セットであり、基底集合Ｓ（１，１）及びＳ（２，１）・Ｓ（２，２）及びＳ（３，１）・Ｓ（３，２）・Ｓ（３，３）及びＳ（４，１）・Ｓ（４，２）・Ｓ（４，３）・Ｓ（４，４）により文字を構成する符号が分類される（図１８：４）。【００４６】  次にＳｈｉｆｔ＿ＪＩＳの場合を例にして、基底集合の構成方法を説明する。【００４７】  Ｓｈｉｆｔ＿ＪＩＳでは、０ｘ００〜０ｘ７Ｆまでの符号は、１バイトの英数文字およびコントロール文字を表現する符号とされ、そのほとんどはＡＳＣＩＩ符号をそのまま埋め込んだものである。０ｘＡ０〜０ｘＤＦは、いわゆる半角カナ文字のための符号で、１バイトで表現される。【００４８】  残る０ｘ８０〜０ｘ９Ｆおよび０ｘＥ０〜０ｘＦＦのうち、特殊な記号のために空けられた０ｘ８０及び０ｘＦＤ・０ｘＦＥ・０ｘＦＦを除いた部分が、いわゆる全角文字のための符号空間であり、この空間に含まれる符号を使って２バイトで表現される全角文字符号の１バイト目を符号化する。【００４９】  ０ｘ００〜０ｘ８０及び、０ｘＡ０〜０ｘＤＦ、０ｘＦＤ〜０ｘＦＦが１バイト文字の１バイト目を表現する符号である。この符号集合のビットセット表現のことを、Ｓｈｉｆｔ＿ＪＩＳの基底集合１−１と呼び、記号Ｓ（１，１）で表す。【００５０】  反対に、０ｘ８１〜０ｘ９Ｆ及び、０ｘＥ０〜０ｘＦＣは、２バイト文字の１バイト目を表現する符号である。この符号集合を、Ｓｈｉｆｔ＿ＪＩＳの基底集合２−１と呼び、Ｓ（２，１）で表す。【００５１】  全角文字の２バイト目は、０ｘ４０〜０ｘＦＦのうち、０ｘ７Ｆ・０ｘ８０・０ｘＦＦを除いたものである。この符号集合はＳｈｉｆｔ＿ＪＩＳの基底集合２−２と呼び、Ｓ（２，２）で表す。【００５２】  「任意文字記号」は、ドット「．」で表される。任意文字記号に対して与えられる構造に、本発明は改良を加える。従来のシングルバイト文字セット用正規表現コンパイラは、任意文字記号に対して基底集合Ｓ（１，１）をラベルに持つＮＦＡ構造（図４：１）を与えていた。【００５３】  本発明における任意文字記号を処理する方法を、流れ図（図１１）に従って説明する。この流れ図に基づくプログラムによって、マルチバイト文字セット用に改良した出力が得られる。この流れ図に基づくプロ��ラムは、正規表現中の次の文字がドット「．」の場合（図１１：１）、１文字すすめ（図１１：２）、マルチバイト文字セットの最大符号長に基づいて、各バイト長で表現され得る文字の符号並びをすべて受理する連結辺から構成され、これらの連結辺を選択的に繋げた構造を出力する（図１１：３）。出力される構造は、最大符号長が２の場合（図４：２）、最大符号長が３の場合（図４：３）、最大符号長が４の場合（図４：４）で異なる。【００５４】  「文字クラス記号列」は全体を「［」と「］」で囲まれた「文字クラス内部」か、全体を「［」と「］」で囲まれて、前に「＾」を伴った「文字クラス内部」であり、便宜上前者を「肯定文字クラス」、後者を「否定文字クラス」と呼ぶ。肯定文字クラスに対して与えられる構造、否定文字クラスに対して与えられる構造の両方に対して、本発明は改良を加える。【００５５】  文字クラス記号列を処理する方法を、流れ図（図１２）に従って説明する。この流れ図に基づくプログラムによって、肯定文字クラスの場合にも、否定文字クラスの場合にも、それぞれ改良した出力が得られる。【００５６】文字クラス記号列を処理する流れは、まず最初に来る記号が開角括弧「［」でない場合には、ただちに処理を終了する（図１２：１）。開角括弧である場合には、１文字すすめて（図１２：２）、次に初に来る記号が「＾」であるか否かによって、否定文字クラスの場合と、肯定文字クラスの場合に分岐する（図１２：３）。【００５７】  肯定文字クラスの場合は、文字クラス記号列の表す文字集合をちょうど受理するＮＦＡ構造を作るために最初に何も受理しないＮＦＡ構造（図６）を用意する。否定文字クラスの場合は、最初に任意の文字を受理するＮＦＡ構造（図７）を用意する。文字クラス内に現れる文字が、１バイト長である場合は既知のビットセットを用いる手法によって、ＮＦＡ構造を実現できる。１バイト長の場合に用いるビットセットをＣと呼ぶ。文字クラス内に現れる文字が、２バイト長以上である場合、ＮＦＡ構造は、行数を伸縮することができる表を用いて記憶領域内に格納する。伸縮表はバイト長が２の場合に単純化して図示できる（図８）。この表は、あらかじめ十分な記憶領域を確保した上で、使用行数を保持する変数を設けることによって容易に実現することができるが、さらに高度な動的記憶域管理とポインタの仕組みが提供されている場合には、それを利用しても良い。【００５８】  伸縮表の要素となり得るものは、１バイト長の符号又はビットセット又は別の伸縮表への参照ポインタである。別の伸縮表への参照ポインタは、符号長が３バイト以上の文字クラスを扱う場合にのみ用いられる。【００５９】  伸縮表の各要素は、３８バイトの情報を含むことができるものとする。すなわち、１バイトの種別符号、１バイトのラベル符号、４バイトの他の伸縮表への参照ポインタ、３２バイトのビットセット符号列である。【００６０】  種別フィールドには、０又は１又は２の符号が格納される。０の場合は、伸縮表の要素が１バイト長の符号であることを示し、１の場合には、伸縮表の要素が４バイト長の他の伸縮表への参照ポインタであることを示し、２の場合には、その要素が３２バイト長のビットセットであることを示��。種別フィールドによる区別によって、伸縮表の要素が何であっても正しく格納し、及び取り出すことができる。なお、伸縮表の要素を格納するために、プログラミング言語が構造体や共用体の仕組みを提供している場合には、その仕組みを利用しても良い。また、ビットセットを独立した記憶領域を利用して格納し、伸縮表の要素としてはビットセットへの参照ポインタを格納するようにしてもよい。【００６１】  伸縮表の要素は、横方向に２列、縦方向に数行から数百行並べられて伸縮表を構成する。【００６２】  伸縮表に対して最初に与える構造は、行数にはカウントせず、行番号０を与える。この構造は伸縮表の最初に置かれ、決して取り除かれることはない。動的記憶域管理とポインタの仕組みを利用してＮＦＡ構造を実現している場合には、構造全体を指し示すポインタが最初にこの構造を指すようにし、最初に与える構造の左側端点から伸びるリンクによって残りの行を指すようにする。【００６３】  肯定文字クラスの場合は、最初に何も受理しない構造を、符号長に基づいて準備する。すなわち、符号長が１のもの（図６：１）、符号長が２のもの（図６：２）、符号長が３のもの（図６：３）、符号長が４のもの（図６：４）のラベル符号をマルチバイト文字セットの最大符号長に応じて伸縮表（図８）の最初の行に書き込む。たとえば、符号長が１バイトの場合には、Ｃ＝Ｓ（１，１）とし、符号長が２バイトの場合には、Ａ（０）＝φ、Ｂ（０）＝Ｓ（２，２）とする。【００６４】  続く繰り返し処理では、次に来る記号が閉ブラケット「］」になるまで処理をすすめ（図１２：５）、次々に要素を伸縮表に登録することによって、最終的に望む構造を出力する。【００６５】  ループのはじめに読む文字は、単独の文字であるか、文字範囲指定の始点であるため、まず変数ｘにそれを代入し、１文字すすめる（図１２：６）。次の文字がハイフン「−」ではない場合、文字ｘを伸縮表に登録する処理を呼び出す（図１２：１１）。次の文字がハイフン「−」である場合（図１２：７）、処理しようとしているものが文字範囲指定であることがわかるので、１文字すすめて（図１２：８）、次の文字を変数ｙに代入して、１文字すすめる（図１２：９）。次に変数ｘと変数ｙを引数にして、範囲ｘ〜ｙを伸縮表に登録する処理を呼び出す（図１２：１０）。【００６６】  否定文字クラスの場合は、最初に特定バイト長の任意の文字バイト列を受理できる構造を、符号長が１のもの（図７：１）、符号長が２のもの（図７：２）、符号長が３のもの（図７：３）、符号長が４のもの（図７：４）を伸縮表（図８）の最初の行に書き込む（図１２：１６）。たとえば、符号長が１バイトの場合には、Ｃ＝Ｓ（１，１）とし、符号長が２バイトの場合には、Ａ（０）＝Ｓ（２，１）、Ｂ（０）＝Ｓ（２，２）とする。【００６７】  続く繰り返し処理では、次に来る記号が閉ブラケット「］」になるまで処理をすすめ（図１２：１７）、次々に要素を伸縮表から除録することによって、最終的に望まれる構造を出力する。【００６８】  ループのはじめに読む文字は、単独の文字であるか、文字範囲指定の始点であるため、まず変数ｘにそれを代入し、１文字すすめる（図１２：１８）。次の文字がハイフン「��」ではない場合、文字ｘを伸縮表から除録する処理を呼び出す（図１２：２３）。次の文字がハイフン「−」である場合（図１２：１９）、処理しようとしているものが文字範囲指定であることがわかるので、１文字すすめて（図１２：２０）、次の文字を変数ｙに代入して、１文字すすめる（図１２：２１）。次に変数ｘと変数ｙを引数にして、範囲ｘ〜ｙを伸縮表から除録する処理を呼び出す（図１２：２２）。【００６９】  範囲ｘ〜ｙを伸縮表に登録する処理では、範囲を要素に分解して繰り返し処理を行う。ここでは２バイトで符号化される文字を登録する場合（図１３）を例にする。始点文字ｘから終点文字ｙまでの範囲を伸縮表に追加するために、プログラムは最初に変数ｉにｘをセットして（図１３：１）、変数ｉをｙに達するまで増やしながら（図１３：２）、変数ｉで符号化される文字を伸縮表に登録してゆく（図１３：７）。その際に、変数ｉで符号化される文字が、マルチバイトキャラクタセット内の正しい文字符号であるかを判断するため、バイト長に分解された符号が、基底集合に属するか否かの判断を行う（図１３：５及び図１３：６）。【００７０】  範囲ｘ〜ｙを伸縮表から除録する処理では、範囲を要素に分解して繰り返し処理を行う。ここでは２バイトで符号化される文字を除録する場合（図１４）を例にする。始点文字ｘから終点文字ｙまでの範囲を伸縮表から除録するために、プログラムは最初に変数ｉにｘをセットして（図１４：１）、変数ｉをｙに達するまで増やしながら（図１４：２）、変数ｉで符号化される文字を伸縮表から除録してゆく（図１４：７）。その際に、変数ｉで符号化される文字が、マルチバイトキャラクタセット内の正しい文字符号であるかを判断するため、バイト長に分解された符号が、基底集合に属するか否かの判断を行う（図１４：５及び図１４：６）。【００７１】  文字ｃを伸縮表に登録する処理は、本発明の根幹を実現する部分である。ここでは２バイトで符号化される文字を登録する処理（図１５）を例にする。まず文字ｃを最初のバイトａと残りのバイトｂに分解する（図１５：１）。最初のバイトａがすでに符号集合Ａ（０）に含まれている場合、すでに文字ｃは伸縮表から構成されるＮＦＡ構造によって受理されるものになっているため、ただちに登録処理を終了する（図１５：２）。【００７２】  最初のバイトａがＡ（０）に含まれない場合、他の可能性を調べるために伸縮表を下にたどりながらａに一致するバイトをラベルａ（ｉ）の中に調べてゆく。これを行うために、変数ｉをまず１にセットし（図１５：３）、変数ｎに伸縮表の最大行番号をセットする（図１５：４）。【００７３】  もしａがａ（ｉ）と一致すれば（図１５：６）、残る部分ｂについてそれを表のｉ番目に追加する処理を行う（図１５：８）。もしａと一致するａ（ｉ）がどこにもなければ、新たな構造（ａ，｛ｂ｝）を伸縮表に追加する処理を行う（図１５：１２及び１３）。【００７４】  いずれの場合も、構造を追加した結果、残りの部分が飽和すれば（図１５：９）、符号集合Ａ（０）に最初のバイトａを加え（図１５：１０）、飽和した構造を破棄する（図１５：１１）。【００７５】  文字ｃを伸縮表から除録する処理は、文字ｃを伸縮表に登録するルーチンと並んで本発明の根幹をなす。ここでは２バイトで符号化される文字を除録する処理（図１６）を例にする。まず文字ｃを最初のバイトａと残りのバイトｂに分解する（図１６：１）。最初のバイトａがまだ符号集合Ａ（０）に含まれていない場合、すでに文字ｃは伸縮表から構成されるＮＦＡ構造によって受理されないものになっているため、ただちに除録処理を終了する（図１６：２）。【００７６】  最初のバイトａがＡ（０）に含まれている場合、他の可能性を調べるために構造を下にたどりながらａに一致するバイトをラベルａ（ｉ）の中に調べてゆく。これを行うために、変数ｉをまず１にセットし（図１６：３）、変数ｎに伸縮表の最大行番号をセットする（図１６：４）。【００７７】  もしａがａ（ｉ）と一致すれば（図１６：６）、残る部分ｂについてそれを表のｉ行目から削除する処理を行う（図１６：８）。もしａと一致するａ（ｉ）がどこにもなければ、Ａ（０）からａを削除し（図１６：１１）、新たな構造（ａ，Ｓ（２，２）＼｛ｂ｝）を表に追加する処理を行う（図１６：１２及び１３）。【００７８】  いずれの場合も、構造を削除した結果、残りの部分が空になってしまえば、その構造はどのようなバイト列も受理しないものになっていて不要なため、構造を削除する（図１６：１０）。【００７９】  肯定文字クラス及び否定文字クラスの処理において、伸縮表を完成したら、それをＮＦＡ構造に変換する（図１２：１３及び図１２：２５）。この作業は、表に必要な要素を補うことによって行う。ｍを最終的な表の最大行番号だとすると、０番目からｍ−１番目までの行の左側状態には、すべて下向きのリンクを付け、１番目からｍ番目までの行の右側状態には、すべて上向きのリンクを付ける。０番目からｍ番目までのすべての行の左側状態から中間状態には右向きの矢印をつけ、中間状態から右側状態には右向きの矢印をつける（図９）。【００８０】  肯定文字クラス及び否定文字クラスの処理において、各バイト長毎のＮＦＡ構造を構成したら、それぞれの構造を左端と右端で結合し、各バイト毎のＮＦＡ構造を分枝に持つＮＦＡ構造を構築し、出力する（図１２：１４及び図１２：２６）。結合は、マルチバイト文字セットの最大符号長に応じた図式に従い、１バイトの場合（図５：１）、２バイトの場合（図５：２）、３バイトの場合（図５：３）、４バイトの場合（図５：４）に応じた形を使用する。【００８１】  任意文字記号と、文字クラス記号列に対応するＮＦＡ構造は、再帰下降型構文解析機によって、正規表現の他の部分に対応するＮＦＡ構造と組み合わせて使用し、最終的に正規表現全体の翻訳であるＮＦＡ構造を決定する。
【図面の簡単な説明】
【００８２】
【図１】  正規表現エンジンの構成
【図２】  正規表現構文解析機の文法流れ図（１）
【図３】  正規表現構文解析機の文法流れ図（２）
【図４】  任意文字記号に対して与えるＮＦＡ構造
【図５】  文字クラス記号列に対して与えるＮＦＡ構造
【図６】  肯定文字クラスの場合に与える初期構造
【図７】  否定文字クラスの場合に与える初期構造
【図８】  文字クラス記号列の構造構築に使う伸縮表
【図９】  伸縮表からＮＦＡ構造への変換
【図１０】  最大符号長が２バイトのマルチバイト文字セットの文字クラス記号列に対して与えるＮＦＡ構造
【図１１】  任意文字記号を処理してＮＦＡ構造を出力する流れ図
【図１２】  文字クラス記号列を処理してＮＦＡ構造を出力する流れ図
【図１３】  範囲ｘ〜ｙを伸縮表に登録する流れ図
【図１４】  範囲ｘ〜ｙを伸縮表から除録する流れ図
【図１５】  文字ｃを伸縮表に登録する流れ図
【図１６】  文字ｃを伸縮表から除録する流れ図
【図１７】  マルチバイト文字セットの文字を処理する基本流れ図
【図１８】  各マルチバイト文字セットの基底集合
【符号の説明】
【００８３】１００  正規表現コンパイラ
１１０  ＮＦＡ・ＤＦＡ変換機
２００  ＮＦＡ用正規表現エンジン
３００  ＤＦＡ用正規表現エンジン
【図１】
2007102744.tif 000005
【図２】
2007102744.tif 000006
【図３】
2007102744.tif 000007
【図４】
2007102744.tif 000008
【図５】
2007102744.tif 000009
【図６】
2007102744.tif 000010
【図７】
2007102744.tif 000011
【図８】
2007102744.tif 000012
【図９】
2007102744.tif 000013
【図１０】
2007102744.tif 000014
【図１１】
2007102744.tif 000015
【図１２】
2007102744.tif 000016
【図１３】
2007102744.tif 000017
【図１４】
2007102744.tif 000018
【図１５】
2007102744.tif 000019
【図１６】
2007102744.tif 000020
【図１７】
2007102744.tif 000021
【図１８】
2007102744.tif 000022