RE: XML parsers use what computational power?

["Costello, Roger L." <costello@mitre.org>]

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:

    &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.

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?

/Roger