a parser generator

Writing a parser by hand is tedious and error-prone, especially as a language grows. A parser generator is a program you give a grammar to, and it writes the parser for you, the same way a 3D printer takes a design file and produces the physical object. You describe the shape of the language; the tool produces the source code of a parser that recognizes it.

You feed the generator a grammar in a notation close to BNF, with each rule optionally tagged with a semantic action, a snippet of code to run when that rule is reduced, typically to build a node of the abstract syntax tree. The classic tools yacc and its open successor bison compute an LALR(1) bottom-up parsing table from your grammar and emit a fast table-driven parser in C; ANTLR takes the top-down route, generating a predictive (LL-style, with extended look-ahead) recursive-descent parser. Crucially, parser generators usually pair with a scanner generator (lex or flex) that turns regular-expression token definitions into the lexer, enforcing the standard division of labour: the generated scanner produces tokens, the generated parser consumes them and builds the tree.

Parser generators matter because they turn decades of automata theory into a button you press. Instead of hand-coding error-prone shift-reduce tables, you maintain a readable grammar and regenerate the parser whenever the language changes. The honest catch is that the generated parser is only as good as your grammar: if the grammar is ambiguous or outside the tool's class, the generator reports shift-reduce or reduce-reduce conflicts that you must understand and resolve, usually with precedence and associativity declarations or by rewriting rules. The tool automates the mechanism, not the grammar design.