#+title: context-free grammar
#+options: tex:t
#+STARTUP: latexpreview
- tags :: [[file:20210411214221-programming_language_implementation.org][programming language implementation]]

A context-free grammar (CFG) is a set of recursive rules that describe a
[[file:20210307152738-programming_languages.org][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.