Context Free Languages
Productions: || A&alpha |
|| A&isin N |
|| &alpha &isin V
Since left-hand-side of each production is a
single nonterminal, every derivation is a tree.
Many good parsers are known. Parsing requires a recursive program,
or equivalently, a stack for temporary storage.
- Parsing time is O(n^3) .
- Used for language elements that can contain themselves, e.g.,
Arithmetic expressions can contain
sub-expressions: A + B * (C + D) .
A noun phrase can contain a prepositional phrase, which
contains a noun phrase:
a girl with a hat on her head.