正規表現

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

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

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

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

プログラミング言語の構文を形式的に記述するためのメタ言語記法。非終端記号を::=で定義し、|で選択肢を示す。コンパイラの構文解析器の設計やプロトコル仕様の記述に広く使用される。拡張BNF（EBNF）はさらに繰返しや省略の記法を追加。

演算子をオペランドの後に置く数式の表記法（後置記法）。括弧が不要でスタックを用いて容易に評価でき、コンパイラの中間コード生成や電卓の実装に利用される。例：「3 4 + 5 *」は(3+4)*5を表す。