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:
>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

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/ 

[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