📄 tab.java
字号:
if (a!=null) {
s2 = First(nod.p2);
s2.or(s1);
Sets.Differ(set[a.p1], s2);
} else {
s1.or(First(nod.p1));
}
q = nod.p2;
}
}
p = n.next;
}
}
static private void CompAnySets() {
for (curSy=firstNt; curSy<=lastNt; curSy++)
FindAS(sy[curSy].struct);
}
static BitSet Expected(int p, int sp) {
BitSet s = First(p);
if (DelGraph(p)) s.or(follow[sp-firstNt].ts);
return s;
}
static private void CompSync(int p) {
GraphNode n;
BitSet s;
while (p > 0 && !visited.get(p)) {
n = Node(p); visited.set(p);
if (n.typ==sync) {
s = Expected(Math.abs(n.next), curSy); s.set(eofSy);
set[0].or(s);
n.p1 = NewSet(s);
} else if (n.typ==alt) {
CompSync(n.p1); CompSync(n.p2);
} else if (n.typ==opt || n.typ==iter)
CompSync(n.p1);
p = n.next;
}
}
static private void CompSyncSets() {
visited = new BitSet();
for (curSy=firstNt; curSy<=lastNt; curSy++)
CompSync(sy[curSy].struct);
}
static void CompDeletableSymbols() {
int i;
boolean changed;
do {
changed = false;
for (i=firstNt; i<=lastNt; i++)
if (!sy[i].deletable && DelGraph(sy[i].struct)) {
sy[i].deletable = true; changed = true;
}
} while (changed);
for (i=firstNt; i<=lastNt; i++)
if (sy[i].deletable) System.out.println(" " + sy[i].name + " deletable");
}
static private void MovePragmas() {
if (maxP > firstNt) {
maxP = maxT;
for (int i=maxSymbols-1; i>lastNt; i--) {
maxP++; Assert(maxP < firstNt, 6);
sy[maxP] = sy[i];
}
}
}
static void CompSymbolSets() {
int i = NewSym(t, "not", 0); // unknown symbols get code maxT
MovePragmas();
CompDeletableSymbols();
CompFirstSets();
CompFollowSets();
CompAnySets();
CompSyncSets();
if (ddt[1]) {
Trace.println("First & follow symbols:");
for (i=firstNt; i<=lastNt; i++) {
Trace.println(sy[i].name);
Trace.print("first: "); PrintSet(first[i-firstNt].ts, 10);
Trace.print("follow: "); PrintSet(follow[i-firstNt].ts, 10);
Trace.println();
}
if (maxSet >= 0) {
Trace.println(); Trace.println();
Trace.println("List of sets (ANY, SYNC): ");
for (i=0; i<=maxSet; i++) {
Trace.print(" set[" + i + "] = ");
PrintSet(set[i], 16);
}
Trace.println(); Trace.println();
}
}
}
/*---------------------------------------------------------------------
Grammar checks
---------------------------------------------------------------------*/
static private void GetSingles(int p, BitSet singles) {
if (p <= 0) return; // end of graph
GraphNode n = Node(p);
if (n.typ==nt) {
if (DelGraph(Math.abs(n.next))) singles.set(n.p1);
} else if (n.typ==alt || n.typ==iter || n.typ==opt) {
if (DelGraph(Math.abs(n.next))) {
GetSingles(n.p1, singles);
if (n.typ==alt) GetSingles(n.p2, singles);
}
}
if (DelNode(n)) GetSingles(n.next, singles);
}
static boolean NoCircularProductions() {
boolean ok, changed, onLeftSide, onRightSide;
CNode[] list = new CNode[maxList];
CNode x;
BitSet singles;
Symbol sym;
int i, j, len = 0;
for (i=firstNt; i<=lastNt; i++) {
singles = new BitSet();
GetSingles(sy[i].struct, singles); // get nts such that i-->j
for (j=firstNt; j<=lastNt; j++) {
if (singles.get(j)) {
x = new CNode(); x.left = i; x.right = j; x.deleted = false;
Assert(len < maxList, 9); list[len++] = x;
}
}
}
do {
changed = false;
for (i=0; i<len; i++) {
if (!list[i].deleted) {
onLeftSide = false; onRightSide = false;
for (j=0; j<len; j++) {
if (!list[j].deleted) {
if (list[i].left==list[j].right) onRightSide = true;
if (list[j].left==list[i].right) onLeftSide = true;
}
}
if (!onLeftSide || !onRightSide) {
list[i].deleted = true; changed = true;
}
}
}
} while(changed);
ok = true;
for (i=0; i<len; i++) {
if (!list[i].deleted) {
ok = false;
System.out.println(" "+sy[list[i].left].name+" --> "+sy[list[i].right].name);
}
}
return ok;
}
static private void LL1Error(int cond, int ts) {
System.out.print(" LL(1) warning in " + sy[curSy].name + ": ");
if (ts > 0) System.out.print(sy[ts].name + " is ");
switch (cond) {
case 1: {System.out.println("the start of several alternatives"); break;}
case 2: {System.out.println("the start & successor of a deletable structure"); break;}
case 3: {System.out.println("an ANY node that matches no symbol"); break;}
}
}
static private boolean Overlap(BitSet s1, BitSet s2, int cond) {
boolean overlap = false;
for (int i=0; i<=maxT; i++) {
if (s1.get(i) && s2.get(i)) {LL1Error(cond, i); overlap = true;}
}
return overlap;
}
static private boolean AltOverlap(int p) {
boolean overlap = false;
GraphNode n, a;
BitSet s1, s2;
int q;
while (p > 0) {
n = Node(p);
if (n.typ==alt) {
q = p; s1 = new BitSet();
while (q != 0) { // for all alternatives
a = Node(q); s2 = Expected(a.p1, curSy);
if (Overlap(s1, s2, 1)) overlap = true;
s1.or(s2);
if (AltOverlap(a.p1)) overlap = true;
q = a.p2;
}
} else if (n.typ==opt || n.typ==iter) {
s1 = Expected(n.p1, curSy);
s2 = Expected(Math.abs(n.next), curSy);
if (Overlap(s1, s2, 2)) overlap = true;
if (AltOverlap(n.p1)) overlap = true;
} else if (n.typ==any) {
if (Sets.Empty(Set(n.p1))) {LL1Error(3, 0); overlap = true;}
// e.g. {ANY} ANY or [ANY] ANY
}
p = n.next;
}
return overlap;
}
static boolean LL1() {
boolean ll1 = true;
for (curSy=firstNt; curSy<=lastNt; curSy++)
if (AltOverlap(sy[curSy].struct)) ll1 = false;
return ll1;
}
static boolean NtsComplete() {
boolean complete = true;
for (int i=firstNt; i<=lastNt; i++) {
if (sy[i].struct==0) {
complete = false;
System.out.println(" No production for " + sy[i].name);
}
}
return complete;
}
static private void MarkReachedNts(int p) {
GraphNode n;
while (p > 0) {
n = Node(p);
if (n.typ==nt) {
if (!visited.get(n.p1)) { // new nt reached
visited.set(n.p1);
MarkReachedNts(sy[n.p1].struct);
}
} else if (n.typ==alt || n.typ==iter || n.typ==opt) {
MarkReachedNts(n.p1);
if (n.typ==alt) MarkReachedNts(n.p2);
}
p = n.next;
}
}
static boolean AllNtReached() {
GraphNode n;
boolean ok = true;
visited = new BitSet();
visited.set(gramSy);
MarkReachedNts(Sym(gramSy).struct);
for (int i=firstNt; i<=lastNt; i++) {
if (!visited.get(i)) {
ok = false;
System.out.println(" " + sy[i].name + " cannot be reached");
}
}
return ok;
}
static private boolean Term(int p) { // true if graph can be derived to terminals
GraphNode n;
while (p > 0) {
n = Node(p);
if (n.typ==nt && !termNt.get(n.p1)) return false;
if (n.typ==alt && !Term(n.p1) && (n.p2==0 || !Term(n.p2))) return false;
p = n.next;
}
return true;
}
static boolean AllNtToTerm() {
boolean changed, ok = true;
int i;
termNt = new BitSet();
do {
changed = false;
for (i=firstNt; i<=lastNt; i++)
if (!termNt.get(i) && Term(sy[i].struct)) {
termNt.set(i); changed = true;
}
} while (changed);
for (i=firstNt; i<=lastNt; i++)
if (!termNt.get(i)) {
ok = false;
System.out.println(" " + sy[i].name + " cannot be derived to terminals");
}
return ok;
}
/*---------------------------------------------------------------------
Utility functions
---------------------------------------------------------------------*/
static void NewName (String alias, String str) {
Assert(lastName < maxNames, 8);
lastName++;
NameTab[lastName] = new UserName();
NameTab[lastName].alias = alias; NameTab[lastName].str = str;
}
static private String Str(String s, int len) {
int i = s.length();
char[] a = new char[i+len];
s.getChars(0, i, a, 0);
for (; i<len; i++) a[i] = ' ';
return new String(a, 0, len);
}
static private String Int(int n, int len) {
String s = String.valueOf(n);
int i = s.length(); if (len < i) len = i;
int j = 0, d = len - s.length();
char[] a = new char[len];
for (i=0; i<d; i++) a[i] = ' ';
for (j=0; i<len; i++) {a[i] = s.charAt(j); j++;}
return new String(a, 0, len);
}
static private String Ascii (char ch) {
switch (ch) {
case 0 : return "nul";
case 1 : return "soh";
case 2 : return "stx";
case 3 : return "etx";
case 4 : return "eot";
case 5 : return "enq";
case 6 : return "ack";
case 7 : return "bel";
case 8 : return "bs";
case 9 : return "ht";
case 10 : return "lf";
case 11 : return "vt";
case 12 : return "ff";
case 13 : return "cr";
case 14 : return "so";
case 15 : return "si";
case 16 : return "dle";
case 17 : return "dc1";
case 18 : return "dc2";
case 19 : return "dc3";
case 20 : return "dc4";
case 21 : return "nak";
case 22 : return "syn";
case 23 : return "etb";
case 24 : return "can";
case 25 : return "em";
case 26 : return "sub";
case 27 : return "esc";
case 28 : return "fs";
case 29 : return "gs";
case 30 : return "rs";
case 31 : return "us";
case ' ' : return "sp";
case '!' : return "bang";
case '\"' : return "dquote";
case '#' : return "hash";
case '$' : return "dollar";
case '%' : return "percent";
case '&' : return "and";
case '\'' : return "squote";
case '(' : return "lparen";
case ')' : return "rparen";
case '*' : return "star";
case '+' : return "plus";
case ',' : return "comma";
case '-' : return "minus";
case '.' : return "point";
case '/' : return "slash";
case '0' : return "d0";
case '1' : return "d1";
case '2' : return "d2";
case '3' : return "d3";
case '4' : return "d4";
case '5' : return "d5";
case '6' : return "d6";
case '7' : return "d7";
case '8' : return "d8";
case '9' : return "d9";
case ':' : return "colon";
case ';' : return "semicolon";
case '<' : return "less";
case '=' : return "equal";
case '>' : return "greater";
case '?' : return "query";
case '@' : return "at";
case '[' : return "lbrack";
case '\\' : return "backslash";
case ']' : return "rbrack";
case '^' : return "uparrow";
case '_' : return "underscore";
case '`' : return "accent";
case '{' : return "lbrace";
case '|' : return "bar";
case '}' : return "rbrace";
case '~' : return "tilde";
case 127 : return "delete";
default : return "ASC" + Integer.toString(ch, 10);
}
}
static private String SymName(String name) {
for (int i = 1; i <= lastName; i++) {
if (name.equals(NameTab[i].str)) return NameTab[i].alias;
}
if (name.charAt(0) != '\"') return name + "Sym";
StringBuffer S = new StringBuffer();
for (int i = 1; i < name.length()-1; i++) {
char ch = name.charAt(i);
if ('a' <= ch && ch <= 'z' || 'A' <= ch && ch <= 'Z') S.append(ch);
else S.append(Ascii(ch));
}
S.append("Sym");
return S.toString();
}
static void AssignNames() {
for (int i = 0; i < maxT; i++) sy[i].symName = SymName(sy[i].name);
System.out.println("Names assigned");
}
static void PrintSymbolTable() {
int i;
Trace.println("Symbol Table:");
Trace.println(" nr name typ hasAt struct del line"); Trace.println();
i = 0;
while (i < maxSymbols) {
Trace.print(Int(i, 3) + " " + Str(sy[i].name, 10) + " " + nTyp[sy[i].typ]);
if (sy[i].attrPos==null) Trace.print(" false "); else Trace.print(" true ");
Trace.print(Int(sy[i].struct, 5));
if (sy[i].deletable) Trace.print(" true "); else Trace.print(" false ");
Trace.print(Int(sy[i].line, 5));
if (sy[i].typ == t && sy[i].symName != null) Trace.print(" " + sy[i].symName);
Trace.println();
if (i==maxT - 1) i++;
if (i==maxT) i = firstNt; else i++;
}
Trace.println();
}
static void XRef() {
Symbol sym;
GraphNode n;
XNode[] list = new XNode[lastNt+1];
XNode p, q, x;
int i, col;
if (maxT <= 0) return;
MovePragmas();
// search lines where symbol has been referenced
for (i=nNodes; i>=1; i--) {
n = Node(i);
if (n.typ==t || n.typ==wt || n.typ==nt) {
p = new XNode(); p.line = n.line;
p.next = list[n.p1]; list[n.p1] = p;
}
}
// search lines where symbol has been defined and insert in order
i = 1;
while (i <= lastNt) {
sym = Sym(i); p = list[i]; q = null;
while (p != null && sym.line > p.line) {q = p; p = p.next;}
x = new XNode(); x.line = -sym.line; x.next = p;
if (q==null) list[i] = x; else q.next = x;
if (i==maxP) i = firstNt; else i++;
}
// print cross reference list
Trace.println();
Trace.println("Cross reference list:"); Trace.println();
Trace.println("Terminals:");
Trace.println(" 0 EOF");
i = 1;
while (i <= lastNt) {
Trace.print(Int(i, 3) + " " + Str(sy[i].name, 10) + " ");
p = list[i]; col = 16;
while (p != null) {
if (col + 5 > lineLength) {
Trace.println();
for (col=0; col<16; col++) Trace.print(" ");
}
if (p.line==0) Trace.print("??? "); else Trace.print(Int(p.line, 5));
col = col + 5;
p = p.next;
}
Trace.println();
if (i==maxT - 1) {i++; Trace.println(); Trace.println("Pragmas:");}
if (i==maxP) {Trace.println(); Trace.println("Nonterminals:"); i = firstNt;}
else i++;
}
Trace.println(); Trace.println();
}
static void Init() {
err = Scanner.err;
maxSet = 0; set[0] = new BitSet(); set[0].set(eofSy);
maxT = -1;
maxP = maxSymbols;
firstNt = maxSymbols;
lastNt = maxP - 1;
lastName = 0;
dummyName = 0;
maxC = -1;
nNodes = -1;
int dummy = NewNode(0, 0, 0);
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -