Tab.ts

/*-------------------------------------------------------------------------
Compiler Generator Coco/R,
Copyright (c) 1990, 2004 Hanspeter Moessenboeck, University of Linz
extended by M. Loeberbauer & A. Woess, University of Linz
ported from C# to Java by Wolfgang Ahorner
with improvements by Pat Terry, Rhodes University
ported from Java to Typescript by Stefan Kempinger, University of Linz

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.
------------------------------------------------------------------------*/

import {CharSet, State} from "./DFA";
import {Trace} from "./Trace";
import {Errors, Parser} from "./Parser";
import BitSet from "bitset";


export class Position {
    public readonly beg: number;
    public readonly end: number;
    public readonly col: number;

    constructor(beg: number, end: number, col: number) {
        this.beg = beg;
        this.end = end;
        this.col = col;
    }
}

export class SymInfo {
    name: string;
    kind: number;
}

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

    public n: number;           // symbol number
    public typ: number;         // t, nt, pr, unknown, rslv /* ML 29_11_2002 slv added */ /* AW slv --> rslv */
    public name: string;        // symbol name
    public graph: Node_;       // nt: to first node_ of syntax graph
    //in java this is not there because this works because uninitialized int is 0, but in js it is undefined
    public tokenKind: number = Symbol.fixedToken;   // t:  token kind (fixedToken, classToken, ...)
    public deletable: boolean;   // nt: true if nonterminal is deletable
    public firstReady: boolean;  // nt: true if terminal start symbols have already been computed
    public first: BitSet;       // nt: terminal start symbols
    public follow: BitSet;      // nt: terminal followers
    public nts: BitSet;         // nt: nonterminals whose followers have to be added to this sym
    public line: number;        // source text line number of item in this node_
    public attrPos: Position;     // nt: position of attributes in source text (or undefined)
    public semPos: Position;      // pr: pos of semantic action in source text (or undefined)
                                  // nt: pos of local declarations in source text (or undefined)
    public retType: string;     // AH - nt: Type of output attribute (or undefined)
    public retVar: string;      // AH - nt: Name of output attribute (or undefined)

    constructor(typ: number, name: string, line: number) {
        this.typ = typ;
        this.name = name;
        this.line = line;
    }
}


export class Node_ {
    // constants for node_ kinds
    public static readonly t = 1;  // terminal symbol
    public static readonly pr = 2;  // pragma
    public static readonly nt = 3;  // nonterminal symbol
    public static readonly clas = 4;  // character class
    public static readonly chr = 5;  // character
    public static readonly wt = 6;  // weak terminal symbol
    public static readonly any = 7;  //
    public static readonly eps = 8;  // empty
    public static readonly sync = 9;  // synchronization symbol
    public static readonly sem = 10;  // semantic action: (. .)
    public static readonly alt = 11;  // alternative: |
    public static readonly iter = 12;  // iteration: { }
    public static readonly opt = 13;  // option: [ ]
    public static readonly rslv = 14;  // resolver expr  /* ML */ /* AW 03-01-13 renamed slv --> rslv */

    public static readonly normalTrans = 0;		// transition codes
    public static readonly contextTrans = 1;

    public n: number;				// node_ number
    public typ: number;			// t, nt, wt, chr, clas, any, eps, sem, sync, alt, iter, opt, rslv
    public next: Node_;			// to successor node_
    public down: Node_;			// alt: to next alternative
    public sub: Node_;			// alt, iter, opt: to first node_ of substructure
    public up: boolean;				// true: "next" leads to successor in enclosing structure
    public sym: Symbol;			// nt, t, wt: symbol represented by this node_
    public val: number;			// chr:  ordinal character value
    // clas: index of character class
    public code: number;			// chr, clas: transition code
    public set: BitSet;				// any, sync: the set represented by this node_
    public pos: Position;			// nt, t, wt: pos of actual attributes
    // sem:       pos of semantic action in source text
    public line: number;			// source text line number of item in this node_
    public state: State;		// DFA state corresponding to this node_
    // (only used in DFA.ConvertToStates)
    public retVar: string;			// AH 20040206 - nt: name of output attribute (or undefined)

    constructor(typ: number, sym: Symbol, line: number) {
        this.typ = typ;
        this.sym = sym;
        this.line = line;
    }
}

export class Graph {
    public l: Node_;	// left end of graph = head
    public r: Node_;// right end of graph = list of node_s to be linked to successor graph

    constructor();
    constructor(left: Node_, right: Node_);
    constructor(p: Node_);

    //INTERNAL USE ONLY, .ts can only overload this way
    constructor(p?: Node_, left?: Node_, right?: Node_) {
        if (p != undefined) {
            this.l = p;
            this.r = p;
        } else if (left != undefined) {
            this.l = left;
            this.r = right;
        } else {

        }
    }
}


//=====================================================================
// Sets
//=====================================================================
export class Sets {
    public static Elements(s: BitSet): number {
        return s.cardinality();
    }

    public static Equals(a: BitSet, b: BitSet): boolean {
        return a.equals(b);
    }

    public static Intersect(a: BitSet, b: BitSet): boolean {// a * b != {}
        return !a.and(b).isEmpty();
    }

    public static Subtract(a: BitSet, b: BitSet) { // a = a - b
        let c = b.clone();
        //a.and(c.not());
        c.flip();	// c.not
        return a.and(c);
    }
}


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

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

    constructor(name: string, s: CharSet) {
        this.name = name;
        this.set = s;
    }
}

export class CNode {	// node of list for finding circular productions
    public left: Symbol;
    public right: Symbol;

    constructor(l: Symbol, r: Symbol) {
        this.left = l;
        this.right = r;
    }
}

