Logo Search packages:      
Sourcecode: monodevelop version File versions  Download package

Tab.cs

/* ------------------------------------------------------------------------
 * Tab.cs
 * Symbol table management of Coco/R
 * by H.Moessenboeck, Univ. of Linz
 * ------------------------------------------------------------------------*/
using System;
using System.IO;
using System.Collections;

namespace at.jku.ssw.Coco {

public class Position {  // position of source code stretch (e.g. semantic action, resolver expressions)
      public int beg;      // start relative to the beginning of the file
      public int len;      // length of stretch
      public int col;      // column number of start position
      
      public Position(int beg, int len, int col) {
            this.beg = beg; this.len = len; this.col = col;
      }
}


//---------------------------------------------------------------------
// Symbols
//---------------------------------------------------------------------
      
public class Symbol : IComparable {
      public static ArrayList terminals = new ArrayList();
      public static ArrayList pragmas = new ArrayList();
      public static ArrayList nonterminals = new ArrayList();
      public static Hashtable tokenNames = null;  /* AW 2003-03-25 */
      
      public const int classToken    = 0;       // token kinds
      public const int litToken      = 1;
      public const int classLitToken = 2;
      
      public int      n;           // symbol number
      public int      typ;         // t, nt, pr, unknown, rslv /* ML 29_11_2002 slv added */ /* AW slv --> rslv */
      public string   name;        // symbol name
      public Node     graph;       // nt: to first node of syntax graph
      public int      tokenKind;   // t:  token kind (literal, class, ...)
      public bool     deletable;   // nt: true if nonterminal is deletable
      public bool     firstReady;  // nt: true if terminal start symbols have already been computed
      public BitArray first;       // nt: terminal start symbols
      public BitArray follow;      // nt: terminal followers
      public BitArray nts;         // nt: nonterminals whose followers have to be added to this sym
      public int      line;        // source text line number of item in this node
      public Position attrPos;     // nt: position of attributes in source text (or null)
      public Position semPos;      // pr: pos of semantic action in source text (or null)
                                   // nt: pos of local declarations in source text (or null)
      public override string ToString()
      {
            return String.Format("[Symbol:Name={0}, n={1}]", name, n);
      }
      public Symbol(int typ, string name, int line) {
            if (name.Length == 2 && name[0] == '"') {
                  Parser.SemErr("empty token not allowed"); name = "???";
            }
            if (name.IndexOf(' ') >= 0) Parser.SemErr("tokens must not contain blanks");
            this.typ = typ; this.name = name; this.line = line;
            switch (typ) {
                  case Node.t:  n = terminals.Count; terminals.Add(this); break;
                  case Node.pr: pragmas.Add(this); break;
                  case Node.nt: n = nonterminals.Count; nonterminals.Add(this); break;
            }
      }
      
      public static Symbol Find(string name) {
            foreach (Symbol s in terminals)
                  if (s.name == name) return s;
            foreach (Symbol s in nonterminals)
                  if (s.name == name) return s;
            return null;
      }
      
      public int CompareTo(object x) {
            return name.CompareTo(((Symbol)x).name);
      }
      
}


//---------------------------------------------------------------------
// Syntax graph (class Node, class Graph)
//---------------------------------------------------------------------

public class Node {
      public static ArrayList nodes = new ArrayList();
      public static string[] nTyp =
            {"    ", "t   ", "pr  ", "nt  ", "clas", "chr ", "wt  ", "any ", "eps ",  /* AW 03-01-14 nTyp[0]: " " --> "    " */
             "sync", "sem ", "alt ", "iter", "opt ", "rslv"};
      
      // constants for node kinds
      public const int t    =  1;  // terminal symbol
      public const int pr   =  2;  // pragma
      public const int nt   =  3;  // nonterminal symbol
      public const int clas =  4;  // character class
      public const int chr  =  5;  // character
      public const int wt   =  6;  // weak terminal symbol
      public const int any  =  7;  // 
      public const int eps  =  8;  // empty
      public const int sync =  9;  // synchronization symbol
      public const int sem  = 10;  // semantic action: (. .)
      public const int alt  = 11;  // alternative: |
      public const int iter = 12;  // iteration: { }
      public const int opt  = 13;  // option: [ ]
      public const int rslv = 14;  // resolver expr  /* ML */ /* AW 03-01-13 renamed slv --> rslv */
      
      public const int normalTrans  = 0;        // transition codes
      public const int contextTrans = 1;
      
