The Development of Syntax Notations

Apology

The bad news: there was a mixup; two different talks by me were assigned to this slot.

The other was ixml standards update.

The good news: there is a whole paper about it from this year's XML Prague; available on my home page.

In the beginning

1951 Kleene, regular language in automata theory.

Uses Kleene star *.

In logic parent* x = x or parent x or parent parent x etc.

Chomsky

Mid 50's

uses arrows as definition symbol
uses capitals for nonterminals, lower case for terminals
terminals stand for themselves,
connects terms in an alternative with ^,
seems to use "," as alternative separator (one example)

Sentence → NP^VP
VP → Verb^NP
NP → the^man, the^book

Later:

A → BcD
A → a
S → ε

BNF Late 50's

Introduced by Backus for Algol 60

Wrongly quotes nonterminals instead of terminals

Uses ::= as definition symbol
Rules are not explicitly terminated
Nonterminals are enclosed by angle brackets and may contain spaces
Terminals stand for themselves
Introduced alternatives, had to use | for alternatives

Therefore there are some reserved symbols: ::=, and |, chosen because they don't appear in Algol60

Not a normal form, so renamed to Backus Naur Form

<if clause> ::= if <Boolean expression> then
<unconditional statement> ::= 
   <basic statement>|
   <for statement>|
   <compound statement>|
   <block>
<if statement> ::= 
    <if clause> <unconditional statement>|
    <label>: <if statement>
<conditional statement> ::= 
    <if statement>|
    <if statement> else <statement>

vwf mid 60's

Used for Algol 68

uses ":" as definition symbol
uses "." to end rule
nonterminals can contain spaces
alternatives separated by ";"
terms are separated by ","
terminals are named *symbol, plus a list of representations.

exponent part: 
   times ten to the power choice, power of ten.
times ten to the power choice: 
   times ten to the power symbol;
   letter e symbol.

Uses second level to define repetition and option etc. *option *list *sequence *pack

THING option: THING; EMPTY.
THING sequence: THING; THING, THING sequence.

=> letter sequence option

Wirth WSN 1977

Uses = as definition symbol
rules are terminated with "."
alternatives separated by "|"
terms separated by space
terminals are quoted
Uses {} for repetition
[] for optional
Allows grouping with ()

No way of expressing "empty".

syntax = {production}.
production = identifier "=" expression ".".
expression = term {"|" term}.
term = factor {factor}.
factor = 
   identifier | 
   literal | 
   "(" expression ")" |
   "[" expression "]" | 
   "{" expression "}".
literal = """" character {character} """".

Wirth EBNF

Now ISO / IEX 14997 (1996)

= for definition symbol
rules terminated with ";"
| for alternatives
uses "," to separate terms
Nonterminal names may contain spaces
Terminals are quoted
[] for option
{} for repeat
(* comment *)
6 * letter
empty is empty
has 'exceptions' { all characters - '"' }

all characters = ? all visible characters ? ;

symbol = "[" | "]" | "{" | "}" |
         "(" | ")" | "<" | ">" |
         "'" | '"' | "=" | "|" | 
         "." | "," | ";" | "-" |
         "+" | "*" | "?" | "\n"|
        "\t" | "\r" | "\f" | "\b" ;

character = letter | digit | symbol |
            "_" | " " ;
identifier = letter, { letter | digit | "_" } ;

S = { " " | "\n" | "\t" | "\r" |
     "\f" | "\b" } ;

terminal = "'" , character - "'" , 
           { character - "'" } , "'"
         | '"' , character - '"' , 
           { character - '"' } , '"' ;

ABNF

rfc 733 1977 first appearance
rfc 2234 1997 first def
rfc 4234 2005
rfc 5234 2008

Uses = for definition symbol
no rule terminator
/ for alternatives
space is term separator
; for comments to end of line
terminals are quoted
case insensitive, even in terminals!
can use =/ to add to a rule
grouping with ()
[option]
*name for repetition
uses prefix notations: 2 digit, *1(option) 0*1(option) 1*(element) is one or more.
character ranges, but only over octals

rulelist     =  1*( rule / (*c-wsp c-nl) )
rule         =  rulename defined-as elements c-nl
                ; continues if next line starts
                ; with white space
rulename     =  ALPHA *(ALPHA / DIGIT / "-")
defined-as   =  *c-wsp ("=" / "=/") *c-wsp
                ; basic rules definition and
                ; incremental alternatives