BNF記法のススメ

達人プログラマーを読んでいる時に出てきて、
そういや最近いろんなところで見たなと思ったので調査。

BNFをすらすら読めると資料解読がはかどりますよ、という話です。

BNF(バッカスナウア記法とは)

文脈自由文法を定義するのに用いられるメタ言語のこと

by Wikipediaより

例

達人プログラマーの演習問題から。

時刻表記を定義するBNF文法を作成せよ、ただし以下の例を解釈できること
4pm, 7:38pm, 23:42, 3:16, 3:16am

時刻を表すBNF

<時刻> ::=  <時間><午前午後>|
           <時間>:<分><午前午後>|
           <時間>:<分>
<午前午後> ::= am|pm
<時間> ::= <10進桁>|
          <10進桁><10進桁>
<分> ::=<10進桁><10進桁>
<10進桁> ::= 0|1|2|3|4|5|6|7|8|9

34:15とか余分なものも解釈できてしまうが今回はその解説は省略。

SQLとの関係

最近、この投稿で教えていただいたSQL92のドキュメントがBNFで書かれていた。通常、こういう厳密な定義のあと、わかりやすい具体例が表示されるが、お硬い資料だとそういうのを付けてくれないので、BNFを理解する気がないと解読できない。

クエリの定義

<query specification> ::=
     SELECT [ <set quantifier> ] <select list> <table expression>

<select list> ::=
       <asterisk>
     | <select sublist> [ { <comma> <select sublist> }... ]

<select sublist> ::=
       <derived column>
     | <qualifier> <period> <asterisk>

<derived column> ::= <value expression> [ <as clause> ]

<as clause> ::= [ AS ] <column name>

補足

<set quantifier> ::= DISTINCT | ALL

<table expression> ::=
     <from clause>
     [ <where clause> ]
     [ <group by clause> ]
     [ <having clause> ]

※[]はあってもなくても良い項目です。

[ ] Square brackets indicate optional elements in a formula. The
portion of the formula within the brackets may be explicitly
specified or may be omitted.

加えてBNFを視覚的に表現した構文図式というものもある

OracleのドキュメントではBNFの代わりとして使われているので、こちらも一緒に覚えておくと資料調査に役立つ。

感想

ググったら応用情報の問題とかで出て来るし、実は大学でちょっとだけかじったことがある。
プログラミング言語なんか作らないから関係ないっしょwと適当にその場限りで学習しており、自分の仕事に関係するところ(SQLのドキュメント)で出てくるとは思っていなかったのですっかり忘れていた。

情報系の学部でないとまず知らない(学習する機会がない)と思うので、
未経験でスタートした人はこういうものでドキュメントが書かれることもあると知っておくと、後々役立つかもしれない。

参考

達人プログラマー https://estore.ohmsha.co.jp/titles/978427421933P
達人プログラマー(amazon) https://www.amazon.co.jp/dp/427421933X
Wikipedia https://ja.wikipedia.org/wiki/バッカス・ナウア記法
BNFが使われている資料 http://www.contrib.andrew.cmu.edu/%7Eshadow/sql/sql1992.txt
構文図式(英語) https://en.wikipedia.org/wiki/Syntax_diagram
構文図式が使われている資料 https://docs.oracle.com/cd/E16338_01/server.112/b56299/queries003.htm