形式言語とは？正規表現・字句解析・構文解析を基礎から理解しよう

はじめに

私たちが使っている日本語や英語には、

• 使用する文字
• 単語
• 文法
• 文の作り方

といったルールがあります。

コンピュータの世界でも、同じように、

決められた記号とルールに従って作られる文字列

を扱う考え方があります。

これが**形式言語（Formal Language）**です。

形式言語は、

• プログラミング言語
• 正規表現
• コンパイラ
• 字句解析
• 構文解析
• オートマトン

などを理解するための基礎になります。

この記事では、

• アルファベット
• 文字列
• 空文字
• 形式言語
• 形式文法
• 終端記号・非終端記号
• 生成規則
• BNF
• 正規表現
• 字句解析
• トークン
• 構文解析
• 構文木
• オートマトンとの関係

について順番に整理していきます。

---

1. 形式言語とは

**形式言語（Formal Language）**とは、

決められた規則を満たす文字列の集合

です。

ここでいう「言語」は、日本語や英語だけを指しているわけではありません。

例えば、

0と1だけを使い、
最後が1で終わる文字列

というルールを考えてみます。

このルールを満たす文字列には、

1
01
11
101
1001

などがあります。

これらの文字列をまとめた集合を、1つの形式言語として考えることができます。

🍯 はちみつメモ

形式言語 = 決められたルールを満たす文字列の集合

---

2. アルファベットとは

形式言語では、最初に使用できる記号を決めます。

この記号の集合を**アルファベット（Alphabet）**と呼びます。

例えば、

Σ = {0, 1}

なら、

0
1

の2種類の記号を使用できます。

また、

Σ = {a, b}

なら、aとbを使って文字列を作ります。

Σはギリシャ文字のシグマです。

---

3. 文字列とは

アルファベットに含まれる記号を並べたものを**文字列（String）**と呼びます。

例えば、

Σ = {0, 1}

なら、

0
1
01
101
11001

などはすべて文字列です。

一方、

102

にはアルファベットに含まれていない2があるため、このアルファベットから作られた文字列ではありません。

---

4. 空文字とは

文字を1つも含まない文字列を**空文字（Empty String）**と呼びます。

一般的に、

ε

と表します。

εはギリシャ文字のイプシロンです。

空文字の長さは0です。

|ε| = 0

となります。

前回学んだNFAのε遷移も、この空文字と関係しています。

---

5. 文字列の長さ

文字列に含まれる記号の数を、文字列の長さといいます。

例えば、

10101

なら、長さは5です。

文字列wの長さは、

|w|

と表すことがあります。

例えば、

w = 10101

なら、

|w| = 5

です。

---

6. 言語とは

アルファベットから作ることのできる文字列の中から、特定の条件を満たすものを集めた集合を**言語（Language）**と呼びます。

例えば、

Σ = {0, 1}

として、

最後が1で終わる文字列

を集めるとします。

すると、

1
01
11
101
1001

などが言語に含まれます。

つまり、

アルファベット
↓
文字列を作る
↓
条件に合う文字列を集める
↓
言語

という関係です。

---

7. 形式文法とは

形式言語では、

どのような文字列を正しいものとして扱うのか

というルールが必要です。

そのルールを表すものが**形式文法（Formal Grammar）**です。

形式文法とは、

文字列をどのようなルールで作るかを定めたもの

です。

プログラミング言語にも、

if文はこの形で書く
変数宣言はこの形で書く
式はこの形で書く

といったルールがあります。

これも「言語の文法」と考えることができます。

---

8. 終端記号と非終端記号

形式文法では、主に2種類の記号を使います。

終端記号

**終端記号（Terminal Symbol）**とは、

最終的な文字列に残る記号

です。

例えば、

a
b
0
1
+
-

などです。

---

非終端記号

**非終端記号（Nonterminal Symbol）**とは、

文字列を作る途中で使われる記号

です。

例えば、

S
A
B

などがあります。

非終端記号は、途中で別の記号へ置き換えられます。

---

9. 生成規則とは

文字列を作るための置き換えルールを**生成規則（Production Rule）**と呼びます。

例えば、

S → aA
A → b

という規則があるとします。

最初にSから始めます。

S

1つ目のルールを使うと、

S
↓
aA

となります。

さらに、

A → b

を適用すると、

aA
↓
ab

となります。

