[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

RE: RE: XML parsers use what computational power?

• From: "Costello, Roger L." <costello@mitre.org>
• To: "xml-dev@lists.xml.org" <xml-dev@lists.xml.org>
• Date: Tue, 9 Apr 2013 20:11:42 +0000

Bjoern wrote about entity resolution:

> Whatever you pop() here from the stack would 
> be lost afterwards. If you need 'ha1', then you 
> have to forget 'ha2' to retrieve it. And all other
> state you keep on the stack.

Wow!

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.

/Roger

-----Original Message-----
From: Bjoern Hoehrmann [mailto:derhoermi@gmx.net] 
Sent: Tuesday, April 09, 2013 1:53 PM
To: Costello, Roger L.
Cc: xml-dev@lists.xml.org
Subject: Re:  RE: XML parsers use what computational power?

* Costello, Roger L. wrote:
>Can XML parsers be implemented using exclusively these two tools:
>
>1. A finite state machine (FSM)
>2. A stack

You seem to be missing that in the computational model the stack is all
the memory you have. If you add a second stack, so you could e.g. pop()
items from one and push() them to the other, you have a turing machine.

Take your example:

>Consider these two ENTITY declarations in the XML document's internal DTD subset:
>
><!ENTITY ha1 "ha">
><!ENTITY ha2 "&ha1;&ha1;">
>
>Each entity name and replacement value could be stored in the stack.
>
>When the entity name is encountered within the XML document:
>
>    &ha2;
>
>the parser could pop the stack until it encounters the name ha2 and get its
>replacement text, which involves getting ha1 and its replacement text. So I
>could imagine that entity resolution could be implemented using a FSM plus
>stack.

Whatever you pop() here from the stack would be lost afterwards. If you
need 'ha1', then you have to forget 'ha2' to retrieve it. And all other
state you keep on the stack.
-- 
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/ 

• Follow-Ups:
  • Re: RE: XML parsers use what computational power?
    • From: Bjoern Hoehrmann <derhoermi@gmx.net>
  • Re: RE: XML parsers use what computational power?
    • From: David Sheets <kosmo.zb@gmail.com>

• References:
  • XML parsers use what computational power?
    • From: "Costello, Roger L." <costello@mitre.org>
  • RE: XML parsers use what computational power?
    • From: "Costello, Roger L." <costello@mitre.org>
  • Re: RE: XML parsers use what computational power?
    • From: Bjoern Hoehrmann <derhoermi@gmx.net>