|NFA-->DFA converter (pascal) firstname.lastname@example.org (Bob) (2006-03-22)|
|Date:||22 Mar 2006 23:42:04 -0500|
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);
tokNFA, NFA, DFA, mDFA: TFSA;
i, tc, tokindex: Integer;
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
I appreciate any comments or suggestions people might have.
Return to the
Search the comp.compilers archives again.