基本情報技術者試験(FE) ～情報の基礎理論「形式言語・数式記法」～【第1回】

形式言語（BNF）

「BNF」は、文法の定義（構文規則）を表現する形式言語です。構文規則は、順次、反復、選択があり、以下の表の記号を用います。

記号	意味
	xという構文要素を表す。
::=	左に示す構文要素に対し、右の構文規則を定義することを表す。
・・・	左の構文要素を繰り返すことを表す。
｜	左右の構文要素のどちらかを表す。
[　]	[　]で囲まれた構文要素は省略可能を表す。

以下は、順次、選択、反復の表現方法を示します。
①順次

【表記例】	::=
【意味】	構文要素は、構文要素の後に構文要素が続く。
【例】	::=

②選択

【表記例】	::=\|
【意味】	構文要素は、構文要素または構文要素からなる。
【例】	::=+\|-
	::=\|
	::=0\|1\|2\|3\|4\|5\|6\|7\|8\|9

③反復

【表記例】	::=･･･
【意味】	構文要素は、構文要素を１個以上の繰返しからなる。
【例】	::=･･･
	::=\|
	::=0\|1\|2\|3\|4\|5\|6\|7\|8\|9\|

例えば、以下のような構文規則が定義されたとします。

この定義によって、表現できる構文は、「A」「B」「C＊D」「（A+B）＊（C+D）」などが該当します。「（A＊B）」「A+B」などは、構文規則から外れるため、該当しません。

数式記法（逆ポーランド記法）

数式を処理する場合は、演算の種類以外に演算する優先順位を把握して、正しく処理する必要があります。ひとは、式全体を見渡してどこから処理を始めればよいかがわかりますが、コンピュータは数式を先頭から順に読みながら把握をするため、一般的な数式の記述方式では式全体を理解することが困難な場合があります。
そこで、コンピュータが数式を処理しやすいようにした記法が考えられて、その１つに、「逆ポーランド記法」があります。

「逆ポーランド記法」では、数式にカッコ（括弧）が現れず、オペランド（演算対象となる値、または、変数）と演算のみで構成されます。また、演算対象を２つのオペランドの右側に配置して表現します。

例えば、「Y = (A + B) × (C – (D ÷ E))」の数式は、「逆ポーランド記法」によると「YAB + CDE ÷ + × =」になります。

この際の変換は、以下のようになります。

逆ポーランド記法で表された演算式から演算式を実行する場合は、「スタック」を使用します。

演算式を左から順にみていき、現れた内容によって以下の操作を実行します。

以上の操作を演算子の最終記号まで実行したとき、スタック内に結果が格納されていることになります。

以下は、逆ポーランド記法で表された式「YAB + CDE ÷ – × =」に対する演算処理の過程を示します。