[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Seeking FSM for XML

• To: xml-dev@l...
• Subject: Re: Seeking FSM for XML
• From: Rick Jelliffe <rjelliffe@a...>
• Date: Thu, 20 Apr 2006 12:05:10 +1000
• In-reply-to: <000301c663b3$5071aa00$0115a8c0@E...>
• References: <88aed1ea0604070509x36849a9blafb60298e835177@m...> <7.0.1.0.2.20060410220233.028d2810@C...> <443B2C83.3020502@a...> <443B3502.6040600@j...> <443B38A1.3000808@a...> <15381.60.229.226.213.1144850557.squirrel@i...> <7870f82e0604121011x1bede22dgcf3df1a941ad702e@m...> <16295.60.229.226.213.1144863578.squirrel@i...> <e8aa138c0604190250p59164964q91367eb1daed739e@m...> <000301c663b3$5071aa00$0115a8c0@E...>
• User-agent: Mozilla Thunderbird 0.6 (X11/20040502)

Rick Marshall wrote:

> which raises the other issue - a fsm controls something - ie some 
> states have effects - i presume you have a list of states and desired 
> effects that you want to plug into this fsm - but then yacc should 
> still be able to do that....

Tim Bray kindly sent me his DFA spec that he used in Lark. Tim has also 
now made his version available to the public, see his 
www.tbray.org/ongoing website or  planet.xmlhack.com

I have made an XML-syntax version of this: if Tim OK's it I will make 
that public shortly--I am checking it against the corrections to XML 1.0 
and against XML 1.1.  It should be a really good headstart to anyone 
wanting to experiment with parser design issues. You could use XSLT as 
the proprocessor to generate the code. Actually, there are still 
platforms which don't have strong XML processors available (or not open 
source ones): I was hearing of a home-made one written for PR/I systems 
using EBCDIC 2 weeks ago for example.

Tim's spec does has various triggers for states and assumes some kind of 
stack: whether it is implemented using an actual pushdown automaton or 
some other arrangement with a stack is up to the implementer.

Tim's implementation does not separate tokenizing and parsing really, 
except for keywords: consequently his DFA for DTDs is quite complex. I 
think a two level approach (e.g. tokenize "(" "#PCDATA" "|" "b" ")" "*" 
in the DFA and then have some higher PDA to parse these tokens into the 
declaration components)  would be neater, but not faster. And it would 
have added to the complexity: if you have a tbale-basd system, you may 
as well use it to the full.

Cheers
Rick Jelliffe

• References:
  • Code List Value Validation
    • From: "Fraser Goffin" <goffinf@g...>
  • Re: Code List Value Validation
    • From: "G. Ken Holman" <gkholman@C...>
  • Re: Re: Code List Value Validation
    • From: Rick Jelliffe <rjelliffe@a...>
  • Re: Re: Code List Value Validation
    • From: Jeff Rafter <lists@j...>
  • Re: Re: Code List Value Validation
    • From: Rick Jelliffe <rjelliffe@a...>
  • Seeking FSM for XML
    • From: "Rick Jelliffe" <rjelliffe@a...>
  • Re: Seeking FSM for XML
    • From: "Mukul Gandhi" <gandhi.mukul@g...>
  • Re: Seeking FSM for XML
    • From: "Rick Jelliffe" <rjelliffe@a...>
  • Re: Seeking FSM for XML
    • From: adasal <adam.saltiel@g...>

• Prev by Date: [Fwd: [Tri-XML] ANN: Call for presenters open until April 30th...Send your presentation proposal now for the Tri-XML 2006 Conference]
• Previous by thread: Re: Seeking FSM for XML
• Next by thread: Re: [XPath] is it legal ?
• Index(es):
  • Date
  • Thread