Syntax diagram
From Wikipedia, the free encyclopedia
Syntax diagrams (or railroad diagrams) are a way to represent a formal grammar. They represent a graphical alternative to Backus-Naur Form or EBNF. Early books using syntax diagrams include the "Pascal User Manual" written by Niklaus Wirth [1] (diagrams start at page 47) and the Burroughs CANDE manual [2]. In the compilation field, textual representations like BNF or its variants are usually preferred. BNF is well understood by compiler writers and compilers, but is not well understood by most users of languages. Railroad diagrams are more readily understood by most people. Some of the popularity of the JSON data interchange format is due to its representation in railroad diagrams.
Contents |
[edit] 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.
[edit] Example
We use arithmetic expressions as an example. First we provide a simplified BNF grammar:
<expression> ::= <term> | <term> "+" <expression> <term> ::= <factor> | <factor> "*" <term> <factor> ::= <constant> | <variable> | "(" <expression> ")" <variable> ::= "x" | "y" | "z" <constant> ::= <digit> | <digit> <constant> <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
This grammar can also be expressed in EBNF:
expression = term , {"+" term}; term = factor , {"*" factor}; factor = constant | variable | "(" , expression , ")"; variable = "x" | "y" | "z"; constant = digit , {digit}; digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";
One possible set of syntax diagrams for this grammar is :
[edit] See also
- Extended Backus-Naur form (EBNF)
[edit] References
[edit] External links
- (English) JSON website including syntax diagrams
- (English) Automatic generator of syntax diagrams
- (English) Syntax diagrams of BNF
- (English) Generator from EBNF
- (English) From EBNF to a postscript file wit the diagrams
Chomsky hierarchy |
Grammars | Languages | Minimal automaton |
---|---|---|---|
Type-0 | Unrestricted | Recursively enumerable | Turing machine |
n/a | (no common name) | Recursive | Decider |
Type-1 | Context-sensitive | Context-sensitive | Linear-bounded |
n/a | Indexed | Indexed | Nested stack |
n/a | Tree-adjoining etc. | (Mildly context-sensitive) | Embedded pushdown |
Type-2 | Context-free | Context-free | Nondeterministic pushdown |
n/a | Deterministic context-free | Deterministic context-free | Deterministic pushdown |
Type-3 | Regular | Regular | Finite |
n/a | Star-free | Counter-Free | |
Each category of languages or grammars is a proper subset of the category directly above it, and any automaton in each category has an equivalent automaton in the category directly above it. |