Re: [xml-dev] RE: XML parsers use what computational power?

[Bjoern Hoehrmann <derhoermi@gmx.net>]

* Costello, Roger L. wrote:
>As I understand it, you have just explained why entity resolution 
>necessitates an XML parser be a Turing machine!
>
>This is big news (at least for me):
>
>    To implement a parser for the XML specification 
>    requires the parser be Turing-complete.
>
>The ramifications of this are huge, particularly with regard to security 
>and XML's attack surface.

There are various levels of complexity between a simple stack machine
and a universal turing machine, and since we can always tell whether,
for instance, a string is a well-formed XML 1.0 document, at most a
Decider (machine always halts) is needed for that particular problem.

Also note that we tend to use these terms rather colloquially. If you
make an XML parser that can only parse files up to 4GB in size, you're
unlikely to encounter anyone who claims it's not an XML parser if that
is the only problem. However, with that limitation, your parser could
simply be a finite state machine without any loops, so less than what
is needed to recognize most regular expressions with a `*` in them.
-- 
Björn Höhrmann · mailto:bjoern@hoehrmann.de · http://bjoern.hoehrmann.de
Am Badedeich 7 · Telefon: +49(0)160/4415681 · http://www.bjoernsworld.de
25899 Dagebüll · PGP Pub. KeyID: 0xA4357E78 · http://www.websitedev.de/