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;qinfa.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=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;j0) 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) 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", 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;imax) return -1; if (n>max-pos) return -1; for(j=0;jmax) return -1; if (n>max-pos) return -1; for(j=0;j='0' && str[p]<='7') { for (v = str[p++]-'0';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;pbool 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 (max0;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