Components of a grammar:
-
a finite set of tokens (obtained from the scanner);
-
a set of variables representing “related” sets of strings, e.g., declarations, statements, expressions.
-
a set of rules that show the structure of these strings.
-
an indication of the “top-level” set of strings we care about
-
Context-free Grammars: Definition
-
Formally, a context-free grammar G is a 4-tuple G = (V, T, P, S), where:
-
V is a finite set of variables (or nonterminals). These describe sets of “related” strings.
-
T is a finite set of terminals (i.e., tokens).
-
P is a finite set of productions, each of the form
-
A → α
-
S ε V is the start symbol.
-
where A ε V is a variable, and α ε (V ∪ T)* is a sequence of terminals and nonterminals.
Example of CFG :
E ==>E A E | (E) | -E | id
A==> + | - | * | / |
Where E,A are the non-terminals while id, +, *, -, /,(, ) are the terminals.
