Determining an instance of the membership problem; i.e. given a string, determine whether where is the language generated by some grammar ; is also known as parsing.
Formally, the set of all context-free languages is identical to the set of languages accepted by pushdown automata (PDA). Parser algorithms for context-free languages include the CYK algorithm and the Earley's Algorithm.
A special subclass of context-free languages are the deterministic context-free languages which are defined as the set of languages accepted by a deterministic pushdown automaton and can be parsed by a LR(k) parser.
See also parsing expression grammar as an alternative approach to grammar and parser.
Read more about this topic: Context-free Language
Related Phrases
Related Words