      public int      n;                  // node number
      public int      typ;          // t, nt, wt, chr, clas, any, eps, sem, sync, alt, iter, opt, rslv
      public Node     next;         // to successor node
      public Node     down;         // alt: to next alternative
      public Node     sub;          // alt, iter, opt: to first node of substructure
      public bool     up;                 // true: "next" leads to successor in enclosing structure
      public Symbol   sym;          // nt, t, wt: symbol represented by this node
      public int      val;          // chr:  ordinal character value
                                                                              // clas: index of character class
      public int      code;         // chr, clas: transition code
      public BitArray set;          // any, sync: the set represented by this node
      public Position pos;          // nt, t, wt: pos of actual attributes
                                                                              // sem:       pos of semantic action in source text
      public int      line;         // source text line number of item in this node
      public State    state;  // DFA state corresponding to this node
                                                                              // (only used in DFA.ConvertToStates)

      public Node(int typ, Symbol sym, int line) {
            this.typ = typ; this.sym = sym; this.line = line;
            n = nodes.Count;
            nodes.Add(this);
      }
      
      public Node(int typ, Node sub): this(typ, null, 0) {
            this.sub = sub;
      }
      
      public Node(int typ, int val, int line): this(typ, null, line) {
            this.val = val;
      }
      
      public static bool DelGraph(Node p) {
            return p == null || DelNode(p) && DelGraph(p.next);
      }
      
      public static bool DelAlt(Node p) {
            return p == null || DelNode(p) && (p.up || DelAlt(p.next));
      }
      
      public static bool DelNode(Node p) {
            if (p.typ == nt) return p.sym.deletable;
            else if (p.typ == alt) return DelAlt(p.sub) || p.down != null && DelAlt(p.down);
            else return p.typ == eps || p.typ == iter || p.typ == opt || p.typ == sem || p.typ == sync;
      }
      
      //----------------- for printing ----------------------
      
      static int Ptr(Node p, bool up) {
            if (p == null) return 0; 
            else if (up) return -p.n;
            else return p.n;
      }
      
      static string Pos(Position pos) {
            if (pos == null) return "     "; else return String.Format("{0,5}", pos.beg);
      }
      
      public static string Name(string name) {
            return (name + "           ").Substring(0, 12);
            /* isn't this better (less string allocations, easier to understand): *
             * return (name.Length > 12) ? name.Substring(0,12) : name;           */
      }
      
      public static void PrintNodes() {
            Trace.WriteLine("Graph nodes:");
            Trace.WriteLine("----------------------------------------------------");
            Trace.WriteLine("   n type name          next  down   sub   pos  line");
            Trace.WriteLine("                               val  code");
            Trace.WriteLine("----------------------------------------------------");
            foreach (Node p in nodes) {
                  Trace.Write("{0,4} {1} ", p.n, nTyp[p.typ]);
                  if (p.sym != null)
                        Trace.Write("{0,12} ", Name(p.sym.name));
                  else if (p.typ == Node.clas) {
                        CharClass c = (CharClass)CharClass.classes[p.val];
                        Trace.Write("{0,12} ", Name(c.name));
                  } else Trace.Write("             ");
                  Trace.Write("{0,5} ", Ptr(p.next, p.up));
                  switch (p.typ) {
                        case t: case nt: case wt:
                              Trace.Write("             {0,5}", Pos(p.pos)); break;
                        case chr:
                              Trace.Write("{0,5} {1,5}       ", p.val, p.code); break;
                        case clas:
                              Trace.Write("      {0,5}       ", p.code); break;
                        case alt: case iter: case opt:
                              Trace.Write("{0,5} {1,5}       ", Ptr(p.down, false), Ptr(p.sub, false)); break;
                        case sem:
                              Trace.Write("             {0,5}", Pos(p.pos)); break;
                        case eps: case any: case sync:
                              Trace.Write("                  "); break;
                  }
                  Trace.WriteLine("{0,5}", p.line);
            }
            Trace.WriteLine();
      }
      
}


public class Graph {
      static Node dummyNode = new Node(Node.eps, null, 0);
      
      public Node l;    // left end of graph = head
      public Node r;    // right end of graph = list of nodes to be linked to successor graph
      
      public Graph() {
            l = null; r = null;
      }
      
      public Graph(Node left, Node right) {
            l = left; r = right;
      }
      
      public Graph(Node p) {
            l = p; r = p;
      }

      public static void MakeFirstAlt(Graph g) {
            g.l = new Node(Node.alt, g.l); g.l.line = g.l.sub.line; /* AW 2002-03-07 make line available for error handling */
            g.l.next = g.r;
            g.r = g.l;
      }
      
      public static void MakeAlternative(Graph g1, Graph g2) {
            g2.l = new Node(Node.alt, g2.l); g2.l.line = g2.l.sub.line;
            Node p = g1.l; while (p.down != null) p = p.down;
            p.down = g2.l;
            p = g1.r; while (p.next != null) p = p.next;
            p.next = g2.r;
      }
      
      public static void MakeSequence(Graph g1, Graph g2) {
            Node p = g1.r.next; g1.r.next = g2.l; // link head node
            while (p != null) {  // link substructure
                  Node q = p.next; p.next = g2.l; p.up = true;
                  p = q;
            }
            g1.r = g2.r;
      }
      
      public static void MakeIteration(Graph g) {
            g.l = new Node(Node.iter, g.l);
            Node p = g.r;
            g.r = g.l;
            while (p != null) {
                  Node q = p.next; p.next = g.l; p.up = true;
                  p = q;
            }
      }
      
      public static void MakeOption(Graph g) {
            g.l = new Node(Node.opt, g.l);
            g.l.next = g.r;
            g.r = g.l;
      }
      
      public static void Finish(Graph g) {
            Node p = g.r;
            while (p != null) {
                  Node q = p.next; p.next = null; p = q;
            }
      }
      
  public static void SetContextTrans(Node p) { // set transition code in the graph rooted at p
    DFA.hasCtxMoves = true;
    while (p != null) {
      if (p.typ == Node.chr || p.typ == Node.clas) {
        p.code = Node.contextTrans;
      } else if (p.typ == Node.opt || p.typ == Node.iter) {
        SetContextTrans(p.sub);
      } else if (p.typ == Node.alt) {
        SetContextTrans(p.sub); SetContextTrans(p.down);
      }
      if (p.up) break;
      p = p.next;
    }
  }
      
      public static void DeleteNodes() {
            Node.nodes = new ArrayList();
            dummyNode = new Node(Node.eps, null, 0);
      }
      
      public static Graph StrToGraph(string str) {
            string s = DFA.Unescape(str.Substring(1, str.Length-2));
            if (s.IndexOf('\0') >= 0) Parser.SemErr("\\0 not allowed here. Used as eof character");
            if (s.Length == 0) Parser.SemErr("empty token not allowed");
            Graph g = new Graph();
            g.r = dummyNode;
            for (int i = 0; i < s.Length; i++) {
                  Node p = new Node(Node.chr, (int)s[i], 0);
                  g.r.next = p; g.r = p;
            }
            g.l = dummyNode.next; dummyNode.next = null;
            return g;
      }
      
}


//----------------------------------------------------------------
// Bit sets 
//----------------------------------------------------------------

public class Sets {
      
      public static int First(BitArray s) {
            int max = s.Count;
            for (int i=0; i<max; i++)
                  if (s[i]) return i;
            return -1;
      }
      
      public static int Elements(BitArray s) {
            int max = s.Count;
            int n = 0;
            for (int i=0; i<max; i++)
                  if (s[i]) n++;
            return n;
      }
      
      public static bool Equals(BitArray a, BitArray b) {
            int max = a.Count;
            for (int i=0; i<max; i++)
                  if (a[i] != b[i]) return false;
            return true;
      }
      
      public static bool Includes(BitArray a, BitArray b) { // a > b ?
            int max = a.Count;
            for (int i=0; i<max; i++)
                  if (b[i] && ! a[i]) return false;
            return true;
      }
      
      public static bool Intersect(BitArray a, BitArray b) { // a * b != {}
            int max = a.Count;
            for (int i=0; i<max; i++)
                  if (a[i] && b[i]) return true;
            return false;
      }
      
      public static void Subtract(BitArray a, BitArray b) { // a = a - b
            BitArray c = (BitArray) b.Clone();
            a.And(c.Not());
      }
      
      public static void PrintSet(BitArray s, int indent) {
            int col, len;
            col = indent;
            foreach (Symbol sym in Symbol.terminals) {
                  if (s[sym.n]) {
                        len = sym.name.Length;
                        if (col + len >= 80) {
                              Trace.WriteLine();
                              for (col = 1; col < indent; col++) Trace.Write(" ");
                        }
                        Trace.Write("{0} ", sym.name);
                        col += len + 1;
                  }
            }
            if (col == indent) Trace.Write("-- empty set --");
            Trace.WriteLine();
      }
      
}


//---------------------------------------------------------------------
// Character class management
//---------------------------------------------------------------------

public class CharClass {
      public static ArrayList classes = new ArrayList();
      public static int dummyName = 'A';
      
      public const int charSetSize = 256;  // must be a multiple of 16
      
      public int n;           // class number
      public string name;           // class name
      public BitArray set;    // set representing the class

      public CharClass(string name, BitArray s) {
            if (name == "#") name = "#" + (char)dummyName++;
            this.n = classes.Count; this.name = name; this.set = s;
            classes.Add(this);
      }
      
      public static CharClass Find(string name) {
            foreach (CharClass c in classes)
                  if (c.name == name) return c;
            return null;
      }
      
      public static CharClass Find(BitArray s) {
            foreach (CharClass c in classes)
                  if (Sets.Equals(s, c.set)) return c;
            return null;
      }
      
      public static BitArray Set(int i) {
            return ((CharClass)classes[i]).set;
      }
      
      static string Ch(int ch) {
            if (ch < ' ' || ch >= 127 || ch == '\'' || ch == '\\') return ch.ToString();
            else return String.Format("'{0}'", (char)ch);
      }
      
