who3411のブログ

情報系の勉強やイベントの参加に関するブログ(をしたい)です。

拡張BNFを用いたLL1文法の判定器を作った話

はじめに

今回、GitHubの勉強も兼ねてタイトルの通りのプログラムを作成してみました。

使い方や記述方法については、リンク先のREADME.mdに書かれているので、このブログでは「そもそもLL1って何?」とかの話も軽く話していきたいと思います。なお本ブログを読むにあたって、拡張BNFやLL1の話はかなり砕いて説明をしているので、詳しく知りたい方は他サイトや書籍を探して読むことをオススメします。

拡張BNFとは

拡張BNFは、BNF記法を拡張したものです。「じゃあBNFって何?」というと、文脈自由文法の定義などに用いられるものです。文脈自由文法は、正規表現よりも記述できる範囲が拡張された文法です。例えば「(1 * (2 + 3) )」のような括弧が混じった数式における"("と")"の対応を正規表現では記述することが出来ませんが、文脈自由文法では記述することが可能です。(BNFの記述方法については、ググってもらえば、分かりやすい解説が大量にあるので検索してみてください)

拡張BNFでは、BNF記法に加えて「繰り返し」が存在します。そのためBNF記法で繰り返しを表現したい場合、BNF記法では再帰的に定義することで擬似的に「繰り返し」を表現する必要があります。

例として、括弧を含めた加算を行う数式を表現する場合を、BNF記法の場合と拡張BNF記法の場合で表します。

BNF記法の場合

<DIGIT>  ::= ( "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" )
<DIGITS> ::= <DIGIT> <DIGITS> | <DIGIT>
<EXPR>   ::= <DIGITS> "+" <DIGITS> | "(" EXPR ")" | <DIGITS>

拡張BNF記法の場合

DIGIT  ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
DIGITS ::= DIGIT { DIGIT }
EXPR   ::= DIGITS { "+" DIGITS } | "(" EXPR ")"

このとき、DIGIT、DIGITS、EXPRのように"::="の前にある記号のことを非終端記号といいます。また"0"、"("、"+"のように"::="の後ろにしかない記号のことは終端記号といいます。

LL1文法とは

LL1文法は、1つ先読みすることで構文を決定できる文法の事を指します。この場合の「1つ先読み」とは「1トークン先読み」のことを指しており、つまり「1トークンを先読みすることで、構文を決定・解析できるような文法」を指しています。

つまり今回作成した「拡張BNFを用いたLL1文法の判定器」とは、「拡張BNFで記述されたものがLL1文法であるかどうかを判定する」ことが目的のプログラムになっています。

ではLL1文法を判定するためにどのようにすればよいのでしょうか。ここで必要となってくるのがFirst集合、Follow集合、Director集合という3つの集合です。それぞれについて説明していきます。

First集合

First集合とは、非終端記号と終端記号からなる記号列に対して、記号列から生成される先頭の終端記号の集合を現します。例えば「拡張BNFとは」で説明した文法について説明すると、非終端記号はDIGIT、DIGITS、EXPRの3つ、終端記号は"0"~"9"、"+"、"("、")"の12つです。

このとき、終端記号から生成される「先頭の終端記号」とは、自身を示しています。そのためFirst("0") = { "0" }、First("1") = { "1" }…のように、自身の終端記号のみを生成します。

それに対して非終端記号から生成される「先頭の終端記号」とは、First(DIGIT) = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" }、First(DIGITS) = First(DIGIT)、First(EXPR) = First(DIGITS) + { "(" }のように、各記号列の先頭に出る終端記号の集合を生成します。

Follow集合

Follow集合とは、非終端記号に対して、非終端記号の後ろに現れる可能性のある終端記号の集合を現します。例えばDIGITの後ろにはDIGITと"+"と")"が発生する可能性があるのでFollow(DIGIT) = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "+", ")" }となります。

First集合とFollow集合についての注意事項として、First集合では終端記号も求める必要がありますが、Follow集合では求める必要がありません。これはDirector集合で意味が分かると思うので、今は省略します。