これで終端記号だけになったため、

ab

という文字列が完成します。

---

10. 導出とは

生成規則を使って文字列を作っていくことを**導出（Derivation）**と呼びます。

例えば、

S
⇒ aA
⇒ ab

という流れです。

つまり、

開始記号
↓
生成規則で置き換える
↓
さらに置き換える
↓
終端記号だけになる
↓
文字列完成

となります。

🍯 はちみつメモ

生成規則 = 文字列を作るための置き換えルール

導出 = そのルールを使って実際に文字列を作ること

---

11. BNFとは

プログラミング言語などの文法を記述するときによく使われる方法がBNFです。

BNFは、

Backus-Naur Form

の略で、日本語ではバッカス・ナウア記法と呼ばれます。

例えば、

<数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

と書いた場合、

<数字>には0〜9のどれかを使用できる

という意味になります。

---

12. BNFで使われる記号

BNFでは、

::=

は、

左側を右側の内容として定義する

という意味です。

また、

|

は、

または

を意味します。

例えば、

<数字> ::= 0 | 1

なら、

数字は0または1

という意味です。

---

13. BNFで整数を表す

例えば、

<整数> ::= <数字> | <数字><整数>

というルールを考えます。

これは、

整数
=
数字1つ

または

数字 + 整数

という意味です。

このルールを繰り返すことで、

1
12
123
1234

のような複数桁の整数も表現できます。

BNFでは、このようにルールの中から再び同じルールを利用することがあります。

---

14. 正規表現とは

文字列のパターンを表現するためによく使われるのが**正規表現（Regular Expression）**です。

例えば、

a*

という正規表現を考えます。

*は、

直前の文字が0回以上繰り返される

ことを意味します。

そのため、

ε
a
aa
aaa
aaaa

などが条件に当てはまります。

---

15. 正規表現の基本

代表的な表現を見てみましょう。

*

a*

は、

aが0回以上繰り返される

という意味です。

---

|

a|b

は、

aまたはb

という意味です。

---

連結

ab

なら、

aの次にbが続く

という意味になります。

---

例えば、

a*b

なら、

b
ab
aab
aaab

などが条件に当てはまります。

🍯 はちみつメモ

正規表現では、

* = 0回以上の繰り返し

| = または

をまず覚えておきましょう。

---

16. 正規表現とオートマトン

前回の記事で学んだ有限オートマトンと正規表現には深い関係があります。

例えば、

0と1からなる文字列で最後が1

という条件は、正規表現でも有限オートマトンでも表現できます。

つまり、

正規表現
    ↕
有限オートマトン
    ↓
同じ種類の文字列を表現できる

という関係があります。

有限オートマトンが受理できる言語を正規言語と呼びます。

正規表現も同じ正規言語を表現できます。

---

17. 正規表現はどこで使われる？

正規表現は実際のITでも非常によく使われます。

例えば、

• 特定の文字列を検索する
• メールアドレスの形式を確認する
• ログから特定のパターンを探す
• 文字列を置換する
• 入力値をチェックする

といった用途があります。

例えば、数字だけの文字列を探したり、

ERROR

を含むログだけを探したりする場面などです。

形式言語の理論は、実際の文字列処理にもつながっています。

---

18. プログラムも文字列

私たちが書いているプログラムも、コンピュータから見ると最初は単なる文字列です。

例えば、

total = price + tax;

というプログラムも、最初は文字の並びです。

コンパイラなどは、この文字列をいきなり実行するわけではありません。

大まかには、

ソースコード
↓
字句解析
↓
トークン
↓
構文解析
↓
構文木

のように処理していきます。

---

19. 字句解析とは

**字句解析（Lexical Analysis）**とは、

ソースコードを意味のある最小単位に分割する処理

です。

例えば、

total = price + tax;

というソースコードを、

total
=
price
+
tax
;

のように分割します。

この一つ一つを**トークン（Token）**と呼びます。

---

20. トークンとは

トークンとは、プログラムを構成する意味のある単位です。

例えば、

if (age >= 20)

なら、

if
(
age
>=
20
)

のように分けることができます。

さらに、それぞれを、

if   → キーワード
age  → 識別子
>=   → 演算子
20   → 数値

のように分類します。

つまり字句解析では、

長い文字列を、意味のある部品へ分解している

と考えると分かりやすいでしょう。

