Wed, 19 Sep 2007 20:49:49 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 20:49:49 GMT |

Organization: | Virgo Supercluster |

References: | 07-09-025 07-09-075 |

Keywords: | parse, theory |

Posted-Date: | 19 Sep 2007 18:09:30 EDT |

haberg@math.su.se (Hans Aberg) wrote:

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

*> [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]*

This is context free or type 2 grammar in the Chomsky Hierarchy, which in

[loc.cit.], definition 5.7, p. 105 is given as:

Type 0. Each production (s,t) in P satisfies s in V+, t in V*, where V+ =

V*-{empty string}.

Type 1 (context sensitive). Each production has the form m a n -> m x n,

where m, n in V*, a in N, x in V+.

Type 2 (context insensitive). Each production has the form a -> x, a in N,

x in V*.

Type 3 (regular). Each production has form either A -> a, A in N, a in T

union {empty string}, or A -> a B, A, B in N and a in T.

I have seen some variations on these definitions, and I do not know

exactly how they are related.

Hans Aberg

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.