export class Tab {
    public semDeclPos: Position;        // position of global semantic declarations
    public ignored: CharSet;            // characters ignored by the scanner
    public ddt: boolean[] = [];              // debug and test switches
    public gramSy: Symbol;              // root nonterminal; filled by ATG
    public eofSy: Symbol;               // end of file symbol
    public noSym: Symbol;               // used in case of an error
    public allSyncSets: BitSet;         // union of all synchronisation sets
    public literals: Symbol[];         // symbols that are used as literals

    public srcName: string;             // name of the atg file (including path)
    public srcDir: string;              // directory path of the atg file
    public nsName: string;              // package name for generated files
    public frameDir: string;            // directory containing the frame files
    public outDir: string;              // directory for generated files
    public checkEOF = true;            // should coco generate a check for EOF at
                                       // the end of Parser.Parse():

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

    parser: Parser;                     // other Coco objects
    trace: Trace;
    errors: Errors;

    public nodes: Node_[] = [];
    public nTyp = ["    ", "t   ", "pr  ", "nt  ", "clas", "chr ", "wt  ", "any ", "eps ",  /* AW 03-01-14 nTyp[0]: " " --> "    " */
        "sync", "sem ", "alt ", "iter", "opt ", "rslv"];
    dummyNode: Node_;

    public terminals = [];
    public pragmas = [];
    public nonterminals: Symbol[] = [];

    tKind = ["fixedToken", "classToken", "litToken", "classLitToken"];

    public classes = [];
    public dummyName = 'A';

    constructor(parser: Parser) {
        this.parser = parser;
        this.trace = parser.trace;
        this.errors = parser.errors;
        this.eofSy = this.NewSym(Node_.t, "EOF", 0);
        this.dummyNode = this.NewNode(Node_.eps, undefined, 0);
        this.literals = [];
    }

    NewSym(typ: number, name: string, line: number): Symbol {
        if (name.length == 2 && name.charAt(0) == '"') {
            this.parser.SemErr("empty token not allowed");
            name = "???";
        }
        let sym = new Symbol(typ, name, line);
        switch (typ) {
            case Node_.t:
                sym.n = this.terminals.length;
                this.terminals.push(sym);
                break;
            case Node_.pr:
                this.pragmas.push(sym);
                break;
            case Node_.nt:
                sym.n = this.nonterminals.length;
                this.nonterminals.push(sym);
                break;
        }
        return sym;
    }

    public FindSym(name: string): Symbol {
        let s: Symbol;
        //foreach (Symbol s in terminals)
        for (let i = 0; i < this.terminals.length; i++) {
            s = this.terminals[i];
            if (s.name === name) return s;
        }
        //foreach (Symbol s in nonterminals)
        for (let i = 0; i < this.nonterminals.length; i++) {
            s = this.nonterminals[i];
            if (s.name === name) return s;
        }
        return undefined;
    }

    Num(p: Node_): number {
        if (p == undefined) return 0; else return p.n;
    }

    PrintSym(sym: Symbol) {
        this.trace.Write(sym.n.toString(), 3);
        this.trace.Write(" ");
        this.trace.Write(this.Name(sym.name), -14);
        this.trace.Write(" ");
        this.trace.Write((this.nTyp)[sym.typ], 2);
        if (sym.attrPos == undefined) this.trace.Write(" false "); else this.trace.Write(" true  ");
        if (sym.typ == Node_.nt) {
            this.trace.Write(this.Num(sym.graph).toString(), 5);
            if (sym.deletable) this.trace.Write(" true  "); else this.trace.Write(" false ");
        } else
            this.trace.Write("            ");
        this.trace.Write(sym.line.toString(), 5);
        this.trace.WriteLine(" " + this.tKind[sym.tokenKind]);
    }

    public PrintSymbolTable(s?: string) {
        this.trace.WriteLine("Symbol Table:");
        this.trace.WriteLine("------------");
        this.trace.WriteLine();
        this.trace.WriteLine(" nr name           typ  hasAt graph  del   line tokenKind");
        //foreach (Symbol sym in Symbol.terminals)
        for (let i = 0; i < this.terminals.length; i++) {
            this.PrintSym(this.terminals[i]);
        }
        //foreach (Symbol sym in Symbol.pragmas)
        for (let i = 0; i < this.pragmas.length; i++) {
            this.PrintSym(this.pragmas[i]);
        }
        //foreach (Symbol sym in Symbol.nonterminals)
        for (let i = 0; i < this.nonterminals.length; i++) {
            this.PrintSym(this.nonterminals[i]);
        }
        this.trace.WriteLine();
        this.trace.WriteLine("Literal Tokens:");
        this.trace.WriteLine("--------------");
        //foreach (DictionaryEntry e in literals) {
        for (let literalsData in this.literals) {
            this.trace.WriteLine("_" + this.literals[literalsData].name + " = " + literalsData + ".");
        }
        this.trace.WriteLine();
    }

    public PrintSet(s: BitSet, indent: number) {
        let col = indent;
        //foreach (Symbol sym in Symbol.terminals) {
        for (let i = 0; i < this.terminals.length; i++) {
            let sym = this.terminals[i];
            if (s.get(sym.n)) {
                let len = sym.name.length;
                if (col + len >= 80) {
                    this.trace.WriteLine();
                    for (col = 1; col < indent; col++) this.trace.Write(" ");
                }
                this.trace.Write(sym.name + " ");
                col += len + 1;
            }
        }
        if (col == indent) this.trace.Write("-- empty set --");
        this.trace.WriteLine();
    }

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

    public NewNode(typ: number, sym: Symbol, line: number): Node_

    public NewNode(typ: number, sub: Node_): Node_

