私は正規表現の歴史と発展を研究しています。次のタイムラインが見つかりました。
- 1956 - Kleeneはニューラルネットワークに関する論文で正規表現を紹介します。
- 1964 - Brzozowsiは正規表現派生語の概念を導入しました。
- 1968 - Thompson が正規表現コンパイラを作成する方法を説明します。
- 1960年代後半/1970年代初頭
- ThompsonはQEDエディタをCTSSに移植し、正規表現のサポートを追加しました。
- ThompsonとRitchieはQEDをMulticsに移植し、最終的に1970年代にはUnixに移植しました。
- ThompsonはQEDに触発され、エドを書きました。
- Unix V1以降、Thompsonはedから正規表現コードを抽出してgrepを作成しました。
- Unix V7では、egrepとfgrepが導入されました。
KleeneとBrzozowskiは正規表現と同じですが、異なる定義を持っています。
私が混乱しているのは、edの交代（2つの正規表現の1つと一致）で何が起こっているのかです。 Kleene、Brzozowski、Thompsonの論文にはシフトが含まれています。 QEDでは、Thompsonの正規表現の実装には置換が含まれていますが、edはそうではありません。初期のgrepも同様でした。
私にとってもっと奇妙なことは、edが正規表現に逆参照サポートを導入したことです。つまり、正規表現は(a.c)\1一致しますabcabcが一致しませんabcadc。逆参照を使用すると、edとgrepは一部の非伝統的な言語を認識できますが、置換が不足していることは、一部の一般言語を認識できないことを意味します。
Thompsonがqedとedの交互にサポートを削除したのはなぜですか？逆参照は追加されますが、代替は追加されません。
ベストアンサー1
Dennis Ritchieは次のような短い記事を書いたことがあります。QEDテキストエディタの不完全な歴史。本文で私たちが読むことができるもの
「標準UNIXエディタ」は
edもともとKen ThompsonがPDP-7用に作成しました。デフォルトのテキスト行方向を維持しますが、演算子のみを含めるように正規表現を基本的に単純化します*。つまり、シフトや括弧はありません。私のQEDには文脈のない言語がたくさん含まれていますが、このバージョンはすべての一般言語でさえ表現することはできません。損失は大きくありません。同様に、KenのUnixは
edマルチバッファとバッファ実行の概念をあきらめました。 Unixの将来のバージョンed（現在はCで書かれています）には、いくつかの複雑さが追加され始めました（たとえば、「正規」表現の逆参照は現在、すべての一般言語または文脈自由言語をカバーするわけではありませんが、文脈検出言語を侵害しています。 ）。
この短い段落では、ケンの主な関心事はどのようにed使用するのかがわかります。仕事を終える、実際には使用されていない正規表現を実装しようとする代わりに。これ」損失は大きくありません。「おそらく、ケンが本文に個人的にアクセスしたという信号です。必要変更または逆参照（少なくとも絶望的ではない）。
ギルスもそうです。コメントとして指摘する、代替実装は遅く、比較的メモリ集約的である可能性がありますが、逆参照は異常な状況で遅くなる可能性があるため、限られたハードウェアで逆参照が実装される可能性が高くなります。
開発の初期に、UNIXチームが使用したPDP-7は8kワードのメモリを持ち、KenがQEDバージョンを実装したMulticsシステムは64kワードのメモリを持つシステムで実行されました。これは、ed元の実装に非常に基本的なパターンマッチング機能しかなかった別の理由である可能性が高いです。
要約：2つの理由があるかもしれません。
- 制限されたハードウェア（PDP-7）のため、インターリーブや逆参照などを実装することは不可能または面倒です。
- エディタの目的には、実際に完全な正規表現構文は必要ありません。より強力なハードウェア（PDP-11）に移動し、逆参照がエディタに再追加されましたが、その時点でエディタのユーザー間で変更が必要ないことがあります。