BNFや構文解析についてのメモ

言語処理系 BNF

BNFとは

バッカスナウア記法のことであり、文脈自由文法を定義する事ができる。
プログラミング言語の構文はこのBNFを使用して定義されることが多い。

分かれば何でもいいので、独自に拡張したBNFや図を使用して定義されることもある。

例として四則演算と括弧を含んだ式の構文を表すBNFは以下のようになる。
ただし、この構文は後述する 左再帰性の問題 を抱えている。

<expr> ::= <term> | <expr> "+" <term> | <expr> "-" <term>
<term> ::= <fact> | <term> "*" <fact> | <term> "/" <fact>
<fact> ::= <number> | "-" <fact> | "(" <expr> ")"

<number> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

このBNFは演算子の優先順位も反映している。
つまり、括弧の中身は何よりも早く処理され、次いで乗算や除算、加算と減算といった具合だ。

より優先順位の高い演算子はより優先順位の低い演算子から呼び出されるように組めばよい。

再起下降構文解析

構文解析とは、与えられた構文1に従ってある文字列から構文木を作成する事である。
代表的なものに トップダウン構文解析 と ボトムアップ構文解析 が存在する。

トップダウン構文解析は一般的にボトムアップ構文解析より人の手によって作成しやすいとされている。

再帰下降構文解析は再帰関数によってトップダウン構文解析を行う。

具体的にはBNFの生成規則をそのまま関数に適応する。

<A> ::= "a" <B> "c"
<B> ::= "b"
void A() {
    // "a"を読む
    B();
    // "c"を読む
}
void B() {
    // "b"を読む
}

左再帰性の問題

ここで、BNFとは で定義した四則演算の構文を思いだしてほしい。
それは以下のようだった。

<expr> ::= <term> | <expr> "+" <term> | <expr> "-" <term>
<term> ::= <fact> | <term> "*" <fact> | <term> "/" <fact>
<fact> ::= <number> | "-" <fact> | "(" <expr> ")"

<number> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

これに対応する再帰下降構文解析のコードを考えてみよう。

void expr() {
    // termを読むか読まないかする
    expr();
    // ~~~
}
void term() {
    // factを読むか読まないかする
    term();
    // ~~~
}
void fact() {
    // ~~~
}

BNFをそのままプログラムに反映した。
expr関数とterm関数を見て欲しい。

左結合の演算子である "+" "-" "*" "/" に合致した構文木を生成するために、まず自分自身を呼び出している。
これでは、BNF上で正しくとも、プログラム上では無限ループ2となってしまう。

これを解決するにはBNF上で左再帰を行わなければよい。
言い換えれば、連続する優先順位が同等な演算子を、再帰ではなくループによって実装すればよい。

なお、eはイプシロン(ε)を表し、空文を意味する。

<expr> ::= <term> | <term> <expr_loop> | <term> <expr_loop>
<term> ::= <fact> | <fact> <term_loop> | <fact> <term_loop>
<fact> ::= <number> | "-" <fact> | "(" <expr> ")"

<expr_loop> ::= "+" <term> <expr_loop> | "-" <term> <expr_loop> | e
<term_loop> ::= "*" <fact> <term_loop> | "/" <fact> <term_loop> | e

<number> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

  1. BNFなどで定義される↩

  2. その前にスタックオーバーフローかな↩