      static void WriteCharSet(BitArray s) {
                  int i = 0, len = s.Count;
                  while (i < len) {
                        while (i < len && !s[i]) i++;
                        if (i == len) break;
                        int j = i;
                        while (i < len && s[i]) i++;
                        if (j < i-1) Trace.Write("{0}..{1} ", Ch(j), Ch(i-1)); 
                        else Trace.Write("{0} ", Ch(j));
                  }
      }
      
      public static void WriteClasses () {
            foreach (CharClass c in classes) {
                  Trace.Write("{0,-10}: ", c.name);
                  WriteCharSet(c.set);
                  Trace.WriteLine();
            }
            Trace.WriteLine();
      }
}


//-----------------------------------------------------------
// Symbol table management routines
//-----------------------------------------------------------

public class Tab {
      public static Position semDeclPos;  // position of global semantic declarations
      public static BitArray ignored;                 // characters ignored by the scanner
      public static bool[] ddt = new bool[10];  // debug and test switches
      public static Symbol gramSy;                    // root nonterminal; filled by ATG
      public static Symbol eofSy;                           // end of file symbol
      public static Symbol noSym;                           // used in case of an error
      public static BitArray allSyncSets; // union of all synchronisation sets
      public static string nsName;        // namespace for generated files
      
      static BitArray visited;                                    // mark list for graph traversals
      static Symbol curSy;                                              // current symbol in computation of sets
      
      //---------------------------------------------------------------------
      //  Symbol set computations
      //---------------------------------------------------------------------

      /* Computes the first set for the given Node. */
      static BitArray First0(Node p, BitArray mark) {
            BitArray fs = new BitArray(Symbol.terminals.Count);
            while (p != null && !mark[p.n]) {
                  mark[p.n] = true;
                  switch (p.typ) {
                        case Node.nt: {
                              if (p.sym.firstReady) fs.Or(p.sym.first);
                              else fs.Or(First0(p.sym.graph, mark));
                              break;
                        }
                        case Node.t: case Node.wt: {
                              fs[p.sym.n] = true; break;
                        }
                        case Node.any: {
                              fs.Or(p.set); break;
                        }
                        case Node.alt: {
                              fs.Or(First0(p.sub, mark));
                              fs.Or(First0(p.down, mark));
                              break;
                        }
                        case Node.iter: case Node.opt: {
                              fs.Or(First0(p.sub, mark));
                              break;
                        }
                  }
                  if (!Node.DelNode(p)) break;
                  p = p.next;
            }
            return fs;
      }
      
      /// <returns>
      /// BitArray which contains the first tokens.
      /// </returns>
      public static BitArray First(Node p) {
            BitArray fs = First0(p, new BitArray(Node.nodes.Count));
            if (ddt[3]) {
                  Trace.WriteLine(); 
                  if (p != null) Trace.WriteLine("First: node = {0}", p.n);
                  else Trace.WriteLine("First: node = null");
                  Sets.PrintSet(fs, 0);
            }
            return fs;
      }

      
      static void CompFirstSets() {
            foreach (Symbol sym in Symbol.nonterminals) {
                  sym.first = new BitArray(Symbol.terminals.Count);
                  sym.firstReady = false;
            }
            foreach (Symbol sym in Symbol.nonterminals) {
                  sym.first = First(sym.graph);
                  sym.firstReady = true;
            }
      }
      
      static void CompFollow(Node p) {
            while (p != null && !visited[p.n]) {
                  visited[p.n] = true;
                  if (p.typ == Node.nt) {
                        BitArray s = First(p.next);
                        p.sym.follow.Or(s);
                        if (Node.DelGraph(p.next))
                              p.sym.nts[curSy.n] = true;
                  } else if (p.typ == Node.opt || p.typ == Node.iter) {
                        CompFollow(p.sub);
                  } else if (p.typ == Node.alt) {
                        CompFollow(p.sub); CompFollow(p.down);
                  }
                  p = p.next;
            }
      }
      
      static void Complete(Symbol sym) {
            if (!visited[sym.n]) {
                  visited[sym.n] = true;
                  foreach (Symbol s in Symbol.nonterminals) {
                        if (sym.nts[s.n]) {
                              Complete(s);
                              sym.follow.Or(s.follow);
                              if (sym == curSy) sym.nts[s.n] = false;
                        }
                  }
            }
      }
      
      static void CompFollowSets() {
            foreach (Symbol sym in Symbol.nonterminals) {
                  sym.follow = new BitArray(Symbol.terminals.Count);
                  sym.nts = new BitArray(Symbol.nonterminals.Count);
            }
            visited = new BitArray(Node.nodes.Count);
            foreach (Symbol sym in Symbol.nonterminals) { // get direct successors of nonterminals
                  curSy = sym;
                  CompFollow(sym.graph);
            }
            foreach (Symbol sym in Symbol.nonterminals) { // add indirect successors to followers
                  visited = new BitArray(Symbol.nonterminals.Count);
                  curSy = sym;
                  Complete(sym);
            }
      }
      
