FE基礎理論 · 情報に関する理論

正規表現

Regular Expression

せいきひょうげん

文字列のパターンを表現するための記法。特殊文字（メタキャラクタ）を使って文字列の検索・置換・抽出を行う。正規言語に対応し、有限オートマトンで認識できる。

共有:

他の資格での定義

文字列のパターンを記述するための形式言語。メタ文字（*, +, ?, [], |など）を用いてパターンを定義し、文字列の検索・置換・検証に利用される。正規言語と等価であり、有限オートマトンで認識可能。

Past Exams

過去問で 1 回出題（基本情報技術者試験 1）

出典: 独立行政法人情報処理推進機構（IPA）の過去問題。問題文は IPA のサイトの PDF で確認できます。用語名で照合しているため、関係の薄い問題が含まれることがあります。

プログラム言語などの形式言語の文法を記述するためのメタ言語。非終端記号、終端記号、生成規則で構成され、言語の構文規則を厳密に定義できる。コンパイラの構文解析で使用される。

入力に応じて状態が遷移する抽象的な計算モデル。有限オートマトンは有限個の状態を持ち、正規言語の認識に対応する。状態遷移表や状態遷移図で動作を表現する。コンパイラの字句解析などに応用される。

演算子を被演算子の後に記述する数式の表記法。後置記法とも呼ばれる。例えば「A+B」は「AB+」と書く。括弧が不要で、スタックを使って効率的に計算できるため、コンパイラの中間表現に使われる。

感染や複製のたびに自身のコードを異なる鍵で暗号化するなどして外見を変化させ、パターンマッチングによる検知を逃れるマルウェア。暗号を解く復号ルーチンは変わらないため、そこを手掛かりにしたり、実行時の振る舞いを調べたりして検知する。

文字列の検索、照合、置換、比較などを行うアルゴリズム。長い文字列の中から特定のパターンを探す文字列照合では、1文字ずつずらして比べる力まかせ法のほか、不一致の情報を使ってずらす幅を大きくするKMP法やBM法がある。