    public NewNode(typ: number, val: number, line: number): Node_

    // public NewNode(typ: number, sym?: Symbol, val?: number, line?: number, sub?: Node_): Node_ {
    public NewNode(typ: number, arg2?, arg3?): Node_ {
        let node: Node_;

        if (typeof arg2 === "number") {
            node = this.NewNode(typ, undefined, arg3);
            node.val = arg2;
        } else if (arg3 != undefined) {
            node = new Node_(typ, arg2, arg3);
            node.n = this.nodes.length;
            this.nodes.push(node);
        } else {
            node = this.NewNode(typ, undefined, 0);
            node.sub = arg2;
        }
        return node;
    }

    public MakeFirstAlt(g: Graph) {
        g.l = this.NewNode(Node_.alt, g.l);
        g.l.line = g.l.sub.line;
        g.r.up = true;
        g.l.next = g.r;
        g.r = g.l;
    }

// The result will be in g1
    public MakeAlternative(g1: Graph, g2: Graph) {
        g2.l = this.NewNode(Node_.alt, g2.l);
        g2.l.line = g2.l.sub.line;
        g2.l.up = true;
        g2.r.up = true;
        let p = g1.l;
        while (p.down != undefined) p = p.down;
        p.down = g2.l;
        p = g1.r;
        while (p.next != undefined) p = p.next;
        // append alternative to g1 end list
        p.next = g2.l;
        // append g2 end list to g1 end list
        g2.l.next = g2.r;
    }

    // The result will be in g1
    public MakeSequence(g1: Graph, g2: Graph) {
        let p = g1.r.next;
        g1.r.next = g2.l; // link head node_
        while (p != undefined) {  // link substructure
            let q = p.next;
            p.next = g2.l;
            p = q;
        }
        g1.r = g2.r;
    }

    public MakeIteration(g: Graph) {
        g.l = this.NewNode(Node_.iter, g.l);
        g.r.up = true;
        let p = g.r;
        g.r = g.l;
        while (p != undefined) {
            let q = p.next;
            p.next = g.l;
            p = q;
        }
    }

    public MakeOption(g: Graph) {
        g.l = this.NewNode(Node_.opt, g.l);
        g.r.up = true;
        g.l.next = g.r;
        g.r = g.l;
    }

    public Finish(g: Graph) {
        let p = g.r;
        while (p != undefined) {
            let q = p.next;
            p.next = undefined;
            p = q;
        }
    }

    public DeleteNodes() {
        this.nodes = [];
        this.dummyNode = this.NewNode(Node_.eps, undefined, 0);
    }

    public StrToGraph(str: string): Graph {
        let s = this.Unescape(str.substring(1, str.length - 1));
        if (s.length == 0) this.parser.SemErr("empty token not allowed");
        let g = new Graph();
        g.r = this.dummyNode;
        for (let i = 0; i < s.length; i++) {
            let p = this.NewNode(Node_.chr, s.charCodeAt(i), 0);
            g.r.next = p;
            g.r = p;
        }
        g.l = this.dummyNode.next;
        this.dummyNode.next = undefined;
        return g;
    }

    public SetContextTrans(p: Node_) { // set transition code in the graph rooted at p
        while (p != undefined) {
            if (p.typ == Node_.chr || p.typ == Node_.clas) {
                p.code = Node_.contextTrans;
            } else if (p.typ == Node_.opt || p.typ == Node_.iter) {
                this.SetContextTrans(p.sub);
            } else if (p.typ == Node_.alt) {
                this.SetContextTrans(p.sub);
                this.SetContextTrans(p.down);
            }
            if (p.up) break;
            p = p.next;
        }
    }

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

    public DelGraph(p: Node_): boolean {
        return p == undefined || this.DelNode(p) && this.DelGraph(p.next);
    }

    public DelSubGraph(p: Node_): boolean {
        return p == undefined || this.DelNode(p) && (p.up || this.DelSubGraph(p.next));
    }

    public DelNode(p: Node_): boolean {
        if (p.typ == Node_.nt) return p.sym.deletable;
        else if (p.typ == Node_.alt) return this.DelSubGraph(p.sub) || p.down != undefined && this.DelSubGraph(p.down);
        else return p.typ == Node_.iter || p.typ == Node_.opt || p.typ == Node_.sem
                || p.typ == Node_.eps || p.typ == Node_.sync || p.typ == Node_.rslv;
    }

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

    Ptr(p: Node_, up: boolean): string {
        let ptr = (p == undefined) ? "0" : p.n.toString();
        return (up) ? ("-" + ptr) : ptr;
    }

    Pos(pos: Position): string {
        if (pos == undefined) return "     ";
        else return this.trace.formatString(pos.beg.toString(), 5);
    }

