CFG design

Designing a context-free grammar is like writing a recursive recipe for an entire family of strings: you describe the simplest case directly, then describe how to build a bigger case out of smaller ones. The mindset is recursive thinking — 'a balanced string is either empty, or a smaller balanced string wrapped in a matching pair, or two balanced strings side by side'. Turn each such sentence into a production rule and you have a grammar.

In practice you proceed by identifying the recursive shape of the language and giving each meaningful sub-category its own nonterminal. A few patterns recur so often they are worth memorising. For matched counts a^n b^n: S → a S b | ε — each rule adds one a on the left and one b on the right, keeping them equal. For balanced brackets: S → ( S ) | S S | ε. For palindromes over {a, b}: S → a S a | b S b | a | b | ε — symmetric rules grow the string from both ends. For simple statement blocks: Block → { StmtList }, StmtList → Stmt StmtList | ε. The recursive rule (a nonterminal that reappears on its own right-hand side) is what lets a handful of rules describe infinitely many, ever-deeper strings.

For something like arithmetic you usually want more than mere generation — you want the grammar to ENCODE meaning, so its parse trees group operands the way the math does. That means baking in precedence and associativity with layered nonterminals (Expr for + and -, Term for * and /, Factor for atoms and parentheses), which also makes the grammar unambiguous. So good CFG design has two goals at once: generate exactly the right set of strings, AND give each string the parse tree that reflects its intended structure. A common beginner mistake is to write a grammar that generates the right language but is ambiguous — correct as a set, wrong as a description of meaning.