Cart
[Home] [By Thread] [By Date] [Recent Entries]
On Tue, Apr 9, 2013 at 9:11 PM, Costello, Roger L. <costello@m...> wrote: > 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. I don't think this is true... an XML parser must be more powerful than a pure stack machine HOWEVER I don't see how one could encode, e.g., SK calculus in XML's entity resolution semantics. Can you set XML parsers into infinite loops via entity resolution? Afaik, entities cannot be self-referential and support no parameterization... dS > The ramifications of this are huge, particularly with regard to security and XML's attack surface. > > /Roger > > -----Original Message----- > From: Bjoern Hoehrmann [mailto:derhoermi@g...] > Sent: Tuesday, April 09, 2013 1:53 PM > To: Costello, Roger L. > Cc: xml-dev@l... > 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@h... · 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/ > > _______________________________________________________________________ > > XML-DEV is a publicly archived, unmoderated list hosted by OASIS > to support XML implementation and development. To minimize > spam in the archives, you must subscribe before posting. > > [Un]Subscribe/change address: http://www.oasis-open.org/mlmanage/ > Or unsubscribe: xml-dev-unsubscribe@l... > subscribe: xml-dev-subscribe@l... > List archive: http://lists.xml.org/archives/xml-dev/ > List Guidelines: http://www.oasis-open.org/maillists/guidelines.php >
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] |