    public Name(name: string): string {
        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 PrintNodes() {
        this.trace.WriteLine("Graph node_s:");
        this.trace.WriteLine("----------------------------------------------------");
        this.trace.WriteLine("   n type name          next  down   sub   pos  line");
        this.trace.WriteLine("                               val  code");
        this.trace.WriteLine("----------------------------------------------------");
        //foreach (Node_ p in nodes) {
        for (let i = 0; i < this.nodes.length; i++) {
            let p = this.nodes[i];
            this.trace.Write(p.n.toString(), 4);
            this.trace.Write(" " + (this.nTyp)[p.typ] + " ");
            if (p.sym != undefined) {
                this.trace.Write(this.Name(p.sym.name), 12);
                this.trace.Write(" ");
            } else if (p.typ == Node_.clas) {
                let c = this.classes[p.val];
                this.trace.Write(this.Name(c.name), 12);
                this.trace.Write(" ");
            } else this.trace.Write("             ");
            this.trace.Write(this.Ptr(p.next, p.up), 5);
            this.trace.Write(" ");
            switch (p.typ) {
                case Node_.t:
                case Node_.nt:
                case Node_.wt:
                    this.trace.Write("             ");
                    this.trace.Write(this.Pos(p.pos), 5);
                    break;
                case Node_.chr:
                    this.trace.Write(p.val.toString(), 5);
                    this.trace.Write(" ");
                    this.trace.Write(p.code.toString(), 5);
                    this.trace.Write("       ");
                    break;
                case Node_.clas:
                    this.trace.Write("      ");
                    this.trace.Write(p.code.toString(), 5);
                    this.trace.Write("       ");
                    break;
                case Node_.alt:
                case Node_.iter:
                case Node_.opt:
                    this.trace.Write(this.Ptr(p.down, false), 5);
                    this.trace.Write(" ");
                    this.trace.Write(this.Ptr(p.sub, false), 5);
                    this.trace.Write("       ");
                    break;
                case Node_.sem:
                    this.trace.Write("             ");
                    this.trace.Write(this.Pos(p.pos), 5);
                    break;
                case Node_.eps:
                case Node_.any:
                case Node_.sync:
                    this.trace.Write("                  ");
                    break;
            }
            this.trace.WriteLine(p.line.toString(), 5);
        }
        this.trace.WriteLine();
    }

    //---------------------------------------------------------------------
    //  character class management
    //---------------------------------------------------------------------


    public NewCharClass(name: string, s: CharSet): CharClass {
        if (name == "#") {
            name = "#" + this.dummyName;
            this.dummyName = String.fromCharCode(this.dummyName.charCodeAt(0) + 1)
        }
        let c = new CharClass(name, s);
        c.n = this.classes.length;
        this.classes.push(c);
        return c;
    }

    public FindCharClass(name: string): CharClass

    public FindCharClass(s: CharSet): CharClass

    public FindCharClass(arg0): CharClass {

        if (typeof arg0 === "string") {
            //foreach (CharClass c in classes)
            for (let i = 0; i < this.classes.length; i++) {
                let c = this.classes[i];
                if (c.name === arg0) return c;
            }
        } else {
            for (let i = 0; i < this.classes.length; i++) {
                let c = this.classes[i];
                if (arg0.Equals(c.set)) return c;
            }
        }

        return undefined;
    }

    public CharClassSet(i: number): CharSet {
        return this.classes[i].set;
    }

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

    Ch(ch: number): string {
        if (ch < ' '.charCodeAt(0) || ch >= 127 || ch == '\''.charCodeAt(0) || ch == '\\'.charCodeAt(0)) return ch.toString();
        else return ("'" + String.fromCharCode(ch) + "'");
    }

    WriteCharSet(s: CharSet) {
        for (let r = s.head; r != undefined; r = r.next) {
            if (r.from < r.to) {
                this.trace.Write(this.Ch(r.from) + ".." + this.Ch(r.to) + " ");
            } else {
                this.trace.Write(this.Ch(r.from) + " ");
            }
        }
    }

    public WriteCharClasses() {
        //foreach (CharClass c in classes) {
        for (let i = 0; i < this.classes.length; i++) {
            let c = this.classes[i];
            this.trace.Write(c.name + ": ", -10);
            this.WriteCharSet(c.set);
            this.trace.WriteLine();
        }
        this.trace.WriteLine();
    }

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

// Computes the first set for the graph rooted at p
    First0(p: Node_, mark: BitSet): BitSet {
        // let fs = new BitSet(this.terminals.length);
        let fs = new BitSet();
        while (p != undefined && !mark.get(p.n)) {
            mark.set(p.n);
            switch (p.typ) {
                case Node_.nt: {
                    if (p.sym.firstReady)
                        fs = fs.or(p.sym.first);
                    else
                        fs = fs.or(this.First0(p.sym.graph, mark));
                    break;
                }
                case Node_.t:
                case Node_.wt: {
                    fs.set(p.sym.n);
                    break;
                }
                case Node_.any: {
                    fs = fs.or(p.set);
                    break;
                }
                case Node_.alt: {
                    fs = fs.or(this.First0(p.sub, mark));
                    fs = fs.or(this.First0(p.down, mark));
                    break;
                }
                case Node_.iter:
                case Node_.opt: {
                    fs = fs.or(this.First0(p.sub, mark));
                    break;
                }
            }
            if (!this.DelNode(p)) break;
            p = p.next;
        }
        return fs;
    }

    public First(p: Node_): BitSet {
        // let fs = this.First0(p, new BitSet(this.nodes.length));
        let fs = this.First0(p, new BitSet());
        if ((this.ddt)[3]) {
            this.trace.WriteLine();
            if (p != undefined) this.trace.WriteLine("First: node = " + p.n);
            else this.trace.WriteLine("First: node = undefined");
            this.PrintSet(fs, 0);
        }
        return fs;
    }


    CompFirstSets() {
        let sym: Symbol;
        //foreach (Symbol sym in Symbol.nonterminals) {
        for (let i = 0; i < this.nonterminals.length; i++) {
            sym = this.nonterminals[i];
            // sym.first = new BitSet(this.terminals.length);
            sym.first = new BitSet();
            sym.firstReady = false;
        }
        //foreach (Symbol sym in Symbol.nonterminals) {
        for (let i = 0; i < this.nonterminals.length; i++) {
            sym = this.nonterminals[i];
            sym.first = this.First(sym.graph);
            sym.firstReady = true;
        }
    }

    CompFollow(p: Node_) {
        while (p != undefined && !this.visited.get(p.n)) {
            this.visited.set(p.n);
            if (p.typ == Node_.nt) {
                let s = this.First(p.next);
                p.sym.follow = p.sym.follow.or(s);
                if (this.DelGraph(p.next))
                    p.sym.nts.set(this.curSy.n);
            } else if (p.typ == Node_.opt || p.typ == Node_.iter) {
                this.CompFollow(p.sub);
            } else if (p.typ == Node_.alt) {
                this.CompFollow(p.sub);
                this.CompFollow(p.down);
            }
            p = p.next;
        }
    }

    Complete(sym: Symbol) {
        if (!this.visited.get(sym.n)) {
            this.visited.set(sym.n);
            //foreach (Symbol s in Symbol.nonterminals) {
            for (let i = 0; i < this.nonterminals.length; i++) {
                let s = this.nonterminals[i];
                if (sym.nts.get(s.n)) {
                    this.Complete(s);
                    sym.follow = sym.follow.or(s.follow);
                    if (sym == this.curSy) sym.nts.clear(s.n);
                }
            }
        }
    }

    CompFollowSets() {
        let nNonterminals = this.nonterminals.length;
        let nTerminals = this.terminals.length;

        // foreach (Symbol sym in Symbol.nonterminals) {
        for (const sym of this.nonterminals) {
            // sym.follow = new BitSet(nTerminals);
            // sym.nts = new BitSet(nNonterminals);
            sym.follow = new BitSet();
            sym.nts = new BitSet();
        }

        this.gramSy.follow.set(this.eofSy.n);
        // let visited = new BitSet(this.nodes.length);
        this.visited = new BitSet();

        // foreach (Symbol sym in Symbol.nonterminals) {
        for (const curSy of this.nonterminals) {
            // get direct successors of nonterminals
            this.curSy = curSy;
            this.CompFollow(curSy.graph);
        }

        // foreach (Symbol sym in Symbol.nonterminals) {
        for (let curSy of this.nonterminals) {
            // add indirect successors to followers
            this.curSy = curSy;
            // visited = new BitSet(nNonterminals);
            this.visited = new BitSet();
            this.Complete(curSy);
        }
    }

    LeadingAny(p: Node_): Node_ {
        if (p == undefined) return undefined;
        let a: Node_ = undefined;
        if (p.typ == Node_.any) a = p;
        else if (p.typ == Node_.alt) {
            a = this.LeadingAny(p.sub);
            if (a == undefined) a = this.LeadingAny(p.down);
        } else if (p.typ == Node_.opt || p.typ == Node_.iter) a = this.LeadingAny(p.sub);
        if (a == undefined && this.DelNode(p) && !p.up) a = this.LeadingAny(p.next);
        return a;
    }

    FindAS(p: Node_) { // find ANY sets
        let a: Node_;
        while (p != undefined) {
            if (p.typ == Node_.opt || p.typ == Node_.iter) {
                this.FindAS(p.sub);
                a = this.LeadingAny(p.sub);
                if (a != undefined) a.set = Sets.Subtract(a.set, this.First(p.next));
            } else if (p.typ == Node_.alt) {
                // let s1 = new BitSet(this.terminals.length);
                let s1 = new BitSet();
                let q = p;
                while (q != undefined) {
                    this.FindAS(q.sub);
                    a = this.LeadingAny(q.sub);
                    if (a != undefined) {
                        let h = this.First(q.down);
                        h = h.or(s1);
                        a.set = Sets.Subtract(a.set, h);
                    } else
                        s1 = s1.or(this.First(q.sub));
                    q = q.down;
                }
            }

            // Remove alternative terminals before ANY, in the following
            // examples a and b must be removed from the ANY set:
            // [a] ANY, or {a|b} ANY, or [a][b] ANY, or (a|) ANY, or
            // A = [a]. A ANY
            if (this.DelNode(p)) {
                a = this.LeadingAny(p.next);
                if (a != undefined) {
                    let q = (p.typ == Node_.nt) ? p.sym.graph : p.sub;
                    a.set = Sets.Subtract(a.set, this.First(q));
                }
            }

            if (p.up) break;
            p = p.next;
        }
    }

    CompAnySets() {
        let sym: Symbol;
        //foreach (Symbol sym in Symbol.nonterminals)
        for (let i = 0; i < this.nonterminals.length; i++) {
            sym = this.nonterminals[i];
            this.FindAS(sym.graph);
        }
    }

    public Expected(p: Node_, curSy: Symbol): BitSet {
        let s = this.First(p);
        if (this.DelGraph(p))
            s = s.or(curSy.follow);
        return s;
    }

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

    CompSync(p: Node_) {
        while (p != undefined && !this.visited.get(p.n)) {
            this.visited.set(p.n);
            if (p.typ == Node_.sync) {
                let s = this.Expected(p.next, this.curSy);
                s.set(this.eofSy.n);
                this.allSyncSets = this.allSyncSets.or(s);
                p.set = s;
            } else if (p.typ == Node_.alt) {
                this.CompSync(p.sub);
                this.CompSync(p.down);
            } else if (p.typ == Node_.opt || p.typ == Node_.iter)
                this.CompSync(p.sub);
            p = p.next;
        }
    }

    CompSyncSets() {
        // this.allSyncSets = new BitSet(this.terminals.length);
        this.allSyncSets = new BitSet();
        this.allSyncSets.set(this.eofSy.n);
        this.visited = new BitSet();
        //foreach (Symbol sym in Symbol.nonterminals) {
        for (let i = 0; i < this.nonterminals.length; i++) {
            this.curSy = this.nonterminals[i];
            this.CompSync(this.curSy.graph);
        }
    }

    public SetupAnys() {
        //foreach (Node p in Node.nodes)
        for (let i = 0; i < this.nodes.length; i++) {
            let p = this.nodes[i];
            if (p.typ == Node_.any) {
                // p.set = new BitSet(this.terminals.length);
                p.set = new BitSet();
                p.set.setRange(0, this.terminals.length);
                p.set.clear(this.eofSy.n);
            }
        }
    }

    public CompDeletableSymbols() {
        let changed: boolean;
        let sym: Symbol;
        do {
            changed = false;
            //foreach (Symbol sym in Symbol.nonterminals)
            for (let i = 0; i < this.nonterminals.length; i++) {
                sym = this.nonterminals[i];
                if (!sym.deletable && sym.graph != undefined && this.DelGraph(sym.graph)) {
                    sym.deletable = true;
                    changed = true;
                }
            }
        } while (changed);
        //foreach (Symbol sym in Symbol.nonterminals)
        for (let i = 0; i < this.nonterminals.length; i++) {
            sym = this.nonterminals[i];
            if (sym.deletable) this.errors.Warning("  " + sym.name + " deletable");
        }
    }

    public RenumberPragmas() {
        let n = this.terminals.length;
        //foreach (Symbol sym in Symbol.pragmas)
        for (let i = 0; i < this.pragmas.length; i++) {
            let sym = this.pragmas[i];
            sym.n = n++;
        }
    }

    public CompSymbolSets() {
        this.CompDeletableSymbols();
        this.CompFirstSets();
        this.CompAnySets();
        this.CompFollowSets();
        this.CompSyncSets();
        if ((this.ddt)[1]) {
            this.trace.WriteLine();
            this.trace.WriteLine("First & follow symbols:");
            this.trace.WriteLine("----------------------");
            this.trace.WriteLine();
            let sym: Symbol;
            //foreach (Symbol sym in Symbol.nonterminals) {
            for (let i = 0; i < this.nonterminals.length; i++) {
                sym = this.nonterminals[i];
                this.trace.WriteLine(sym.name);
                this.trace.Write("first:   ");
                this.PrintSet(sym.first, 10);
                this.trace.Write("follow:  ");
                this.PrintSet(sym.follow, 10);
                this.trace.WriteLine();
            }
        }
        if ((this.ddt)[4]) {
            this.trace.WriteLine();
            this.trace.WriteLine("ANY and SYNC sets:");
            this.trace.WriteLine("-----------------");
            //foreach (Node p in Node.nodes)
            for (let i = 0; i < this.nodes.length; i++) {
                let p = this.nodes[i];
                if (p.typ == Node_.any || p.typ == Node_.sync) {
                    this.trace.Write("Line: ");
                    this.trace.WriteLine(p.line.toString(), 4);
                    this.trace.Write("Node: ");
                    this.trace.Write(p.n.toString(), 4);
                    this.trace.Write(" ");
                    this.trace.Write((this.nTyp)[p.typ], 4);
                    this.trace.Write(": ");
                    this.PrintSet(p.set, 11);
                }
            }
        }
    }

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

    Hex2Char(s: string): string {
        let val = 0;
        for (let i = 0; i < s.length; i++) {
            let ch = s.charAt(i);
            if ('0' <= ch && ch <= '9') val = 16 * val + (ch.charCodeAt(0) - '0'.charCodeAt(0));
            else if ('a' <= ch && ch <= 'f') val = 16 * val + (10 + ch.charCodeAt(0) - 'a'.charCodeAt(0));
            else if ('A' <= ch && ch <= 'F') val = 16 * val + (10 + ch.charCodeAt(0) - 'A'.charCodeAt(0));
            else this.parser.SemErr("bad escape sequence in string or character");
        }
        //TODO: maybe reimplement this
// if (val > Character.MAX_VALUE) /* pdt */
//     this.parser.SemErr("bad escape sequence in string or character");
        return String.fromCharCode(val);
    }

    Char2Hex(ch: string): string {
        let hex = ch.charCodeAt(0).toString(16);
        for (let i = hex.length; i < 4; i++) hex = "0" + hex;
        return "\\u" + hex;
    }

    public Unescape(s: string): string {
        /* replaces escape sequences in s by their Unicode values. */
        let buf = "";
        let i = 0;
        while (i < s.length) {
            if (s.charAt(i) == '\\') {
                switch (s.charAt(i + 1)) {
                    case '\\':
                        buf += '\\';
                        i += 2;
                        break;
                    case '\'':
                        buf += '\'';
                        i += 2;
                        break;
                    case '\"':
                        buf += '\"';
                        i += 2;
                        break;
                    case 'r':
                        buf += '\r';
                        i += 2;
                        break;
                    case 'n':
                        buf += '\n';
                        i += 2;
                        break;
                    case 't':
                        buf += '\t';
                        i += 2;
                        break;
                    case 'v':
                        buf += '\u000b';
                        i += 2;
                        break;
                    case '0':
                        buf += '\0';
                        i += 2;
                        break;
                    case 'b':
                        buf += '\b';
                        i += 2;
                        break;
                    case 'f':
                        buf += '\f';
                        i += 2;
                        break;
                    case 'a':
                        buf += '\u0007';
                        i += 2;
                        break;
                    case 'u':
                    case 'x':
                        if (i + 6 <= s.length) {
                            buf += this.Hex2Char(s.substring(i + 2, i + 6));
                            i += 6;
                            break;
                        } else {
                            this.parser.SemErr("bad escape sequence in string or character");
                            i = s.length;
                            break;
                        }
                    default:
                        this.parser.SemErr("bad escape sequence in string or character");
                        i += 2;
                        break;
                }
            } else {
                buf += s.charAt(i);
                i++;
            }
        }
        return buf.toString();
    }

    public Escape(s: string): string {
        let buf = "";
        for (let i = 0; i < s.length; i++) {
            let ch = s.charAt(i);
            switch (ch) {
                case '\\':
                    buf += "\\\\";
                    break;
                case '\'':
                    buf += "\\'";
                    break;
                case '\"':
                    buf += "\\\"";
                    break;
                case '\t':
                    buf += "\\t";
                    break;
                case '\r':
                    buf += "\\r";
                    break;
                case '\n':
                    buf += "\\n";
                    break;
                default:
                    if (ch < ' ' || ch > '\u007f') buf += this.Char2Hex(ch);
                    else buf += ch;
                    break;
            }
        }
        return buf.toString();
    }

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

    public GrammarOk(): boolean {
        let ok = this.NtsComplete()
            && this.NoCircularProductions()
            && this.AllNtToTerm();
        if (ok) {
            this.AllNtReached();
            this.CheckResolvers();
            this.CheckLL1();
        }
        return ok;
    }

    //--------------- check for circular productions ----------------------


    GetSingles(p: Node_, singles: Symbol[]) {
        if (p == undefined) return;  // end of graph
        if (p.typ == Node_.nt) {
            if (p.up || this.DelGraph(p.next)) singles.push(p.sym);
        } else if (p.typ == Node_.alt || p.typ == Node_.iter || p.typ == Node_.opt) {
            if (p.up || this.DelGraph(p.next)) {
                this.GetSingles(p.sub, singles);
                if (p.typ == Node_.alt) this.GetSingles(p.down, singles);
            }
        }
        if (!p.up && this.DelNode(p)) this.GetSingles(p.next, singles);
    }

    public NoCircularProductions(): boolean {
        let ok, changed, onLeftSide, onRightSide: boolean;

        let list = [];
        for (let i = 0; i < this.nonterminals.length; i++) {
            let sym = this.nonterminals[i];
            let singles = [];
            this.GetSingles(sym.graph, singles); // get nonterminals s such that sym-->s
            for (let j = 0; j < singles.length; j++) {
                let s = singles[j];
                list.push(new CNode(sym, s));
            }
        }
        do {
            changed = false;
            for (let i = 0; i < list.length; i++) {
                let n = list[i];
                onLeftSide = false;
                onRightSide = false;
                for (let j = 0; j < list.length; j++) {
                    let m = list[j];
                    if (n.left == m.right) onRightSide = true;
                    if (n.right == m.left) onLeftSide = true;
                }
                if (!onLeftSide || !onRightSide) {
                    list.splice(list.indexOf(n), 1);
                    i--;
                    changed = true;
                }
            }
        } while (changed);
        ok = true;
        for (let i = 0; i < list.length; i++) {
            let n = list[i];
            ok = false;
            this.errors.SemErr("  " + n.left.name + " --> " + n.right.name);
        }
        return ok;
    }

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

    LL1Error(cond: number, sym: Symbol) {
        let s = "  LL1 warning in " + this.curSy.name + ": ";
        if (sym != undefined) 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;
        }
        this.errors.Warning(s);
    }

