Syntax diagrams (by )

I've always liked syntax diagrams as a way of describing languages. They make it clear what options are legal in any given situation.

However, drawing them by hand is tedious, so after a moment's thought, I realised it would be pretty trivial to design a reasonable layout algorithm to generate them automatically.

And so, on a train journey, banterpixra was born!

It's quite simple. It takes a BNF-esque grammer, encoded in s-expressions like so:

(rule
 . (choice
    rule-label
    literal
    (seq "(elidable" " " literal ")")
    (seq "(optional" " " rule ")")
    (seq "(zero-or-more" " " rule ")")
    (seq "(one-or-more" " " rule ")")
    (seq "(seq" (one-or-more (seq " " rule)) ")")
    (seq "(choice" (one-or-more (seq " " rule)) ")")
    (seq "(optional-choice" (one-or-more (seq " " rule)) ")")
    (seq "(comment" " " literal " " rule ")")))

...and it turns it into a nice syntax diagram, rendered as an SVG file. I found producing an SVG to be a very easy way of generating vector images - SVG is quite a decent format to generate, and inkscape will happily convert .svg files to .png and .pdf from the command line, so it's easy to automate rendering.

The layout algorithm is quite easy. The BNF is parsed, and a tree of layout objects generated from the bottom up. Layout objects may contain other layout objects, recursively, and cover a rectangular extent of the two-dimensional plane. New layout objects are created at the origin, and then the parent layout looks at the sizes of the child layouts within it, and relocates them to appropriate locations within itself. When the layout object tree has been generated, it's processed top-down to generate actual SVG. Each different type of layout object renders its children recursively (unless it's a terminal, in which case it just renders itself at the chosen location), then it adds the arrows and lines that join the children together.

That's really all there is to it.

The output is quite decent, if your browser supports SVG!

1 Comment

  • By elderK, Tue 12th Feb 2013 @ 10:35 am

    I've been looking for something like this! Doing this kind of thing in GraphViz by hand is tedious as hell.

    And you're right: syntax diagrams are very useful and far easier to understand in a glance than a bunch of BNF rules.

Other Links to this Post

RSS feed for comments on this post.

Leave a comment

WordPress Themes

Creative Commons Attribution-NonCommercial-ShareAlike 2.0 UK: England & Wales
Creative Commons Attribution-NonCommercial-ShareAlike 2.0 UK: England & Wales