Powered by SmartDoc
(印刷用 PS 版は /home/hattori/visual-prog/latex2e/main.ps です)

グラフ文法の例

ビジュアル・プログラミング言語では、終端記号→基本図形、文→グラフというように拡張する。

以下の内容については、資料"A Graph Grammar Approach to Graphical Parsing"(/home/hattori/visual-prog/graph-grammar.ps)を参照。

Parsingの過程

グラフの parsing
  1. Graphical Scanning ---位置、大きさ、形などから空間的関係を判別。
  2. Low Level Parsing ---空間的関係から意味的なまとまりを持つ単位に変換。
  3. High Level Parsing ---導出列を生成。
    1. Bottom-up phase ---すべてのproduction instanceを列挙。
    2. Top-down phase --- dependencyに従ってpartial derivationを作っていく。

ただし、Syntax directed editorを使うので、High Level Parsingしかやらないことも多い。

埋め込み問題

グラフ文法の例

テキスト言語では文字が一列に並んでいるので、規則の適用により新たに生まれる文字の位置は自明である。それに対してグラフ言語では、新たに生まれるノードと既存のノードの関係を示さなければならない。解決策の一つは、規則を文脈依存にすることである。図4.2[グラフ文法の例]では、文脈ノードを破線で示している。他の解決法としては、生成規則とは別に埋め込み規則を記述する方法などがある。

Parsingのアルゴリズム

導出の例
  1. bottom-up phaseでは、規則の右辺とマッチするパターンを探し、その左辺に対応するノードを付加する(図4.3[導出の例])。これを繰り返し、すべての可能な規則の適用例のリストを作る。
  2. 規則の適用例の間には、制約関係が存在する。
  3. top-down phaseでは、開始記号から出発し、制約関係を満たすような規則の適用例の列を作っていく。

宿題

図4.2[グラフ文法の例]の上のグラフを、下の文法でparseせよ。ただし、論文のアルゴリズムを使わなくてもよい(使うとメチャクチャ大変)。提出物は、開始記号から始まって、適用する規則の番号と、適用結果のグラフを順に書き並べたもの。

ただし、文法のB?, C? ∈ {begin, fork, if}B?, C? ∈ {begin, assign, fork, join, send, receive, if}に訂正。