Wed, 19 Sep 2007 19:31:05 GMT

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) |

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.