OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]
Re: [xml-dev] RE: XML parsers use what computational power?

* 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/ 

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]

News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 1993-2007 XML.org. This site is hosted by OASIS