bnf.rst
author Oleksandr Gavenko <gavenkoa@gmail.com>
Sat, 03 Oct 2015 18:29:10 +0300
changeset 1765 2132765de2f4
parent 418 3a5d2c76aa30
permissions -rw-r--r--
Cellular automaton.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
418
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
     1
-*- mode: outline; coding: utf-8 -*-
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
     2
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
     3
* What is BNF?
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
     4
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
     5
BNF is an acronym for "Backus Naur Form". John Backus and Peter Naur
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
     6
introduced for the first time a formal notation to describe the syntax of a
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
     7
given language (ALGOL 60 programming language).
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
     8
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
     9
  rfc2234
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    10
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    11
* BNF syntax.
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    12
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    13
The meta-symbols of BNF are:
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    14
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    15
  ::=
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    16
    meaning "is defined as"
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    17
  |
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    18
    meaning "or"
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    19
  < >
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    20
    angle brackets used to surround category names (some times skipped).
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    21
  [  ]
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    22
    optional items are enclosed in.
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    23
  { }
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    24
    repetitive items (zero or more times) are enclosed in.
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    25
  " "
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    26
    terminals are enclosed in to distinguish them from meta-symbols.
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    27
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    28
* BNF in BNF.
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    29
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    30
  syntax     ::=  { rule }
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    31
  rule       ::=  identifier  "::="  expression
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    32
  expression ::=  term { "|" term }
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    33
  term       ::=  factor { factor }
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    34
  factor     ::=  identifier |
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    35
                  quoted_symbol |
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    36
                  "("  expression  ")" |
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    37
                  "["  expression  "]" |
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    38
                  "{"  expression  "}"
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    39
  identifier ::=  letter { letter | digit }
3a5d2c76aa30 BNF syntax.
Oleksandr Gavenko <gavenkoa@gmail.com>
parents:
diff changeset
    40
  quoted_symbol ::= """ { any_character } """