context-free grammars

Formal grammar of the form A -> α.

Where A is a single nonterminal symbol, α is a string of terminals / nonterminals / empty.

Note: Do not confuse symbol with tokens. Symbols are groupings of tokens.

Set of recursive rules used to generate pattern of strings.

It is “context-free” because replacement of a non-terminal does not depend on surrounding symbols i.e. context.

Examples:

stmt -> id = Expr
stmt -> {stmtList}
stmtlist -> stmt
stmtlist -> stmtlist stmt
...