Syntax diagram

Syntax diagrams (or railroad diagrams) are a way to represent a formal grammar. They represent a graphical alternative to Backus-Naur Form or EBNF. Syntax diagrams are mainly used for educational purpose where finding a path within the diagrams can be a more intuitive way to introduce what parsing is that the classical derivation of a non terminal. In the compilation field, textual representations like BNF or its variants are usually preferred.

Principle

The representation of a grammar is made of a set of syntax diagrams. Each diagram defines a non-terminal. There is a main diagram which defines the language in the following way: to belong to the language, a word must describe a path in the main diagram.

Each diagram has an entry point and an end point. The diagram describes possibles paths between these two points by going through other nonterminals and terminals. Terminals are represented by round boxes while nonterminals are represented by square boxes.

Example

We use arithmetic expressions as an example. First we provide a simplified BNF grammar:

<expression> ::= <terme> | <terme> "+" <expression>

<terme> ::= <facteur> | <facteur> "*" <terme>

<facteur> ::= <constante> | <variable> | "(" <expression> ")"
 
<variable> ::= "x" | "y" | "z" 

<constante> ::= <chiffre> | <chiffre> <constante>

<chiffre> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

This grammar can also be expressed in EBNF:

expression = terme , {"+" terme};

terme = facteur , {"*" facteur};

facteur = constante | variable | "(" , expression , ")";
 
variable = "x" | "y" | "z"; 

constante = chiffre , {chiffre};

chiffre = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";

One possible set of syntax diagrams for this grammar is :