⛳

【初心者向け】BNF, EBNFをざっくり解説

2024/06/11に公開

初心者向け

(元々はサークル内記事として書かれたものです)
(たぶん初記事です！訂正や質問、感想をお待ちしてます～)

世の中では様々なプログラミング言語が使われている。
また、設定ファイルなどで使われるデータ記述言語まで含めれば、さらに多くの言語に触れていると言えよう。

諸言語を学ぶ上で欠かせない、構文を表現するための記述方法をざっくり解説する。

対象

プログラミング始めたての方
言語のリファレンスを見てみたら謎い記法が使われてて困った！って方

何らかの言語における基本的な制御構文(ifとかforとか)を理解してる、くらいを想定
文字や文字列に関する基礎知識があると良いかも

TL; DR

構文(Syntax)を説明するための記法だよ

構文ってなに？

ある文字列がその言語であるかどうかを決める規則のこと。

プログラミング言語を例に挙げよう。コードが言語の構文にあっていれば型検査などが行われ、構文に適合しないなら構文エラーが出る。

#include <iostream>

int main() {
std::cout << "hello world!" << std::endl;
// 閉じ括弧がない

prog.cc: In function 'int main()':
prog.cc:4:41: error: expected '}' at end of input
 std::cout << "hello world!" << std::endl;

main関数の関数本体の閉じ波括弧が無いため、構文に適合せずエラーが出ている。

文字列が構文に適合することを、構文が文字列にマッチするという。

バッカス・ナウア記法(Backus–Naur form)

構文を表現するための記法。

※^[1]

文字列リテラル

0個以上の文字の列を表す。
引用符"で囲う。

"A"
"Hello"
"ABC"
"123"

0文字の文字列は空文字列と呼ばれ、""で表される。

非終端記号

プログラミング言語でいう変数のようなもの。
=の左に新たに導入する名前を、右側にその定義を書く。

a = "A"
cat = "Cat"
hello = "Hello"
hello2 = hello

それぞれ、A, Cat, Hello, Helloにマッチする。

連結

記号aの後にすぐ記号bがくる、という記号を定義できる。

HelloWorld = hello "World" "!"

HelloWorld!にマッチする。

選択

記号aか記号bに適合する、という記号を定義できる。

Color = "Red" | "White" | "Black"

ColorはRed, White, Blackにマッチする。

選択と連接では連接のほうが優先順位が高い。

Hat = "Cap" | "Sun" "Hat" | "Sombrero"

HatはCap, SunHat, Sombreroにマッチする。CapHatやSunSombreroでないことに注意。

再帰

非終端記号の定義は、まさに今定義している非終端記号を含むこともできる。

A = "a" | "a" A

これは1文字以上aが連続するような文字列全て(a, aa, aaa, ...)にマッチする。

EBNF (Extended BNF)

BNFは主に文法の数学的な性質に興味のある人たちが使うもので、我々が普段使いするにはちょっと使いにくい。

そこで、もう少し扱いやすくした記法がいくつか誕生している。それらの間に記号の差異はあれど、割と似通っている。これらを纏めてEBNFと呼ぶ^[2]。

多くのEBNFに存在する機能を紹介する。

コメント。

# コメントです

null文字列

0文字の文字列にマッチする終端記号。よく $\epsilon$ やnullで表されることが多い。
人によっては空文字列と呼ぶかも。
空白文字(画面に表示されるときに空白な文字)とは別なことに注意。あれらは表示されないだけのただの文字だ。

A = "a"
B = A null "b"  // "ab"にマッチ

繰り返し

○○が任意個続く、という文法は多い。
これを表現するために、一々新たな名前を導入するのは煩雑だ(可能な限り文でなく式であるべきだ)。

item = number | string  # "1", "abc"などにマッチ
item_list_helper = null | item ", " item_list_helper  # 再帰で繰り返しを表すには名前を導入せねばならない
item_list = "{" item_list_helper "}"  # "{}", "{1, }", "{abc, 1, }"などにマッチ

そこで、繰り返しを表現できるような新たな演算子がいくつか導入されている。
ふつう、これらの単項演算子は連接より優先順位が高い。

`*`

オペランドの非終端記号が0個以上続くような文字列全てにマッチする。
つまり、空文字にもマッチする。

item = number | string  # "1", "abc"などにマッチ
item_list = "{" *(item, ", ") "}"  # "{}", "{1, }", "{abc, 1, }"などにマッチ

`+`

オペランドの非終端記号が1個以上続くような文字列全てにマッチする。
かならず1個はその非終端記号が来なきゃいけない。

digits = "1"
additive_expression = digits +((" + " | " - ") digits)
# "1 + 1", "1 - 1 + 1"にマッチ
# "1"にはマッチしない

オプション `?`

オペランドの非終端記号が0個もしくは1個あるような文字列にマッチする。
オプショナルな記号などによく使う。

variable_declaration = (identifier | "auto") " " identifier ?(" = " expression) ";"
# `int x;`や`auto z = 0;`にマッチ

正規表現

終端記号を正規表現で表すことができるものも多い。

例

C++20のfor文を見てみよう。今日やった演算子などで書き直すと、

"for" "(" init_statement ?condition ";" ?expression ")" statement

となる。非終端記号を順に追っていこう。

init_statementは初期化文だ。int i = 0;とかがマッチする。
conditionは条件だ。多くの場合式が来る。i < 10とかがマッチする。
ここは?がついているから省略できる。
expressionは更新式だ。++iなどにマッチする。
ここも?がついてるから省略できる。
statementは繰り返される文だ。複合文が来ることが多い。
{std::cout << i << std::endl;}などがマッチする。

^[3]

これが

{
    init_statement
    while ( condition ) {
        statement
        expression ;
    }
}

とほぼ等価らしい。

つまり、

for(int i = 0; i < 10; ++i) {
    std::cout << i << std::endl;
}

これが、

{
    int i = 0;
    while ( i < 10 ) {
        {
            std::cout << i << std::endl;
        }
        ++i ;
    }
}

となるらしい。実際、実行すると同じ出力が得られる。

脚注

以下の説明で使われる記号は元々提案されたものと少し異なる。場合によっては怒られが発生するかも、注意。 ↩︎
「EBNF」という標準化されている記法もあるらしい。紛らわしいね。 ↩︎
BNFではセミコロンの前後に空白が無いのに、実際には空白を入れても良いのは何故？という疑問が沸くかもしれない。実は、構文チェックの前に空白は取り除かれてしまう。空白があった位置でコードが断片化され、それが構文チェックに掛けられるのだ。ここら辺を詳しく知りたいなら、字句解析で調べてみてほしい ↩︎