      static Node LeadingAny(Node p) {
            if (p == null) return null;
            Node a = null;
            if (p.typ == Node.any) a = p;
            else if (p.typ == Node.alt) {
                  a = LeadingAny(p.sub);
                  if (a == null) a = LeadingAny(p.down);
            }
            else if (p.typ == Node.opt || p.typ == Node.iter) a = LeadingAny(p.sub);
            else if (Node.DelNode(p) && !p.up) a = LeadingAny(p.next);
            return a;
      }
      
      static void FindAS(Node p) { // find ANY sets
            Node a;
            while (p != null) {
                  if (p.typ == Node.opt || p.typ == Node.iter) {
                        FindAS(p.sub);
                        a = LeadingAny(p.sub);
                        if (a != null) Sets.Subtract(a.set, First(p.next));
                  } else if (p.typ == Node.alt) {
                        BitArray s1 = new BitArray(Symbol.terminals.Count);
                        Node q = p;
                        while (q != null) {
                              FindAS(q.sub);
                              a = LeadingAny(q.sub);
                              if (a != null)
                                    Sets.Subtract(a.set, First(q.down).Or(s1));
                              else
                                    s1.Or(First(q.sub));
                              q = q.down;
                        }
                  }
                  if (p.up) break;
                  p = p.next;
            }
      }
      
      static void CompAnySets() {
            foreach (Symbol sym in Symbol.nonterminals) FindAS(sym.graph);
      }
      
      public static BitArray Expected(Node p, Symbol curSy) {
            BitArray s = First(p);
            if (Node.DelGraph(p)) s.Or(curSy.follow);
            return s;
      }

      public static BitArray Expected(Node p, Symbol curSy, int outmost) {
            BitArray s = First(p);
            if (Node.DelGraph(p)) s.Or(curSy.follow);
            return s;
      }
      
      static void CompSync(Node p) {
            while (p != null && !visited[p.n]) {
                  visited[p.n] = true;
                  if (p.typ == Node.sync) {
                        BitArray s = Expected(p.next, curSy);
                        s[eofSy.n] = true;
                        allSyncSets.Or(s);
                        p.set = s;
                  } else if (p.typ == Node.alt) {
                        CompSync(p.sub); CompSync(p.down);
                  } else if (p.typ == Node.opt || p.typ == Node.iter)
                        CompSync(p.sub);
                  p = p.next;
            }
      }
      
      static void CompSyncSets() {
            allSyncSets = new BitArray(Symbol.terminals.Count);
            allSyncSets[eofSy.n] = true;
            visited = new BitArray(Node.nodes.Count);
            foreach (Symbol sym in Symbol.nonterminals) {
                  curSy = sym;
                  CompSync(curSy.graph);
            }
      }
      
      public static void SetupAnys() {
            foreach (Node p in Node.nodes)
                  if (p.typ == Node.any) {
                        p.set = new BitArray(Symbol.terminals.Count, true);
                        p.set[eofSy.n] = false;
                  }
      }
      
      public static void CompDeletableSymbols() {
            bool changed;
            do {
                  changed = false;
                  foreach (Symbol sym in Symbol.nonterminals)
                        if (!sym.deletable && sym.graph != null && Node.DelGraph(sym.graph)) {
                              sym.deletable = true; changed = true;
                        }
            } while (changed);
            foreach (Symbol sym in Symbol.nonterminals)
                  if (sym.deletable) Console.WriteLine("  {0} deletable", sym.name);
      }
      
      public static void RenumberPragmas() {
            int n = Symbol.terminals.Count;
            foreach (Symbol sym in Symbol.pragmas) sym.n = n++;
      }

      public static void CompSymbolSets() {
            CompDeletableSymbols();
            CompFirstSets();
            CompFollowSets();
            CompAnySets();
            CompSyncSets();
            if (ddt[1]) {
                  Trace.WriteLine();
                  Trace.WriteLine("First & follow symbols:");
                  Trace.WriteLine("----------------------"); Trace.WriteLine();
                  foreach (Symbol sym in Symbol.nonterminals) {
                        Trace.WriteLine(sym.name);
                        Trace.Write("first:   "); Sets.PrintSet(sym.first, 10);
                        Trace.Write("follow:  "); Sets.PrintSet(sym.follow, 10);
                        Trace.WriteLine();
                  }
            }
            if (ddt[4]) {
                  Trace.WriteLine();
                  Trace.WriteLine("ANY and SYNC sets:");
                  Trace.WriteLine("-----------------");
                  foreach (Node p in Node.nodes)
                        if (p.typ == Node.any || p.typ == Node.sync) {
                              Trace.Write("{0,4} {1,4}: ", p.n, Node.nTyp[p.typ]);
                              Sets.PrintSet(p.set, 11);
                        }
            }
      }
      
