コンパイラ入門3 バッカス記法・構文図式

前回の記事はこちら

コンパイラ入門2 コンパイラの例・論理的構造・物理的構造

バッカス記法

初めて国際的な組織で開発されたプログラム言語の構文がバッカス記法であったため、多くのプログラム言語の構文規則はバッカス記法か、これを拡張したものです。

バッカス記法において、識別子(名前)を定義すると次のようになります。

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

<英字> → a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z

<名前> → <英字> | <名前><英字> | <名前><数字>

ここでの<>で囲まれたものを構文要素と呼びます。一番上は、数字は0~9のどれかというように解釈できます。「|」は「または」という意味です。

この記法で日本語の構文を一部定義してみると次のようになります。

<文> → <主部><述部>

<主部> → <名詞><助詞>

<述部> → <動詞>

<名詞> → 私|友達|猫

<助詞> → は|が|も

<動詞> → 寝る|帰る|走る

木構造で考えると、<文>が木の根であり、「私」などが葉に相当します。葉は終端記号と呼ばれ、それ以外は非終端記号と呼ばれます。

拡張バッカス記法も色々考えられており、よく使うのは{ α }という形で、これは次のような意味を持ちます

ε|α|αα…

εは「空」を表す記号であり、この場合αはαを0個以上並べたものを表します。

A → { B }

は、以下をわかりやすく表現したものです

A → ε|AB

この記法を使うことで、最初の<名前>は次のように書けます。

<名前> → <英字>{<英字>|<数字>}

構文図式

構文規則を図式化したものを構文図式と言います。構文図式は、構文規則に対して以下の規則を繰り返し適用することによって得られます。

1, 構文規則

A → α

に対応する図式は次の形となります。

2, αとそれに対応する図式は以下のよおりになります。

例えば、

<名前> → <英字><英字>|<数字>

の時の構文図式は次のようになります