grammars
elements of a grammar
- rules (or “productions”)
- terminals
- non-terminals
- start non-terminal
example
- grammar for baby arithmetic language
pgm ::= <> | stmt pgm
stmt ::= assign | print
assign ::= var ":=" expr
print ::= “print” expr
expr ::= var | var op expr
op ::= + | *
derivations
- to derive a sentence:
start with the special start non-terminal
apply a matching grammar rule to a nonterminal until no non-terminals are left
- from a grammar, can derive many sentences