      //---------------------------------------------------------------------
      //  Grammar checks
      //---------------------------------------------------------------------
      
      public static bool GrammarOk() {
            bool ok = NtsComplete() 
                  && AllNtReached() 
                  && NoCircularProductions()
                  && AllNtToTerm();
    if (ok) CheckLL1();
    return ok;
      }

      //--------------- check for circular productions ----------------------
      
      class CNode {     // node of list for finding circular productions
            public Symbol left, right;
      
            public CNode (Symbol l, Symbol r) {
                  left = l; right = r;
            }
      }

      static void GetSingles(Node p, ArrayList singles) {
            if (p == null) return;  // end of graph
            if (p.typ == Node.nt) {
                  if (p.up || Node.DelGraph(p.next)) singles.Add(p.sym);
            } else if (p.typ == Node.alt || p.typ == Node.iter || p.typ == Node.opt) {
                  if (p.up || Node.DelGraph(p.next)) {
                        GetSingles(p.sub, singles);
                        if (p.typ == Node.alt) GetSingles(p.down, singles);
                  }
            }
            if (!p.up && Node.DelNode(p)) GetSingles(p.next, singles);
      }
      
      public static bool NoCircularProductions() {
            bool ok, changed, onLeftSide, onRightSide;
            ArrayList list = new ArrayList();
            foreach (Symbol sym in Symbol.nonterminals) {
                  ArrayList singles = new ArrayList();
                  GetSingles(sym.graph, singles); // get nonterminals s such that sym-->s
                  foreach (Symbol s in singles) list.Add(new CNode(sym, s));
            }
            do {
                  changed = false;
                  for (int i = 0; i < list.Count; i++) {
                        CNode n = (CNode)list[i];
                        onLeftSide = false; onRightSide = false;
                        foreach (CNode m in list) {
                              if (n.left == m.right) onRightSide = true;
                              if (n.right == m.left) onLeftSide = true;
                        }
                        if (!onLeftSide || !onRightSide) {
                              list.Remove(n); i--; changed = true;
                        }
                  }
            } while(changed);
            ok = true;
            foreach (CNode n in list) {
                  ok = false; Errors.count++;
                  Console.WriteLine("  {0} --> {1}", n.left.name, n.right.name);
            }
            return ok;
      }
      
      //--------------- check for LL(1) errors ----------------------
      
      static void LL1Error(int cond, Symbol sym) {
            Console.Write("  LL1 warning in {0}: ", curSy.name);
            if (sym != null) Console.Write("{0} is ", sym.name);
            switch (cond) {
                  case 1: Console.WriteLine(" start of several alternatives"); break;
                  case 2: Console.WriteLine(" start & successor of deletable structure"); break;
                  case 3: Console.WriteLine(" an ANY node that matches no symbol"); break;
            }
      }
      
      static void CheckOverlap(BitArray s1, BitArray s2, int cond) {
            foreach (Symbol sym in Symbol.terminals) {
                  if (s1[sym.n] && s2[sym.n]) LL1Error(cond, sym);
            }
      }
      
      static void CheckAlts(Node p) {
            BitArray s1, s2;
            while (p != null) {
                  if (p.typ == Node.alt) {
                        Node q = p;
                        s1 = new BitArray(Symbol.terminals.Count);
                        while (q != null) { // for all alternatives
                              s2 = Expected(q.sub, curSy);
                              CheckOverlap(s1, s2, 1);
                              s1.Or(s2);
                              CheckAlts(q.sub);
                              q = q.down;
                        }
                  } else if (p.typ == Node.opt || p.typ == Node.iter) {
                        s1 = Expected(p.sub, curSy);
                        s2 = Expected(p.next, curSy);
                        CheckOverlap(s1, s2, 2);
                        CheckAlts(p.sub);
                  } else if (p.typ == Node.any) {
                        if (Sets.Elements(p.set) == 0) LL1Error(3, null);
                        // e.g. {ANY} ANY or [ANY] ANY
                  }
                  if (p.up) break;
                  p = p.next;
            }
      }

      static void RSlvError(string msg) {
            Console.WriteLine(msg);
      }


