Fortranで正規表現 #正規表現

概要

Fortran Regular Expression (Forgex)という正規表現エンジンを作ったので公開しました。

Fortranコードから正規表現マッチングを行うことができます。

Fortranコードのみで記述したので、Fortranコンパイラ（とFortran Package Manager fpm）さえあれば利用可能です。他の外部の依存関係パッケージはありません。

Forgexについて

Forgexは正規表現を処理するライブラリモジュールです（筆者は"forge x"と読んでいます）。

実装されている機能

Forgexに実装されているもので特徴的な要素としては、UTF-8への対応があります。UTF-8のマルチバイト文字の処理をすることができるので、絵文字や日本語文字列の処理も可能です。

以下に実装されている機能を列挙します。

メタキャラクター

|（選択）
*（0回以上の繰り返し）
+（1回以上の繰り返し）
?（1個あるか、無いか）
\（エスケープ文字）
.（あらゆる1文字にマッチ）

文字クラス

文字クラス[a-z]
否定の文字クラス[^a-z]
UTF-8の文字クラス[α-ωぁ-ん]（否定クラスも可能）

位置へのマッチ

^（先頭にマッチ）
$（末尾にマッチ）

繰り返し回数の指定

{num} （繰り返し回数の指定）
{,max}（最大回数の指定）
{min,}（最低回数の指定）
{min, max}（最低・最高回数の両方を指定）
- 例：正規表現a{3,5}は文字列aaa, aaaa, aaaaaにマッチする。

バックスラッシュによる略記法

\t, タブ文字
\n, 改行文字（LF, CRLFにマッチ）
\r, 復帰文字（CRにマッチ）
\s, 任意の空白文字（半角スペース、改行・復帰文字、タブ文字、全角スペース(U+3000)にマッチ）
\S, \s以外のすべての文字
\w, [a-zA-Z0-9_]
\W, \w以外のすべての文字
\d, [0-9]
\D, \d以外のすべての文字（すなわち[^0-9]）

ライセンスについて

ForgexのGitHubのLICENSEページにある通り、MITライセンスで公開されているオープンソースソフトウェアです。ユーザーはこのコードを自由に利用、改変などすることができます。

Forgexの使い方

ビルド

Fortranパッケージマネージャーを使用することが前提になります（一応、CMakeでもビルドできます）。

最初に、あなたのプロジェクトのfpm.tomlに以下の記述を追加します。

[dependencies]
forgex = {git = "https://github.com/shinobuamasaki/forgex"}

API

プログラムの先頭でuse forgexを宣言すると、.in.と.match.の演算子とregex関数が導入されます。以下ではこの3つそれぞれの使い方を見ていきます。

.in.演算子は、パターン（左の項）が文字列（右の項）に含まれる場合に、真を返します。

block
   character(:), allocatable :: pattern, str

   pattern = 'foo(bar|baz)'
   str = "foobarbaz"
   print *, pattern .in. str  ! T

   str = "foofoo"
   print *, pattern .in. str  ! F
end block

.match.演算子は、パターンと文字列が完全に一致する場合に、真を返します。

block
   character(:), allocatable :: pattern, str

   pattern = '\d{3}-\d{4}'
   str = '100-0001'
   print *, pattern .match. str  ! T

   str = '1234567'
   print *, pattern .match. str  ! F
end block

regex関数は、パターンと文字列を引数に取り、一致した部分文字列を返す関数です。部分文字列は最左最長一致でマッチした文字列となります。

block
   character(:), allocatable :: pattern, str
   
   pattern = '[ぁ-ん]{7}'
   str = 'いろはにほへとちりぬるを'

   print *, regex(pattern, str)  ! いろはにほへと
end block

オプションで、文字列長が格納される整数型引数lengthを渡すこともできます。

block
   character(:), allocatable :: pattern, str
   integer :: length
   
   pattern = '[ぁ-ん]{7}'
   str = 'いろはにほへとちりぬるを'

   print *, regex(pattern, str, length)  ! いろはにほへと
   print *, length                       ! 21 (=3バイト*7文字)
end block

regex関数のインターフェースは次の通りです。

function regex (pattern, str, length) result(res)
   character(*), intent(in) :: pattern, str
   integer, intent(inout), optional :: length
   character(:), allocatable :: res

エンジンの実装について

正規表現エンジンの実装方法には大まかに決定性有限オートマトン（DFA）を用いる方式と、仮想機械を構築する方式がありますが、Forgexでは前者のDFAによるアプローチを採用しました。

この選択のため以下の機能は実装されません。

後方参照
再帰的パターン

また現段階では、on-the-flyのDFA構成のアルゴリズムは実装されていないため、状態数爆発の問題を回避できていません¹。そのため[a-z]{20}bのようなパターンは苦手な部類になります。

終わりに

最適化や並列処理への対応など、まだ課題はありますが、ひとまず必要な機能が揃ったので現時点での公開を選択しました。

Fortranは文字列の扱いが苦手、という話はちらほら聞きますが、このライブラリの公開によってあなたのFortran文字列処理の利便性が向上することを期待しています。

動作確認

Linuxにインストールされた、以下のコンパイラで動作を確認しています。

% gfortran --version
GNU Fortran (Gentoo 13.2.1_p20230826 p7) 13.2.1 20230826
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

% ifx --version
ifx (IFX) 2024.0.0 20231017
Copyright (C) 1985-2023 Intel Corporation. All rights reserved.

謝辞

"Regular Expression Matching Can Be Simple And Fast", Russ Cox, Jan. 2007
『定本　Cプログラマのためのアルゴリズムとデータ構造』、近藤嘉雪、1998年、SB Creative
- 以上の2つはForgexのエンジンの実装に際して参考にしました。
Fortran で priority queue を作ってみた、@ue1221 さん
- 優先度付きキューの実装を参考にしました (GItHub)。
Fortranでユーザー定義演算子.in.を作る、 @soybean さん
- .in.演算子を文字列に適用するというアイデアはこちらの記事にインスパイアされました。

DFAのon-the-fly構成のアルゴリズムに詳しい方、助言を頂きたいです。 ↩

Fortranで正規表現

概要