グラフ文法の例

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

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

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. 規則の適用例の間には、制約関係が存在する。
   • above(a, b) --- aはbより前に適用されなければならない。
   • exclude(a, b) --- aとbは同じ導出列の中には現れない。
3. top-down phaseでは、開始記号から出発し、制約関係を満たすような規則の適用例の列を作っていく。