NFA-->DFA converter (pascal)

"Bob" <>
22 Mar 2006 23:42:04 -0500

          From comp.compilers

Related articles
NFA-->DFA converter (pascal) (Bob) (2006-03-22)
| List of all articles for this month |

From: "Bob" <>
Newsgroups: comp.compilers
Date: 22 Mar 2006 23:42:04 -0500
Organization: Compilers Central
Keywords: lex, Pascal

As a modest start to a very ambitious project, I have written some
routines which will convert some regular expressions to an NFA, and
then convert that NFA into a DFA to be used by a lexical analyser.

I have some issues with it. The first is mostly a result of imposed
simplicity for the front end -- it is easy to spot finishing states,
because they are all negative, and they are all unique to each token
(and one for each). This can result in problems, which I have sort of
worked around, but not quite. Greedy detection is one of the
casualities, which isn't that much of a problem for me, as I'm not a
fan of it, but does result in behaviour that is sometimes hard to
predict, as sometimes it will be greedy, others not (very frustrating).

Anyway, I've registered the project at sourceforge. If anyone wants to
have a look at it, it's at .
There's only one file there; that's the one with the lexical stuff in.
I discuss other issues in the readme.txt bundled in this release.

If you have delphi, you can make a relatively straightforward program
to see what kind of of output the process generates. Place five memos
on a form, and a button. Use the event handler below for the button's
OnClick event. Be sure to add the lang and lputils units from the
release. It's probably a good idea to label the outputs respectively.

procedure TForm1.Button1Click(Sender: TObject);
    tokNFA, NFA, DFA, mDFA: TFSA;
    i, tc, tokindex: Integer;
    table: TStateTable;
    continue: Boolean;
    ics: TSysCharSet = [' ', #9];
// nfa output
// dfa output
// minimal dfa output
// state table output
    NFA := TFSA.Create;
    tc := Memo1.Lines.Count - 1;
    tokindex := 0;
    continue := true;
    for i := 0 to tc do
// parse the input
        if Trim(Memo1.Lines[i]) <> '' then
                tokNFA := RexStrToNFA(Memo1.Lines[i], nil);
                on e: Exception do
                    continue := False;
            NFA.Add(LSTART, tokindex, tokNFA);
    if continue then
// generate the data
        DFA := NFAToDFA(NFA);
        mDFA := MinimalDFA(DFA);
        Table := DFAToStateTable(mDFA);
// output the data
        DisplayTable(Table, Memo5.Lines);
// cleanup

I appreciate any comments or suggestions people might have.



Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.