Re: Definition of Production

Al <two@haik.us> wrote:


> I'm looking for a clear definition of `production' in a (computer)
> grammatic/syntactic context. I've seen it used to mean anything from
> rule (in the xBNF sense) to input string, to mixtures of both
> (e.g. the segment of the input that matched a given rule).
>
> I would like to know if there is more precise definition, and an
> example or two if possible :). A related question is whether
> `production' == `production rule'. Thanks in advance for the help.


> [No terms in comp sci have precise definitions, but I've consistently
> seen production used in the sense of a grammar rule. -John]


Grammar productions are defined formally in Waite & Goos, "Compiler
construction", ch 5.1, p. 103:


Given a non-empty finite set V called vocabulary, a production (see below)
is merely a pair (s, t), where s, t in V*, the free monoid on V (the set
of finite V strings, including the empty string). A subset of V is called
a language. A grammar G is a quadruple (N, T, P, Z), where V is the
disjoint union of the non-terminals N the terminals T; P is a finite set
of productions, and Z in N is the sentence symbol. The language generated
by G is the subset of T* that can be gotten from Z by a sequence of
rewritings using the productions in P (different rewriting sequences
produce different elements of T*). A (direct) rewriting of a string using
the production (s, t) is a replacement of a substring s with t. This
source writes (s, t) as s -> t (though some write it the opposite
direction, I think).


    Hans Aberg
[Ah, let me extend my remarks to say that no terms in comp sci have
universally accepted precise definitions. This is a perfectly
reasonable definition although in most of the applications I've seen,
s is limited to a single symbol, not a string. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.