Parsing
Algorithms that turn text into structured meaning.
Parsing algorithms read tokens or strings and build structure according to grammar or expression rules.
Recursive Descent Parsing
Parses input with one function per grammar rule.
Pratt Parsing
Parses expressions by assigning binding powers to tokens and recursing by precedence.
CYK Algorithm
Checks whether a string can be generated by a context-free grammar.
Dijkstra's Two-Stack Algorithm
Evaluates fully parenthesized expressions with separate stacks for operators and values.
Earley Parser
Parses general context-free grammars with a chart of partial parse states.
LL Parsing
Parses input from left to right using leftmost derivations.
LR Parsing
Parses input bottom-up with shift and reduce actions.
Operator Precedence Parsing
Parses expressions by comparing precedence relations between operators.
Packrat Parsing
Parses with memoized recursive descent for linear-time parsing expression grammars.
Shunting Yard Algorithm
Converts infix expressions to postfix form using operator and output stacks.
PEG Parsing
Parses text using ordered-choice grammar rules that describe one intended parse.
Tokenization
Breaks raw text into meaningful tokens before parsing or analysis.
Parser Combinators
Builds parsers by composing small parser functions into larger grammar rules.
DFA Construction
Builds a deterministic finite automaton by grouping NFA state sets into DFA states.
NFA Simulation
Matches input by tracking all possible nondeterministic automaton states.
Thompson's Construction
Compiles a regular expression into an epsilon-NFA using small pattern fragments.
GLR Parsing
Parses ambiguous or nondeterministic grammars by following multiple LR parse paths.
LALR Parsing
Builds compact LR-style parse tables by merging states with the same cores.
FIRST/FOLLOW Set Computation
Computes grammar symbol sets used to predict valid parser choices.
LL(1) Parse Table Construction
Builds a predictive parsing table from FIRST and FOLLOW sets.
Canonical LR Parsing
Canonical LR Parsing uses grammar states and parse tables to recognize syntax.
SLR Parsing
SLR Parsing uses grammar states and parse tables to recognize syntax.
Recursive Ascent Parsing
Recursive Ascent Parsing turns grammar rules and token streams into structured syntax.
Precedence Climbing
Precedence Climbing turns grammar rules and token streams into structured syntax.
Left Recursion Elimination
Left Recursion Elimination turns grammar rules and token streams into structured syntax.
Left Factoring
Left Factoring turns grammar rules and token streams into structured syntax.
Panic Mode Error Recovery
Panic Mode Error Recovery recovers from syntax errors without abandoning the whole parse.
Phrase-Level Error Recovery
Phrase-Level Error Recovery recovers from syntax errors without abandoning the whole parse.
Incremental Parsing
Incremental Parsing turns grammar rules and token streams into structured syntax.
Island Parsing
Island Parsing turns grammar rules and token streams into structured syntax.
Scannerless Parsing
Scannerless Parsing turns grammar rules and token streams into structured syntax.
Lexical Tie-In Parsing
Lexical Tie-In Parsing turns grammar rules and token streams into structured syntax.
Abstract Syntax Tree Construction
Abstract Syntax Tree Construction turns grammar rules and token streams into structured syntax.
Parse Forest Construction
Parse Forest Construction turns grammar rules and token streams into structured syntax.
Attribute Grammar Evaluation
Attribute Grammar Evaluation turns grammar rules and token streams into structured syntax.
Syntax Directed Translation
Syntax Directed Translation turns grammar rules and token streams into structured syntax.
DFA Minimization
DFA Minimization builds or runs finite automata over tokens.
Regular Expression Derivative Parsing
Regular Expression Derivative Parsing builds or runs finite automata over tokens.
Hopcroft DFA Minimization
Minimizes a DFA by repeatedly splitting state partitions with distinguishing transitions.
Brzozowski DFA Minimization
Brzozowski DFA Minimization addresses finite-state machine minimization by reversing and determinizing the automaton twice.
LR(1) Item Set Construction
Builds canonical LR(1) parser states from grammar items with lookahead symbols.
GLL Parsing
GLL Parsing addresses general context-free parsing by using graph-structured stacks to explore multiple parse paths.
Recursive Transition Network
Recursive Transition Network addresses grammar-driven parsing by representing grammar rules as transition graphs that call one another.