読み込み中...
読み込み中...
読み込み中...
読み込み中...
読み込み中...
プログラムが効率よくデータを処理するには、データをどのような形で保持するかが重要です。この「データの持ち方」を データ構造 と呼びます。
適切なデータ構造を選ぶことで、探索・挿入・削除などの操作が高速になり、プログラム全体の性能が大きく変わります。基本情報技術者試験では、各データ構造の 特徴 ・ 操作の計算量 ・ 使い分け が頻出テーマです。
ここでは、配列・連結リスト・スタック・キュー・木構造・ハッシュ・グラフの7つの基本データ構造を学びます。
配列 は、同じ型のデータを連続したメモリ領域に格納するデータ構造です。各要素には 添字（インデックス） でアクセスします。
要素が一列に並んだ最も基本的な配列です。
インデックス: [0] [1] [2] [3] [4]
値: 10 25 33 47 52
行と列の2つの添字で要素を指定する配列です。表やマトリクスの表現に使います。
列0 列1 列2
行0 [ 10, 20, 30 ]
行1 [ 40, 50, 60 ]
行2 [ 70, 80, 90 ]
メモリ上では1次元に展開されます。行優先（row-major） の場合、a[i][j] のアドレスは 先頭アドレス + (i × 列数 + j) × 要素サイズ で計算します。C言語やJavaは行優先、Fortranは列優先です。
| 操作 | 計算量 |
|---|---|
| 要素の参照（添字アクセス） | O(1) |
| 末尾への追加 | O(1) |
| 途中への挿入・削除 | O(n) |
| 探索（ソートなし） | O(n) |
連結リスト は、各要素（ ノード ）がデータと次のノードへの ポインタ（参照） を持つデータ構造です。メモリ上で連続している必要がなく、挿入・削除が高速です。
各ノードが「データ」と「次のノードへのポインタ」を持ちます。最後のノードのポインタは null です。
[10|→] → [25|→] → [33|→] → [47|null]
各ノードが「前のノードへのポインタ」「データ」「次のノードへのポインタ」の3つを持ちます。
null ← [←|10|→] ⇄ [←|25|→] ⇄ [←|33|→] ⇄ [←|47|→] → null
最後のノードが先頭ノードを指す構造です。単方向・双方向のどちらにも適用できます。
[10|→] → [25|→] → [33|→] → [47|→] ─┐
↑─────────────────────────────────────┘
| データ構造 | ランダムアクセス | 先頭への挿入 | 途中への挿入 | メモリ効率 |
|---|---|---|---|---|
| 配列 | O(1) | O(n) | O(n) | 高い |
| 単方向リスト | O(n) | O(1) | O(1)※ | 低い |
| 双方向リスト | O(n) | O(1) | O(1)※ | より低い |
※挿入位置のノードが既知の場合
スタック は LIFO（Last In, First Out: 後入れ先出し） のデータ構造です。お皿を積み重ねるイメージで、最後に入れたデータが最初に取り出されます。
基本操作:
push(10) → push(25) → push(33) → pop()
| | | | | | | |
| | | | | 33 | ←top| 25 | ←top
| | | 25 | ←top| 25 | | 10 |
| 10 | ←top| 10 | | 10 | └────┘
└────┘ └────┘ └────┘ 33を取得
スタックの応用例:
キュー は FIFO（First In, First Out: 先入れ先出し） のデータ構造です。行列に並ぶイメージで、最初に入れたデータが最初に取り出されます。
基本操作:
enqueue(10) → enqueue(25) → enqueue(33) → dequeue()
先頭→ [10] [10][25] [10][25][33] [25][33]
10を取得
キューの応用例:
通常のキューとは異なり、各要素に 優先度 が設定され、優先度の高い要素から先に取り出されます。内部実装には ヒープ がよく使われます。
木構造 は、ノード間に親子関係を持つ階層的なデータ構造です。最上位のノードを 根（root） 、子を持たないノードを 葉（leaf） と呼びます。
上図で青が根ノード、緑が葉ノードです。
基本用語:
| 用語 | 説明 |
|---|---|
| 根（root） | 最上位のノード。親を持たない |
| 葉（leaf） | 子を持たないノード。末端ノード |
| 深さ（depth） | 根からそのノードまでの辺の数 |
| 高さ（height） | そのノードから最も深い葉までの辺の数 |
| 次数（degree） | ノードが持つ子の数 |
| 部分木（subtree） | あるノードを根とする木 |
各ノードが 最大2つの子 を持つ木です。左の子を 左部分木 、右の子を 右部分木 と呼びます。
「左の子 < 親 < 右の子」という規則を持つ二分木です。上図はこの規則に従っています。
ヒープ は「親 ≧ 子」（最大ヒープ）または「親 ≦ 子」（最小ヒープ）の規則を持つ完全二分木です。
B木 は、1つのノードに 複数のキー を持ち、3つ以上の子を持てる 多分木 です。データベースのインデックスやファイルシステムで広く使われます。
二分木のすべてのノードを訪問する方法には3つの代表的な順序があります。
| 走査順序 | 訪問の順番 | 上図での結果 |
|---|---|---|
| 前順（preorder） | 根 → 左 → 右 | 50, 30, 20, 10, 40, 70, 60, 80 |
| 中順（inorder） | 左 → 根 → 右 | 10, 20, 30, 40, 50, 60, 70, 80 |
| 後順（postorder） | 左 → 右 → 根 | 10, 20, 40, 30, 60, 80, 70, 50 |
中順走査 で二分探索木をたどると、値が 昇順（ソート済み） に得られます。これは試験でよく問われるポイントです。
覚え方:
各走査は 再帰 で簡潔に実装できます。例えば中順走査は「左部分木を中順走査 → 根を処理 → 右部分木を中順走査」です。
このほか、木の各段を順に訪問する 幅優先走査（レベル順走査） もあり、キューを使って実装します。
ハッシュ は、キーから ハッシュ関数 を使って格納位置（ハッシュ値）を直接計算するデータ構造です。探索・挿入・削除がいずれも平均 O(1) で行えるため、高速なデータアクセスが必要な場面で使われます。
ハッシュ関数の例: h(key) = key mod テーブルサイズ
キー 23, 48, 35 をテーブルサイズ 10 で格納する場合:
異なるキーが同じハッシュ値を生成することを 衝突 と呼びます。例えば h(23) = 3 と h(33) = 3 は衝突です。衝突の解決方法には2つの代表的な手法があります。
| 手法 | 説明 | 特徴 |
|---|---|---|
| オープンアドレス法 | 衝突時に別の空き位置を探す | メモリ効率が良い。線形探査法では h(key)+1, h(key)+2... と順に探す |
| チェイン法（連鎖法） | 同じハッシュ値の要素を連結リストでつなぐ | 実装が容易。テーブルが満杯になりにくい |
オープンアドレス法では、データが密集するとクラスタリング（連続した位置が埋まる）が起き、性能が劣化します。チェイン法では連結リストが長くなると探索が O(n) に近づきます。
良いハッシュ関数の条件は、ハッシュ値が一様に分散する ことと、計算が高速 であることです。
グラフ は、頂点（ノード） と頂点間を結ぶ 辺（エッジ） からなるデータ構造です。ネットワーク、経路、関係性の表現に使います。
グラフの表現方法:
| 表現方法 | 説明 | 向いている場合 |
|---|---|---|
| 隣接行列 | 頂点数 n × n の2次元配列。a[i][j] = 1 なら辺あり | 辺が密なグラフ。辺の有無の判定が O(1) |
| 隣接リスト | 各頂点について、隣接する頂点のリストを持つ | 辺が疎なグラフ。メモリ効率が良い |
例: 4頂点の無向グラフ（0-1, 0-2, 1-3, 2-3）
隣接行列:
0 1 2 3
0 [ 0, 1, 1, 0 ]
1 [ 1, 0, 0, 1 ]
2 [ 1, 0, 0, 1 ]
3 [ 0, 1, 1, 0 ]
隣接リスト:
0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2]
ポイント
データ構造は目的に応じて使い分ける。配列 はランダムアクセス O(1) だが挿入・削除は O(n)。連結リスト は挿入・削除が O(1) だがランダムアクセスは O(n)。スタック は LIFO（push/pop）、キュー は FIFO（enqueue/dequeue）。二分探索木 は「左 < 親 < 右」で平均 O(log n) の探索。ヒープ は「親 ≧ 子」（or ≦）の完全二分木で優先度付きキューに使用。B木 はデータベースのインデックスに使われる多分木。木の 中順走査 で二分探索木をたどるとソート済みの値が得られる。ハッシュ は平均 O(1) の高速アクセス。衝突解決は オープンアドレス法 と チェイン法 。グラフ は隣接行列（密向き）と隣接リスト（疎向き）で表現する。
用語
アルゴリズム とは、問題を解くための手順を明確に定めたものです。同じ問題でもアルゴリズムによって処理速度やメモリ使用量が大きく異なります。
アルゴリズムの効率は 計算量（オーダー） で評価します。O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) の順に遅くなります。基本情報技術者試験では、代表的な探索・ソートアルゴリズムの 手順 ・ 計算量 ・ 特徴 を正確に理解することが求められます。
データの中から目的の値を見つけ出す処理です。
データを 先頭から順に 1つずつ比較して探す最も単純な方法です。
例: 配列 [10, 25, 33, 47, 52] から 33 を探索
ソート済み のデータに対して、中央の要素と比較し、探索範囲を半分に絞り込む方法です。
例: ソート済み配列 [10, 25, 33, 47, 52, 61, 78] から 61 を探索
線形探索なら6回かかるところを2回で発見できます。データ数が多いほど差は劇的に広がり、100万件でも約20回の比較で済みます。
ハッシュ関数でキーから格納位置を直接計算して探す方法です。
| 探索アルゴリズム | 計算量 | 前提条件 |
|---|---|---|
| 線形探索 | O(n) | なし |
| 二分探索 | O(log n) | ソート済み |
| ハッシュ探索 | O(1) 平均 | ハッシュテーブル |
データを昇順（または降順）に並べ替える処理です。まず計算量 O(n²) の基本的なソートを学びます。
隣接する要素を比較し、順序が逆なら交換する操作を繰り返します。大きい値が泡のように「浮かんでいく」イメージです。
例: [5, 3, 8, 1] を昇順にソート
1回目のパス:
2回目のパス:
3回目のパス:
未ソート部分から 最小値を見つけて 先頭と交換する操作を繰り返します。
例: [5, 3, 8, 1] を昇順にソート
未ソートの要素を、ソート済み部分の 正しい位置に挿入 していく方法です。トランプの手札を整列するイメージです。
例: [5, 3, 8, 1] を昇順にソート
計算量 O(n log n) のソートアルゴリズムです。
基準値（ピボット） を選び、データをピボットより小さいグループと大きいグループに 分割 し、それぞれを再帰的にソートします。
データを半分ずつ分割し、各部分をソートしてから マージ（併合） する方法です。
データを ヒープ に構築し、根（最大値）を取り出す操作を繰り返します。
| アルゴリズム | 最悪 | 平均 | 最良 | 安定性 | 追加メモリ |
|---|---|---|---|---|---|
| バブルソート | O(n²) | O(n²) | O(n) | 安定 | O(1) |
| 選択ソート | O(n²) | O(n²) | O(n²) | 不安定 | O(1) |
| 挿入ソート | O(n²) | O(n²) | O(n) | 安定 | O(1) |
| クイックソート | O(n²) | O(n log n) | O(n log n) | 不安定 | O(log n) |
| マージソート | O(n log n) | O(n log n) | O(n log n) | 安定 | O(n) |
| ヒープソート | O(n log n) | O(n log n) | O(n log n) | 不安定 | O(1) |
試験のポイント:
関数が自分自身を呼び出すことを 再帰 と呼びます。再帰には必ず 基底条件（再帰を止める条件） が必要です。
フィボナッチ数列:
単純な再帰実装では同じ計算を繰り返すため O(2ⁿ) ですが、メモ化 （計算結果を記憶）で O(n) に改善できます。
ハノイの塔:
| 手法 | 概要 | 代表例 |
|---|---|---|
| 分割統治法 | 問題を小さく分割し、各部分を解いて結合 | クイックソート、マージソート、二分探索 |
| 動的計画法 | 部分問題の解をメモ化し、重複計算を回避 | フィボナッチ、ナップサック問題、最短経路 |
| 貪欲法（グリーディ法） | その時点で最良の選択を繰り返す | ハフマン符号化、クラスカル法 |
| バックトラッキング | 候補を試し、行き詰まったら戻って別の候補を試す | 8クイーン問題、数独 |
分割統治法 と 動的計画法 の違いは、部分問題に 重複 があるかどうかです。重複がない場合は分割統治法、重複がある場合は動的計画法（メモ化）が有効です。
テキスト中からパターン文字列を見つけ出すアルゴリズムです。
| アルゴリズム | 概要 | 計算量 |
|---|---|---|
| 力まかせ法（Brute Force） | テキストの各位置からパターンを1文字ずつ比較 | 最悪 O(n×m) |
| BM法（Boyer-Moore法） | パターンの末尾から比較し、不一致時にパターンをずらす量を最大化 | 平均 O(n/m) |
BM法は不一致文字がパターン中にない場合、パターン長 m だけ一気にずらせるため、実用上非常に高速です。テキストエディタの検索機能などで広く使われています。
ポイント
探索は 線形探索 O(n)、二分探索 O(log n)（要ソート済み）、ハッシュ探索 O(1) の3つ。ソートは O(n²) の基本3種（バブル・選択・挿入）と O(n log n) の高速3種（クイック・マージ・ヒープ）を区別する。安定ソート はバブル・挿入・マージ。クイックソートは平均最速だが最悪 O(n²)。再帰には 基底条件 が必須で、メモ化 で効率化できる。アルゴリズム設計手法は 分割統治法 （重複なし）・ 動的計画法 （重複あり、メモ化）・ 貪欲法 ・ バックトラッキング の4つ。文字列探索では BM法 がパターン末尾から比較し平均 O(n/m) で高速。
用語
プログラム とは、コンピュータに実行させる命令の集まりです。プログラムの作成（ プログラミング ）にはデータの扱い方、処理の流れの制御、コードの構造化など、さまざまな知識が必要です。
基本情報技術者試験では、特定のプログラミング言語に依存しない プログラムの基本構造 と 設計の考え方 が問われます。ここではプログラムの基本から、オブジェクト指向、テスト手法まで体系的に学びます。
あらゆるプログラムは、以下の 3つの基本構造 の組み合わせで表現できます。これを 構造化定理（ベーム-ヤコピーニの定理） と呼びます。
| 構造 | 説明 | 例 |
|---|---|---|
| 順次（sequence） | 上から下へ順番に処理を実行 | 代入、計算、出力 |
| 選択（selection） | 条件によって処理を分岐 | if文、switch文 |
| 繰返し（iteration） | 条件が成立する間、処理を繰り返す | for文、while文 |
この3構造だけであらゆるアルゴリズムを記述できるため、goto文のような無条件分岐を使わずにプログラムを書くことが推奨されます（ 構造化プログラミング ）。
変数 は、データを一時的に格納する名前付きの領域です。変数にはそのデータの種類を示す データ型 があります。
| データ型 | 説明 | 例 |
|---|---|---|
| 整数型（int） | 整数値を格納 | -5, 0, 42 |
| 浮動小数点型（float/double） | 小数を含む数値 | 3.14, -0.001 |
| 文字型（char） | 1文字を格納 | 'A', '7' |
| 文字列型（string） | 文字の並びを格納 | "Hello" |
| 論理型（boolean） | 真（true）か偽（false） | true, false |
変数の値が変更できない場合は 定数 と呼びます。プログラム中のマジックナンバー（意味不明な数値）は定数として名前を付けるのがよい設計です。
プログラミングにおける 配列 は、同じデータ型の値を連続して格納し、添字（インデックス）でアクセスする仕組みです。多くの言語でインデックスは 0 から始まります。
// 配列の宣言と初期化（疑似コード）
scores[5] = {85, 72, 93, 68, 91}
scores[0] → 85
scores[3] → 68
ポインタ は、メモリ上のアドレス（番地）を格納する変数です。C言語で重要な概念です。
アドレス 値
0x1000 42 ← 変数 x
0x2000 0x1000 ← ポインタ p（xのアドレスを保持）
ポインタを使うことで:
関数（サブルーチン） は、特定の処理をまとめて名前を付けたものです。処理の再利用性と可読性を高めます。
| 渡し方 | 説明 | 影響 |
|---|---|---|
| 値渡し（call by value） | 引数の値のコピーを渡す | 関数内で変更しても呼び出し元に影響しない |
| 参照渡し（call by reference） | 引数のアドレス（参照）を渡す | 関数内で変更すると呼び出し元も変わる |
スコープ（有効範囲） とは、変数が参照できる範囲のことです。
関数が自分自身を呼び出す 再帰関数 は、数学的帰納法と同じ発想です。必ず 基底条件 を定義しないと無限ループに陥ります。
// 階乗の再帰関数（疑似コード）
function factorial(n)
if n <= 1 then return 1 // 基底条件
return n × factorial(n - 1) // 再帰呼び出し
factorial(5) = 5 × 4 × 3 × 2 × 1 = 120
プログラムの設計思想・書き方のスタイルを プログラミングパラダイム と呼びます。
| パラダイム | 特徴 | 代表的な言語 |
|---|---|---|
| 手続き型 | 処理の手順を上から順に記述。関数で構造化 | C, COBOL, FORTRAN |
| オブジェクト指向 | データと処理をオブジェクトにまとめる | Java, C++, Python |
| 関数型 | 関数の適用と合成で処理を記述。副作用を避ける | Haskell, Lisp, Erlang |
| 論理型 | 事実と規則を定義し、推論エンジンが解を導く | Prolog |
近年の言語は複数のパラダイムを取り入れた マルチパラダイム が主流です（Python, JavaScript, Scala など）。
オブジェクト指向 は、現実世界の「もの」をプログラム上で表現する考え方です。
| 概念 | 説明 |
|---|---|
| クラスとインスタンス | クラスは設計図、インスタンスは設計図から作った実体。「犬」クラスから「ポチ」というインスタンスを生成する |
| カプセル化 | データ（属性）と処理（メソッド）をひとまとめにし、外部からの不正なアクセスを防ぐ。情報隠蔽とも呼ばれる |
| 継承（インヘリタンス） | 既存クラス（親クラス）の属性やメソッドを引き継いで新しいクラス（子クラス）を作る。コードの再利用性を高める |
| ポリモーフィズム（多態性） | 同じメソッド名で異なるクラスごとに違う動作をさせる。上図では「動物」の「鳴く()」を犬は「ワンワン」、猫は「ニャー」と実装する |
このほか 抽象クラス （インスタンス化できないクラス）や インタフェース （メソッドの仕様だけ定義）も重要な概念です。
プログラムを書いた後は テスト（試験） で品質を検証します。テスト手法は大きく2つに分類されます。
プログラムの 内部構造（ソースコード） に着目したテストです。すべての処理経路が正しく動くかを検証します。
| カバレッジ基準 | 内容 |
|---|---|
| 命令網羅（C0） | すべての命令を最低1回実行 |
| 分岐網羅（C1） | すべての分岐（true/false）を最低1回通過 |
| 条件網羅（C2） | すべての条件の真偽の組み合わせを網羅 |
| 経路網羅 | すべての実行経路を網羅（最も厳しい） |
分岐網羅（C1）が実務で最も一般的に使われる基準です。
プログラムの内部構造を意識せず、入力と出力の関係（仕様） に着目したテストです。
| 技法 | 内容 |
|---|---|
| 同値分割 | 入力を「同じ結果になるグループ（同値クラス）」に分け、各グループの代表値でテスト |
| 境界値分析 | 同値クラスの境界値（例: 0, 1, 最大値, 最大値+1）でテスト。バグは境界に集中する |
| 原因結果グラフ | 入力条件（原因）と出力（結果）の関係を図示し、テストケースを導出 |
| デシジョンテーブル | 条件と動作の全組み合わせを表にして漏れなくテスト |
例: 年齢による料金区分テスト
同値クラス: 0〜5歳（無料）、6〜12歳（子供料金）、13〜64歳（大人料金）、65歳以上（シニア料金）
境界値: 5, 6, 12, 13, 64, 65 を重点的にテスト
ポイント
プログラムの基本構造は 順次・選択・繰返し の3つ（構造化定理）。変数には データ型 があり、スコープ で参照範囲が決まる。引数の渡し方は 値渡し （コピー）と 参照渡し （アドレス）。プログラミングパラダイムは手続き型・オブジェクト指向・関数型・論理型の4つ。オブジェクト指向の4本柱は クラスとインスタンス ・ カプセル化 ・ 継承 ・ ポリモーフィズム 。テストは内部構造に着目する ホワイトボックステスト （命令網羅C0、分岐網羅C1）と、仕様に着目する ブラックボックステスト （同値分割、境界値分析）に大別される。
用語
プログラミング言語にはさまざまな種類があり、目的や用途に応じて使い分けられます。また、人間が書いたプログラム（ ソースコード ）をコンピュータが実行できる形に変換する仕組みも重要なテーマです。
ここではプログラム言語の分類と特徴、翻訳の仕組み、マークアップ言語、正規表現、文法の形式的な記述方法（BNF記法）を学びます。
| 言語 | 分類 | 特徴 | 主な用途 |
|---|---|---|---|
| C | コンパイラ型 | ハードウェアに近い低水準操作が可能。高速。ポインタ操作 | OS、組込みシステム、デバイスドライバ |
| Java | コンパイラ＋インタプリタ型 | JVM上で動作し「一度書けばどこでも動く」。ガベージコレクション | 業務システム、Androidアプリ、Webサーバ |
| Python | インタプリタ型 | 簡潔な文法で学びやすい。豊富なライブラリ | AI・機械学習、データ分析、Web開発 |
| JavaScript | インタプリタ型 | ブラウザ上で動作する唯一の言語（歴史的に）。非同期処理に強い | Webフロントエンド、Node.jsでサーバサイドも |
| アセンブリ言語 | 低水準言語 | 機械語と1対1に対応するニーモニックで記述。CPU依存 | 組込み制御、性能最適化、リバースエンジニアリング |
アセンブリ言語では、加算を ADD、データ転送を MOV などの ニーモニック で記述します。アセンブリ言語を機械語に変換するプログラムを アセンブラ と呼びます。
ソースコードを実行可能な形に変換する方法は大きく2種類あります。
| 方式 | 動作 | 特徴 |
|---|---|---|
| コンパイラ | ソースコード全体を一括して機械語に翻訳 | 実行速度が速い。翻訳に時間がかかる |
| インタプリタ | ソースコードを1行ずつ翻訳しながら実行 | 開発中の動作確認が容易。実行速度は遅い |
Java は 中間コード方式 を採用しています。コンパイラがソースコードを バイトコード （中間コード）に変換し、JVM（Java仮想マシン） がバイトコードを解釈・実行します。これにより、OS に依存しない実行が可能です。
コンパイラは以下の段階を経てソースコードを機械語に変換します。
リンカ は、コンパイラが生成した複数の オブジェクトモジュール と ライブラリ を結合して、1つの ロードモジュール（実行可能ファイル） を生成するプログラムです。
リンクの方式:
ローダ は、実行可能ファイルをメモリにロード（読み込み）して実行を開始するプログラムです。
| ローダの機能 | 説明 |
|---|---|
| 割付け（allocation） | プログラムに必要なメモリ領域を確保 |
| 連係（linking） | 外部参照を解決（動的リンクの場合） |
| 再配置（relocation） | アドレスを実際のメモリ位置に調整 |
| ロード（loading） | プログラムをメモリに読み込む |
データの構造や見た目を「タグ」で記述する言語です。プログラム言語とは異なり、処理の手順は書きません。
| 言語 | 特徴 | 用途 |
|---|---|---|
| HTML | Webページの構造を記述。タグは固定 | Webサイトの画面構成 |
| XML | ユーザがタグを自由に定義できる。データ交換用 | 設定ファイル、SOAP、RSS |
| JSON | JavaScriptのオブジェクト記法に基づく軽量フォーマット | Web API、設定ファイル |
JSON はタグを使わずキーと値のペアで記述するため、XML より軽量です。現在の Web API ではほぼ JSON が標準です。
// XML の例
<user>
<name>田中太郎</name>
<age>25</age>
</user>
// JSON の例
{"name": "田中太郎", "age": 25}
正規表現（Regular Expression） は、文字列のパターンを記述するための表記法です。テキストの検索・置換・入力チェック（バリデーション）に広く使われます。
| 記号 | 意味 | 例 | マッチする文字列 |
|---|---|---|---|
. | 任意の1文字 | a.c | abc, aXc, a1c |
* | 直前の文字の0回以上の繰返し | ab*c | ac, abc, abbc |
+ | 直前の文字の1回以上の繰返し | ab+c | abc, abbc（acは不可） |
? | 直前の文字の0回または1回 | ab?c | ac, abc |
[ ] | 文字クラス（いずれか1文字） | [abc] | a, b, c |
[^ ] | 否定文字クラス | [^0-9] | 数字以外の1文字 |
^ | 行の先頭 | ^Hello | 行頭のHello |
$ | 行の末尾 | end$ | 行末のend |
\d | 数字1文字（[0-9]と同等） | \d{3} | 123, 456 |
{n} | 直前の文字のn回の繰返し | a{3} | aaa |
{n,m} | 直前の文字のn〜m回の繰返し | a{2,4} | aa, aaa, aaaa |
| 用途 | 正規表現 | 説明 |
|---|---|---|
| 郵便番号 | ^\d{3}-\d{4}$ | 3桁-4桁の数字 |
| メールアドレス（簡易） | ^[a-zA-Z0-9.]+@[a-zA-Z0-9.]+$ | @の前後に英数字とドット |
| 電話番号 | ^0\d{1,4}-\d{1,4}-\d{4}$ | 0で始まるハイフン区切りの数字 |
正規表現は grep、sed、各種プログラミング言語で広く利用されています。
BNF記法 は、プログラミング言語の文法規則を形式的に記述するための表記法です。コンパイラの構文解析で使われます。
基本の記号:
::= — 「〜として定義される」| — 「または」< > — 非終端記号（さらに展開できる記号）例: 整数の文法定義
<整数> ::= <符号><数字列> | <数字列>
<符号> ::= + | -
<数字列> ::= <数字> | <数字列><数字>
<数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
この定義から「-42」「7」「+123」などが正しい整数として導出できます。
BNF をより読みやすく拡張した記法です。
| 記号 | 意味 |
|---|---|
{ } | 0回以上の繰返し |
[ ] | 省略可能（0回または1回） |
( ) | グループ化 |
上記の整数を EBNF で書くと:
整数 = [符号] 数字 {数字}
BNF記法を視覚的に表した図です。矢印に沿って進み、通過した要素を並べるとその文法で許される文字列になります。
試験では「このBNF定義から導出できる文字列はどれか」「この構文図が表す文字列の集合はどれか」といった形式で出題されます。BNFの再帰的な定義を丁寧にたどれるようにしましょう。
ポイント
プログラム言語は 高水準言語 （C, Java, Python）と 低水準言語 （アセンブリ言語）に分類される。翻訳方式は コンパイラ （一括翻訳、高速実行）と インタプリタ （逐次翻訳、開発が容易）。Java は中間コード（バイトコード）方式で JVM 上で動作する。コンパイラの処理は字句解析→構文解析→意味解析→最適化→コード生成の5段階。リンカ がオブジェクトモジュールを結合し、ローダ が実行ファイルをメモリにロードする。マークアップ言語は HTML（構造固定）・XML（タグ自由）・JSON（軽量）。正規表現 は文字列パターンの記述に使い、. * + [ ] などのメタ文字を組み合わせる。BNF記法 はプログラミング言語の文法を ::= と | で形式的に定義する。
用語