Show HN: テキスト編集のための Transductive 正規表現

 (github.com/c0stya)
1 ポイント 投稿者 GN⁺ 2025-02-09 | 1件のコメント | WhatsAppで共有

  • TRRE: 変換正規表現

  • 要約
    • テキスト編集や grep に似たコマンドラインツール向けの正規表現の拡張。
    • プロトタイプなので、実運用では使用しないこと。

  • 紹介

    • 正規表現は、テキスト内のパターンを検索するのに便利なツール。
    • テキスト編集には不自然だと感じられるため、拡張を提案する。
    • 変換正規表現、または trre と呼ぶ。
    • : 記号を使って変換を定義する。
    • a:b は a を b に置き換える最も単純な形式。
    • trre というコマンドラインツールを作成し、この概念を実演している。

  • 例

    • 基本

      • cat を dog に変更: 
        $ echo 'cat' | trre 'c:da:ot:g'
dog
      • sed のように、文字列内のすべての一致を置換: 
        $ echo 'Mary had a little lamb.' | trre '(lamb):(cat)'
Mary had a little cat.
      • 削除: 
        $ echo 'xor' | trre '(x:)or'
or
      • 挿入: 
        $ echo 'or' | trre '(:x)or'
xor

    • 変換による正規表現

      • 選択 を使用: 
        $ echo 'cat dog' | trre 'c:bat|d:hog'
bat hog
      • スター を使って変換を繰り返す: 
        $ echo 'catcatcat' | trre '((cat):(dog))*'
dogdogdog

    • 範囲変換

      • 文字範囲の変換: 
        $ echo "regular expressions" | trre "[a:A-z:Z]"
REGULAR EXPRESSIONS

    • ジェネレーター

      • trre は単一の入力に対して複数の出力文字列を生成できる。
      • 2進シーケンス: 
        $ echo '' | trre -ma ':(0|1){3}'
000  001  010  011  100  101  110  111

  • 言語仕様

    • trre は パターンマッチング:パターン生成 の組として定義される。
    • パターンマッチング は文字列または正規表現になれる。
    • パターン生成 は通常は文字列だが、regex にすることもできる。

  • なぜ動くのか

    • trre は 有限状態変換器 (FST) という特別なオートマトンを構築する。
    • FST は入力と出力の組を処理する。

  • 設計上の選択と未解決の問い

    • : の結合性、優先順位、暗黙のイプシロンなど、さまざまな決定が必要。

  • モードと貪欲性

    • trre は 2 つのモードをサポートする:
      • スキャンモード (デフォルト): 変換を順番に適用する。
      • マッチモード: 式に対して文字列全体を検証する。

  • 決定化

    • 非決定性オートマトンを決定性オートマトンに変換する過程が重要。

  • 性能

    • NFT (非決定的) 版は sed よりわずかに遅い。
    • 複雑な作業では、trre_dft (決定版) が sed より高性能になる可能性がある。

  • TODO

    • ERE 機能セットの完成、完全な Unicode サポート、効率的な範囲処理など。

  • 参考文献

    • Russ Cox の記事と Cyril Allauzen、Mehryar Mohri の論文から着想を得ている。

関連記事

1件のコメント

 
GN⁺ 2025-02-09
Hacker Newsのコメント

  • いいね、このプロジェクトの発展に期待

    • 演算子の優先順位が自然ではないと感じる
    • cat:dog が (cat):(dog) よりも ca(t:d)og と解釈されるのは奇妙

  • XFST (Xerox Finite-State Transducer) を推薦

    • 20年以上にわたって計算言語学で使われてきたツール
    • フィンランド語の形態素解析に FST を使う事例を聞いたことがある

  • 標準的な正規表現の代替として Rosie Pattern Language を推薦

    • グループのロジックで苦労する人にとって、保守しやすい代替になりうる
    • 関連リンク: GitLab, Rosie公式サイト

  • 1997年に有限状態変換器に関する論文を書いた経験を共有

    • テーマは形態素解析で、過小評価されていた分野だった
    • 構文について、 : が ab より強く結合するように設定するのが正しいのかと質問

  • 構造的置換を行うには十分ではないと感じる

    • 正規表現がマッチした部分に対して構文木を定義するのだから、木に対する一般的な変換を行えれば有用なはず

  • 正規表現がテキスト編集には不自然だという主張に疑問を持つ

    • プロジェクトの目的はこの主張に依存しているが、例がない
    • グループの使用でなぜ苦労するのか理解できない
    • 正規表現よりこのプロジェクトの文法が優れている理由を示す例が必要

  • Cコードがとてもきれいだと称賛

    • README の theory.pdf リンクが壊れており、修正が必要

  • * や + を使うなという助言に疑問を持つ

    • 文法はもっと複雑になるだろうが、これを許可しないほうがよいはず

  • 最初の例がおかしいと感じる

    • echo 'cat' | trre 'c:da:ot:g' の結果が奇妙
    • 構文木がどう構成されるのか理解しづらい
    • MS-DOS 時代の検索・置換のほうが直感的だと感じる

  • 例が本当にプログラムの出力なのか疑問

    • 文法の理解が足りないのかもしれないが、例が間違っているように見える
    • echo 'cat dog' | trre 'c:bat|d:hog' の結果がおかしい