      static void CheckResolver(Node p) {
            while (p != null) {
                  // check subnodes of current node p
                  if ((p.typ == Node.alt || p.typ == Node.iter || p.typ == Node.opt) &&
                      !p.sub.up)
                        if (p.sub.typ == Node.rslv) CheckResolver(p.sub.next);
                        else CheckResolver(p.sub);
                  
                  // check current node p
                  switch (p.typ) {
                        case Node.alt:
                              BitArray uncovered = new BitArray(Symbol.terminals.Count);  // first symbols of alternatives without a resolver (not "covered" by a resolver)
                              ArrayList coveredList = new ArrayList();  // list of follow symbols of each resolver (these are "covered" by the resolver)
                              ArrayList rslvList = new ArrayList();

                              // build set of uncovered first symbols & check for misplaced resolvers 
                              // (= not at the first n-1 of n conflicting alternatives)
                              Node q = p;
                              while (q != null) {
                                    BitArray curCovered;
                                    if (q.sub.typ == Node.rslv) {
                                      // get followers of resolver (these are "covered" by it)
                                          if (q.sub.next == null) curCovered = curSy.follow;
                                          else curCovered = First0(q.sub.next, new BitArray(Node.nodes.Count));
                                          coveredList.Add(curCovered);
                                          rslvList.Add(q.sub);
                                          // resolver must "cover" all but the last occurrence of a conflicting symbol
                                          if (Sets.Intersect(uncovered, curCovered))
                                                RSlvError("Misplaced resolver at line " + q.sub.line + " will never be evaluated. " +
                                                          "Place resolver at previous conflicting alternative.");
                                    } else uncovered.Or(First0(q.sub, new BitArray(Node.nodes.Count)));
                                    q = q.down;
                              }

                              // check for obsolete resolvers 
                              // (= alternatives starting with resolvers, when there is no conflict)
                              BitArray[] covered = (BitArray[]) coveredList.ToArray(typeof(BitArray));
                              Node[] rslvs = (Node[]) rslvList.ToArray(typeof(Node));
                              for (int i = 0; i < rslvs.Length; ++i) {
                                    if (!Sets.Intersect(uncovered, covered[i])) 
                                          RSlvError("Obsolete resolver at line " + rslvs[i].line + ". " +
                                                    "Neither of the start symbols of the alternative occurs without a resolver.");
                                    /*
                                    if (!Sets.Includes(uncovered, covered[i]))
                                          RSlvError("At least one of the symbols after the resolver at line " + rslvs[i].line + 
                                                    " does not appear without a resolver. Remove the last resolver covering this symbol.");
                                    */
                                    /*
                                    if (Sets.Equals(, covered[i]))
                                          RSlvError("Resolver at line " + rslvArr[i].line + " covers more symbols than necessary.\n" +
                                                    "Place resolvers only in front of conflicting symbols.");
                                    */
                              }
                              break;
                        case Node.iter: case Node.opt:
                              if (p.sub.typ == Node.rslv) {
                                    BitArray fs = First0(p.sub.next, new BitArray(Node.nodes.Count));
                                    BitArray fsNext;
                                    if (p.next == null) fsNext = curSy.follow;
                                    else fsNext = First0(p.next, new BitArray(Node.nodes.Count));
                                    if (!Sets.Intersect(fs, fsNext)) 
                                          RSlvError("Obsolete resolver expression (IF ...) at line " + p.sub.line);
                              }
                              break;
                        case Node.rslv:
                              RSlvError("Unexpected Resolver in line " + p.line + ". Will cause parsing error.");
                              break;
                  }
                  if (p.up) break; 
                  p = p.next;
            }
      }

      public static void CheckLL1() {
            foreach (Symbol sym in Symbol.nonterminals) {
                  curSy = sym;
                  CheckAlts(curSy.graph);
                  CheckResolver(curSy.graph);
            }
      }
      
      //------------- check if every nts has a production --------------------
      
      public static bool NtsComplete() {
            bool complete = true;
            foreach (Symbol sym in Symbol.nonterminals) {
                  if (sym.graph == null) {
                        complete = false; Errors.count++;
                        Console.WriteLine("  No production for {0}", sym.name);
                  }
            }
            return complete;
      }
      
      //-------------- check if every nts can be reached  -----------------
      
      static void MarkReachedNts(Node p) {
            while (p != null) {
                  if (p.typ == Node.nt && !visited[p.sym.n]) { // new nt reached
                        visited[p.sym.n] = true;
                        MarkReachedNts(p.sym.graph);
                  } else if (p.typ == Node.alt || p.typ == Node.iter || p.typ == Node.opt) {
                        MarkReachedNts(p.sub);
                        if (p.typ == Node.alt) MarkReachedNts(p.down);
                  }
                  if (p.up) break;
                  p = p.next;
            }
      }
      
      public static bool AllNtReached() {
            bool ok = true;
            visited = new BitArray(Symbol.nonterminals.Count);
            visited[gramSy.n] = true;
            MarkReachedNts(gramSy.graph);
            foreach (Symbol sym in Symbol.nonterminals) {
                  if (!visited[sym.n]) {
                        ok = false; Errors.count++;
                        Console.WriteLine("  {0} cannot be reached", sym.name);
                  }
            }
            return ok;
      }
      
      //--------- check if every nts can be derived to terminals  ------------
      
      static bool IsTerm(Node p, BitArray mark) { // true if graph can be derived to terminals
            while (p != null) {
                  if (p.typ == Node.nt && !mark[p.sym.n]) return false;
                  if (p.typ == Node.alt && !IsTerm(p.sub, mark) 
                  && (p.down == null || !IsTerm(p.down, mark))) return false;
                  if (p.up) break;
                  p = p.next;
            }
            return true;
      }
      
      public static bool AllNtToTerm() {
            bool changed, ok = true;
            BitArray mark = new BitArray(Symbol.nonterminals.Count);
            // a nonterminal is marked if it can be derived to terminal symbols
            do {
                  changed = false;
                  foreach (Symbol sym in Symbol.nonterminals)
                        if (!mark[sym.n] && IsTerm(sym.graph, mark)) {
                              mark[sym.n] = true; changed = true;
                        }
            } while (changed);
            foreach (Symbol sym in Symbol.nonterminals)
                  if (!mark[sym.n]) {
                        ok = false; Errors.count++;
                        Console.WriteLine("  {0} cannot be derived to terminals", sym.name);
                  }
            return ok;
      }
      
      /*---------------------------------------------------------------------
        Utility functions
      ---------------------------------------------------------------------*/
      
      static int Num(Node p) {
            if (p == null) return 0; else return p.n;
      }
      
      static void PrintSym(Symbol sym) {
            Trace.Write("{0,3} {1,-14} {2}", sym.n, Node.Name(sym.name), Node.nTyp[sym.typ]);
            if (sym.attrPos==null) Trace.Write(" false "); else Trace.Write(" true  ");
            if (sym.typ == Node.nt) {
                  Trace.Write("{0,5}", Num(sym.graph));
                  if (sym.deletable) Trace.Write(" true  "); else Trace.Write(" false ");
            } else
                  Trace.Write("            ");
            Trace.WriteLine("{0,5}", sym.line);
      }

      public static void PrintSymbolTable() {
            Trace.WriteLine("Symbol Table:");
            Trace.WriteLine("------------"); Trace.WriteLine();
            Trace.WriteLine(" nr name          typ  hasAt graph  del   line");
            foreach (Symbol sym in Symbol.terminals) PrintSym(sym);
            foreach (Symbol sym in Symbol.pragmas) PrintSym(sym);
            foreach (Symbol sym in Symbol.nonterminals) PrintSym(sym);
            Trace.WriteLine();
      }
      
      public static void XRef() {
            SortedList tab = new SortedList();
            // collect lines where symbols have been defined
            foreach (Symbol sym in Symbol.nonterminals) {
                  ArrayList list = (ArrayList)tab[sym];
                  if (list == null) {list = new ArrayList(); tab[sym] = list;}
                  list.Add(- sym.line);
            }
            // collect lines where symbols have been referenced
            foreach (Node n in Node.nodes) {
                  if (n.typ == Node.t || n.typ == Node.wt || n.typ == Node.nt) {
                        ArrayList list = (ArrayList)tab[n.sym];
                        if (list == null) {list = new ArrayList(); tab[n.sym] = list;}
                        list.Add(n.line);
                  }
            }
            // print cross reference list
            Trace.WriteLine();
            Trace.WriteLine("Cross reference list:");
            Trace.WriteLine("--------------------"); Trace.WriteLine();
            foreach (Symbol sym in tab.Keys) {
                  Trace.Write("  {0,-12}", Node.Name(sym.name));
                  ArrayList list = (ArrayList)tab[sym];
                  int col = 14;
                  foreach (int line in list) {
                        if (col + 5 > 80) {
                              Trace.WriteLine();
                              for (col = 1; col <= 14; col++) Trace.Write(" ");
                        }
                        Trace.Write("{0,5}", line); col += 5;
                  }
                  Trace.WriteLine();
            }
            Trace.WriteLine(); Trace.WriteLine();
      }
      
      public static void SetDDT(string s) {
            s = s.ToUpper();
            foreach (char ch in s) {
                  if ('0' <= ch && ch <= '9') ddt[ch - '0'] = true;
                  else switch (ch) {
                        case 'A' : ddt[0] = true; break; // trace automaton
                        case 'F' : ddt[1] = true; break; // list first/follow sets
                        case 'G' : ddt[2] = true; break; // print syntax graph
                        case 'I' : ddt[3] = true; break; // trace computation of first sets
                        case 'J' : ddt[4] = true; break; // print ANY and SYNC sets
                        case 'P' : ddt[8] = true; break; // print statistics
                        case 'S' : ddt[6] = true; break; // list symbol table
                        case 'X' : ddt[7] = true; break; // list cross reference table
                        default : break;
                  }
            }
      }

      public static void Init () {
            eofSy = new Symbol(Node.t, "EOF", 0);
      }
      
} // end Tab

} // end namespace

Generated by  Doxygen 1.6.0   Back to index