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 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. > > 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 > LR-Parsing 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 table-driven LR parser. This is small, compact, easy to develop and quite efficient.
However, I decided *not* to develop in XSLT another YACC-like 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 table-driven 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 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. > > 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 > LR-Parsing 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 |