『詳説 正規表現 第2版』 を読む
lemonadernスクラップの概要
『詳説 正規表現 第2版』 を読むので、その感想などを残す
- スクラップに章ごとに感想をまとめている人を見て、良さそうだな〜と思ったので試してみる
- なぜ読むのか・どこに注目したいのかなども書き起こしておいて、読む指針として使いたい（なにせ分厚い本なので...）
lemonadern読む前の知識
- 正規表現の経験は、簡単なものをググりながらなんとか書くレベル
- 最近オートマトンや形式文法・言語に入門した
なぜ読もうと思ったのか
- 有限オートマトンの活用場所としての正規表現（エンジン）について知りたくなった
- 目次をみる限り4章がそういう話っぽいので楽しみ
- 正規表現の具体的な記法を習得したい！という感じではない
なぜいま(第3版でなく)第2版なのか
学校からの借り物だから。
一応 diff が気になって調べたけど、
第3版では、前版のJavaと.NETに加え、新たにPHPの章が追加された。
https://www.oreilly.co.jp/books/9784873113593/
とあって、自分の読みたいところとはあまり関係ないので気にしなくていいかなと思っている
lemonadern関係ないけど、この本の発行年を見たら俺と同い年だった。歴史...
lemonadernはじめに
"本書を最大限に活用するには、まず、6章までを読み物として読んでほしい" とある。
構成は、
- 1~3章：正規表現への導入
- 4~6章：正規表現についての詳細な解説
- 7~9章：各言語の正規表現（パッケージ）についての解説
となっているらしい。章立てがわかりやすくて助かる。
lemonadern第1章
概要
正規表現への導入をする章。
はじめに正規表現の考え方や、リテラル・メタ文字などの説明がなされる。
その後は、メタ文字や文字クラスの使い方を説明しながら egrep を用いて正規表現の例を見ていく感じになっている。
感想
正規表現に完全入門するにはちょうどいい章だった。
この本では、正規表現を「テキストを便利に操作するための(?)汎用パターン言語およびその表現」くらいのニュアンスで説明している。
形式言語を先に入門したせいで「正規表現は正規文法というか正規言語を扱うやつなんだろうな〜」などと思い込んでいたものの、どうやらそういうわけではないみたい。なんか普通に文字列ごと記憶してるやつとか出てくるし（後方参照?）。別に詳しくないが、そういう言語は有限オートマトンでは受理できないことくらいはわかるよ！
いちおう p4 の脚注では
「正規表現」という言葉は代数学からきている。
と触れられているものの、第1章ではそれっきりだった。4章で触れるらしいので期待。
ところで egrep て何？俺は grep しか使ったことがないんだけど何が違うんだろうか
調べたこと
正規表現と正規・正則言語
Wikipedia 正規表現 の説明を読んでみると、
もともと正規表現は形式言語理論において正規言語を表すための手段として導入された。
その後正規表現は単機能の文字列探索ツールやテキストエディタ、ワードプロセッサなどのアプリケーションで、マッチさせるべき対象を表すために使用されるようになり、表せるパターンの種類を増やすために本来の正規表現にはないさまざまな記法が新たに付け加えられた。このような拡張された正規表現には正規言語ではない文字列も表せるものも多く、ゆえに正規表現という名前は実態に即していない面もあるが、伝統的に正規表現と呼ばれ続けている。
とある。最初は正規言語を表すために使っていたものの、次第に便利な表現・機能が追加された結果、現在では一般に正規表現が扱う言語は正規言語に限らないらしい。なるほど。
egrep
egrep は extended grep らしい。知らなかった。
tldr egrep
~> tldr egrep
egrep
Find patterns in files using extended regular expression (supports ?, +, {}, () and |).
More information: https://manned.org/egrep.
- Search for a pattern within a file:
egrep "search_pattern" path/to/file
- Search for a pattern within multiple files:
egrep "search_pattern" path/to/file1 path/to/file2 path/to/file3
- Search stdin for a pattern:
cat path/to/file | egrep search_pattern
- Print file name and line number for each match:
egrep --with-filename --line-number "search_pattern" path/to/file
- Search for a pattern in all files recursively in a directory, ignoring binary files:
egrep --recursive --binary-files=without-match "search_pattern" path/to/directory
- Search for lines that do not match a pattern:
egrep --invert-match "search_pattern" path/to/file
違う本の話だけど、そういえばこれ κeen さんのブログに出てきた
あとegrepを使ってる。 奴は互換性のためだけに残された非推奨コマンドで、実体は grep -Eだ。古のシェルスクリプトでもない限りgrep -Eを使え。絶対許さない。
https://keens.github.io/blog/2015/05/10/seikihyougengijutsunyuumonwoyonda/
GNU grep のドキュメントをみると
- What happened to egrep and fgrep?
7th Edition Unix had commands egrep and fgrep that were the counterparts of the modern ‘grep -E’ and ‘grep -F’. Although breaking up grep into three programs was perhaps useful on the small computers of the 1970s, egrep and fgrep were not standardized by POSIX and are no longer needed. In the current GNU implementation, egrep and fgrep issue a warning and then act like their modern counterparts; eventually, they are planned to be removed entirely.
https://www.gnu.org/software/grep/manual/grep.html
らしい。なるほど。
egrep の位置づけ完全に理解しました。
lemonadern第2章
概要
Perl を使って、正規表現を利用したいろんなテキスト操作の紹介をする章。
この章では、Perl の正規表現を利用したテキスト操作を実際に行いながら、
- 後方参照
- 量指定子
- 前後読みとその肯定・否定
- 検索・置換
などの機能についての説明をする。
感想
電車で半分寝ながら読んでた気がする
実例とともに機能の説明がなされていたので結構わかりやすかった。Perl を書いたことがないので大丈夫かなと思っていたものの、正規表現中心なので Perl わかんなくても全然問題なかった。
この章（第2章）は、正規表現を使うイメージをつけるための章という感じ。今まで VSCode で Ctrl + F して全体一致・置換しかしたことなかった脳筋みたいな俺でも正規表現できそうという気分になった。
以下はその他感想
-
s/target/replacement/が出てきたときは、「これTwitterで誤字した人がやるやつだ！」となった。なんなら一番みる正規表現はこれかもしれない。初心者すぎて恥ずかしいぜ - 量指定子
*や+が表す量（数）は、語の集合を表すときの\sum {^*} \sum {^+}
lemonadern第3章
概要
正規表現を取り巻く環境や事情について知ることができる章。
「正規表現の種類と機能」と題して、正規表現の歴史や各種ツールが持っている背景についての説明がなされる。各環境における正規表現の扱われ方や各々の差異・注意点などについての説明もある。
他にも、
- 正規表現における文字列
- エンコーディングと正規表現
- マッチモード
- よく使われるメタ文字
の解説などがある。
感想
正規表現の使い方が知りたくて読んでいるわけではないのと、文字列の文脈で出てくる言語（Perl, .NET, Java, PHP, Python など）は普段全く使わないので興味が湧かなかったというのもあり、適当に読みながした。
最低限、「正規表現と一口に言っても様々な実装や事情があって、ものによって全然違うよ」ということだけ分かればいいかなと思う。
読めてよかったのは正規表現の歴史の話と、Unicodeの話。
歴史
この本によると、1940年代に二人の神経生理学者が”神経系統の機能を示すモデル”を示し、ある数学者がそのモデルの形式を「正則集合」と名付けた代数(?)によって記述したという。その数学者は、正則集合を表現する表記法を考案し、それを正則表現 Regular Expressions と名付けた。
その後正規表現がコンピュータに応用されるようになり、UNIX のエディタである qed, ed へとつながっていったらしい。ed で使えた "Global Regular Expression Print" という機能がユーティリティになったのが grep らしい。へーーー。
その後もいろんなツールが生まれ進化していったが、正規表現の表記法には規格がなかったので状況は混沌としていった。
そんな状況を整理すべく、POSIX では BRE (Basic Regular Expressions) と ERE (Extended Regular Expressions) が定められたらしい。
本文では、 "本書で解説する各種正規表現の中で、 POSIXに厳密に準拠しているものは1つもない。" とも言っている。まあそんなものだよな。
その後はPerl などのプログラミング言語の機能としても使われるようになり、いろんな機能がいろんな記法で追加されていきましたよーという感じだった。
オートマトンの話が出てくるかと思ったけど出てこなかった。正直最初の神経がどうとかはちょっとよくわからないので、言語理論との関係と歴史を知りたいなーと思った。まあ、便利だったから開発されて広まっていったことは分かったので、正規表現で扱うものが正規言語に収まらないのも納得がいくなと思った。理論より利便性重視みたいな。
2023-01-05 追記: この辺の歴史、この記事によくまとまってた！ありがたい！
Unicode
エンコーディングの文脈でUnicodeの話が出てきた。この辺の話は、何をもって「文字」だと考えるかが難しいという話だと理解している。1文字 と簡単に言っても難しいんだよね。
正規表現の Unicode 対応は大変みたいな話はよく聞くので、このへんにフォーカスした話はもうちょい知りたいかな。その前に文字コードをちゃんと理解する必要があるけど。
このへんを踏まえるとしたら、正規表現技術入門とか文字コード技術入門らへんを読むのが良さそうかなーと思った。
lemonadern4章
4章は思ったことが多いのでスレッドの外に。感想も節ごとに述べる。
1~3章に比べると突然内容が重くなった。でもオートマトンの勉強をしてる人なら中身の動作や性質の想像がしやすいと思う。
lemonadern4.1節
車の例を使って、正規表現の中身をなんとなく説明しながら分類しようとしてくれる。DFA・NFA・POSIX NFA・ハイブリッド の4つに分けていた。
感想
具体的な中身の話をしていないので内容については「はい、そうですか」って感じなんだけど、DFAやNFAが何か知らない人に対して、その中身を解説することなく分類を説明しようとするとこうなるんだーと思って勉強になった。
特に、『電気自動車が排気ガスの排出基準を満たしているとしたら、それは特別な電気自動車であることを示しているのではなく原理的なクリーンさを「祝福」しているだけである』という話とかは興味深い例えだった。本文では、この例からDFAとPOSIXの話に持っていってた。
lemonadern4.2節
正規表現が行うマッチの基本原則について。
最初のマッチが優先されることと、量指定子の標準動作は欲張りであることを説明する。
感想
これは読めばわかる。たしかにそう動いてるなと思った。
lemonadern4.3節
NFAエンジンとDFAエンジンをそれぞれ「正規表現制御型」と「テキスト制御型」と名付け、マッチ動作とその特徴について解説・比較する。
感想
正規表現の選択要素をどうマッチするかを例に挙げて説明していたのだけど、これをオートマトンの動作と比較して考えてみると少し面白かった。
本文ではオートマトンについての説明を行っていないので、説明としてはどうしても元の正規表現から離れることなく（つまり、「今は正規表現のこの部分を使っていますよー」という形式を保ったままで）説明せねばならない。
先に言ってしまえば、両者の違いとして、選択要素があるときに「ひとつずつの選択肢を最後まで検証する」NFAエンジンに対して、「選択肢の重複部分を平行に確認しながらマッチを検証する」DFAエンジンという違いがある、という説明がなされている。
ではこの説明をNFAエンジンはnfaと、DFAエンジンはdfaの動作とそれぞれ比較してみる。
NFAエンジンの方は非決定性有限オートマトン自体の動作と大した相違はないので、ほとんどそのまま説明すればいい。選択要素は一つづつ見ていき、マッチしなかったら戻って他の候補を試す。この動作は、nfaが言語を受理しないことを示すためにありうる様相すべてを検証することとほとんど同じだと思う。
ではDFAエンジンについて。この本では、DFAエンジンを "文字列をスキャンしながら「そのとき実行している」あらゆるマッチを管理するタイプ" のエンジンと説明している。対象文字列をひと文字スキャンするたびに、（もとの正規表現から抽出された）マッチする可能性のある正規表現からなる「マッチ候補リスト」が更新されるのだと。1文字読むたびに「マッチ候補」が更新され（合わないものは除外され）、候補のいずれかにマッチすればマッチ成功となる、という説明である。著者はこれを「テキストからスキャンされる各文字がエンジンを制御する」という意味でテキスト制御型と呼んでいる。
DFAエンジンのこの説明は決定性有限オートマトンの動作の説明とはイメージが異なる。dfaでは複数の遷移を同時におこなっているわけではない。選択という動作が存在しなくて、実際には1つの入力には1つの遷移しかありえないからである。「マッチする選択肢が複数ありえる」とか「候補を平行に検証する」という状態はdfaのレベルではどう表現されるかというと、入力によって道が枝分かれしているか、道の途中が受理状態かのどちらかと考えることができる。
このことは、「dfaの動きを正規表現のレベルのまま説明するとそうなるんだー」という気づきがあって面白かった。
lemonadern4.4節
バックトラックについての説明。
バックトラックの概念について説明したあと、重要事項として
量指定子の対象になる要素に関して、「テストを行う」か「テストをスキップする」かを判断する状況に遭遇すると、エンジンはまず、欲張り量指定子についてはテストを行い、非欲張り量指定子についてはテストをスキップする。
局所的な失敗によってバックトラックが行われると、最も新しく保存された候補が選択される。つまりLIFO（Last In First Out）である。
の2つを述べている。そのあと貪欲さとバックトラックの観点から?, ?? および スター・プラスの挙動について解説するという流れ。
lemonadern4.5節 前半
「貪欲さについてもう少し学ぶ」と題されているように、貪欲さに関連する内容。
4.5.1~4.5.3
「クオートに囲まれた文字列」や「開きタグ・閉じタグ（=> 複数文字のクオート）に囲まれた文字列」をどうマッチさせるかを題材に、NFAの欲張りマッチ・非欲張りマッチについて説明する。
先読みの有用なユースケースも知れる。
4.5.4
「マッチ成功はマッチ不成功よりも常に優先される」ことの説明。
マッチ不成功は全ての経路が失敗しないとそれを認めず、これは欲張りかどうかは関係がない。
4.5.5
欲張りかどうかによって変わるのはマッチする「経路を試す順番」であるので、
- 不成功ならどちらも全ての経路が試される
- 成功マッチが1つなら欲張りかどうかによって結果は変わらない
ことがいえる。
成功マッチが1つの場合に両者の間で変わってくるのは「マッチに至るまでに試すパターンの数」であり、これが効率性の問題に繋がってくる。
そして、欲張り・非欲張り・バックトラッキングへの理解があれば、2つ以上のマッチが可能な場合にどれが選択されるかが分かるようになる。
感想
これはなかなか勉強になる。ここらへんの理解が甘いせいで書いた正規表現が意図した挙動をせず、「正規表現わからない or 難しい」となっている人多そう。まあ実際難しい。
lemonadern4.5 節 後半
引き続き貪欲さに着目しながら「アトミックなグループ」という考え方によってバックトラックの動作を制御する表現について学び、バックトラックの動作が制限されるという意味での前後読みについても触れる。
最後は貪欲さという観点から選択の動作を考え、「順序付き選択」についてとその扱い方を説明する。
4.5.6 ~ 4.5.7
アトミックなグループと、強欲な量指定子について。
具体的な問題から「自分がマッチしたときだけ、自分をスキップする経路を破棄する」ことはできないだろうか？（=> できますよ）という導入。
アトミックなグループと強欲な量指定子
アトミックなグループ (?>xxx) について。
括弧内にマッチして括弧を抜けた場合、括弧内で保存されていたステートが捨てられる。その先でマッチせずバックトラックすることがあっても、括弧内のパターンは1つとして扱われる。
不要な保存ステートを破棄してバックトラックを避ける目的で利用することができ、「マッチ失敗をより早く判定する」ユースケースが一般的。
強欲な量指定子 量指定子+ について。
(一般的には)アトミックなグループのシンタックスシュガーで、マッチ中にバックトラックを作成しないという動作をする。（シンタックスシュガーなので）これをアトミックなグループとして書き直すことができる。
前半で確認した「貪欲さよりもマッチ成功がいつでも優先される」という原則を（部分的にでも）崩すような実際の手段として、アトミックなグループと強欲な量指定子の紹介をしている。
4.5.8
前後読みは、それ以外の箇所とステートを共有しないという意味でアトミックなグループと関連があることを説明し、肯定の先読みを使うことでアトミックなグループを模倣する例について述べる。
4.5.9 ~ 4.5.10
各エンジンにおける選択の動作方法と、順序付き選択の注意点について。
選択は正規表現エンジンによって動作が異なることを述べ、書かれた順にテストする「順序つき選択」というものがあること、そして順序付き選択においては選択肢の順序に注意を払う必要があることについて説明する。
また、短い文字列を先にマッチするならば非欲張り、長い文字列先にマッチしようとするならば欲張りであると言うことができ、DFAにおける選択は欲張りであるとの記載もある。
感想
4.5節だけでかなり重かった。ただマッチの貪欲さおよびバックトラッキングについての理解はかなり深まったと思う。
- 貪欲さの違いはバックトラッキングによってパターンを網羅する順番の違いであるということ
- バックトラッキングを制御することで「Atomic」な要素を考えることができること
- 前後読みはバックトラックの制限があるという意味でアトミックなグループと共通点があること
- 「選択の貪欲さ」というものを考えることができること
などを説明できる。点と点がいろんなところでつながるような内容で楽しい。
ただ、いままでこれを知らないで正規表現書いてたの怖いなとも思った。そんなに高度なものを書いてたわけではないけど。
lemonadern4.6 節
NFA・DFA および POSIXについての話。
DFAはその性質として最長最左(Longest-Leftmost)マッチをおこなう。一方でNFAはマッチすればそれで終わりなので、パターンが最長であるとは限らない。
POSIX標準では最左中の最長マッチを返すものと規定されているので、POSIX準拠のNFAを実装するならば、マッチを見つけたとしてもそれが最長であるかを確認せねばならず、マッチ不成功を判定するのと同じだけの時間がかかる。（原理的にはこうだが、実際はいろいろな最適化の工夫があるらしい）
各正規表現に出会ったときに一度だけ発生するオーバーヘッドを正規表現のコンパイルといい、DFAとNFAは、それぞれに適した内部表現にコンパイルをおこなう。
一般的にはこのオーバーヘッドは時間的にもメモリ的にもNFAのほうが少ない。
感想
あくまで正規表現の方面から説明しているから、それぞれのエンジンが「なぜそのような挙動をするのか」「なぜそのような性質をもつのか」に関してはうまく語れていない感じがする。（例えがたくさん使われていてかなりわかりやすいとは思う。）
でも（数学的な方の）DFA・NFAの知識があるとこのへんは納得感を持って読めるなと思った。
たとえば、DFAにおけるコンパイルがNFAのそれよりもオーバーヘッドが大きいのは、DFAエンジンの場合は正規表現をDFA（をプログラムとして表現したもの）に変換する作業があるのに対し、NFAエンジンは非決定的な動作をバックトラックによって実現するのが本質なので、NFAのエミュレート自体に凝った内部表現が必要ないということなんだろうなと想像できる。
これはそのまま、DFAのマッチスピードが正規表現と関係がないのに対してNFAのマッチスッピードは直接の関係があることの説明にもなる。
あまり詳しくは書いていなかったけど、DFAのコンパイル時オーバーヘッドを減らすために遅延評価を導入するケースがあるらしい。なんかすごそう。
あとは、コラムで数学的なNFAと正規表現エンジンにおけるNFAの話が書いてあった。正規表現はその機能の発展とともに、数学的な意味でのNFAの意味体系とは開きが生じたらしい。ユーザはどんな機能を持っているかだけに興味があり、扱う言語が regular であるかどうかには興味がないという話だった。納得。ここだけ一番最初に読んだほうがよかったかも。
lemonadern4.7 節 まとめ
4章まとめ。
コラムにDFAとNFAハイブリッド型のエンジンの話が書いてあった。
lemonadern4章までしか読んでいないけど、知りたいことは一通り知れたので一旦おわり。
また機会があれば再開する。