---

21. 字句解析と正規表現

字句解析では、どの文字列をどの種類のトークンとして扱うかを判定する必要があります。

例えば、

0〜9が1文字以上並んだものを数値として扱う

といったルールです。

こうした文字列のパターンを表現するために、正規表現が利用されます。

イメージとしては、

ソースコード
↓
正規表現などで文字列パターンを判定
↓
トークンへ分割

という流れです。

ここで、

正規表現
↓
有限オートマトン
↓
字句解析

という、前回の記事とのつながりが見えてきます。

---

22. 構文解析とは

字句解析の次に行われる代表的な処理が**構文解析（Parsing）**です。

構文解析とは、

トークンの並びが文法に従っているか調べ、その構造を解析する処理

です。

例えば、

1 + 2

という式は、

数値
+
数値

という文法に従っているとします。

一方、

+ 1 2

が正しいかどうかは、そのプログラミング言語の文法によって決まります。

---

23. 字句解析と構文解析の違い

この2つは混同しやすいので整理しておきましょう。

字句解析

total = price + tax;

を、

total
=
price
+
tax
;

のようなトークンへ分割します。

つまり、

文字を部品へ分ける処理

です。

---

構文解析

そのトークンについて、

識別子
=
識別子
+
識別子
;

という並びが、文法として正しいかを確認します。

つまり、

部品の並び方や構造を確認する処理

です。

---

整理すると、

字句解析
=
文字列をトークンへ分割

構文解析
=
トークンの並びが文法に合っているか確認

となります。

🍯 はちみつメモ

字句解析 = 文字を部品に分ける

構文解析 = 部品の並び方を確認する

---

24. 構文木とは

構文解析では、プログラムや式の構造を木構造として表すことがあります。

これを**構文木（Parse Tree）**と呼びます。

例えば、

1 + 2

なら、簡単に表すと、

      式
     / | \
    1  +  2

のようになります。

もう少し複雑な、

1 + 2 * 3

であれば、

        +
       / \
      1   *
         / \
        2   3

のような構造として扱うことができます。

この構造によって、

2 × 3

を先に計算してから、

1 + 6

と処理する、といった演算の構造も表現できます。

---

25. なぜ構文解析が必要なの？

人間は、

x = 10 + 20;

を見れば、なんとなく意味を理解できます。

しかしコンピュータは、

どこが変数なのか
どこが演算子なのか
どの順番で計算するのか

といったことを、決められたルールに従って判断する必要があります。

そのため、

文字列
↓
トークンへ分割
↓
文法に従って構造を解析

という処理が必要です。

形式文法は、この構文解析で「正しい構造とは何か」を判断する基準になります。

---

26. 構文解析とBNF

BNFは、プログラミング言語の文法を表すためにも利用されます。

例えば、

<式> ::= <数> | <式> + <数>

というルールを定義したとします。

この文法なら、

1
1 + 2
1 + 2 + 3

などを表現できます。

構文解析では、このような文法ルールと入力されたトークン列を比較して、

このプログラムは文法として正しいか

を判定します。

つまり、

BNFなど
↓
文法を定義

ソースコード
↓
構文解析

文法に一致する？
↓
正しい構文か判定

という関係です。

---

27. 構文エラーとは

プログラミングをしていると、

Syntax Error（構文エラー）

という言葉を見ることがあります。

例えば、

