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

[Bjoern Hoehrmann <derhoermi@gmx.net>]

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