Re: Definition of Production

haberg@math.su.se (Hans Aberg)
Wed, 19 Sep 2007 19:31:05 GMT

          From comp.compilers

Related articles
Definition of Production two@haik.us (Al) (2007-09-10)
Re: Definition of Production DrDiettrich1@aol.com (Hans-Peter Diettrich) (2007-09-11)
Re: Definition of Production haberg@math.su.se (2007-09-19)
Re: Definition of Production haberg@math.su.se (2007-09-19)
| List of all articles for this month |

From: haberg@math.su.se (Hans Aberg)
Newsgroups: comp.compilers
Date: Wed, 19 Sep 2007 19:31:05 GMT
Organization: Virgo Supercluster
References: 07-09-025
Keywords: parse
Posted-Date: 19 Sep 2007 15:59:24 EDT

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]



Post a followup to this message

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