if (x > 10 {

のように、必要な)が抜けている場合です。

プログラミング言語の文法では、

if (条件) {

という形が必要なのに、その規則を満たしていません。

このように、

プログラムが言語の文法に従っていない

ときに発生するのが構文エラーです。

形式言語や形式文法は、普段見るSyntax Errorにもつながっているわけです。

---

28. 正規表現と構文解析は役割が違う

正規表現と構文解析は、どちらも文字列を扱いますが、役割は少し異なります。

正規表現は主に、

文字列のパターンを表現する

ために使われます。

例えば、

数字だけ
特定の文字から始まる
特定の文字を含む

といった条件です。

一方、構文解析では、

文字列やトークンが文法上どのような構造を持っているか

を調べます。

整理すると、

技術	主な役割
正規表現	文字列のパターンを表現する
字句解析	文字列をトークンへ分割する
構文解析	トークンの文法的な構造を解析する

となります。

---

29. 正規表現だけでは表現しにくい構造

正規表現は文字列パターンを表すのに便利ですが、複雑な入れ子構造などは扱いにくくなります。

例えば、

((1 + 2) * 3)

のような括弧の対応です。

プログラミング言語には、

if (...) {
    while (...) {
        ...
    }
}

のような入れ子構造が多くあります。

こうした構造は、単純な文字列パターンを見るだけではなく、

どの要素がどの要素の中にあるのか

という構造まで確認する必要があります。

そこで構文解析が重要になります。

---

30. コンパイラではどうつながる？

ここまでの内容を、プログラムが処理される流れで見てみましょう。

例えば、

total = price + tax;

というソースコードがあるとします。

まず、

ソースコード
↓
字句解析

を行います。

そして、

total
=
price
+
tax
;

というトークンへ分割します。

続いて、

トークン
↓
構文解析

を行い、

       =
      / \
 total   +
        / \
     price tax

のように構造を解析します。

つまり、

ソースコード
↓
字句解析
↓
トークン
↓
構文解析
↓
構文木

という流れになります。

---

31. オートマトンとのつながり

ここまで学習してきた、

• オートマトン
• 形式言語
• 正規表現
• 字句解析

は別々の話ではありません。

例えば、

数字が並んでいる文字列

というパターンを正規表現として定義します。

その正規表現に対応する有限オートマトンを考えることができます。

そして、その仕組みを使って、

12345

が「数値」というトークンであることを判断できます。

つまり、

正規表現
↓
文字列のパターンを定義
↓
有限オートマトン
↓
パターンに一致するか判定
↓
字句解析

というつながりがあります。

---

32. 形式言語全体を整理しよう

今回の内容を整理すると、

アルファベット
↓
使える記号を決める
↓
文字列
↓
ルールに合う文字列を集める
↓
形式言語

となります。

そのルールを表すのが、

形式文法
↓
生成規則
↓
文字列を生成

です。

そして実際のプログラミング言語では、

ソースコード
↓
字句解析
↓
トークン
↓
構文解析
↓
構文木

という処理につながります。

さらに字句解析では、

正規表現
↕
有限オートマトン

という仕組みが重要になります。

---

33. 試験で押さえたいポイント

形式言語

決められた規則を満たす文字列の集合

です。

---

アルファベット

使用できる記号の集合です。

Σ = {0, 1}

のように表します。

---

空文字

ε

で表します。

長さは0です。

---

形式文法

文字列をどのようなルールで生成するかを定めたものです。

---

生成規則

S → aA

のような記号の置き換えルールです。

---

BNF

文法を表す代表的な記法です。

<数字> ::= 0 | 1 | 2

のように表します。

---

正規表現

文字列のパターンを表現します。

基本として、

*

は0回以上の繰り返し、

|

は「または」を表します。

---

字句解析

ソースコード
↓
トークン

へ分割する処理です。

---

構文解析

トークンの並びが文法に従っているか調べ、その構造を解析します。

---

字句解析と構文解析

字句解析
=
文字列を部品に分ける

構文解析
=
部品の並び方・構造を調べる

と整理しましょう。

---

まとめ

今回は、形式言語について学びました。

この記事で覚えること

• 形式言語は決められた規則を満たす文字列の集合
• アルファベットは使用できる記号の集合
• 記号を並べたものが文字列
• 文字を含まない文字列を空文字εという
• 形式文法は文字列を作るためのルール
• 終端記号は最終的な文字列に残る記号
• 非終端記号は文字列を作る途中で使う記号
• 生成規則は記号の置き換えルール
• 生成規則を使って文字列を作ることを導出という
• BNFは文法を記述する代表的な方法
• 正規表現は文字列のパターンを表現する
• 正規表現と有限オートマトンには深い関係がある
• 字句解析ではソースコードをトークンへ分割する
• 構文解析ではトークンの並びと構造を解析する
• 構文解析によって構文木を作ることができる
• 形式言語の考え方はコンパイラなどにつながっている

🍯 はちみつメモ

形式言語 = 決められたルールを満たす文字列の集合

プログラムでは、

ソースコード → 字句解析 → トークン → 構文解析 → 構文木

という流れが重要です。

また、

正規表現 = 文字列のパターンを表す

字句解析 = 文字列を部品に分ける

構文解析 = 部品の並び方を調べる

と整理すると覚えやすくなります。