Re: Definition of Production (Hans Aberg)
Wed, 19 Sep 2007 20:49:49 GMT

          From comp.compilers

Related articles
Definition of Production (Al) (2007-09-10)
Re: Definition of Production (Hans-Peter Diettrich) (2007-09-11)
Re: Definition of Production (2007-09-19)
Re: Definition of Production (2007-09-19)
| List of all articles for this month |

From: (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 (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.