Theory

A tutorial on the compiler-construction theory behind Alpaca: what a lexer and parser actually are, how regular expressions become finite automata, how context-free grammars drive LR parsing, and where conflicts, ambiguity, and error recovery come from.

You don't need any of this to use the library — the reference pages and the Cookbook are enough to build a language. Read this section when you want to understand why a grammar has a conflict, what the generated parse table means, or how the pieces fit together formally.

Start with The Compilation Pipeline for the mental model everything else builds on, then follow the chapters in order:

• The Compilation Pipeline — the four stages from source text to typed result
• Tokens and Lexemes — token classes vs. instances, and how Alpaca represents them
• The Lexer: Regex to Finite Automata — compiling regular expressions
• Regular vs Context-Free — why lexing and parsing are separate problems
• Context-Free Grammars — productions, derivations, parse trees
• EBNF and Extended Notations — repetition and optionality operators
• The Shift-Reduce Loop — the core parsing algorithm
• Why LR Parsing — the trade-offs behind Alpaca's choice
• Conflicts and Disambiguation — shift/reduce and reduce/reduce
• Semantic Actions — attaching meaning to reductions
• AST Construction Patterns — shaping the output tree
• Operator Precedence Grammars — encoding precedence and associativity
• Ambiguity — grammars with more than one parse
• Error Recovery Theory — continuing past a syntax error
• Attribute Grammars — the formal model behind semantic actions
• Full Calculator Example — every concept in one worked grammar