    CheckOverlap(s1: BitSet, s2: BitSet, cond: number) {
        for (let i = 0; i < this.terminals.length; i++) {
            let sym = this.terminals[i];
            if (s1.get(sym.n) && s2.get(sym.n)) {
                console.log("CheckOverlap")
                this.LL1Error(cond, sym);
            }
        }
    }

    CheckAlts(p: Node_) {
        let s1, s2: BitSet;
        while (p != undefined) {
            if (p.typ == Node_.alt) {
                let q = p;
                // s1 = new BitSet(this.terminals.length);
                s1 = new BitSet();
                while (q != undefined) { // for all alternatives
                    s2 = this.Expected0(q.sub, this.curSy);
                    this.CheckOverlap(s1, s2, 1);
                    s1 = s1.or(s2);
                    this.CheckAlts(q.sub);
                    q = q.down;
                }
            } else if (p.typ == Node_.opt || p.typ == Node_.iter) {
                if (this.DelSubGraph(p.sub)) this.LL1Error(4, undefined); // e.g. [[...]]
                else {
                    s1 = this.Expected0(p.sub, this.curSy);
                    s2 = this.Expected(p.next, this.curSy);
                    this.CheckOverlap(s1, s2, 2);
                }
                this.CheckAlts(p.sub);
            } else if (p.typ == Node_.any) {
                if (Sets.Elements(p.set) == 0) this.LL1Error(3, undefined);
                // e.g. {ANY} ANY or [ANY] ANY or ( ANY | ANY )
            }
            if (p.up) break;
            p = p.next;
        }
    }

