LL(1)構文解析

いっかい、構文解析についてまとめておきます。
主に自分の理解を増すためです。

まずは、LL(1)構文解析について。
詳細な部分は省き、どのような利点、どのような問題があり、それをどのように解決しているか？をまとめていきます。

また、表記のルールとして、
非終端記号をアルファベット大文字、終端記号をアルファベット小文字で書き、
生成規則はA→aBcをいうように矢印で表すことにします。

再帰下向き構文解析

LL(1)構文解析は、再帰下向き構文解析の一種です。
再帰下向き構文解析は、非終端記号ごとに、その生成規則を反映した解析関数を用意し、
最初に出発記号「S」の解析関数を呼び出し、
その生成規則「S→α」の右辺の記号列「α」に含まれる非終端記号「A」の解析関数を呼び出し、
非終端記号「A」の生成規則「A→aBc」に含まれる非終端記号「B」の解析関数を呼び出し、
･･･と行った具合に、再帰的に解析関数を呼び出すことで、
抽象構文木をrootからleafに向けて生成する構文解析法です。

再帰下向き構文解析には、
「コードが文法を反映したものになるので、直感的でわかりやすい」
という利点があります。

その一方で、以下のような問題点があります
「左再帰」
「バックトラック」

左再帰とバックトラック

再帰下向き構文解析の問題となる、左再帰とバックトラックについて説明します。

左再帰

たとえば、「A→Aa|b」と言う生成規則を持つ、非終端記号「A」の解析関数を素直に書くとすると、以下のようになります。

node parse_A() {
 token *prev = p; // pはlexerから得られるトークン
 node x;
 token y;
 if((x = parse_A()) && is_a(y = *p++)) // <-左再帰問題
    return make_node("A", x, y);

 p = prev;

 if(is_b(y = *p++))
    return y;

 p = prev;
 return NULL;
}

矢印の部分で、入力トークンの状態が変わらないのに、parse_Aを再帰的に呼び出してしまい、無限にparse_Aの再帰呼び出しが起こってしまいます。

では、どのようにしてこの問題を解決するかというと、
同様の導出結果を得られるように、新たな生成規則を導入して左再帰を除去します。
生成規則「A→Aa|b」の場合は
A→bA'
A'→aA'|ε
と新たな生成規則A'を作ることで（εは右辺が空であることを示します）
同様の導出結果が得られます。
A'に対応した新たな解析関数parse_A1()を用意することで、問題なく解析が行えるようになります。

バックトラック

非終端記号「A」に対する生成規則が「A→α」「A→β」と複数ある場合、
「A」の解析関数で、まず、「A→α」にあうかどうか調べて、
それが失敗だった場合、「A→α」を調べる前の、元の状態に戻し、
「A→β」を再度調べる必要が有ります。
上記の、赤で書いた部分の処理がバックトラックになります。

一般的にバックトラックのある処理は、実行効率が悪くなります。

また、再帰下向き構文解析では、上の様な単純なバックトラックだけでなく、
より複雑なバックトラック機構を用いなければならない場合があります。
複雑なバックトラック機構を用いると、処理が複雑になるだけでなく、
バックトラックで元の状態に戻ったときでないと、失敗であることが検出できないので、
適切なエラーメッセージを出すことが難しくなります。

このように、バックトラックは様々な問題を含むので、
バックトラックのない構文解析が考案されています。

それが本題のLL(1)構文解析になります。

LL(1)構文解析

LL(k)構文解析とは、ある非終端記号に複数の生成規則が存在する場合、
どの生成規則を適応すれば良いかをk個のトークンを先読みすることで決定する構文解析法です。

すなわち、LL(1)構文解析とは再帰下向き構文解析で、
１個のトークンを先読みすることで、複数の生成規則から、
適応する生成規則を決定する構文解析となります。

LL(1)文法

LL(1)構文解析を用いるためには、文法がLL(1)文法に則している必要があります。

どういうことかというと、LL(1)構文解析では、１個のトークンを先読みし生成規則を決定するので、
１個のトークンを先読みするだけで、その決定ができるような文法である必要がある
ということです。

LL(1)文法を作るためには、first集合、follow集合、director集合をいうものを使います。

first集合とは
非終端記号と終端記号からなる記号列αに対して、
αから生成される記号列の先頭に現れる終端記号の全体
のことを言います。
αに対するfirst集合をFirst(α)と表記します。

follow集合とは
非終端記号Aに対して、
Aの直後に現れる可能性の有る終端記号の全体
のことを言います。
Aに対するfollow集合をFollow(A)と表記します。

director集合とは、
生成規則A→αに対して、
終端記号の集合Director(A, α)は、以下のように定義します。
Director(A, α) = First(α) (α =>* ε でないとき)
First(α) ∪ Follow(A) (α =>* ε のとき)

LL(1)文法では右辺だけが異なる、生成規則「A→α」「A→β」に対して、
Director(A, α) ∩ Director(A, β) = φ
である必要があります。

LL(1)構文解析

文法がLL(1)文法であれば、LL(1)構文解析を用いることができます。

具体的には、複数の生成規則を持つ非終端記号の解析関数の中で、
一つ先のトークンに対して、そのトークンがそれぞれの生成規則のdirector集合に含まれているかどうかをチェックし、
含まれているならば、その生成規則を適応し、
含まれていなければ、別の生成規則に対して同様のチェックを行っていきます。

もし、どの生成規則のチェックも失敗した場合は、
その時点で構文エラーとなるので、エラーの補足も的確な位置でできます。

以上、LL(1)構文解析のまとめでした。

参考文献

コンパイラ (情報系教科書シリーズ)