tags : [[programming language implementation]]
A context-free grammar (CFG) is a set of recursive rules that describe a [[programming language]].
Context-free grammars are a set of names paired with their parsing rules.
For example:
\begin{example} \mathit{expr} \rightarrow \mathit{term}\; \mathtt{+}\; \mathit{expr}
\mathit{expr} \rightarrow \mathit{term}
\mathit{term} \rightarrow \mathit{term}\; \mathtt{*}\; \mathit{factor}
\mathit{term} \rightarrow \mathit{factor}
\mathit{factor} \rightarrow \mathtt{(}\;\mathit{expr}\;\mathtt{)}
\mathit{factor} \rightarrow \mathit{const}
\mathit{const} \rightarrow \mathit{integer} \end{example}
Therefore we know 3 * 7 is a valid expression.