Wed, 30 Jun 1993 19:39:47 GMT

Related articles |
---|

Complexity of compilation peb@procase.com (1993-06-30) |

Re: Complexity of compilation michi@km21.zfe.siemens.de (1993-07-01) |

Newsgroups: | comp.compilers |

From: | peb@procase.com (Paul Baclace) |

Keywords: | theory, question |

Organization: | Procase Corporation, San Jose, CA 95134 |

Date: | Wed, 30 Jun 1993 19:39:47 GMT |

What is the inherent complexity of compilation? I figure that an

assembler would be nearly O(n) time for n lines of code (assuming that

symbol table lookup is not a problem--say, an O(1) hashing method would be

used that assumes a average number of lines of source). For C++ or

optimization, this gets far more complex. O(n*Log(n)) seems likely for

C++ (an intuitive guess), but the graph problems that optimizers must work

on are probably more complex (certainly they seems to use lots of space,

like O(n^2)).

Paul E. Baclace

peb@procase.com

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.