Files

1030 lines
27 KiB
C#

using System;
using System.Collections;
using System.Diagnostics;
using System.IO;
using System.Runtime.Serialization.Formatters.Binary;
namespace Tools
{
[Serializable] public abstract class LNode
{
[NonSerialized] public TokensGen m_tks;
public int m_state;
public LNode(TokensGen tks) {
m_tks = tks;
m_state = tks.NewState();
}
}
[Serializable] public class TokClassDef
{
public TokClassDef(GenBase gbs,string name,string bas)
{
if (gbs is TokensGen)
{
TokensGen tks = (TokensGen) gbs;
m_name=name;
tks.m_tokens.tokens[name] = this;
m_refToken=bas;
}
}
public string m_name = "";
public string m_refToken = "";
public string m_initialisation = "";
public string m_implement = "";
}
[Serializable] public class Dfa : LNode
{
public Dfa(TokensGen tks) : base(tks)
{
m_tokens = tks.m_tokens;
}
[NonSerialized] Tokens m_tokens = null;
public static void SetTokens(Tokens tks, Hashtable h) // needed after deserialisation
{
foreach (Dfa v in h.Values)
{
if (v.m_tokens!=null)
continue;
v.m_tokens = tks;
Dfa.SetTokens(tks,v.m_map);
}
}
public Hashtable m_map = new Hashtable(); // char->Dfa: arcs leaving this node
[Serializable] public class Action
{
public int a_act;
public Action a_next;
public Action(int act,Action next) { a_act = act; a_next = next; }
}
public Action m_actions; // for old-style REJECT
void AddAction(int act)
{
Action a = new Action(act,m_actions);
m_actions = a;
}
void MakeLastAction(int act)
{
while (m_actions!=null && m_actions.a_act>=act)
m_actions = m_actions.a_next;
AddAction(act);
}
public string m_tokClass = ""; // token class name if m_actions!=null
public Dfa(Nfa nfa):base(nfa.m_tks)
{
m_tokens = m_tks.m_tokens;
AddNfaNode(nfa); // the starting node is Closure(start)
Closure();
AddActions(); // recursively build the Dfa
}
internal bool AddNfaNode(NfaNode nfa)
{
if (!m_nfa.Add(nfa))
return false;
if (nfa.m_sTerminal!="")
{
int qi,n;
string tokClass = "";
string p=nfa.m_sTerminal;
if (p[0]=='%')
{ // check for %Tokname special action
for (n=0,qi=1;qi<p.Length;qi++,n++) // extract the class name
if (p[qi]==' '||p[qi]=='\t'||p[qi]=='\n'||p[qi]=='{'||p[qi]==':')
break;
tokClass = nfa.m_sTerminal.Substring(1,n);
}
// special action is always last in the list
if (tokClass=="")
{ //nfa has an old action
if (m_tokClass=="" // if both are old-style
|| // or we have a special action that is later
(m_actions.a_act)>nfa.m_state) // m_actions has at least one entry
AddAction(nfa.m_state);
// else we have a higher-precedence special action so we do nothing
}
else if (m_actions==null || m_actions.a_act>nfa.m_state)
{
MakeLastAction(nfa.m_state);
m_tokClass = tokClass;
} // else we have a higher-precedence special action so we do nothing
}
return true;
}
[NonSerialized] internal NList m_nfa = new NList(); // nfa nodes in m_state order
internal void AddActions()
{
// This routine is called for a new DFA node
m_tks.states.Add(this);
// Follow all the arcs from here
foreach (Charset cs in m_tks.m_tokens.cats.Values)
foreach (char j in cs.m_chars.Keys)
{
Dfa dfa = Target(j);
if (dfa!=null)
m_map[j] = dfa;
}
}
internal Dfa Target(char ch)
{ // construct or lookup the target for a new arc
Dfa n = new Dfa(m_tks);
for (NList pos = m_nfa; !pos.AtEnd; pos=pos.m_next)
pos.m_node.AddTarget(ch,n);
// check we actually got something
if (n.m_nfa.AtEnd)
return null;
n.Closure();
// now check we haven't got it already
for (int pos1=0;pos1<m_tks.states.Count;pos1++)
if (((Dfa)m_tks.states[pos1]).SameAs(n))
return (Dfa)m_tks.states[pos1];
// this is a brand new Dfa node so recursively build it
n.AddActions();
return n;
}
void Closure()
{
for (NList pos=m_nfa; !pos.AtEnd; pos=pos.m_next)
ClosureAdd(pos.m_node);
}
void ClosureAdd(NfaNode nfa)
{
for (int pos=0;pos<nfa.m_eps.Count;pos++)
{
NfaNode p = (NfaNode)nfa.m_eps[pos];
if (AddNfaNode(p))
ClosureAdd(p);
}
}
internal bool SameAs(Dfa dfa)
{
NList pos1 = m_nfa;
NList pos2 = dfa.m_nfa;
while (pos1.m_node==pos2.m_node && !pos1.AtEnd)
{
pos1 = pos1.m_next;
pos2 = pos2.m_next;
}
return pos1.m_node==pos2.m_node;
}
// match a Dfa agsint a given string
public int Match(string str,int ix,ref int action)
{ // return number of chars matched
int r=0;
Dfa dfa=null;
// if there is no arc or the string is exhausted, this is okay at a terminal
if (ix>=str.Length ||
(dfa=((Dfa)m_map[m_tokens.Filter(str[ix])]))==null ||
(r=dfa.Match(str,ix+1,ref action))<0)
{
if (m_actions!=null)
{
action = m_actions.a_act;
return 0;
}
return -1;
}
return r+1;
}
public void Print(TextWriter s)
{
s.Write("{0}:",m_state);
if (m_actions!=null)
{
s.Write(" (");
for (Action a = m_actions; a!=null; a=a.a_next)
s.Write("{0} <",a.a_act);
if (m_tokClass!="")
s.Write(m_tokClass);
s.Write(">)");
}
s.WriteLine();
Hashtable amap = new Hashtable(); // char->bool
IDictionaryEnumerator idx = m_map.GetEnumerator();
for (int count=m_map.Count; count-->0;)
{
idx.MoveNext();
char j = (char)idx.Key;
Dfa pD = (Dfa)idx.Value;
if (!amap.Contains(j))
{
amap[j] = true;
s.Write(" {0} ",pD.m_state);
int ij = (int)j;
if (ij>=32 && ij<128)
s.Write(j);
else
s.Write(" #{0} ",ij);
IDictionaryEnumerator idy = m_map.GetEnumerator();
for (;;)
{
idy.MoveNext();
Dfa pD1 = (Dfa)idy.Value;
if (pD1==pD)
break;
}
for (int count1=count;count1>0;count1--)
{
idy.MoveNext();
j = (char)idy.Key;
Dfa pD1 = (Dfa)idy.Value;
if (pD==pD1)
{
amap[j]=true;
ij = (int)j;
if (ij>=32 && ij<128)
s.Write(j);
else
s.Write(" #{0} ",ij);
}
}
s.WriteLine();
}
}
}
}
public class Regex
{
/*
Construct a Regex from a given string
1. First examine the given string.
If it is empty, there is nothing to do, so return (having cleared m_sub as a precaution).
2. Look to see if the string begins with a bracket ( . If so, find the matching ) .
This is not as simple as it might be because )s inside quotes or [] or escaped will not count.
Recursively call the constructor for the regular expression between the () s.
Mark everything up to the ) as used, and go to step 9.
3. Look to see if the string begins with a bracket [ . If so, find the matching ] , watching for escapes.
Construct a ReRange for everything between the []s.
Mark everything up to the ] as used, and go to step 9.
4. Look to see if the string begins with a ' or " . If so, build the contents interpreting
escaped special characters correctly, until the matching quote is reached.
Construct a ReStr for the contents, mark everything up to the final quote as used, and go to step 9.
4a. Look to see if the string begins with a U' or U" . If so, build the contents interpreting
escaped special characters correctly, until the matching quote is reached.
Construct a ReUStr for the contents, mark everything up to the final quote as used, and go to step 9.
5. Look to see if the string begins with a \ .
If so, build a ReStr for the next character (special action for ntr),
mark it as used, and go to step 9.
6. Look to see if the string begins with a { .
If so, find the matching }, lookup the symbolic name in the definitions table,
recursively call this constructor on the contents,
mark everything up to the } as used, and go to step 9.
7. Look to see if the string begins with a dot.
If so, construct a ReRange("^\n"), mark the . as used, and go to step 9.
8. At this point we conclude that there is a simple character at the start of the regular expression.
Construct a ReStr for it, mark it as used, and go to step 9.
9. If the string is exhausted, return.
We have a simple Regex whose m_sub contains what we can constructed.
10. If the next character is a ? , *, or +, construct a ReOpt, ReStart, or RePlus respectively
out of m_sub, and make m_sub point to this new class instead. Mark the character as used.
11. If the string is exhausted, return.
12. If the next character is a | , build a ReAlt using the m_sub we have and the rest of the string.
13. Otherwise build a ReCat using the m_sub we have and the rest of the string.
*/
public Regex(TokensGen tks,int p,string str)
{
int n = str.Length;
int nlp = 0;
int lbrack = 0;
int quote = 0;
int j;
char ch;
//1. First examine the given string.
// If it is empty, there is nothing to do, so return (having cleared m_sub as a precaution).
m_sub = null;
if (n==0)
return;
//2. Look to see if the string begins with a bracket ( . If so, find the matching ) .
// This is not as simple as it might be because )s inside quotes or [] or escaped will not count.
// Recursively call the constructor for the regular expression between the () s.
// Mark everything up to the ) as used, and go to step 9.
else if (str[0]=='(')
{ // identify a bracketed expression
for (j=1;j<n;j++)
if (str[j]=='\\')
j++;
else if (str[j]=='[' && quote==0 && lbrack==0)
lbrack++;
else if (str[j]==']' && lbrack>0)
lbrack = 0;
else if (str[j]=='"' || str[j]=='\'')
{
if (quote==str[j])
quote = 0;
else if (quote==0)
quote = str[j];
}
else if (str[j]=='(' && quote==0 && lbrack==0)
nlp++;
else if (str[j]==')' && quote==0 && lbrack==0 && nlp--==0)
break;
if (j==n)
goto bad;
m_sub = new Regex (tks,p+1,str.Substring(1,j-1));
j++;
//3. Look to see if the string begins with a bracket [ . If so, find the matching ] , watching for escapes.
// Construct a ReRange for everything between the []s.
// Mark everything up to the ] as used, and go to step 9.
}
else if (str[0]=='[')
{ // range of characters
for (j=1;j<n && str[j]!=']';j++)
if (str[j]=='\\')
j++;
if (j==n)
goto bad;
m_sub = new ReRange(tks,str.Substring(0,j+1));
j++;
}
//4. Look to see if the string begins with a ' or " . If so, build the contents interpreting
// escaped special characters correctly, until the matching quote is reached.
// Construct a CReStr for the contents, mark everything up to the final quote as used, and go to step 9.
else if (str[0] == '\'' || str[0] == '"')
{ // quoted string needs special treatment
string qs ="";
for (j=1;j<n && str[j]!=str[0];j++)
if (str[j]=='\\')
switch (str[++j])
{
case 'n': qs += '\n'; break;
case 'r': qs += '\r'; break;
case 't': qs += '\t'; break;
case '\\': qs += '\\'; break;
case '\'': qs += '\''; break;
case '"': qs += '"'; break;
case '\n': break;
default: qs += str[j]; break;
}
else
qs += str[j];
if (j==n)
goto bad;
j++;
m_sub = new ReStr(tks,qs);
}
//4a. Look to see if the string begins with a U' or U" . If so, build the contents interpreting
// escaped special characters correctly, until the matching quote is reached.
// Construct a ReUStr for the contents, mark everything up to the final quote as used, and go to step 9.
else if (str.StartsWith("U\"")||str.StartsWith("U'"))
{ // quoted string needs special treatment
string qs ="";
for (j=2;j<n && str[j]!=str[1];j++)
if (str[j]=='\\')
switch (str[++j])
{
case 'n': qs += '\n'; break;
case 'r': qs += '\r'; break;
case 't': qs += '\t'; break;
case '\\': qs += '\\'; break;
case '\'': qs += '\''; break;
case '"': qs += '"'; break;
case '\n': break;
default: qs += str[j]; break;
}
else
qs += str[j];
if (j==n)
goto bad;
j++;
m_sub = new ReUStr(tks,qs);
}
//5. Look to see if the string begins with a \ .
// If so, build a ReStr for the next character (special action for ntr),
// mark it as used, and go to step 9.
else if (str[0]=='\\')
{
switch (ch = str[1])
{
case 'n': ch = '\n'; break;
case 't': ch = '\t'; break;
case 'r': ch = '\r'; break;
}
m_sub = new ReStr(tks,ch);
j = 2;
//6. Look to see if the string begins with a { .
// If so, find the matching }, lookup the symbolic name in the definitions table,
// recursively call this constructor on the contents,
// mark everything up to the } as used, and go to step 9.
}
else if (str[0]=='{')
{
for (j=1;j<n && str[j]!='}';j++)
;
if (j==n)
goto bad;
string ds = str.Substring(1,j-1);
string s = (string)tks.defines[ds];
if (s==null)
m_sub = new ReCategory(tks,ds);
else
m_sub = new Regex(tks,p+1,s);
j++;
}
else
{ // simple character at start of regular expression
//7. Look to see if the string begins with a dot.
// If so, construct a CReDot, mark the . as used, and go to step 9.
if (str[0]=='.')
m_sub = new ReRange(tks,"[^\n]");
//8. At this point we conclude that there is a simple character at the start of the regular expression.
// Construct a ReStr for it, mark it as used, and go to step 9.
else
m_sub = new ReStr(tks,str[0]);
j = 1;
}
//9. If the string is exhausted, return.
// We have a simple Regex whose m_sub contains what we can constructed.
if (j>=n)
return;
//10. If the next character is a ? , *, or +, construct a CReOpt, CReStart, or CRePlus respectively
// out of m_sub, and make m_sub point to this new class instead. Mark the character as used.
if (str[j]=='?')
{
m_sub = new ReOpt(m_sub);
j++;
}
else if (str[j]=='*')
{
m_sub = new ReStar(m_sub);
j++;
}
else if (str[j]=='+')
{
m_sub = new RePlus(m_sub);
j++;
}
// 11. If the string is exhausted, return.
if (j>=n)
return;
// 12. If the next character is a | , build a ReAlt using the m_sub we have and the rest of the string.
if (str[j]=='|')
m_sub = new ReAlt(tks,m_sub,p+j+1,str.Substring(j+1,n-j-1));
// 13. Otherwise build a ReCat using the m_sub we have and the rest of the string.
else if (j<n)
m_sub = new ReCat(tks,m_sub,p+j,str.Substring(j,n-j));
return;
bad:
tks.erh.Error(new CSToolsFatalException(1,tks.line(p),tks.position(p),str,String.Format("ill-formed regular expression <{0}>\n", str)));
}
protected Regex() {} // private
public Regex m_sub;
public virtual void Print(TextWriter s)
{
if (m_sub!=null)
m_sub.Print(s);
}
// Match(ch) is used only in arc handling for ReRange
public virtual bool Match(char ch) { return false; }
// These two Match methods are only required if you want to use
// the Regex direcly for lexing. This is a very strange thing to do:
// it is non-deterministic and rather slow.
public int Match(string str)
{
return Match(str,0,str.Length);
}
public virtual int Match(string str,int pos,int max)
{
if (max<0)
return -1;
if (m_sub!=null)
return m_sub.Match(str,pos,max);
return 0;
}
public virtual void Build(Nfa nfa)
{
if (m_sub!=null)
{
Nfa sub = new Nfa(nfa.m_tks,m_sub);
nfa.AddEps(sub);
sub.m_end.AddEps(nfa.m_end);
}
else
nfa.AddEps(nfa.m_end);
}
}
internal class ReAlt : Regex
{
public ReAlt(TokensGen tks,Regex sub,int p,string str)
{
m_sub = sub;
m_alt = new Regex(tks,p,str);
}
public Regex m_alt;
public override void Print(TextWriter s)
{
s.Write("(");
if (m_sub!=null)
m_sub.Print(s);
s.Write("|");
if (m_alt!=null)
m_alt.Print(s);
s.Write(")");
}
public override int Match(string str, int pos, int max)
{
int a= -1, b= -1;
if (m_sub!=null)
a = m_sub.Match(str, pos, max);
if (m_alt!=null)
b = m_sub.Match(str, pos, max);
return (a>b)?a:b;
}
public override void Build(Nfa nfa)
{
if (m_alt!=null)
{
Nfa alt = new Nfa(nfa.m_tks,m_alt);
nfa.AddEps(alt);
alt.m_end.AddEps(nfa.m_end);
}
base.Build(nfa);
}
}
internal class ReCat : Regex
{
public ReCat(TokensGen tks,Regex sub, int p, string str)
{
m_sub = sub;
m_next = new Regex(tks,p,str);
}
Regex m_next;
public override void Print(TextWriter s)
{
s.Write("(");
if (m_sub!=null)
m_sub.Print(s);
s.Write(")(");
if (m_next!=null)
m_next.Print(s);
s.Write(")");
}
public override int Match(string str, int pos, int max)
{
int first, a, b, r = -1;
if (m_next==null)
return base.Match(str,pos,max);
if (m_sub==null)
return m_next.Match(str,pos,max);
for (first = max;first>=0;first=a-1)
{
a = m_sub.Match(str,pos,first);
if (a<0)
break;
b = m_next.Match(str,pos+a,max);
if (b<0)
continue;
if (a+b>r)
r = a+b;
}
return r;
}
public override void Build(Nfa nfa)
{
if (m_next!=null)
{
if (m_sub!=null)
{
Nfa first = new Nfa(nfa.m_tks,m_sub);
Nfa second = new Nfa(nfa.m_tks,m_next);
nfa.AddEps(first);
first.m_end.AddEps(second);
second.m_end.AddEps(nfa.m_end);
}
else
m_next.Build(nfa);
}
else
base.Build(nfa);
}
}
internal class ReStr : Regex
{
public ReStr() {}
public ReStr(TokensGen tks,string str)
{
m_str = str;
for (int i=0;i<str.Length;i++)
tks.m_tokens.UsingChar(str[i]);
}
public ReStr(TokensGen tks,char ch)
{
m_str = new string(ch,1);
tks.m_tokens.UsingChar(ch);
}
public string m_str = "";
public override void Print(TextWriter s)
{
s.Write(String.Format("(\"{0}\")",m_str));
}
public override int Match(string str, int pos, int max)
{
int j,n = m_str.Length;
if (n>max)
return -1;
if (n>max-pos)
return -1;
for(j=0;j<n;j++)
if (str[j]!=m_str[j])
return -1;
return n;
}
public override void Build(Nfa nfa)
{
int j,n = m_str.Length;
NfaNode p, pp = nfa;
for (j=0;j<n;pp = p,j++)
{
p = new NfaNode(nfa.m_tks);
pp.AddArc(m_str[j],p);
}
pp.AddEps(nfa.m_end);
}
}
internal class ReUStr : ReStr
{
public ReUStr(TokensGen tks,string str)
{
m_str = str;
for (int i=0;i<str.Length;i++)
{
tks.m_tokens.UsingChar(Char.ToLower(str[i]));
tks.m_tokens.UsingChar(Char.ToUpper(str[i]));
}
}
public ReUStr(TokensGen tks,char ch)
{
m_str = new string(ch,1);
tks.m_tokens.UsingChar(Char.ToLower(ch));
tks.m_tokens.UsingChar(Char.ToUpper(ch));
}
public override void Print(TextWriter s)
{
s.Write(String.Format("(U\"{0}\")",m_str));
}
public override int Match(string str, int pos, int max)
{
int j,n = m_str.Length;
if (n>max)
return -1;
if (n>max-pos)
return -1;
for(j=0;j<n;j++)
if (Char.ToUpper(str[j])!=Char.ToUpper(m_str[j]))
return -1;
return n;
}
public override void Build(Nfa nfa)
{
int j,n = m_str.Length;
NfaNode p, pp = nfa;
for (j=0;j<n;pp = p,j++)
{
p = new NfaNode(nfa.m_tks);
pp.AddUArc(m_str[j],p);
}
pp.AddEps(nfa.m_end);
}
}
internal class ReCategory : Regex
{
public ReCategory(TokensGen tks,string str)
{
m_str = str;
m_test = tks.m_tokens.GetTest(str);
}
string m_str;
ChTest m_test;
public override bool Match(char ch) { return m_test(ch); }
public override void Print(TextWriter s)
{
s.WriteLine("{"+m_str+"}");
}
public override void Build(Nfa nfa)
{
nfa.AddArcEx(this,nfa.m_end);
}
}
internal class ReRange : Regex
{
public ReRange(TokensGen tks,string str)
{
string ns = "";
int n = str.Length-1,v;
int p;
for (p=1;p<n;p++) // fix \ escapes
if (str[p] == '\\')
{
if (p+1<n)
p++;
if (str[p]>='0' && str[p]<='7')
{
for (v = str[p++]-'0';p<n && str[p]>='0' && str[p]<='7';p++)
v=v*8+str[p]-'0';
ns += (char)v;
}
else
switch(str[p])
{
case 'n' : ns += '\n'; break;
case 't' : ns += '\t'; break;
case 'r' : ns += '\r'; break;
default: ns += str[p]; break;
}
}
else
ns += str[p];
n = ns.Length;
if (ns[0] == '^')
{// invert range
m_invert = true;
ns = ns.Substring(1)+(char)0 +(char)0xFFFF;
}
for (p=0;p<n;p++)
if (p+1<n && ns[p+1]=='-')
{
for (v=ns[p];v<=ns[p+2];v++)
Set(tks,(char)v);
p += 2;
}
else
Set(tks,ns[p]);
}
public Hashtable m_map = new Hashtable(); // char->bool
public bool m_invert = false; // implement ^
public override void Print(TextWriter s)
{
s.Write("[");
if (m_invert)
s.Write("^");
foreach (char x in m_map.Keys)
s.Write(x);
s.Write("]");
}
void Set(TokensGen tks,char ch)
{
m_map[ch] = true;
tks.m_tokens.UsingChar(ch);
}
public override bool Match(char ch)
{
if (m_invert)
return !m_map.Contains(ch);
return m_map.Contains(ch);
}
public override int Match(string str, int pos, int max)
{
if (max<pos)
return -1;
return Match(str[pos])?1:-1;
}
public override void Build(Nfa nfa)
{
nfa.AddArcEx(this,nfa.m_end);
}
}
internal class ReOpt : Regex
{
public ReOpt(Regex sub) { m_sub = sub; }
public override void Print(TextWriter s)
{
m_sub.Print(s);
s.Write("?");
}
public override int Match(string str, int pos, int max)
{
int r;
r = m_sub.Match(str, pos, max);
if (r<0)
r = 0;
return r;
}
public override void Build(Nfa nfa)
{
nfa.AddEps(nfa.m_end);
base.Build(nfa);
}
}
internal class RePlus : Regex
{
public RePlus(Regex sub) {m_sub = sub; }
public override void Print(TextWriter s)
{
m_sub.Print(s);
s.Write("+");
}
public override int Match(string str, int pos, int max)
{
int n,r;
r = m_sub.Match(str, pos, max);
if (r<0)
return -1;
for (n=r;r>0;n+=r)
{
r = m_sub.Match(str, pos+n, max);
if (r<0)
break;
}
return n;
}
public override void Build(Nfa nfa)
{
base.Build(nfa);
nfa.m_end.AddEps(nfa);
}
}
internal class ReStar : Regex
{
public ReStar(Regex sub) {m_sub = sub; }
public override void Print(TextWriter s)
{
m_sub.Print(s);
s.Write("*");
}
public override int Match(string str, int pos, int max)
{
int n,r;
r = m_sub.Match(str,pos,max);
if (r<0)
return -1;
for (n=0;r>0;n+=r)
{
r = m_sub.Match(str, pos+n, max);
if (r<0)
break;
}
return n;
}
public override void Build(Nfa nfa)
{
Nfa sub = new Nfa(nfa.m_tks,m_sub);
nfa.AddEps(sub);
nfa.AddEps(nfa.m_end);
sub.m_end.AddEps(nfa);
}
}
/* The .NET Framework has its own Regex class which is an NFA recogniser
We don't want to use this for lexing because
it would be too slow (DFA is always faster)
programming in actions looks difficult
we want to explain the NFA->DFA algorithm to students
So in this project we are not using the Framework's Regex class but the one defined in regex.cs
*/
internal class Arc
{
public char m_ch;
public NfaNode m_next;
public Arc() {}
public Arc(char ch, NfaNode next) { m_ch=ch; m_next=next; }
public virtual bool Match(char ch)
{
return ch==m_ch;
}
public virtual void Print(TextWriter s)
{
s.WriteLine(String.Format(" {0} {1}",m_ch,m_next.m_state));
}
}
internal class ArcEx : Arc
{
public Regex m_ref;
public ArcEx(Regex re,NfaNode next) { m_ref=re; m_next=next; }
public override bool Match(char ch)
{
return m_ref.Match(ch);
}
public override void Print(TextWriter s)
{
s.Write(" ");
m_ref.Print(s);
s.WriteLine(m_next.m_state);
}
}
internal class UArc : Arc
{
public UArc() {}
public UArc(char ch,NfaNode next) : base(ch,next) {}
public override bool Match(char ch)
{
return Char.ToUpper(ch)==Char.ToUpper(m_ch);
}
public override void Print(TextWriter s)
{
s.WriteLine(String.Format(" U\'{0}\' {1}",m_ch,m_next.m_state));
}
}
public class NfaNode : LNode
{
public string m_sTerminal = ""; // or something for the Lexer
public ObjectList m_arcs = new ObjectList(); // of Arc for labelled arcs
public ObjectList m_eps = new ObjectList(); // of NfaNode for unlabelled arcs
public NfaNode(TokensGen tks):base(tks) {}
// build helpers
public void AddArc(char ch,NfaNode next)
{
m_arcs.Add(new Arc(ch,next));
}
public void AddUArc(char ch,NfaNode next)
{
m_arcs.Add(new UArc(ch,next));
}
public void AddArcEx(Regex re,NfaNode next)
{
m_arcs.Add(new ArcEx(re,next));
}
public void AddEps(NfaNode next)
{
m_eps.Add(next);
}
// helper for building DFa
public void AddTarget(char ch, Dfa next)
{
for (int j=0; j<m_arcs.Count; j++)
{
Arc a = (Arc)m_arcs[j];
if (a.Match(ch))
next.AddNfaNode(a.m_next);
}
}
}
// An NFA is defined by a start and end state
// Here we derive the Nfa from a NfaNode which acts as the start state
public class Nfa : NfaNode
{
public NfaNode m_end;
public Nfa(TokensGen tks) : base(tks)
{
m_end = new NfaNode(m_tks);
}
// build an NFA for a given regular expression
public Nfa(TokensGen tks,Regex re) : base(tks)
{
m_end = new NfaNode(tks);
re.Build(this);
}
}
// shame we have to do this ourselves, but SortedList doesn't allow incremental building of Dfas
internal class NList
{ // sorted List of NfaNode
public NfaNode m_node; // null for the sentinel
public NList m_next;
public NList() { m_node=null; m_next=null; } // sentinel only
NList(NfaNode nd,NList nx) { m_node=nd; m_next=nx; }
public bool Add(NfaNode n)
{
if (m_node==null)
{ // m_node==null iff m_next==null
m_next = new NList();
m_node = n;
}
else if (m_node.m_state < n.m_state)
{
m_next = new NList(m_node,m_next);
m_node = n;
}
else if (m_node.m_state == n.m_state)
return false; // Add fails, there already
else
return m_next.Add(n);
return true; // was added
}
public bool AtEnd { get { return m_node==null; } }
}
}