StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Depends what you mean by "parsed", but if your parsing is supposed to include template instantiation, then not in general:</p> <p>[Shortcut if you want to avoid reading the example - templates provide a rich enough computational model that instantiating them is, in general, a halting-style problem]</p> <pre><code>template<int N> struct Triangle { static const int value = Triangle<N-1>::value + N; }; template<> struct Triangle<0> { static const int value = 0; }; int main() { return Triangle<127>::value; } </code></pre> <p>Obviously, in this case the compiler could theoretically spot that triangle numbers have a simple generator function, and calculate the return value using that. But otherwise, instantiating <code>Triangle<k></code> is going to take O(k) time, and clearly <code>k</code> can go up pretty quickly with the size of this program, as far as the limit of the <code>int</code> type.</p> <p>[End of shortcut]</p> <p>Now, in order to know whether <code>Triangle<127>::value</code> is an object or a type, the compiler in effect must instantiate <code>Triangle<127></code> (again, maybe in this case it could take a shortcut since <code>value</code> is defined as an object in every template specialization, but not in general). Whether a symbol represents an object or a type is relevant to the grammar of C++, so I would probably argue that "parsing" C++ <em>does</em> require template instantiation. Other definitions might vary, though.</p> <p>Actual implementations arbitrarily cap the depth of template instantiation, making a big-O analysis irrelevant, but I ignore that since in any case actual implementations have natural resource limits, also making big-O analysis irrelevant...</p> <p>I expect you can produce similarly-difficult programs in C with recursive <code>#include</code>, although I'm not sure whether you intend to include the preprocessor as part of the parsing step.</p> <p>Aside from that, C, in common with plenty of other languages, can have O(not very much) parsing. You may need symbol lookup and so on, which as David says in his answer cannot in general have a strict O(1) worst case bound, so O(n) might be a bit optimistic. Even an assembler might look up symbols for labels. But for example dynamic languages don't necessarily even need symbol lookup for parsing, since that might be done at runtime. If you pick a language where all the parser needs to do is establish which symbols are keywords, and do some kind of bracket-matching, then the Shunting Yard algorithm is O(n), so there's hope.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload