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

Re: NFA to DFA conversion using XSLT

Subject: Re: NFA to DFA conversion using XSLT
From: "Mukul Gandhi" <gandhi.mukul@xxxxxxxxx>
Date: Fri, 1 Jun 2007 23:26:52 +0530
Re:  NFA to DFA conversion using XSLT
Hi Mike,
  Thanks a lot for your reply, and insightful remarks. I now have
some new things to ponder about.

After I have read something more about parsing theory, I'll have more questions.

Perhaps XSLT is not the right language to implement parsers. But to
learn some concepts from the list, I had put my questions in the
context of XSLT.

On 6/1/07, Michael Kay <mike@xxxxxxxxxxxx> wrote:
> I am toying with the following idea (a sample state table) to
> represent state table of NFA:

Looks a perfectly reasonable representation.

> I am
> following some examples and algorithms from the book,
> "Principles of compiler design - by Aho, Ullman).
> One of the algorithms for NFA to DFA conversion states, that
> we essentially follow the below two steps:
> 1) Compute e-CLOSURE (e stands for epsilon transitions) -
> which involves pushing & popping states from a stack.
> 2) The subset construction - which uses e-CLOSURE function to
> construct a DFA.

I've spent many happy hours studying those three pages of the book, because
Saxon implements those algorithms in its schema processor.

Doing the epsilon-closure of a state is quite easy, I think. Although the
algorithm given by Aho and Ullmann is procedural, it's not difficult to come
up with a (simpler) algorithm that's purely functional.

By contrast, the subset construction algorithm doesn't intuitively translate
into functional form at all, I think you would have to devise a completely
different algorithm, and proving its correctness would not be at all easy.
For what it's worth, I implemented an "optimization" to the Aho and Ullman
algorithm and it took nearly three years before I discovered it was
incorrect - it ran all the 6000 or so test cases in the Schema test suite
without problems, but eventually tripped up on a very innocuous-looking
user-written content model.

I haven't even looked at the state minimization algorithms. I don't see the
point: all the performance issues are to do with the speed of determinizing
the FSA, not with the size of the resulting DFA. Though that might be
because of the lengths XML Schema goes to to disallow ambiguous grammars; if
you were compiling regular expressions it might be more of an issue, I don't

Michael Kay

Mukul Gandhi

Current Thread


Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
First Name
Last Name
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.