Subject: Re: [xsl] NFA to DFA conversion using XSLT From: "Mukul Gandhi" <gandhi.mukul@xxxxxxxxx> Date: Fri, 1 Jun 2007 23:29:02 +0530 
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 eCLOSURE (e stands for epsilon transitions)  which > involves pushing & popping states from a stack. > 2) The subset construction  which uses eCLOSURE function to construct a DFA. > > The book also describes an algorithm to minimize the number of states > of a DFA (whose output is a DFA accepting the same language as > original DFA, but having as few states as possible). > > Do you think, we could do this with XSLT? As I defined the NFA above, > I can specify the meaning of a DFA similarly. > > I recently read on Dimitre's blog, that he has written a framework for > LRParsing using XSLT 2.0. My interest is along the same lines.. >
We can do everything in XSLT.
However, a system's developer may decide how to allocate the available resources in an optimal way  this most probably will exclude the writing in XSLT of parser generators or lexical scanner generators.
What I did implement recently in FXSL is a general tabledriven LR parser. This is small, compact, easy to develop and quite efficient.
However, I decided *not* to develop in XSLT another YACClike tool, which given an LR (1) grammar produces the tables to be used by the parser. Taking into account that suitable tools exist (like YACC and/or BYSON), it would be an enormous waste of time for me to write this in XSLT.
Instead, I just "touched" an available open source version of YACC, so that it now generates the parsing tables in XML format. These are then used by the tabledriven LR parser, which (only) is written in XSLT. The modified YACC is called YACCX and is available in the Tools folder of the CVS of the project.
Another reason for my decision is the fact that parsing tables are produced only once and then they are used many times. As the production of the parsing tables will be done very rarely (once for a given language), we can do this offline with whatever tool we already have available.
As for the lexical analyzer, one could try the same approach and modify an appropriate tool, such as lex, to produce tables in XML. I didn't do this on purpose, as I am now having fun learning to use RegEx expressions and their support in XSLT 2.0. Doing so helps better understand some intrinsic lexical properties of a given language, and is therefore quite beneficial.
 Cheers, Dimitre Novatchev  Truly great madness cannot be achieved without significant intelligence.  To invent, you need a good imagination and a pile of junk  You've achieved success in your field when you don't know whether what you're doing is work or play
On 5/31/07, Mukul Gandhi <gandhi.mukul@xxxxxxxxx> wrote: > Hi Mike, > Thanks for your reply. > > I am toying with the following idea (a sample state table) to > represent state table of NFA: > > <nfastates> > <state name="0"> > <input symbol="a"> > <movetostate name="0" /> > <movetostate name="1" /> > </input> > <input symbol="b"> > <movetostate name="0" /> > </input> > </state> > <state name="1"> > <input symbol="a"> > <movetostate name="none" /> > </input> > <input symbol="b"> > <movetostate name="2" /> > </input> > </state> > <state name="2"> > <input symbol="a"> > <movetostate name="none" /> > </input> > <input symbol="b"> > <movetostate name="3" /> > </input> > </state> > <state name="3" isfinal="yes" /> > </nfastates> > > (this is the NFA recognizing the language (a  b)*abb ). 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 eCLOSURE (e stands for epsilon transitions)  which > involves pushing & popping states from a stack. > 2) The subset construction  which uses eCLOSURE function to construct a DFA. > > The book also describes an algorithm to minimize the number of states > of a DFA (whose output is a DFA accepting the same language as > original DFA, but having as few states as possible). > > Do you think, we could do this with XSLT? As I defined the NFA above, > I can specify the meaning of a DFA similarly. > > I recently read on Dimitre's blog, that he has written a framework for > LRParsing using XSLT 2.0. My interest is along the same lines.. > > On 5/31/07, Michael Kay <mike@xxxxxxxxxxxx> wrote: > > > I am looking for a suitable W3C Schema to represent state > > > table of a NFA. > > > > I think there are such things in the context of workflow modelling (e.g. > > BPEL) but it might carry a lot more baggage than you actually want. > > > > > > My second question is: is it easily possible to write a XSLT > > > program (I can prefer 2.0 language if you wish) to convert a > > > NFA to an equivalent (DFA, with minimal states). > > > > > Possible yes. Easy, I doubt it. I found it challenging enough in Java. But I > > expect someone will prove me wrong! > > > > Michael Kay > > http://www.saxonica.com/
 Regards, Mukul Gandhi
Current Thread 


< Previous  Index  Next > 

Re: [xsl] NFA to DFA conversion usi, Dimitre Novatchev  Thread  [xsl] Calculating months between tw, Ryan Puddephatt 
Re: [xsl] NFA to DFA conversion usi, Mukul Gandhi  Date  Re: [xsl] NFA to DFA conversion usi, Dimitre Novatchev 
Month 