Director集合

Director集合とは、非終端記号Nとその非終端記号から生成される可能性のある記号列Sを使用します。このときDirector集合はDirector(N, S)のように記述します。Director(N, S)は、Sが空文字でなければFirst(S)を、空文字であればFollow(N)を返します。

今回、空文字を使用していなかったため、Follow(N)となる例を見せることは出来ませんが、README.mdでは実行例を表示しているので見てみてください。

LL1文法の判定方法

LL1の判定方法は、結構簡単でNから生成される可能性のある記号列S1とS2(S1≠S2)のDirector集合の積集合Director(N, S1)∩Director(N, S2)が全て空集合であるかどうかで判定します。このとき、全てが空集合であればLL1であり、一つでも空集合でなければLL1ではありません。

プログラムの作成方法

さて、本題であるプログラムの作成方法について記述していきます。手順は以下の通りです。

  1. 拡張BNFトークンごとに分解する。
  2. 分解した拡張BNFが正しい記法であるかをチェックする。このとき、正しい文法でなければエラー又は警告を出力する。
  3. チェックが終了した状態の拡張BNFを出力する。
  4. 非終端記号のFirst集合を求めて出力する。
  5. Follow集合を求めて出力する。
  6. Director集合を求めて出力する。
  7. 拡張BNFがLL1かどうかをDirector集合を用いて判定・出力する。

各工程について説明していきます。

拡張BNFの分解

まず拡張BNFトークンに分解するにあたり、どのような構文にするかを定めます。この際に定めた構文は、README.mdの「拡張BNF記述ルール」を見てください。

次に定めたルールに従って、Tokenizerを作成していきます。今回のTokenizerでは、単純に以下の4種類に分解します。

  1. 文字と数値の組み合わせ
  2. ":"と"="の組み合わせ
  3. EOF
  4. その他

分解したトークンが、どのような情報を持つトークンであるかを、別に用意したルールを利用して情報ごとに分類します。つまり一つのトークンには「トークンの文字列」と「トークンの持つ意味」の2つを格納しています。この時点で、終端記号と非終端記号の分類は行っていません。どちらも「分類していない記号」として情報を格納しています。

分解した拡張BNFのチェック

ここでは、「分類していない記号の分類」と「拡張BNFのチェック」を行います。「分類していない記号の分類」は言葉の通りで、「分類していない記号」を終端記号であるか非終端記号であるかを確認します。

「拡張BNFのチェック」では、"("と")"の数が一致しない、"A ( ) B"のように必要のない括弧があるなど、LL1であるかどうかを判定するのに必要でない括弧の除去などを行っていきます。このとき、プログラムで直せる範囲であれば警告、直せない範囲であればエラーとして出力します。

「拡張BNFのチェック」で、プログラム側が利用者の記述した拡張BNFを修正する可能性あるため、この工程が終了する時点でプログラム側が今後利用していく拡張BNFを出力します。

First集合の求め方

自身の非終端記号を持つ列を見つけ、その非終端記号のFirst集合を求めます。求め終わった後に、全て出力します。

Follow集合の求め方

拡張BNFの右辺("::="の右側)から、非終端記号を見つけ、その非終端記号のFollow集合を求めます。求め終わった後に、全て出力します。

Director集合の求め方

非終端記号とその非終端記号が生成する可能性のある記号列、これまで求めてきたFirst集合とFollow集合を用いて、空文字があればFollow集合を、空文字がなければFirst集合をDirector集合として利用します。求め終わった後に、全て出力します。

LL1の判定

同じ非終端記号から求めたDirector集合を用いて、LL1であるかの判定を行います。LL1の判定を行い、LL1でなければ空集合とならなかった積集合を出力します。

おわりに

雑な説明でしたが、以上が今回作成したプログラムの全貌になります。LL1が作れると何が良いかなどは、各自調べていただければ幸いです。(私は勉強目的ですが、自作言語をしたい方は勉強するといいかもしれません。)