形式言語とは
形式言語(けいしきげんご)とは、あらかじめ厳密に定められた文法ルールと記号のみを使って構成される言語のことです。私たちが普段使っている日本語や英語のような「自然言語」は、文脈によって意味が変わったり曖昧さがあったりしますが、形式言語にはそのような曖昧さは一切ありません。ルール通りであれば誰が読んでも、コンピュータが読んでも、ただ1つの意味として正しく解釈されます。プログラミング言語(PythonやJavaなど)や、データの形式(JSONやXML)、またそれらの文法を定義するための表記法である「BNF記法」などが形式言語の代表的な例です。これにより、コンピュータは命令を誤解することなく実行できます。
具体例
プログラミング言語における変数代入の厳密なルールを例に挙げます。
【正しい文法(形式言語のルール通り)】
x = 10
→ コンピュータは「xに10を代入する」と正しく解釈できます。
【誤った文法(ルール違反)】
10 = x
→ 文法違反となり、コンピュータはエラーを出して処理をストップします。
このように、余計な解釈を挟まずに機械的に正誤を判定できるように厳密な文法で定義されたものが形式言語です。
もう少し詳しく
形式言語の理論は、計算機科学において非常に重要な基礎をなしています。米国の言語学者ノーム・チョムスキーは、形式言語をその文法ルールの厳密さ(生成能力の強さ)に応じて4つのレベルに分類しました(チョムスキー階層)。下から順に、「正規言語(正規表現や有限オートマトンで処理可能)」、「文脈自由言語(BNF記法で定義され、プログラミング言語の構文解析に使われる)」、「文脈依存言語」、「句構造言語(最も制約が緩い)」となります。私たちが書いたプログラムがコンパイラによって実行可能な形に変換される過程では、まず正規言語のレベルで「単語」が切り出され(字句解析)、次に文脈自由言語のレベルで「文法構造(構文木)」が解析される(構文解析)、というように形式言語の理論が段階的に応用されています。
試験でのポイント
試験において「形式言語」という単語そのものの定義を直接問う問題はそれほど多くありませんが、形式言語の文法を定義するためのメタ言語(言語を記述するための言語)である「BNF(バッカス・ナウア記法)」や「EBNF」に関する問題は頻出します。BNFの「::=(〜と定義する)」「|(または)」といった記号の意味を理解し、与えられたBNFのルール定義に従って、「この文法で生成される正しい文字列はどれか」を判定するパズル的な問題を解けるようにしておくことが重要です。ルールを再帰的(自分自身のルールの中で自分自身を呼び出す)に適用する表現が含まれることが多いので、代入を繰り返して展開していく操作に慣れておきましょう。
関連する用語
プログラミング言語の文法規則を定義するためのBNF、プログラムが正しい文法で書かれているかを解析する構文解析、正規言語の枠組みで文字列のパターンを表現する正規表現などが関連します。