Mon, 28 Feb 1994 23:22:56 GMT

Related articles |
---|

question: how to map traces onto integers? frankz@info.win.tue.nl (1994-02-26) |

Re: question: how to map traces onto integers? svensson@ISI.EDU (1994-02-28) |

Newsgroups: | comp.compilers |

From: | svensson@ISI.EDU |

Posted-Date: | Mon, 28 Feb 1994 15:22:56 -0800 |

Keywords: | theory |

Organization: | Compilers Central |

References: | 94-02-194 |

Date: | Mon, 28 Feb 1994 23:22:56 GMT |

I'm looking for a technique to MAP arbitrary TRACES from any

given set of GRAMMAR-RULES onto the set of natural numbers, or

INTEGERS.

I need this in order to be able to identify a complete trace

(e.g. a pascal program or whatever) by a single natural

number.

Well, I guess you could do it with something akin to Goedel numbering.

Your trace is just a sequence of tokens, right?

1) label each of the terminals in your grammar with a natural number, L

2) label the tokens in your trace with unique primes P, starting with 2

and continuing upwards

3) each token in your trace contributes a factor P^L, with P given by

the position in the trace and L given by the terminal your token is

an instance of

4) your unique number is the product of the factors of all the tokens

Warning: these numbers become VERY LARGE VERY FAST. This technique is

probably only useful for theoretical considerations.

J

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.