Grammars and Languages Intro: Explained with Examples

A grammar is a set of rules that generates the strings of a language — where "language" means any precisely defined set of strings, from arithmetic expressions to Python programs. Grammars answer the question: which strings are valid, and what is their structure?

They matter because every programming language is defined by a grammar. Compilers use grammars to parse code into trees, and the same mathematics describes file formats, network protocols and even fragments of human language.

Key Concepts

• Terminal: an actual symbol of the language, like a, plus or an open bracket.
• Nonterminal: a placeholder symbol, written in capitals like S or Expr, that gets replaced during derivation.
• Production: a rewrite rule such as S goes to aSb, read "S may be replaced by aSb".
• Start symbol: the nonterminal from which every derivation begins, usually S.
• Derivation: the sequence of replacements producing a string of terminals.
• Language of a grammar: the set of all terminal strings derivable from the start symbol.

How It Works

1. Start with the start symbol S.
2. Repeatedly pick a nonterminal and replace it using one of its productions.
3. When no nonterminals remain, the resulting terminal string belongs to the language.
4. Different production choices can yield different strings — the grammar generates a whole set.
5. A parse tree records the derivation as a tree, showing the string's structure.

Worked Example

Consider the grammar with productions S goes to aSb, or S goes to the empty string. Derive "aabb": start with S; apply the first production to get aSb; apply it again to the inner S to get aaSbb; apply the empty production to get aabb. Each application adds one a on the left and one b on the right, so the grammar generates exactly the strings with n a's followed by n b's for n = 0, 1, 2, and so on: the empty string, ab, aabb, aaabbb, and beyond. No finite automaton can recognise this language, which is why grammars are strictly more powerful.

Common Misconceptions

• "A grammar checks meaning." Grammars define syntax (form), not semantics (meaning) — a sentence can be grammatically fine yet meaningless.
• "One grammar, one string." A grammar with recursive productions generates infinitely many strings.
• "Regular expressions and grammars are the same." Regex describe regular languages; grammars (context-free and beyond) describe richer ones.

Real-World Applications

• Compilers: parsers turn source code into syntax trees using the language's grammar.
• Data formats: JSON, XML and network protocols are specified with grammar-like rules.
• Natural language processing: grammars model sentence structure for parsing and generation.

Grammars generate languages through productions that rewrite nonterminals into terminals, as the a-to-the-n b-to-the-n example shows. They are the formal foundation of programming-language syntax and everything built on parsing.