第009回_EBNFデータツリーを使った構文解析器

» 2017/03/20

今回から構文をどのように解析するかについて検討します。
この際、字句解析器についてはまだ説明していませんのでトークンはとれたものと仮定します。
また、字句解析の本体は構文解析の途中でそれぞれ実装します。

構文解析手法

LL (1)言語の構文解析を行う手法として、以下の2つが考えられます。
　1.構文解析表を使う方法
　2.EBNFデータツリーを使う方法

それぞれのメリット・デメリットを検討します。

1.構文解析表を使う方法
　■デメリット

・構文解析表を作成する(director集合を作成する)のに"手作業だと"結構な手間がかかる
・構文を追加する時は、構文解析表も修正しなくてはならず、 LL (1)が保てない場合( LL (k)に変更する場合 )は処理を大幅に変更しなくてはならない。つまり、構文の修正はLL(1)の範囲内に保たなければならない

　■メリット

・構文解析表ができれば、あとは半自動的に処理が書ける
・全体のステップ数は短い

2.EBNFデータツリーを使う方法
　■デメリット

・構文に対してステップ数が直線的に(リニアに)増加する(XMLは76個あるのでステップ数が増える)

　■メリット

・構文毎に処理を記載できる
・各実装は平易
・構文追加でLL (1)が保てなくなった場合、「構文解析表」を使う手法に比べて修正量が少なくて済む

3.構文解析手法の決定
メリット・デメリットを説明しましたが、どちらで実装してもそれほど問題はありません。構文解析表を使う方法はXMLの要素宣言の実装で取り扱うという今後の都合で、本体の実装にはEBNFデータツリーを使う方法を採用します。

EBNFデータツリー

■EBNFデータツリーの名称について

筆者が勝手に考えた呼び名ですのでEBNFデータツリーという用語はWikiで調べても出てきません。
※もし正式な呼称があれば修正します。

■EBNF構文の構造化

EBNFデータツリーの考え方がトークンをどうやって解析するかというのは脇に置いて、構文をどうやって定義するかについて簡単に説明します。
　document ::= ( prolog element Misc* )
これは
　document
　+prolog ↓上から
　+element ↓順に
　+Misc* ↓処理する
という構造に置換でき、連接を表す「Sequence」と繰り返しを表す「Repetition」の概念を導入すると
　document
　+Sequence:子要素を順に処理する
　　+prolog
　　+element
　　+Repetition:繰り返し処理する
　　　+Misc
と表現することができます。

　[39] element ::= EmptyElemTag | STag content ETag
　# この構文の | はEBNF的には正しくありません。
　# element ::= EmptyElemTag | ( STag content ETag )
　# とした方が適切でしょう。
のような選択 | の場合は「Alternation」の概念を導入して、
　element
　+Alternation:選択要素を処理する
　　+EmptyElemTag
　　+Sequence
　　　+Stag
　　　+Content
　　　+ETag
とします。

以上のように「Sequence(連接)」,「Repetition(繰り返し)」,「Alternation(選択)」の概念を導入して
構文をツリー構造にできます。

■ツリー構造とクラス化

ツリー構造にできるということはクラス構造とすることができるということです。この考え方自体は、本「JAVAによるパーサ構築技法」(出典) を参考にしています。是非そちらの本も読んでみてください。

EBNFデータツリーのノード毎の役割と整理

構文
　[24] VersionInfo ::= S 'version' Eq ("'" VersionNum "'" | '"' VersionNum '"')
　[25] Eq ::= S? '=' S?
　[26] VersionNum ::= '1.1'
をEBNFデータツリーにして、各ノードの解析時の役割を把握してみましょう。

EBNFデータツリーは次のようになります。

VersionInfo
＋Sequence
　 ├＋S
　 ├＋Symbol ('version')
　 ├＋Eq
　｜　＋Sequence
　｜　　├＋Repetition (0,1)
　｜　　｜　＋S
　｜　　├＋Symbol ('=')
　｜　　└＋Repetition (0,1)
　｜　　　　＋S
　 └＋Alternation
　　　 ├＋LITERAL (' ,'1.1')
　　　 └＋LITERAL (" ,'1.1')

:01.子ノードを全て処理する
:02.子ノードを全て処理する
:03.WHITE_SPACEトークンで一致すればOK
:04.SYMBOL:version と一致すればOK
:05.子ノードを全て処理する
:06.子ノードを全て処理する
:07.子ノードを一回だけ適応し、NGでもOKでも良い
:08.WHITE_SPACEトークンで一致すればOK
:09.SYMBOL:= と一致すればOK
:10.子ノードを一回だけ適応し、NGでもOKでも良い
:11.WHITE_SPACEトークンで一致すればOK
:12.子ノードのうちどれかがOKになったら良い
:13.LiteralToken,クオート,1.1
:14.LiteralToken,ダブルクオート,1.1

上記のEBNFデータツリーには無駄な箇所が4つあるので整理します。
　1.　01と02は同じなので統合できます
　2.　05と06は同じなので統合できます
　3.　13と14はLiteralの定義上、別々にする必要がないので統合できます
　4.　13と14を統合した場合12は不要になります

整理した結果:

VersionInfo(Sequence)
　├＋S
　├＋Symbol ('version')
　├＋Eq (Sequence)
　｜　├＋Repetition (0,1)
　｜　｜　　＋S
　｜　├＋Symbol ('=')
　｜　└＋Repetition (0,1)
　｜　　　＋S
　└＋LITERAL ('1.1')

これでデータツリーの各ノードを体現するものが説明できました。次は、このツリーを使ってどうやって解析するかを説明します。

解析動作

構文を解析する動作は次のようになります。

■終端ノードの場合

1.次のトークンを取り出す
2.トークンが終端ノードと一致するか判定する
　2-1.種類の判定(COMMENTやPI_WORD)
　2-2.中身の文字列パターンの一致による判定

■非終端ノードの場合

共通
Sequence
Alternation
Repetition

:子ノードを処理した結果から構文解析OKかどうかを判定する
:途中の子ノード評価がNGになった場合は処理を中断する。
:途中の子ノード評価がOKになった場合は処理を中断する。
:上限値:上限値の数、子ノードを評価する。下限値:下限値の数、子ノードが評価OKにならない場合NG。つまり、

1.処理ループ(0～上限値まで)
　1-1.子ノード評価を行う
　1-2.評価結果がOKの場合
　　1-2-1.OKカウントを+1する
　1-3.評価結果がNGの場合
　　1-3-1.ループ処理を中断する
　　1-3-2.OKカウントが下限値より少ない場合
　　　1-3-2-1.評価NG
　　1-3-3.OKカウントが下限値より多い場合
　　　1-3-3-1.評価OK

という処理を構築する

以上が各ノードにおける動作の説明になります。次回のコラムでは実装前にVisitorパターンについて検討します。

0/1相転移炉 2017/03/20 10:05:00 Comment(0)

次の投稿へ

前の投稿へ