Generator - Let's us generate all strings in a language
Recognize - Let's us recognize all strings in a language (y/n this is a legal string and parsing)

Grammars

Components of a grammar ($G$)

• Vocabulary
• Set of terminals ($T$)
• Set of non terminals ($N$)
• Set of productions ($P$)
• Starting state ($E$)

Datalog Grammar

• Things in all caps are terminals
• Nonterminals are lowercase
• Order matters -> SCHEMES COLON needs to come first in datalog
• Predicates have a name and a list of parameters
• Schemes, Facts, Queries: declares a list of predicates
• Rules: aren't predicates
  • head predicate
  • a list of body predicates
  • a colon-dash separating the two

Prefix Expression Grammar

$E\to D|OEE$
$O\to +|=|\ast |/$
$D\in 0|1|2|3|4$

$\ast +234$ is equivalent to $(2+3)\ast 4$

LL(1) Grammar is type of context-free grammar

• The FIRST sets tell us which production to use
• $A\to B|C$
  • $B\cap C=\mathrm{\varnothing }$