Compilers · Cluster
Lexing and Parsing
Tokenization, grammars, and parser construction.
- 01 Maximal Munch and the Boundary Between Tokens How a lexer decides where one token ends, why the longest-match rule is separate from the grammar, and which token sequences it produces that the source text does not appear to contain.
- 02 From Regular Expression to DFA Table: Inside a Lexer Generator Thompson construction, subset construction, and table compression, and why a generated lexer scans in time linear in the input no matter how many patterns were declared.
- 03 Recursive Descent and the Cost of One Token of Lookahead How a hand-written parser decides which production to take from a single token, how FIRST and FOLLOW sets make that decision safe, and why the method fails on left-recursive and prefix-sharing grammars.
- 04 Precedence Climbing for Binary Expressions How a loop with a minimum-binding-power parameter parses operator precedence and associativity in one function, and how its behaviour maps onto the grammar it replaces.
- 05 LALR Table Construction and What the Conflicts Mean How LR(1) item sets become LALR states, what shift-reduce and reduce-reduce conflicts actually report about a grammar, and when a precedence declaration is the correct repair.
- 06 Error Recovery in Recursive Descent Parsers How a hand-written parser detects a syntax error, chooses a synchronisation point, and limits cascading diagnostics, including why panic-mode recovery beats local correction.
- 07 Packrat Parsing and the Linear-Time Guarantee How memoising PEG results buys guaranteed linear parse time, what the memo table costs in memory, and why ordered choice removes ambiguity by fiat rather than by analysis.
- 08 GLR Parsing and the Graph-Structured Stack How a generalized LR parser follows every viable parse at once by replacing the stack with a DAG, how ambiguity is packaged into a shared forest, and what the merging costs.
- 09 Context-Dependent Lexing: Typedef Names, Layout, and Lexer Modes How the C typedef ambiguity forces the lexer to consult the parser, how indentation-sensitive layout is implemented, and what string interpolation does to the token model.
- 10 Incremental Reparsing After an Edit How an editor reuses the parse tree around a changed range, why error recovery nodes make reuse unsafe, and what the invalidation rules must guarantee.