Surf Wiki
Save to docs
linguistics

From Surf Wiki (app.surf) — the open knowledge base

Syntax diagram

Visual description of context-free grammar

Syntax diagram

Visual description of context-free grammar

Syntax diagrams (or railroad diagrams) are a way to represent a context-free grammar. They represent a graphical alternative to Backus–Naur form, EBNF, Augmented Backus–Naur form, and other text-based grammars as metalanguages. Early books using syntax diagrams include the "Pascal User Manual" written by Niklaus Wirth (diagrams start at page 47) and the Burroughs CANDE Manual. In the compilation field, textual representations like BNF or its variants are usually preferred. BNF is text-based, and used by compiler writers and parser generators. Railroad diagrams are visual, and may be more readily understood by laypeople, sometimes incorporated into graphic design. The canonical source defining the JSON data interchange format provides yet another example of a popular modern usage of these diagrams.

Principle

The representation of a grammar is a set of syntax diagrams. Each diagram defines a "nonterminal" stage in a process. 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 possible paths between these two points by going through other nonterminals and terminals. Historically, terminals have been represented by round boxes and nonterminals by rectangular boxes but there is no official standard.

Example

We use arithmetic expressions as an example, in various grammar formats.

BNF:

<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"

EBNF:

expression = term , [ "+" , expression ];
term       = factor , [ "*" , term ];
factor     = constant | variable | "(" , expression , ")";
variable   = "x" | "y" | "z"; 
constant   = digit , { constant };
digit      = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";

ABNF:

expression = term ["+" expression]
term       = factor ["*" term]
factor     = constant / variable / "(" expression ")"
variable   = "x" / "y" / "z"
constant   = 1*digit
DIGIT      = "0" / "1" / "2" / "3" / "4" / "5" / "6" / "7" / "8" / "9"

ABNF also supports ranges, e.g. , but it is not used here for consistency with the other examples.

Red (programming language) Parse Dialect:

Red [Title: "Parse Dialect"]
expression: [term opt ["+" expression]]
term:       [factor opt ["*" term]]
factor:     [constant | variable | "(" expression ")"]
variable:   ["x" | "y" | "z"]
constant:   [some digit]
digit:      ["0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"]

This format also supports ranges, e.g. , but it is not used here for consistency with the other examples.

One possible syntax diagram for the example grammars is below. While the syntax for the text-based grammars differs, the syntax diagram for all of them can be the same because it is a metalanguage.

&quot;Railroad&quot; syntax diagram

References

Note: the first link is sometimes blocked by the server outside of its domain, but it is available on archive.org. The file was also mirrored at standardpascal.org.

References

  1. [http://e-collection.library.ethz.ch/eserv/eth:3059/eth-3059-01.pdf Niklaus Wirth: ''The Programming Language Pascal.'' (July 1973)]
  2. [http://bitsavers.org/pdf/burroughs/B6500_6700/5000318_B6700_CANDE_Oct72.pdf Burroughs B6700/B7700 ''Command AND Edit (CANDE) Language: Information Manual'']
Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

formal-languages diagrams
Want to explore this topic further?

Ask Mako anything about Syntax diagram — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report