/*-------------------------------------------------------------------------
Tab.cs -- Symbol Table Management
Compiler Generator Coco/R,
Copyright (c) 1990, 2004 Hanspeter Moessenboeck, University of Linz
extended by M. Loeberbauer & A. Woess, Univ. of Linz
with improvements by Pat Terry, Rhodes University

This program is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 2, or (at your option) any
later version.

This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

As an exception, it is allowed to write an extension of Coco/R that is
used as a plugin in non-free software.

If not otherwise stated, any source code generated by Coco/R (other than
Coco/R itself) does not fall under the GNU General Public License.
-------------------------------------------------------------------------*/
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Text;

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 string virtualFile;
        public int virtualLine;

        public Position(int beg, int len, int col, string file, int line)
        {
            this.beg = beg;
            this.len = len;
            this.col = col;
            this.virtualFile = file;
            this.virtualLine = line;
        }
    }

    //=====================================================================
    // Symbol
    //=====================================================================

    public class Symbol : IComparable
    {
        // token kinds
        public const int fixedToken = 0; // e.g. 'a' ('b' | 'c') (structure of literals)
        public const int classToken = 1; // e.g. digit {digit}   (at least one char class)
        public const int litToken = 2; // e.g. "while"
        public const int classLitToken = 3; // e.g. letter {letter} but without literals that have the same structure

        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 (fixedToken, classToken, ...)
        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 Symbol(int typ, string name, int line)
        {
            this.typ = typ;
            this.name = name;
            this.line = line;
        }

        public int CompareTo(object x)
        {
            return name.CompareTo(((Symbol)x).name);
        }
    }

    //=====================================================================
    // Node
    //=====================================================================

    public class Node
    {
        // 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

        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;
        }
    }

    //=====================================================================
    // Graph
    //=====================================================================

    public class Graph
    {
        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;
        }
    }

    //=====================================================================
    // Sets
    //=====================================================================

    public class Sets
    {
        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 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());
        }
    }

    //=====================================================================
    // CharClass
    //=====================================================================

    public class CharClass
    {
        public int n; // class number
        public string name; // class name
        public CharSet set; // set representing the class

        public CharClass(string name, CharSet s)
        {
            this.name = name;
            this.set = s;
        }
    }

    //=====================================================================
    // Tab
    //=====================================================================

    public class Tab
    {
        public List<Position> semDeclPositions = new List<Position>(); // positions of global semantic declarations
        public CharSet ignored; // characters ignored by the scanner
        public bool[] ddt = new bool[10]; // debug and test switches
        public Symbol gramSy; // root nonterminal; filled by ATG
        public Symbol eofSy; // end of file symbol
        public Symbol noSym; // used in case of an error
        public BitArray allSyncSets; // union of all synchronisation sets
        public Hashtable literals; // symbols that are used as literals

        public string srcName; // name of the atg file (including path)
        public string srcDir; // directory path of the atg file
        public string nsName; // namespace for generated files
        public string frameDir; // directory containing the frame files

        BitArray visited; // mark list for graph traversals
        Symbol curSy; // current symbol in computation of sets

        Parser parser; // other Coco objects
        TextWriter trace;
        Errors errors;

        public Tab(Parser parser)
        {
            this.parser = parser;
            trace = parser.trace;
            errors = parser.errors;
            eofSy = NewSym(Node.t, "EOF", 0);
            dummyNode = NewNode(Node.eps, null, 0);
            literals = new Hashtable();
        }

        //---------------------------------------------------------------------
        //  Symbol list management
        //---------------------------------------------------------------------

        public ArrayList terminals = new ArrayList();
        public ArrayList pragmas = new ArrayList();
        public ArrayList nonterminals = new ArrayList();

        string[] tKind = { "fixedToken", "classToken", "litToken", "classLitToken" };

        public Symbol NewSym(int typ, string name, int line)
        {
            if (name.Length == 2 && name[0] == '"')
            {
                parser.SemErr("empty token not allowed");
                name = "???";
            }
            Symbol sym = new Symbol(typ, name, line);
            switch (typ)
            {
                case Node.t:
                    sym.n = terminals.Count;
                    terminals.Add(sym);
                    break;
                case Node.pr:
                    pragmas.Add(sym);
                    break;
                case Node.nt:
                    sym.n = nonterminals.Count;
                    nonterminals.Add(sym);
                    break;
            }
            return sym;
        }

        public Symbol FindSym(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;
        }

        int Num(Node p)
        {
            if (p == null)
                return 0;
            else
                return p.n;
        }

        void PrintSym(Symbol sym)
        {
            trace.Write("{0,3} {1,-14} {2}", sym.n, Name(sym.name), 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} {1}", sym.line, tKind[sym.tokenKind]);
        }

        public void PrintSymbolTable()
        {
            trace.WriteLine("Symbol Table:");
            trace.WriteLine("------------");
            trace.WriteLine();
            trace.WriteLine(" nr name          typ  hasAt graph  del    line tokenKind");
            foreach (Symbol sym in terminals)
                PrintSym(sym);
            foreach (Symbol sym in pragmas)
                PrintSym(sym);
            foreach (Symbol sym in nonterminals)
                PrintSym(sym);
            trace.WriteLine();
            trace.WriteLine("Literal Tokens:");
            trace.WriteLine("--------------");
            foreach (DictionaryEntry e in literals)
            {
                trace.WriteLine("_" + ((Symbol)e.Value).name + " = " + e.Key + ".");
            }
            trace.WriteLine();
        }

        public void PrintSet(BitArray s, int indent)
        {
            int col,
                len;
            col = indent;
            foreach (Symbol sym in 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();
        }

        //---------------------------------------------------------------------
        //  Syntax graph management
        //---------------------------------------------------------------------

        public ArrayList nodes = new ArrayList();
        public string[] nTyp =
        {
            "    ",
            "t   ",
            "pr  ",
            "nt  ",
            "clas",
            "chr ",
            "wt  ",
            "any ",
            "eps ",
            "sync",
            "sem ",
            "alt ",
            "iter",
            "opt ",
            "rslv",
        };
        Node dummyNode;

        public Node NewNode(int typ, Symbol sym, int line)
        {
            Node node = new Node(typ, sym, line);
            node.n = nodes.Count;
            nodes.Add(node);
            return node;
        }

        public Node NewNode(int typ, Node sub)
        {
            Node node = NewNode(typ, null, 0);
            node.sub = sub;
            return node;
        }

        public Node NewNode(int typ, int val, int line)
        {
            Node node = NewNode(typ, null, line);
            node.val = val;
            return node;
        }

        public void MakeFirstAlt(Graph g)
        {
            g.l = NewNode(Node.alt, g.l);
            g.l.line = g.l.sub.line;
            g.l.next = g.r;
            g.r = g.l;
        }

        public void MakeAlternative(Graph g1, Graph g2)
        {
            g2.l = NewNode(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 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 void MakeIteration(Graph g)
        {
            g.l = NewNode(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 void MakeOption(Graph g)
        {
            g.l = NewNode(Node.opt, g.l);
            g.l.next = g.r;
            g.r = g.l;
        }

        public void Finish(Graph g)
        {
            Node p = g.r;
            while (p != null)
            {
                Node q = p.next;
                p.next = null;
                p = q;
            }
        }

        public void DeleteNodes()
        {
            nodes = new ArrayList();
            dummyNode = NewNode(Node.eps, null, 0);
        }

        public Graph StrToGraph(string str)
        {
            string s = Unescape(str.Substring(1, str.Length - 2));
            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 = NewNode(Node.chr, (int)s[i], 0);
                g.r.next = p;
                g.r = p;
            }
            g.l = dummyNode.next;
            dummyNode.next = null;
            return g;
        }

        public void SetContextTrans(Node p)
        { // set transition code in the graph rooted at p
            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;
            }
        }

        //------------ graph deletability check -----------------

        public bool DelGraph(Node p)
        {
            return p == null || DelNode(p) && DelGraph(p.next);
        }

        public bool DelSubGraph(Node p)
        {
            return p == null || DelNode(p) && (p.up || DelSubGraph(p.next));
        }

        public bool DelAlt(Node p)
        {
            return p == null || DelNode(p) && (p.up || DelAlt(p.next));
        }

        public bool DelNode(Node p)
        {
            if (p.typ == Node.nt)
                return p.sym.deletable;
            else if (p.typ == Node.alt)
                return DelAlt(p.sub) || p.down != null && DelAlt(p.down);
            else
                return p.typ == Node.iter
                    || p.typ == Node.opt
                    || p.typ == Node.sem
                    || p.typ == Node.eps
                    || p.typ == Node.rslv
                    || p.typ == Node.sync;
        }

        //----------------- graph printing ----------------------

        int Ptr(Node p, bool up)
        {
            if (p == null)
                return 0;
            else if (up)
                return -p.n;
            else
                return p.n;
        }

        string Pos(Position pos)
        {
            if (pos == null)
                return "     ";
            else
                return String.Format("{0,5}", pos.beg);
        }

        public string Name(string name)
        {
            return (name + "           ").Substring(0, 12);
            // found no simpler way to get the first 12 characters of the name
            // padded with blanks on the right
        }

        public 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)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 Node.t:
                    case Node.nt:
                    case Node.wt:
                        trace.Write("             {0,5}", Pos(p.pos));
                        break;
                    case Node.chr:
                        trace.Write("{0,5} {1,5}       ", p.val, p.code);
                        break;
                    case Node.clas:
                        trace.Write("      {0,5}       ", p.code);
                        break;
                    case Node.alt:
                    case Node.iter:
                    case Node.opt:
                        trace.Write("{0,5} {1,5}       ", Ptr(p.down, false), Ptr(p.sub, false));
                        break;
                    case Node.sem:
                        trace.Write("             {0,5}", Pos(p.pos));
                        break;
                    case Node.eps:
                    case Node.any:
                    case Node.sync:
                        trace.Write("                  ");
                        break;
                }
                trace.WriteLine("{0,5}", p.line);
            }
            trace.WriteLine();
        }

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

        public ArrayList classes = new ArrayList();
        public int dummyName = 'A';

        public CharClass NewCharClass(string name, CharSet s)
        {
            if (name == "#")
                name = "#" + (char)dummyName++;
            CharClass c = new CharClass(name, s);
            c.n = classes.Count;
            classes.Add(c);
            return c;
        }

        public CharClass FindCharClass(string name)
        {
            foreach (CharClass c in classes)
                if (c.name == name)
                    return c;
            return null;
        }

        public CharClass FindCharClass(CharSet s)
        {
            foreach (CharClass c in classes)
                if (s.Equals(c.set))
                    return c;
            return null;
        }

        public CharSet CharClassSet(int i)
        {
            return ((CharClass)classes[i]).set;
        }

        //----------- character class printing

        string Ch(int ch)
        {
            if (ch < ' ' || ch >= 127 || ch == '\'' || ch == '\\')
                return ch.ToString();
            else
                return String.Format("'{0}'", (char)ch);
        }

        void WriteCharSet(CharSet s)
        {
            for (CharSet.Range r = s.head; r != null; r = r.next)
                if (r.from < r.to)
                {
                    trace.Write(Ch(r.from) + ".." + Ch(r.to) + " ");
                }
                else
                {
                    trace.Write(Ch(r.from) + " ");
                }
        }

        public void WriteCharClasses()
        {
            foreach (CharClass c in classes)
            {
                trace.Write("{0,-10}: ", c.name);
                WriteCharSet(c.set);
                trace.WriteLine();
            }
            trace.WriteLine();
        }

        //---------------------------------------------------------------------
        //  Symbol set computations
        //---------------------------------------------------------------------

        /* Computes the first set for the graph rooted at p */
        BitArray First0(Node p, BitArray mark)
        {
            BitArray fs = new BitArray(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 (!DelNode(p))
                    break;
                p = p.next;
            }
            return fs;
        }

        public BitArray First(Node p)
        {
            BitArray fs = First0(p, new BitArray(nodes.Count));
            if (ddt[3])
            {
                trace.WriteLine();
                if (p != null)
                    trace.WriteLine("First: node = {0}", p.n);
                else
                    trace.WriteLine("First: node = null");
                PrintSet(fs, 0);
            }
            return fs;
        }

        void CompFirstSets()
        {
            foreach (Symbol sym in nonterminals)
            {
                sym.first = new BitArray(terminals.Count);
                sym.firstReady = false;
            }
            foreach (Symbol sym in nonterminals)
            {
                sym.first = First(sym.graph);
                sym.firstReady = true;
            }
        }

        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 (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;
            }
        }

        void Complete(Symbol sym)
        {
            if (!visited[sym.n])
            {
                visited[sym.n] = true;
                foreach (Symbol s in nonterminals)
                {
                    if (sym.nts[s.n])
                    {
                        Complete(s);
                        sym.follow.Or(s.follow);
                        if (sym == curSy)
                            sym.nts[s.n] = false;
                    }
                }
            }
        }

        void CompFollowSets()
        {
            foreach (Symbol sym in nonterminals)
            {
                sym.follow = new BitArray(terminals.Count);
                sym.nts = new BitArray(nonterminals.Count);
            }
            gramSy.follow[eofSy.n] = true;
            visited = new BitArray(nodes.Count);
            foreach (Symbol sym in nonterminals)
            { // get direct successors of nonterminals
                curSy = sym;
                CompFollow(sym.graph);
            }
            foreach (Symbol sym in nonterminals)
            { // add indirect successors to followers
                visited = new BitArray(nonterminals.Count);
                curSy = sym;
                Complete(sym);
            }
        }

        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 (DelNode(p) && !p.up)
                a = LeadingAny(p.next);
            return a;
        }

        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(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;
            }
        }

        void CompAnySets()
        {
            foreach (Symbol sym in nonterminals)
                FindAS(sym.graph);
        }

        public BitArray Expected(Node p, Symbol curSy)
        {
            BitArray s = First(p);
            if (DelGraph(p))
                s.Or(curSy.follow);
            return s;
        }

        // does not look behind resolvers; only called during LL(1) test and in CheckRes
        public BitArray Expected0(Node p, Symbol curSy)
        {
            if (p.typ == Node.rslv)
                return new BitArray(terminals.Count);
            else
                return Expected(p, curSy);
        }

        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;
            }
        }

        void CompSyncSets()
        {
            allSyncSets = new BitArray(terminals.Count);
            allSyncSets[eofSy.n] = true;
            visited = new BitArray(nodes.Count);
            foreach (Symbol sym in nonterminals)
            {
                curSy = sym;
                CompSync(curSy.graph);
            }
        }

        public void SetupAnys()
        {
            foreach (Node p in nodes)
                if (p.typ == Node.any)
                {
                    p.set = new BitArray(terminals.Count, true);
                    p.set[eofSy.n] = false;
                }
        }

        public void CompDeletableSymbols()
        {
            bool changed;
            do
            {
                changed = false;
                foreach (Symbol sym in nonterminals)
                    if (!sym.deletable && sym.graph != null && DelGraph(sym.graph))
                    {
                        sym.deletable = true;
                        changed = true;
                    }
            } while (changed);
            foreach (Symbol sym in nonterminals)
                if (sym.deletable)
                    errors.Warning("  " + sym.name + " deletable");
        }

        public void RenumberPragmas()
        {
            int n = terminals.Count;
            foreach (Symbol sym in pragmas)
                sym.n = n++;
        }

        public 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 nonterminals)
                {
                    trace.WriteLine(sym.name);
                    trace.Write("first:   ");
                    PrintSet(sym.first, 10);
                    trace.Write("follow:  ");
                    PrintSet(sym.follow, 10);
                    trace.WriteLine();
                }
            }
            if (ddt[4])
            {
                trace.WriteLine();
                trace.WriteLine("ANY and SYNC sets:");
                trace.WriteLine("-----------------");
                foreach (Node p in nodes)
                    if (p.typ == Node.any || p.typ == Node.sync)
                    {
                        trace.Write("{0,4} {1,4}: ", p.n, nTyp[p.typ]);
                        PrintSet(p.set, 11);
                    }
            }
        }

        //---------------------------------------------------------------------
        //  String handling
        //---------------------------------------------------------------------

        char Hex2Char(string s)
        {
            int val = 0;
            for (int i = 0; i < s.Length; i++)
            {
                char ch = s[i];
                if ('0' <= ch && ch <= '9')
                    val = 16 * val + (ch - '0');
                else if ('a' <= ch && ch <= 'f')
                    val = 16 * val + (10 + ch - 'a');
                else if ('A' <= ch && ch <= 'F')
                    val = 16 * val + (10 + ch - 'A');
                else
                    parser.SemErr("bad escape sequence in string or character");
            }
            if (val > char.MaxValue) /* pdt */
                parser.SemErr("bad escape sequence in string or character");
            return (char)val;
        }

        string Char2Hex(char ch)
        {
            StringWriter w = new StringWriter();
            w.Write("\\u{0:x4}", (int)ch);
            return w.ToString();
        }

        public string Unescape(string s)
        {
            /* replaces escape sequences in s by their Unicode values. */
            StringBuilder buf = new StringBuilder();
            int i = 0;
            while (i < s.Length)
            {
                if (s[i] == '\\')
                {
                    switch (s[i + 1])
                    {
                        case '\\':
                            buf.Append('\\');
                            i += 2;
                            break;
                        case '\'':
                            buf.Append('\'');
                            i += 2;
                            break;
                        case '\"':
                            buf.Append('\"');
                            i += 2;
                            break;
                        case 'r':
                            buf.Append('\r');
                            i += 2;
                            break;
                        case 'n':
                            buf.Append('\n');
                            i += 2;
                            break;
                        case 't':
                            buf.Append('\t');
                            i += 2;
                            break;
                        case '0':
                            buf.Append('\0');
                            i += 2;
                            break;
                        case 'a':
                            buf.Append('\a');
                            i += 2;
                            break;
                        case 'b':
                            buf.Append('\b');
                            i += 2;
                            break;
                        case 'f':
                            buf.Append('\f');
                            i += 2;
                            break;
                        case 'v':
                            buf.Append('\v');
                            i += 2;
                            break;
                        case 'u':
                        case 'x':
                            if (i + 6 <= s.Length)
                            {
                                buf.Append(Hex2Char(s.Substring(i + 2, 4)));
                                i += 6;
                                break;
                            }
                            else
                            {
                                parser.SemErr("bad escape sequence in string or character");
                                i = s.Length;
                                break;
                            }
                        default:
                            parser.SemErr("bad escape sequence in string or character");
                            i += 2;
                            break;
                    }
                }
                else
                {
                    buf.Append(s[i]);
                    i++;
                }
            }
            return buf.ToString();
        }

        public string Escape(string s)
        {
            StringBuilder buf = new StringBuilder();
            foreach (char ch in s)
            {
                switch (ch)
                {
                    case '\\':
                        buf.Append("\\\\");
                        break;
                    case '\'':
                        buf.Append("\\'");
                        break;
                    case '\"':
                        buf.Append("\\\"");
                        break;
                    case '\t':
                        buf.Append("\\t");
                        break;
                    case '\r':
                        buf.Append("\\r");
                        break;
                    case '\n':
                        buf.Append("\\n");
                        break;
                    default:
                        if (ch < ' ' || ch > '\u007f')
                            buf.Append(Char2Hex(ch));
                        else
                            buf.Append(ch);
                        break;
                }
            }
            return buf.ToString();
        }

        //---------------------------------------------------------------------
        //  Grammar checks
        //---------------------------------------------------------------------

        public bool GrammarOk()
        {
            bool ok = NtsComplete() && AllNtReached() && NoCircularProductions() && AllNtToTerm();
            if (ok)
            {
                CheckResolvers();
                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;
            }
        }

        void GetSingles(Node p, ArrayList singles)
        {
            if (p == null)
                return; // end of graph
            if (p.typ == Node.nt)
            {
                if (p.up || DelGraph(p.next))
                    singles.Add(p.sym);
            }
            else if (p.typ == Node.alt || p.typ == Node.iter || p.typ == Node.opt)
            {
                if (p.up || DelGraph(p.next))
                {
                    GetSingles(p.sub, singles);
                    if (p.typ == Node.alt)
                        GetSingles(p.down, singles);
                }
            }
            if (!p.up && DelNode(p))
                GetSingles(p.next, singles);
        }

        public bool NoCircularProductions()
        {
            bool ok,
                changed,
                onLeftSide,
                onRightSide;
            ArrayList list = new ArrayList();
            foreach (Symbol sym in 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.SemErr("  " + n.left.name + " --> " + n.right.name);
            }
            return ok;
        }

        //--------------- check for LL(1) errors ----------------------

        void LL1Error(int cond, Symbol sym)
        {
            string s = "  LL1 warning in " + curSy.name + ": ";
            if (sym != null)
                s += sym.name + " is ";
            switch (cond)
            {
                case 1:
                    s += "start of several alternatives";
                    break;
                case 2:
                    s += "start & successor of deletable structure";
                    break;
                case 3:
                    s += "an ANY node that matches no symbol";
                    break;
                case 4:
                    s += "contents of [...] or {...} must not be deletable";
                    break;
            }
            errors.Warning(s);
        }

        void CheckOverlap(BitArray s1, BitArray s2, int cond)
        {
            foreach (Symbol sym in terminals)
            {
                if (s1[sym.n] && s2[sym.n])
                    LL1Error(cond, sym);
            }
        }

        void CheckAlts(Node p)
        {
            BitArray s1,
                s2;
            while (p != null)
            {
                if (p.typ == Node.alt)
                {
                    Node q = p;
                    s1 = new BitArray(terminals.Count);
                    while (q != null)
                    { // for all alternatives
                        s2 = Expected0(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)
                {
                    if (DelSubGraph(p.sub))
                        LL1Error(4, null); // e.g. [[...]]
                    else
                    {
                        s1 = Expected0(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;
            }
        }

        public void CheckLL1()
        {
            foreach (Symbol sym in nonterminals)
            {
                curSy = sym;
                CheckAlts(curSy.graph);
            }
        }

        //------------- check if resolvers are legal  --------------------

        void ResErr(Node p, string msg)
        {
            errors.Warning(p.line, p.pos.col, msg);
        }

        void CheckRes(Node p, bool rslvAllowed)
        {
            while (p != null)
            {
                switch (p.typ)
                {
                    case Node.alt:
                        BitArray expected = new BitArray(terminals.Count);
                        for (Node q = p; q != null; q = q.down)
                            expected.Or(Expected0(q.sub, curSy));
                        BitArray soFar = new BitArray(terminals.Count);
                        for (Node q = p; q != null; q = q.down)
                        {
                            if (q.sub.typ == Node.rslv)
                            {
                                BitArray fs = Expected(q.sub.next, curSy);
                                if (Sets.Intersect(fs, soFar))
                                    ResErr(
                                        q.sub,
                                        "Warning: Resolver will never be evaluated. "
                                            + "Place it at previous conflicting alternative."
                                    );
                                if (!Sets.Intersect(fs, expected))
                                    ResErr(
                                        q.sub,
                                        "Warning: Misplaced resolver: no LL(1) conflict."
                                    );
                            }
                            else
                                soFar.Or(Expected(q.sub, curSy));
                            CheckRes(q.sub, true);
                        }
                        break;
                    case Node.iter:
                    case Node.opt:
                        if (p.sub.typ == Node.rslv)
                        {
                            BitArray fs = First(p.sub.next);
                            BitArray fsNext = Expected(p.next, curSy);
                            if (!Sets.Intersect(fs, fsNext))
                                ResErr(p.sub, "Warning: Misplaced resolver: no LL(1) conflict.");
                        }
                        CheckRes(p.sub, true);
                        break;
                    case Node.rslv:
                        if (!rslvAllowed)
                            ResErr(p, "Warning: Misplaced resolver: no alternative.");
                        break;
                }
                if (p.up)
                    break;
                p = p.next;
                rslvAllowed = false;
            }
        }

        public void CheckResolvers()
        {
            foreach (Symbol sym in nonterminals)
            {
                curSy = sym;
                CheckRes(curSy.graph, false);
            }
        }

        //------------- check if every nts has a production --------------------

        public bool NtsComplete()
        {
            bool complete = true;
            foreach (Symbol sym in nonterminals)
            {
                if (sym.graph == null)
                {
                    complete = false;
                    errors.SemErr("  No production for " + sym.name);
                }
            }
            return complete;
        }

        //-------------- check if every nts can be reached  -----------------

        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 bool AllNtReached()
        {
            bool ok = true;
            visited = new BitArray(nonterminals.Count);
            visited[gramSy.n] = true;
            MarkReachedNts(gramSy.graph);
            foreach (Symbol sym in nonterminals)
            {
                if (!visited[sym.n])
                {
                    ok = false;
                    errors.SemErr("  " + sym.name + " cannot be reached");
                }
            }
            return ok;
        }

        //--------- check if every nts can be derived to terminals  ------------

        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 bool AllNtToTerm()
        {
            bool changed,
                ok = true;
            BitArray mark = new BitArray(nonterminals.Count);
            // a nonterminal is marked if it can be derived to terminal symbols
            do
            {
                changed = false;
                foreach (Symbol sym in nonterminals)
                    if (!mark[sym.n] && IsTerm(sym.graph, mark))
                    {
                        mark[sym.n] = true;
                        changed = true;
                    }
            } while (changed);
            foreach (Symbol sym in nonterminals)
                if (!mark[sym.n])
                {
                    ok = false;
                    errors.SemErr("  " + sym.name + " cannot be derived to terminals");
                }
            return ok;
        }

        //---------------------------------------------------------------------
        //  Cross reference list
        //---------------------------------------------------------------------

        public void XRef()
        {
            SortedList xref = new SortedList();
            // collect lines where symbols have been defined
            foreach (Symbol sym in nonterminals)
            {
                ArrayList list = (ArrayList)xref[sym];
                if (list == null)
                {
                    list = new ArrayList();
                    xref[sym] = list;
                }
                list.Add(-sym.line);
            }
            // collect lines where symbols have been referenced
            foreach (Node n in nodes)
            {
                if (n.typ == Node.t || n.typ == Node.wt || n.typ == Node.nt)
                {
                    ArrayList list = (ArrayList)xref[n.sym];
                    if (list == null)
                    {
                        list = new ArrayList();
                        xref[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 xref.Keys)
            {
                trace.Write("  {0,-12}", Name(sym.name));
                ArrayList list = (ArrayList)xref[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 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;
                    }
            }
        }
    } // end Tab
} // end namespace
