Productions:	A &rarr &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 at worst O(n³) , 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.

Contents    Page-10    Prev    Next    Page+10    Index