Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there an extension to railroad diagrams to capture exceptions?

Railroad diagrams are a popular method to visualize context-free grammars and you can map Backus-Naur Form to these diagrams. But some variants of BNF, for instance W3C-BNF allow exceptions (as context-free languages are not closed under difference, these exceptions must be regular). I'd like to visualize a grammar with exceptions in a railroad diagram. Should I invent my own extension to the graphical notation or has someone already experimented with this?

Here is an example of a rule with exception (yes, you could also express this particular grammar without exception, but that's not the point):

comment := "<!--" (string - "--") "-->"

An exception can be any regular grammar. I thought about adding exception connected to non-terminal symbols by some special type of arrow or line (here indicated with exclamation marks):

[<] → [!] → [-] → [-] → (string) → [-] → [-] → [>]
                          !
                          ! → [-] → [-] → ↯

P.S: The grammar was wrong, it should be

comment := "<!--" (string - (string "--" string | string "-")) "-->"

Maybe the non-intuitive use of negation is one reason why it is little used in formal grammars?

like image 233
Jakob Avatar asked Oct 13 '22 17:10

Jakob


1 Answers

When writing a Railroad Diagram Generator for W3C grammars recently, I thought for a while about how to represent this, but I could not come up with a solution that I was happy with. Did not find any examples to follow either.

It is not only the set-difference operator, for which there is no graphical equivalent in conventional railroad diagrams. The notation for codepoints, ranges, and complements also does not fit well.

In the end I refrained from extending the model graphically. What I did is draw a terminal box to hold the grammar fragment that has no railroad equivalent in the original notation. For distinguishing this from literal boxes, it is set in italics. Here is an example from the XML recommendation:

XML comment railroad diagram

The EBNF production was:

Comment ::= '<!--' ((Char - '-') | ('-' (Char - '-')))* '-->'

Edit:

Following Jakob's proposal for a different shape, unresolved EBNF expressions are now shown in a hexagon:

enter image description here

like image 133
Gunther Avatar answered Oct 18 '22 01:10

Gunther