3-11-2025 - CFGs

Context Free Grammars

Describes sets of strings, in particular context free languages Abstracted: convert from one language to another Three things we need for a translator:

• Lexer
  • Typically uses RE to convert text file into a list of tokens (word types)
• Parser
  • Converts tokens to an Abstract Syntax Tree using a Context Free Grammar
• Evaluator/Generator
  • Converts AST to Target or evaluates to value

CFG

$$\begin{array}{rl}R\to \varnothing & \\ |& ϵ\\ |& \sigma \\ |& R_1{R}_2\\ |& R_1|R_2\\ |& R_1^{\ast }\end{array}$$

Another example - recursively defined set

$$S\to aS|Sb|ϵ=\text{a*b*}$$

Terms

Nonterminal symbol - a symbol that is not terminated (done): denoted by convention as a capital letter - describes a set, $S$ Terminal symbol - lowercase, describe symbols that are allowed in the language Production rule - rules about replacement

In $S$:

• $a$, $b$, $ϵ$ are terminals
• $S$ is a nonterminal
• $S\to aS$, $S\to Sb$, $S\to ϵ$ are production rules

Derivation - a proof of a string being in $S$ using just the production rules

Another CFG

$$\begin{array}{rl}& S\to aS|Sb|T\\ & T\to cTc|d\end{array}$$

aSa bSb cSc a b c e - palindrome

Expressions

$$\begin{array}{rl}E\to & \text{ if }E\text{ then }E\text{ else }E\\ & |E\text{ + }E\\ & |E\text{ * }E\\ & |E\text{ \&\& }E\\ & |n\in \mathbb{Z}\\ & |\text{true}\\ & |\text{false}\\ & |f\in \mathbb{R}\end{array}$$

Let’s take the grammar

$$E\to E+E|E\ast E|n\in \mathbb{Z}$$

You could say something like $1+2\in E$. Then But for 1+2+3

$$\begin{array}{rl}& E\to E+E|T\\ & T\to T\ast T|n\in \mathbb{Z}\end{array}$$

$$\begin{array}{rl}& E\to T+E|T\\ & T\to N\ast T|N\\ & N\to n\in \mathbb{Z}\end{array}$$

This enforces a certain shape of a tree. The left hand side MUST be a number or a multiplication - only the right hand side can be another plus.