A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Not every context-free grammar is equally suitable for parsing. Some have shift-reduce conflicts, left-recursion, or ambiguities making parsing difficult. Grammar designers must write grammars that are both unambiguous and compatible with the target parsing algorithm.
Write grammars for small languages and test them with parser generators. Experiment with resolving conflicts through grammar transformations.
Any grammar accepting the language is fine (some are much harder to parse than others). Removing left-recursion is the only transformation needed (you may also eliminate ambiguities or handle precedence).
You already know that a context-free grammar defines which strings belong to a language, and you understand how compilers are organized into phases. But writing a grammar that is *theoretically correct* and writing one that *actually works with a parser* are different skills. Grammar design for compilation is the engineering discipline of crafting grammars that are not only unambiguous but also compatible with the specific parsing algorithm you intend to use — and that produce parse trees reflecting the semantic structure you need for later compiler phases.
The most common obstacle is ambiguity. The classic example is the "dangling else" problem: in `if a then if b then s1 else s2`, does the `else` belong to the inner or outer `if`? Both parse trees are valid under a naive grammar, which means the parser cannot decide. You resolve this by restructuring the grammar — introducing separate productions for "matched" and "unmatched" if-statements — so that only one parse tree is possible. Similarly, arithmetic expressions need their grammar to encode operator precedence and associativity: `3 + 4 * 5` must parse as `3 + (4 * 5)`, not `(3 + 4) * 5`. The standard technique uses a hierarchy of nonterminals — one level for each precedence tier — so that higher-precedence operators bind more tightly by appearing deeper in the grammar's production rules.
Different parsing algorithms impose different constraints on the grammar. Top-down parsers (like recursive descent) cannot handle left-recursion: a production like `Expr → Expr + Term` causes infinite recursion because the parser tries to expand `Expr` by immediately calling itself. The fix is left-recursion elimination, transforming `Expr → Expr + Term | Term` into `Expr → Term Expr'` and `Expr' → + Term Expr' | ε`. This produces the same language but lets the parser proceed. Bottom-up parsers (like LR parsers) handle left-recursion naturally but can stumble on shift-reduce conflicts — situations where the parser cannot decide whether to consume the next token or to reduce what it already has. Resolving these conflicts often requires grammar refactoring or explicit disambiguation rules in the parser generator.
The art of grammar design lies in balancing multiple concerns simultaneously. The grammar must be unambiguous, compatible with your chosen parser, and must produce a parse tree whose structure reflects the program's meaning — because later phases (type checking, code generation) walk that tree. A grammar that parses correctly but produces an awkward tree structure creates downstream headaches. Practical grammar design is iterative: write productions, test them against tricky inputs, run them through a parser generator to check for conflicts, refactor, and repeat. Tools like ANTLR, Yacc, and Bison provide concrete feedback — conflict reports that tell you exactly where your grammar is ambiguous or incompatible — making the design process a productive dialogue between you and the tool.