---
title: "Context-Free Grammar"
type: concept
related: [Context Free Grammars]
source: https://www.jemoka.com/posts/kbhcontext_free_grammars/
confidence: high
status: active
---

We use CFGs to highlight the recursive structure in expressions.
A CFG consists of
Non-Recursed Terminals (if, else, etc.) \(T\) Non-Terminals (expr, stmt, etc.) \(N\) Start symbol (i.e., program) \(S \in N\) Set of productions generative semantics Let \(G\) be an CFG with start symbol \(S\); the language of \(G\) is&hellip;
\begin{equation} \qty {a_1, \dots, a_{n} | S \to^{*} a_{1}, a_{n}} \end{equation}
with each \(a_{j}, \forall j\) being terminals.
That is, the &ldquo;language of a CFG&rdquo; is just the set of languages that could be produced by as many moves as needed until we obtain the output.
productions \begin{equation} X \to Y_1, Y_2, \dots, Y_{n} \end{equation}
whereby \(X \in N\), \(Y_{i} \in T \cup N \cup \qty {\varepsilon}\). Notably, we could replace a non-terminal with nothing.
derivation a derivation is a sequence of productions which leads to a string of only terminals
A derivation can be drawn as a tree&mdash;
start symbol is the root for production \(X \to Y_1, &hellip;, Y_{n}\), add children \(Y_1, &hellip;, Y_{n}\) to note \(X\) stratification stratification allows us to deal with the PEMDAS (/associativity) of the operations. Consider an addition and multiplication world:
E = E+E | E*E | (E) | id how do we parse id * id + id.
We can just have a &ldquo;multiplication world&rdquo; E&rsquo; language, whereby after en counting an multiplication, we are not allowed to do addition anymore unless we encounter a parentheses.
E = E&#39; + E | E&#39; E&#39; = id * E&#39; | id | (E) * E&#39; | (E) dangling if problem Consider the following ambiguous grammar:
E -&gt; if E then E | if E then E else E | .... Consider:
if something then if something then something else something Is the else the first or the second expression?~:w
to fix this, we need to make a world of &ldquo;matched if expression&rdquo;
E -&gt; MIF -- all &#34;then&#34; are matched | UIF -- some &#34;then&#34; is unmatched UIF -&gt; if E then E | if E then MIF else UIF {- &#34;we don&#39;t allow unmatched if expressions in then branches&#34; -} MIF -&gt; if E then MIF else MIF | OTHER Most tools, like flex/bison, will allow you to control precedence.
conventions non-terminals in upper case
terminals in lower case
start symbol is the non-terminal of the first production
membership in a language is a &ldquo;yes&rdquo;/&ldquo;no&rdquo;
we must handle errors gracefully
bison could help us actually implement the parser
example EXPR -&gt; if EXPR then EXPR else EXPR fi | while EXPR loop EXPR pool | id
