Context Free Languages
Productions: || A → α |
|| A ∈ N |
|| α ∈ 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
or equivalently, a stack for temporary storage.
- Parsing time is at worst O(n3) , though programming
languages are commonly O(n) .
- Used for language elements that can contain themselves, e.g.,
Arithmetic expressions can contain
subexpressions: 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.
- Any language that requires counting must be at least context free:
anbn , balanced parentheses.