1

Possible Duplicate:
Tool for generating railroad diagram used on json.org

SQLite has some awesome graphs showing the grammer of the language on their website, does anyone know how these are made?

enter image description here

Is there a tool for generating graphs from grammas?

Community
  • 1
  • 1
Martin Kristiansen
  • 9,875
  • 10
  • 51
  • 83
  • 1
    The authors of the program that generates the sqlite railroad diagrams have explained it http://wiki.tcl.tk/21708 as noted in the Sqlite FAQ http://www.sqlite.org/faq.html#q25 – Dan D. Apr 27 '12 at 10:35
  • @BartKiers: the problem with the solution given on the question you refer to is that there is no support for loops in the diagram. Ad that makes all the difference. – Martin Kristiansen Apr 27 '12 at 10:44
  • @DanD.: For some, unknown to man, sort of reason the answer is tcl code. I was hoping there was a generic solution for this sorta thing :-( – Martin Kristiansen Apr 27 '12 at 10:46
  • 1
    @MartinKristiansen, err, not sure if I understand you. The Q&A I linked to contains many answers to tools that generate railroad diagrams (the tool mentioned by Peter contains loops). One of the answers even links to [this Q&A](http://stackoverflow.com/questions/773371/what-is-a-good-tool-for-creating-railroad-diagrams) which is an **exact** duplicate of your question. – Bart Kiers Apr 27 '12 at 11:05

1 Answers1

1

This example looks a lot like a finite automaton -- i.e. the graph equivalent of a regular expression. If you can repesent your grammar to a RE (naturally, not all grammars will be representable as REs!), you can use the Kleene's theorem to translate it into a FA graph.

Note that the alphabet in question for the REs is not single letters, but words and tokens. In the above example, the corresponding RE looks like:

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 "," */
|()
)

This translates into a FA very similar to your diagram. GraphViz will do a passable job of drawing it legibly.

FA for above RE

However that's not quite the same as the original, is it? Presenting it nicely is the next challenge. I'd suggest taking the nested RE expressions and rendering them recursively, starting at the leaves.

For example, to render (WHERE expr|()):

  1. Two alternate paths. Render each separately:
    1. Render WHERE expr:
      1. Render WHERE as box.
      2. Then an arrow.
      3. Then render expr as a box.
    2. Render () as a single arrow.
  2. Find the longest (the first one) and stretch the others to match it.
  3. Create start and end nodes at each end.
  4. Draw connecting edges from the start node to each subpart, then from each subpart to the end node.

Doing this graphically means keeping track of box sizes and positions, including invisible boxes. There is an invisible box round each subpart. There are three things to note about the recursive structure:

  1. The size of a part depends on the sizes of its children.
  2. The location of a subpart depends on the location of its parent.
  3. Locations of everything (may) depend on the sizes of everything else.

This implies that you should first calculate the sizes of each part, starting at the bottom. Then, once you know the size of the root, you can start positioning the parts, top-down.

Edmund
  • 10,533
  • 3
  • 39
  • 57