    public CheckLL1() {
        for (let i = 0; i < this.nonterminals.length; i++) {
            this.curSy = this.nonterminals[i];
            this.CheckAlts(this.curSy.graph);
        }
    }

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

    ResErr(p: Node_, msg: string) {
        this.errors.Warning(p.line, p.pos.col, msg);
    }

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

    public CheckResolvers() {
        //foreach (Symbol sym in Symbol.nonterminals) {
        for (let i = 0; i < this.nonterminals.length; i++) {
            this.curSy = this.nonterminals[i];
            this.CheckRes(this.curSy.graph, false);
        }
    }

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

    public NtsComplete(): boolean {
        let complete = true;
        for (let i = 0; i < this.nonterminals.length; i++) {
            let sym = this.nonterminals[i];
            if (sym.graph == undefined) {
                complete = false;
                this.errors.SemErr("  No production for " + sym.name);
            }
        }
        return complete;
    }

    //-------------- check if every nts can be reached  -----------------
    MarkReachedNts(p: Node_) {
        while (p != undefined) {
            if (p.typ == Node_.nt && !this.visited.get(p.sym.n)) { // new nt reached
                this.visited.set(p.sym.n);
                this.MarkReachedNts(p.sym.graph);
            } else if (p.typ == Node_.alt || p.typ == Node_.iter || p.typ == Node_.opt) {
                this.MarkReachedNts(p.sub);
                if (p.typ == Node_.alt) this.MarkReachedNts(p.down);
            }
            if (p.up) break;
            p = p.next;
        }
    }

