
 A ContextFree Grammar G = <N, T, S, P> where
 T is a finite set of terminal symbols,
 N is a finite set of nonterminal symbols,
 S is the start symbol, S:N,
 P is a finite set of production rules of the form,
 X ::= &alpha where X:N and α:(N+T)^{*}
 (X > α is alternative notation)
 rules with a common LHS,
X ::= α,
X ::= β,
X ::= ... ,
are often shown thus:
 X ::= α  β  ...
 e.g., see the grammar of
[arithmetic expressions].

 Definitions
=>, =>^{*}, =>^{+} :
 α => β if β can be derived from α using a single production rule,
 α =>^{*} β if β can be derived from α using zero or more applications of production rules,
 α =>^{+} β if β can be derived from α using one or more applications of production rules,
 where α, β :(N+T)^{*}

 Definition:
 γ is a sentential form if
γ:(N+T)^{*} and S =>^{*} γ.

 Definition:
 γ is a sentence in the language defined by G if
γ:T^{*} and
S =>^{+} γ.
 (In some sources word is used in place of sentence.)

 Definition:
 The language
L(G) = {γ:T^{*} s.t. S =>^{+} γ},
 that is, L(G) is the set of sentences
that can be derived from S.

 A derivation can be represented by a (derivation) parse tree.
(However, a parse tree is often based on simpler abstract syntax
rather than concrete syntax.)

 Definitions
_{lm}=>,
_{lm}=>^{*},
_{lm}=>^{+},
_{rm}=>,
_{rm}=>^{*},
_{rm}=>^{+} :
 α _{lm}=> β if β can be derived from α
by applying a single production rule to the leftmost nonterminal
symbol within α.
 &alpha _{lm}=>^{*} β if β can be derived from &alpha using zero or more leftmost applications of production rules.
 &alpha _{lm}=>^{+} β if β can be derived from &alpha using one or more leftmost applications of production rules.
 (Similarly
_{rm}=>,
_{rm}=>^{*},
_{rm}=>^{+},
and rightmost.)

 Definitions:
 γ is a left sentential form if γ:(N+T)^{*} and S _{lm}=>^{*} γ.
 γ is a right sentential form if γ:(N+T)^{*} and S _{rm}=>^{*} γ.

 A [topdown] lefttoright parser
performs leftmost derivations.

 A [bottomup] lefttoright parser
performs rightmost derivations in reverse!

Sources
 The dragon book, Ch.4.
 Search for [parse] and/or [grammar]
in the [Bib].
 The [Algol60 Revised Report],
 which includes the first(?) formal definition of the syntax
of a significant programming language.

window on the wide world:

