Grammars and productions: a production is a pair of a
non-terminal symbol and a sequence (possibly empty) of
terminal and non-terminal symbols.
EBNF to BNF:
-
Backus Normal Form (BNF). Later Backus-Naur Form (BNF).
See page 82 of the Dragon book.
-
Extended BNF (EBNF) allows free use of the operators
|, ?, *, and
+.
-
An EBNF description can be converted into an equivalent
BNF description.
Parse trees:
-
The root node must be labelled with the start symbol.
-
Non-leaf nodes must be labelled with non-terminal symbols.
-
Leaf nodes must be labelled with terminal symbols or
epsilon.
-
The children of a non-leaf node labelled with A must
correspond to a production for A.
-
The terminal symbols appear in order as the leaves of the
parse tree.
Ambiguity:
-
A context-free grammar is ambiguous if there is a string
of terminal symbols that has two or more parse trees.
Rewriting grammars to eliminate ambiguity.
