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 parsers use what computational power?

Hi Folks,

Can XML parsers be implemented using exclusively these two tools:

1. A finite state machine (FSM)
2. A stack

Let's see:

Case 1: parsing a start-tag, content, end-tag

Yes, I can imagine implementing that by pushing the start-tag onto the stack, scanning through the content, and then popping the stack when an end-tag is encountered and comparing it against the start-tag.

Case 2: parsing user-defined entity declarations

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:


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.

Case 3: parsing an IDREF reference

Each ID value is pushed onto the stack. When an IDREF reference is encountered, the stack is popped until it finds a matching ID value. It seems plausible that ID/IDREF matching could be accomplished using a FSM plus stack.

Is there any feature of XML that could not be implemented exclusively using the two tools, FSM and stack?


[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