Generating and Recognizing Recursive Descriptions of Patterns with Context-Free Grammars

A context-free grammar is a set of recursive rewriting rules (or productions) used to generate patterns of strings. Context-free grammars are often used to define the syntax of programming languages.

A parse tree displays the structure used by a grammar to generate an input string. Parse trees are typically used within a compiler to give structure to an input program in terms of the syntactic rules used to define valid programs.

A parser is an algorithm that determines whether a given input string is in a language (and, as a side-effect, usually produces a parse tree for the input). There is a procedure for generating a parser from a given context-free grammar.