    public AllNtReached(): boolean {
        let ok = true;
        // this.visited = new BitSet(this.nonterminals.length);
        this.visited = new BitSet();
        this.visited.set(this.gramSy.n);
        this.MarkReachedNts(this.gramSy.graph);
        for (let i = 0; i < this.nonterminals.length; i++) {
            let sym = this.nonterminals[i];
            if (!this.visited.get(sym.n)) {
                ok = false;
                this.errors.Warning("  " + sym.name + " cannot be reached");
            }
        }
        return ok;
    }

//--------- check if every nts can be derived to terminals  ------------
    IsTerm(p: Node_, mark: BitSet): boolean { // true if graph can be derived to terminals
        while (p != undefined) {
            if (p.typ == Node_.nt && !mark.get(p.sym.n)) return false;
            if (p.typ == Node_.alt && !this.IsTerm(p.sub, mark)
                && (p.down == undefined || !this.IsTerm(p.down, mark))) return false;
            if (p.up) break;
            p = p.next;
        }
        return true;
    }

    public AllNtToTerm(): boolean {
        let changed, ok = true;
        // let mark = new BitSet(this.nonterminals.length);
        let mark = new BitSet();
        // a nonterminal is marked if it can be derived to terminal symbols
        do {
            changed = false;
            for (let i = 0; i < this.nonterminals.length; i++) {
                let sym = this.nonterminals[i];
                if (!mark.get(sym.n) && this.IsTerm(sym.graph, mark)) {
                    mark.set(sym.n);
                    changed = true;
                }
            }
        } while (changed);
        for (let i = 0; i < this.nonterminals.length; i++) {
            let sym = this.nonterminals[i];
            if (!mark.get(sym.n)) {
                ok = false;
                this.errors.SemErr("  " + sym.name + " cannot be derived to terminals");
            }
        }
        return ok;
    }

//---------------------------------------------------------------------
//  Cross reference list
//---------------------------------------------------------------------
    public XRef() {
        let xref = new Map();
        // collect lines where symbols have been defined
        for (let i = 0; i < this.nonterminals.length; i++) {
            let sym = this.nonterminals[i];
            if (!xref.has(sym)) {
                xref.set(sym, []);
            }
            xref.get(sym).push(-sym.line);
        }
        // collect lines where symbols have been referenced
        for (let i = 0; i < this.nodes.length; i++) {
            let n = this.nodes[i];
            if (n.typ == Node_.t || n.typ == Node_.wt || n.typ == Node_.nt) {
                if (!xref.has(n.sym)) {
                    xref.set(n.sym, []);
                }
                xref.get(n.sym).push(n.line);
            }
        }
        // print cross reference list
        this.trace.WriteLine();
        this.trace.WriteLine("Cross reference list:");
        this.trace.WriteLine("--------------------");
        this.trace.WriteLine();
        //foreach (Symbol sym in xref.Keys) {

        //reader, please forgive me, for i have sinned
        //this is the only section that needed es2015/es6
        //also possibly interesting: a[0].name.localeCompare(b[0].name)
        let sorted_xref = new Map([...xref.entries()].sort((a, b) => a[0].name > b[0].name ? 1 : -1));

        for (let [key, value] of sorted_xref) {
            this.trace.Write("  ");
            this.trace.Write(this.Name(key.name), -12);
            let list: [] = value;
            let col = 14;
            //foreach (int line in list) {
            for (let j = 0; j < list.length; j++) {
                let line = list[j];
                if (col + 5 > 80) {
                    this.trace.WriteLine();
                    for (col = 1; col <= 14; col++) this.trace.Write(" ");
                }
                this.trace.Write(line + "", 5);
                col += 5;
            }

            this.trace.WriteLine();
        }

        this.trace.WriteLine();
        this.trace.WriteLine();
    }

