1

重複の可能性：
json.orgで使用される鉄道図を生成するためのツール

SQLiteのウェブサイトには言語の文法を示す素晴らしいグラフがいくつかありますが、これらがどのように作成されているか知っている人はいますか？

ここに画像の説明を入力してください

文法からグラフを生成するためのツールはありますか？

4

1 に答える 1

1

この例は、有限オートマトンによく似ています。つまり、正規表現に相当するグラフです。文法を正規表現に表すことができる場合 (当然、すべての文法が正規表現として表現できるわけではありません!)、クリーネの定理を使用してそれを FA グラフに変換できます。

RE の対象となるアルファベットは 1 文字ではなく、単語とトークンであることに注意してください。上記の例では、対応する RE は次のようになります。

DELETE FROM qualified-table-name
(WHERE expr|())   /* "WHERE expr" is optional; the alternative branch is the empty expression "()" */
(
    (ORDER BY ordering-term (, ordering-term)*|())   /* ", ordering-term" may be repeated */
    LIMIT expr ((OFFSET|,) expr|())   /* can use "OFFSET" or "," */
|()
)

これは、図に非常によく似た FA に変換されます。 GraphVizは、読みやすく描画するというまずまずの仕事をします。

上記REのFA

しかし、それはオリジナルとまったく同じではありませんね。それをうまく表現することが次の課題です。ネストされた RE 式を取得し、葉から始めて再帰的にレンダリングすることをお勧めします。

たとえば、レンダリングするには(WHERE expr|()):

  1. 2 つの代替パス。それぞれを個別にレンダリングします。
    1. レンダリングWHERE expr:
      1. ボックスとしてレンダリングWHEREします。
      2. 次に矢。
      3. 次に、ボックスとしてレンダリングexprします。
    2. ()単一の矢印としてレンダリングします。
  2. 最も長いもの (最初のもの) を見つけて、それに合わせて他のものを引き伸ばします。
  3. 両端に開始ノードと終了ノードを作成します。
  4. 開始ノードから各サブパーツに接続エッジを描画し、次に各サブパーツから終了ノードに接続エッジを描画します。

これをグラフィカルに行うということは、目に見えないボックスを含め、ボックスのサイズと位置を追跡することを意味します。各サブパーツの周りには目に見えないボックスがあります。再帰構造については、次の 3 つの点に注意してください。

  1. パーツのサイズは、その子のサイズによって異なります。
  2. サブパーツの場所は、その親の場所によって異なります。
  3. すべての場所は、他のすべてのサイズに依存する場合があります。

これは、各パーツのサイズを下から順に計算する必要があることを意味します。次に、ルートのサイズがわかったら、トップダウンでパーツの配置を開始できます。

于 2012-04-27T10:10:54.583 に答える