a grammar

Imagine you have a tiny machine that does not check sentences — it BUILDS them. You start with a single placeholder, and you keep replacing placeholders with other pieces according to a fixed list of rules, until nothing but real words is left. A grammar is exactly this: a finite set of rewriting rules that GENERATES strings, rather than a machine like a DFA that READS a string and decides yes or no. This is the second great way to describe a language, and it flips the question from recognition to production.

Concretely, a grammar has a few ingredients: some special placeholder symbols (called variables or nonterminals) that stand for 'a piece that is still under construction', the actual letters of the alphabet that show up in finished strings (terminals), one chosen starting placeholder, and a list of production rules of the form 'this placeholder may be rewritten as that sequence'. You generate a string by starting from the start symbol and applying rules over and over, each time replacing a placeholder with one of its allowed right-hand sides, until only terminals remain. The set of ALL strings you can produce this way is the language the grammar generates.

Grammars matter because they capture STRUCTURE in a way finite automata cannot easily show. A rule like S → ( S ) is recursive: S contains another S inside it, and that nesting is exactly what describes balanced brackets, nested code blocks, and arithmetic expressions. Different families of grammars sit at different rungs of the Chomsky hierarchy; the most important rung for programming languages is the context-free grammar, the focus of this field. Be careful not to confuse a grammar (which generates) with a parser (which, given a string, tries to discover how the grammar could have generated it).