    public SetDDT(s: string) {
        s = s.toUpperCase();
        for (let i = 0; i < s.length; i++) {
            let ch = s.charAt(i);
            if ('0' <= ch && ch <= '9')
                this.ddt[ch.charCodeAt(0) - '0'.charCodeAt(0)] = true;
            else switch (ch) {
                case '0' :
                case 'A' :
                    this.ddt[0] = true;
                    break; // trace automaton
                case '1' :
                case 'F' :
                    this.ddt[1] = true;
                    break; // list first/follow sets
                case '2' :
                case 'G' :
                    this.ddt[2] = true;
                    break; // print syntax graph
                case '3' :
                case 'I' :
                    this.ddt[3] = true;
                    break; // trace computation of first sets
                case '4' :
                case 'J' :
                    this.ddt[4] = true;
                    break; // print ANY and SYNC sets
                case '5' :
                case 'P' :
                    this.ddt[8] = true;
                    break; // print statistics
                case '6' :
                case 'S' :
                    this.ddt[6] = true;
                    break; // list symbol table
                case '7' :
                case 'X' :
                    this.ddt[7] = true;
                    break; // list cross reference table
                default :
                    break;
            }
        }
    }

    public SetOption(s: string) {
        let option = s.split("=", 2);
        let name = option[0], value = option[1];
        if ("$package" === name) {
            if (this.nsName == undefined) this.nsName = value;
        } else if ("$checkEOF" === name) {
            this.checkEOF = "true" === value;
        }
    }
}