BACKUS-NAUR FORM IS A NOTATION FOR WRITING CONTEXT-FREE GRAMMARS. It contains no mathematical content beyond the CFG of the earlier topic — IT IS A SYNTAX FOR GRAMMARS, adopted because it is readable by engineers rather than only by theorists. ── THE NOTATION ──────────────────────────────────────────── <name> a NON-TERMINAL, written in angle brackets ::= "is defined as" — the production arrow | alternation, exactly as in a CFG literal text TERMINALS, often quoted THE CORRESPONDENCE WITH THE FORMAL DEFINITION: <expr> ::= <expr> "+" <term> | <term> is precisely E → E + T | T A SMALL COMPLETE EXAMPLE — arithmetic expressions: <expr> ::= <expr> "+" <term> | <expr> "-" <term> | <term> <term> ::= <term> "*" <factor> | <term> "/" <factor> | <factor> <factor> ::= "(" <expr> ")" | <number> | <ident> <number> ::= <digit> | <number> <digit> <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" NOTE THAT THE SAME LAYERING FOR PRECEDENCE APPEARS, and for the same reason: BNF inherits every property of the underlying grammar, including ambiguity if the grammar is ambiguous. ── THE WEAKNESS OF PLAIN BNF ─────────────────────────────── Repetition and optionality must be expressed by RECURSION, which is verbose and obscures intent: "a list of one or more items separated by commas" <list> ::= <item> | <list> "," <item> "an optional else clause" <if> ::= "if" <cond> "then" <stmt> | "if" <cond> "then" <stmt> "else" <stmt> — the entire production must be duplicated. ── EXTENDED BNF (EBNF) ───────────────────────────────────── Adds three constructs, standardised as ISO 14977: [ x ] OPTIONAL — zero or one occurrence { x } REPETITION — zero or more occurrences ( x | y ) GROUPING THE SAME EXAMPLES BECOME: <list> ::= <item> { "," <item> } <if> ::= "if" <cond> "then" <stmt> [ "else" <stmt> ] DRAMATICALLY CLEARER, and note something important: THE REPETITION FORM { x } IS NEITHER LEFT- NOR RIGHT-RECURSIVE, SO IT EXPRESSES NO ASSOCIATIVITY. That is an advantage for readability and a problem for meaning — the specification must state associativity separately in prose, or the implementer must decide. SOME EBNF DIALECTS ADD: x+ one or more x? optional (same as [ x ]) x* zero or more (same as { x }) which is the regular-expression-influenced style used by most modern parser generators. IMPORTANT: EBNF ADDS NO EXPRESSIVE POWER. Every EBNF grammar can be mechanically rewritten in plain BNF: { x } becomes <new> ::= ε | <new> x [ x ] becomes <new> ::= ε | x IT IS SYNTACTIC SUGAR — a genuine improvement in readability with no change to the class of languages describable, which remains exactly the context-free languages. ── AUGMENTED BNF (ABNF) ──────────────────────────────────── RFC 5234, used throughout the internet standards. Its distinctive features: rule = definition (no angle brackets) n*m element repetition with explicit bounds %x41 a character by hex code "abc" case-INSENSITIVE literal by default EVERY IETF PROTOCOL — HTTP, SMTP, URIs, JSON — DEFINES ITS SYNTAX IN ABNF, which makes it arguably the most widely deployed grammar notation in existence. ── SYNTAX DIAGRAMS (RAILROAD DIAGRAMS) ───────────────────── A graphical equivalent of EBNF, in which a valid string is any path traced from left to right: · a straight line is a sequence · a branch is an alternation · a backward loop is a repetition Used in the Pascal report and still common in database documentation. THEY CONTAIN EXACTLY THE INFORMATION OF THE EBNF THEY WERE DRAWN FROM — the choice is presentational.

── WHAT BNF IS USED FOR ──────────────────────────────────── 1. LANGUAGE SPECIFICATION. The syntax section of every language standard. 2. INPUT TO PARSER GENERATORS. yacc, bison, ANTLR and their relatives all consume a BNF-like grammar and emit a parser. THE GRAMMAR IN THE SPECIFICATION AND THE GRAMMAR IN THE COMPILER ARE OFTEN THE SAME FILE, which is how a standard and its implementation are kept in step. 3. DOCUMENTATION — command-line syntax, configuration file formats, protocol messages. 4. PROTOCOL DEFINITION, via ABNF as above. 5. TEST GENERATION — a grammar can be run BACKWARDS to generate random valid inputs, which is the basis of GRAMMAR-BASED FUZZING for finding parser bugs. ── A WORKED SPECIFICATION FRAGMENT ───────────────────────── A small language's statement syntax in EBNF: program = { declaration } , { statement } ; declaration = type , identifier , [ "=" , expression ] , ";" ; type = "int" | "float" | "char" | "bool" ; statement = assignment | if_stmt | while_stmt | block ; block = "{" , { statement } , "}" ; assignment = identifier , "=" , expression , ";" ; if_stmt = "if" , "(" , expression , ")" , statement , [ "else" , statement ] ; while_stmt = "while" , "(" , expression , ")" , statement ; identifier = letter , { letter | digit | "_" } ; READ THE if_stmt RULE CAREFULLY: the optional else is written [ "else" , statement ] — WHICH IS EXACTLY THE DANGLING ELSE AMBIGUITY OF THE PREVIOUS TOPIC, expressed compactly. EBNF's brevity does not remove the ambiguity; it hides it, which is a genuine hazard of the notation. The specification must add a prose rule stating that else binds to the nearest if. ── THE LIMITS OF BNF ─────────────────────────────────────── BNF DESCRIBES SYNTAX ONLY, and only context-free syntax. It cannot express: · "a variable must be declared before use" · "the types on both sides of an assignment must match" · "the number of arguments must match the declaration" · "a break statement must be inside a loop" · SEMANTICS OF ANY KIND — what a construct MEANS THESE ARE STATED IN PROSE ALONGSIDE THE GRAMMAR IN EVERY LANGUAGE STANDARD, and enforced by the compiler's semantic analysis phase using a symbol table. THE DIVISION IS EXACTLY THE ONE PREDICTED BY THE CHOMSKY HIERARCHY: the CFG handles nesting, and everything requiring long-range matching is pushed to a later phase. FORMAL METHODS FOR THE REST: ATTRIBUTE GRAMMARS attach ATTRIBUTES to grammar symbols and SEMANTIC RULES to productions, so that type information and symbol tables can be computed while parsing. SYNTHESISED attributes flow UP the tree (a node's type computed from its children); INHERITED attributes flow DOWN (a declaration's scope passed to its uses). DENOTATIONAL, OPERATIONAL and AXIOMATIC SEMANTICS are the formal frameworks for specifying what programs MEAN, and belong to the programming languages subject rather than this one. ── THE SUMMARY ───────────────────────────────────────────── BNF IS A CFG IN ENGINEERS' NOTATION. Nothing about the theory changes; what changes is that a language committee, a compiler writer and a textbook author can all read the same document. THAT IS NOT A SMALL ACHIEVEMENT — the ALGOL 60 report is remembered precisely because it was the first time a language's syntax was stated without ambiguity of description, and every subsequent language has followed it.