NFA-->DFA converter (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 https://sourceforge.net/projects/xpas-age/ .
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);
var
    tokNFA, NFA, DFA, mDFA: TFSA;
    i, tc, tokindex: Integer;
    table: TStateTable;
    continue: Boolean;
const
    ics: TSysCharSet = [' ', #9];
begin
// nfa output
    Memo2.Lines.Clear;
// dfa output
    Memo3.Lines.Clear;
// minimal dfa output
    Memo4.Lines.Clear;
// state table output
    Memo5.Lines.Clear;
    NFA := TFSA.Create;
    tc := Memo1.Lines.Count - 1;
    tokindex := 0;
    continue := true;
    for i := 0 to tc do
// parse the input
    begin
        if Trim(Memo1.Lines[i]) <> '' then
        begin
            try
                tokNFA := RexStrToNFA(Memo1.Lines[i], nil);
            except
                on e: Exception do
                begin
                    continue := False;
                    Break;
                end;
            end;
            dec(tokindex);
            NFA.Add(LSTART, tokindex, tokNFA);
            tokNFA.Free;
        end;
    end;
    if continue then
    begin
// generate the data
        DFA := NFAToDFA(NFA);
        mDFA := MinimalDFA(DFA);
        Table := DFAToStateTable(mDFA);
// output the data
        NFA.DebugOut(Memo2.Lines);
        DFA.DebugOut(Memo3.Lines);
        mDFA.DebugOut(Memo4.Lines);
        DisplayTable(Table, Memo5.Lines);
// cleanup
        NFA.Free;
        DFA.Free;
        mDFA.Free;
        Source.Free;
        Stream.Free;
        FreeTable(table);
    end;
end;


I appreciate any comments or suggestions people might have.


Thanks!


Bob

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