Parsing - Introduction to Compiler Construction in a Java World - page 63

and T occurs in no other rule. Likewise,

fX Y Zg

can be expressed as U, where U is defined by the rules

U ::= X Y Z U
U ::=

and U appears nowhere else in the grammar. Finally,

(X j Y j Z)

can be expressed as V , where V is defined by the rules

V ::= X
j Y
j Z

and V appears nowhere else in the grammar.
Even though these abbreviations express the same sorts of languages as classic BNF,
we use them for convenience. They make for more compact and more easily understood
grammars.

3.2.2 Grammar and the Language It Describes
Denition 3.1. A context-free grammar is a tuple, G = (N;T;S;P), where

N is a set of non-terminal symbols, sometimes called non-terminals;

T is a set of terminal symbols, sometimes called terminals;

S 2 N is a designated non-terminal, called the start symbol,; and

P is a set of production rules, sometimes called productions or rules.

For example, a context-free grammar that describes (very) simple arithmetic expressions
is G = (N;T;S;P), where N = fE;T;Fg is the set of non-terminals, T = f + , * , ( , ) , id g
is the set of terminals, S = E is the start symbol, and

P = fE ::= E + T,
E ::= T,
T ::= T * F,
T ::= F,
F ::= ( E ) ,
F ::= id g

(3.8)

A little less formally, we can denote the same grammar simply as a sequence of produc-
tion rules. For example, (3.9) denotes the same grammar as does (3.8).