A Context-Free Grammar G = <N, T, S, P> where

T is a finite set of terminal symbols,

N is a finite set of non-terminal symbols,

S is the start symbol, S:N,

P is a finite set of production rules of the form,

X ::= α 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 left-most non-terminal symbol within α.

α _lm=>^* β if β can be derived from α using zero or more left-most applications of production rules.

α _lm=>⁺ β if β can be derived from α using one or more left-most applications of production rules.

(Similarly _rm=>, _rm=>^*, _rm=>⁺, and right-most.)

 

Definitions:

γ is a left sentential form if γ:(N+T)^* and S _lm=>^* γ.

γ is a right sentential form if γ:(N+T)^* and S _rm=>^* γ.

 

A [top-down] left-to-right parser performs left-most derivations.

 

A [bottom-up] left-to-right parser performs right-most derivations in reverse!

 

Sources

The dragon book, Ch.4.

Search for [parse] and/or [grammar].

The [Algol-60 Revised Report],

which includes the first(?) formal definition of the syntax of a significant programming language.