Complexity of compilation

peb@procase.com (Paul Baclace)
Wed, 30 Jun 1993 19:39:47 GMT

          From comp.compilers

Related articles
Complexity of compilation peb@procase.com (1993-06-30)
Re: Complexity of compilation michi@km21.zfe.siemens.de (1993-07-01)
| List of all articles for this month |

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.