BNF and Real Language Syntax

The grammar you already know, in working clothes

Here is a quietly remarkable fact to open with: the context-free grammar you have been scribbling all rung — variables, terminals, rules like E → E + T — is literally the same device that the reference manual for Python, C, JSON, or SQL uses to define what counts as a legal program. The manuals just write it in a standard skin called BNF (Backus-Naur Form), invented around 1960 to pin down the syntax of ALGOL. Nothing new is happening underneath; you already own the machinery. This guide is the bridge from the chalkboard to the page where real syntax actually lives.

The translation is almost cosmetic. A variable (nonterminal) is wrapped in angle brackets, like <expr> or <stmt>; the rewrite arrow → becomes ::= (read 'is defined as'); the choice bar | stays exactly the bar you already use; terminals — the literal characters that survive into the program — are written plainly or quoted. So your rule E → E + T | T, expressed in BNF, reads <expr> ::= <expr> "+" <term> | <term>. Same variables, same terminals, same alternatives, same recursion. If you can read a grammar, you can read BNF.

EBNF: the sugar that tames repetition

Plain BNF gets clumsy fast. Suppose a function call has zero or more comma-separated arguments. In bare BNF you must spell repetition with a recursive helper variable: <args> ::= <arg> | <arg> "," <args>, and an empty case for 'no arguments at all.' It works, but every list in the language breeds its own little recursive rule, and the page fills with bookkeeping. EBNF (Extended BNF) adds three pieces of shorthand that absorb these common patterns directly.

The three are: braces { X } meaning 'zero or more copies of X' (a Kleene-star style repetition); square brackets [ X ] meaning 'X is optional — zero or one'; and round parentheses ( X | Y ) for grouping alternatives inline. With these, the argument list collapses to one readable line: <args> ::= [ <arg> { "," <arg> } ] — read it as 'optionally: one arg, then any number of comma-arg pairs.' This is the same language as the recursive BNF; EBNF is pure sugar that expands back into ordinary context-free rules.

Two layers: a lexer feeds the grammar

Real language specs almost never run the grammar over raw characters. They split the work into two layers, and it is worth seeing why. First a scanner (or lexer) sweeps the character stream and chunks it into tokens — the words of the language: the identifier `count`, the number `42`, the keyword `while`, the operator `==`. This first layer is purely regular: the lexer is essentially a DFA built from regular expressions, exactly the tool from the rungs below. It knows nothing about nesting; it just classifies runs of characters.

Then the context-free grammar runs over the token stream, not the letters. Its terminals are token kinds (IDENT, NUMBER, '+', 'while'), and its job is the genuinely context-free part: the nesting of expressions, blocks, and statements that a DFA provably cannot handle (recall a^n b^n). This division is not laziness — it matches the parsing you have already glimpsed, where a recursive-descent parser walks a leftmost derivation while requesting one token at a time. Regular work to the regular tool, context-free work to the grammar.

The grammar also does not just answer 'legal or not.' Riding on the parse tree it builds, the front end emits an abstract syntax tree (AST): a slimmed-down tree that drops the noise — parentheses, separators, layers introduced only to force precedence — and keeps the bare structure that means something. The concrete parse tree records exactly how the grammar matched; the AST records what the program is. Later compiler stages walk the AST, not the original text.

A tiny real grammar, end to end

Let us assemble everything you have learned into one believable fragment of a language: arithmetic expressions, an `if` statement, and a block. Watch the techniques from the whole rung show up by name: layered variables (<expr>, <term>, <factor>) to encode that * binds tighter than +; EBNF braces for the statement list; the recursion <factor> ::= "(" <expr> ")" that gives the unbounded nesting a DFA never could. This is not a toy version of how it is done — it is genuinely how a manual's grammar section looks.

Tokens (from the lexer, a DFA):  IDENT  NUMBER  if  (  )  {  }  ==  +  *

Grammar in EBNF (runs over tokens, not characters):

  <block>  ::= "{" { <stmt> } "}"
  <stmt>   ::= <if> | <expr> ";"
  <if>     ::= "if" "(" <expr> ")" <block>

  <expr>   ::= <term>   { "+" <term> }      // + binds loosest
  <term>   ::= <factor> { "*" <factor> }    // * binds tighter
  <factor> ::= IDENT | NUMBER | "(" <expr> ")"

Parse-tree skeleton for the token stream  a + b * c :

        <expr>
        /  |  \
   <term>  +  <term>
      |       /  |  \
  <factor> <fac> * <fac>
      |      |       |
      a      b       c        ->  groups as  a + (b * c),  one tree only

Trace what the layering buys you. Because every + lives at the <expr> level and every * at the deeper <term> level, the only way to build a + b * c is to first form the <term> b * c and then add it — the grouping a + (b * c) is forced, and the dangerous flat rule <expr> ::= <expr> "+" <expr> | <expr> "*" <expr> that admitted two trees is gone. The precedence you would otherwise carry in your head is now baked into the shape of the rules, exactly the cure from the ambiguity guide, just published in BNF.

Where the clean theory gets honest

Now the honest part, because real grammars are not as tidy as the chalkboard. Famous case: the dangling-else. With <stmt> ::= "if" <expr> <stmt> | "if" <expr> <stmt> "else" <stmt> | ..., the string `if a if b s else t` has two parse trees — does the `else` pair with the inner `if` or the outer one? That is genuine grammar ambiguity. Languages like C and Java do not fix it by rewriting the grammar; they keep the ambiguous-looking rule and bolt on a disambiguation rule in prose: 'an else matches the nearest unmatched if.' The published grammar stays ambiguous; a side note settles it.

And there is a deeper, more sobering limit. A programming language's full set of rules — 'a variable must be declared before use,' 'the call passes the right number of arguments,' 'the types match' — is not context-free at all. The classic witness is the pattern behind a^n b^n c^n, which is provably outside the context-free world; declaration-before-use has the same flavour. So the grammar in the manual captures only the context-free skeleton of legality. Everything beyond it is checked by later, non-grammar passes (name resolution, type checking) that the BNF deliberately does not try to express.

Closing the rung

Look back at the climb. You saw why grammars exist (finite automata cannot match nested brackets); you learned derivations and parse trees as the record of structure; you practised designing grammars for a^n b^n, balanced brackets, and arithmetic; you removed ambiguity by layering precedence and associativity; and now you can read the BNF and EBNF that real manuals actually print. The context-free grammar is no longer an abstraction — it is the working definition of programming-language syntax, lexer in front and AST behind.

Two threads now run forward out of this rung. One asks which machine matches this generating power on the recognising side — the pushdown automaton, a finite control with one stack of plates where you only ever touch the top; that stack is exactly the unbounded memory the DFA lacked, and it turns out a CFG and a PDA describe the very same languages. The other thread asks how a computer actually parses — the recursive-descent and LR algorithms that build the leftmost and rightmost derivations you already met. You arrived at this rung able only to read strings; you leave it able to generate them, structure them, and publish their grammar the way the rest of the world does.