Parsing
From Algorithm wiki
[edit] Parsing Algorithm list
- Converts NFA to DFA
- Lexical Analyzer
- Recursive descent parser: A top-down parser suitable for LL(k) grammars
- LL parser: A relatively simple linear time parsing algorithm for a limited class of context-free grammars
- LR parser: A more complex linear time parsing algorithm for a larger class of context-free grammars. Variants:
- Packrat parser: A linear time parsing algorithm supporting some context-free grammars and parsing expression grammars
- CYK algorithm: An O(n3) algorithm for parsing any context-free grammar
- Earley parser: Another O(n3) algorithm for parsing any context-free grammar
- GLR parser:An algorithm for parsing any context-free grammar by Masaru Tomita. It is tuned for deterministic grammars, on which it performs almost linear time and O(n3) in worst case.
- Inside-outside algorithm: An O(n3) algorithm for re-estimating production probabilities in probabilistic context-free grammars

