Re: Definition of Production

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

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