commit 45bbbb593e7c2aa83a8bf9b40728cf441afb1ca6
parent faa784e971aba23ab59bf3aba9e860fc4a7fbd54
Author: erai <erai@omiltem.net>
Date: Sun, 13 Apr 2025 07:10:50 -0400
generate slr sets
Diffstat:
| M | cc0.c | | | 521 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- |
| M | lalr.om | | | 381 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---- |
2 files changed, 878 insertions(+), 24 deletions(-)
diff --git a/cc0.c b/cc0.c
@@ -149,12 +149,20 @@ u zlabels_to_ir();
u zlalr_alt();
u zlalr_alt_nonterminal();
u zlalr_alt_terminal();
+u zlalr_assoc();
u zlalr_compiler();
+u zlalr_goto();
+u zlalr_itemcmp();
u zlalr_items();
+u zlalr_itemsetcmp();
+u zlalr_linkout();
u zlalr_lookup();
+u zlalr_memoset();
u zlalr_mkalt();
+u zlalr_mkitemset();
u zlalr_mkprod();
u zlalr_pattern();
+u zlalr_pointcmp();
u zlalr_primary();
u zlalr_rules();
u zlalr_suffix();
@@ -26232,14 +26240,14 @@ u zlalr_alt_nonterminal(u vlc, u va, u vs) {
v6 = va + 0UL;
v7 = va + 16UL;
v8 = *(u*)(va + 8UL) + 1UL;
- v9 = 24UL;
+ v9 = 64UL;
v10 = ((u(*)())v4)(v5, v6, v7, v8, v9);
v10;
vi = *(u*)(va + 8UL);
*(u*)(va + 8UL) = *(u*)(va + 8UL) + 1UL;
- *(u*)(*(u*)(va + 0UL) + vi * 24UL + 0UL) = 1UL;
- *(u*)(*(u*)(va + 0UL) + vi * 24UL + 8UL) = *(u*)(vs + 32UL);
- *(u*)(*(u*)(va + 0UL) + vi * 24UL + 16UL) = *(u*)(vs + 40UL);
+ *(u*)(*(u*)(va + 0UL) + vi * 64UL + 32UL) = 0UL;
+ *(u*)(*(u*)(va + 0UL) + vi * 64UL + 40UL) = *(u*)(vs + 32UL);
+ *(u*)(*(u*)(va + 0UL) + vi * 64UL + 48UL) = *(u*)(vs + 40UL);
return 0UL;
}
u zlalr_alt_terminal(u vlc, u va, u vname, u vid) {
@@ -26256,18 +26264,77 @@ u zlalr_alt_terminal(u vlc, u va, u vname, u vid) {
v7 = va + 0UL;
v8 = va + 16UL;
v9 = *(u*)(va + 8UL) + 1UL;
- v10 = 24UL;
+ v10 = 64UL;
v11 = ((u(*)())v5)(v6, v7, v8, v9, v10);
v11;
vi = *(u*)(va + 8UL);
*(u*)(va + 8UL) = *(u*)(va + 8UL) + 1UL;
- *(u*)(*(u*)(va + 0UL) + vi * 24UL + 0UL) = 1UL;
- *(u*)(*(u*)(va + 0UL) + vi * 24UL + 8UL) = vid;
- *(u*)(*(u*)(va + 0UL) + vi * 24UL + 16UL) = vname;
+ *(u*)(*(u*)(va + 0UL) + vi * 64UL + 32UL) = 1UL;
+ *(u*)(*(u*)(va + 0UL) + vi * 64UL + 40UL) = vid;
+ *(u*)(*(u*)(va + 0UL) + vi * 64UL + 48UL) = vname;
return 0UL;
}
+u zlalr_assoc(u vlc, u vi, u vt) {
+ u vp = 0;
+ u vlink = 0;
+ u vd = 0;
+ u vdir = 0;
+ u v7 = 0;
+ u v8 = 0;
+ u v9 = 0;
+ u v10 = 0;
+ u v11 = 0;
+ u v12 = 0;
+ u v13 = 0;
+ u v14 = 0;
+ u v15 = 0;
+ u v16 = 0;
+ u v17 = 0;
+ u v18 = 0;
+ u v19 = 0;
+ u v20 = 0;
+ u v21 = 0;
+ vp = 0UL;
+ vlink = vi + 32UL;
+b1: vd = *(u*)vlink;
+ if (!vd) goto b7;
+ v7 = 0UL;
+b8: if (!v7) goto b5;
+ v12 = (u)zalloc;
+ v13 = *(u*)(vlc + 0UL);
+ v14 = 64UL;
+ v15 = ((u(*)())v12)(v13, v14);
+ vd = v15;
+ *(u*)(vd + 40UL) = *(u*)(vt + 40UL);
+ *(u*)(vd + 48UL) = *(u*)(vt + 48UL);
+ *(u*)(vd + 56UL) = *(u*)(vt + 56UL);
+ v16 = (u)zrb_link;
+ v17 = vi + 32UL;
+ v18 = vlink;
+ v19 = vp;
+ v20 = vd + 0UL;
+ v21 = ((u(*)())v16)(v17, v18, v19, v20);
+ v21;
+ return vd;
+b5: v8 = (u)zlalr_itemcmp;
+ v9 = vt;
+ v10 = vd;
+ v11 = ((u(*)())v8)(v9, v10);
+ vdir = v11;
+ if ((s)vdir >= (s)0UL) goto b12;
+ vlink = vd + 0UL + 16UL;
+ vp = vd + 0UL;
+b10: goto b1;
+b12: if ((s)vdir <= (s)0UL) goto b14;
+ vlink = vd + 0UL + 24UL;
+ vp = vd + 0UL;
+ goto b10;
+b14: return 0UL;
+b7: v7 = 1UL;
+ goto b8;
+}
u zlalr_compiler(u vc, u vpn, u verr) {
- u v_lc[7] = {0};
+ u v_lc[11] = {0};
u vlc = 0;
u v5 = 0;
u v6 = 0;
@@ -26291,8 +26358,371 @@ u zlalr_compiler(u vc, u vpn, u verr) {
v11;
return 0UL;
}
+u zlalr_goto(u vlc, u vi) {
+ u vt = 0;
+ u va = 0;
+ u vseen = 0;
+ u vqueue = 0;
+ u vprod = 0;
+ u valt = 0;
+ u vsym = 0;
+ u vr[8] = {0};
+ u vj = 0;
+ u v11 = 0;
+ u v12 = 0;
+ u v13 = 0;
+ u v14 = 0;
+ u v15 = 0;
+ u v16 = 0;
+ u v17 = 0;
+ u v18 = 0;
+ u v19 = 0;
+ u v20 = 0;
+ u v21 = 0;
+ u v22 = 0;
+ u v23 = 0;
+ u v24 = 0;
+ u v25 = 0;
+ u v26 = 0;
+ u v27 = 0;
+ u v28 = 0;
+ u v29 = 0;
+ u v30 = 0;
+ u v31 = 0;
+ u v32 = 0;
+ u v33 = 0;
+ u v34 = 0;
+ u v35 = 0;
+ u v36 = 0;
+ u v37 = 0;
+ u v38 = 0;
+ u v39 = 0;
+ u v40 = 0;
+ u v41 = 0;
+ u v42 = 0;
+ u v43 = 0;
+ u v44 = 0;
+ u v45 = 0;
+ u v46 = 0;
+ u v47 = 0;
+ u v48 = 0;
+ u v49 = 0;
+ u v50 = 0;
+ u v51 = 0;
+ u v52 = 0;
+ u v53 = 0;
+ v11 = (u)zlalr_mkitemset;
+ v12 = vlc;
+ v13 = ((u(*)())v11)(v12);
+ vseen = v13;
+ v14 = (u)zrb_first;
+ v15 = *(u*)(vi + 32UL);
+ v16 = ((u(*)())v14)(v15);
+ vt = v16;
+b3: if (!vt) goto b9;
+ v17 = 0UL;
+b10: if (!v17) goto b7;
+b16: vt = vqueue;
+ if (!vt) goto b22;
+ v26 = 0UL;
+b23: if (!v26) goto b20;
+ v43 = (u)zrb_first;
+ v44 = *(u*)(vi + 48UL);
+ v45 = ((u(*)())v43)(v44);
+ vsym = v45;
+b45: if (!vsym) goto b51;
+ v46 = 0UL;
+b52: if (!v46) goto b49;
+ return 0UL;
+b49: v47 = (u)zlalr_memoset;
+ v48 = vlc;
+ v49 = *(u*)(vsym + 56UL);
+ v50 = ((u(*)())v47)(v48, v49);
+ *(u*)(vsym + 56UL) = v50;
+ v51 = (u)zrb_next;
+ v52 = vsym + 0UL;
+ v53 = ((u(*)())v51)(v52);
+ vsym = v53;
+ goto b45;
+b51: v46 = 1UL;
+ goto b52;
+b20: vqueue = *(u*)(vt + 32UL);
+ valt = *(u*)(*(u*)(*(u*)(*(u*)(vlc + 32UL) + *(u*)(vt + 40UL) * 8UL) + 48UL) + *(u*)(vt + 48UL) * 8UL);
+ if (*(u*)(vt + 56UL) != *(u*)(valt + 8UL)) goto b26;
+ goto b16;
+b26: vsym = *(u*)(valt + 0UL) + *(u*)(vt + 56UL) * 64UL;
+ *(u*)((u)vr + 40UL) = *(u*)(vt + 40UL);
+ *(u*)((u)vr + 48UL) = *(u*)(vt + 48UL);
+ *(u*)((u)vr + 56UL) = *(u*)(vt + 56UL) + 1UL;
+ v27 = (u)zlalr_assoc;
+ v28 = vlc;
+ v29 = vseen;
+ v30 = (u)vr;
+ v31 = ((u(*)())v27)(v28, v29, v30);
+ va = v31;
+ if (!va) goto b30;
+ *(u*)(va + 32UL) = vqueue;
+ vqueue = va;
+b28: v32 = (u)zlalr_linkout;
+ v33 = vlc;
+ v34 = vi + 48UL;
+ v35 = vsym;
+ v36 = (u)vr;
+ v37 = ((u(*)())v32)(v33, v34, v35, v36);
+ v37;
+ if (!*(u*)(vsym + 32UL)) goto b34;
+ goto b16;
+b34: vprod = *(u*)(*(u*)(vlc + 32UL) + *(u*)(vsym + 40UL) * 8UL);
+ vj = 0UL;
+b35: if (vj != *(u*)(vprod + 56UL)) goto b39;
+ goto b16;
+b39: *(u*)((u)vr + 40UL) = *(u*)(vsym + 40UL);
+ *(u*)((u)vr + 48UL) = vj;
+ *(u*)((u)vr + 56UL) = 0UL;
+ v38 = (u)zlalr_assoc;
+ v39 = vlc;
+ v40 = vseen;
+ v41 = (u)vr;
+ v42 = ((u(*)())v38)(v39, v40, v41);
+ va = v42;
+ if (!va) goto b43;
+ *(u*)(va + 32UL) = vqueue;
+ vqueue = va;
+b41: vj = vj + 1UL;
+ goto b35;
+b43: goto b41;
+b30: goto b28;
+b22: v26 = 1UL;
+ goto b23;
+b7: v18 = (u)zlalr_assoc;
+ v19 = vlc;
+ v20 = vseen;
+ v21 = vt;
+ v22 = ((u(*)())v18)(v19, v20, v21);
+ va = v22;
+ if (!va) goto b14;
+ *(u*)(va + 32UL) = vqueue;
+ vqueue = va;
+b12: v23 = (u)zrb_next;
+ v24 = vt + 0UL;
+ v25 = ((u(*)())v23)(v24);
+ vt = v25;
+ goto b3;
+b14: goto b12;
+b9: v17 = 1UL;
+ goto b10;
+}
+u zlalr_itemcmp(u va, u vb) {
+ if ((s)*(u*)(va + 40UL) >= (s)*(u*)(vb + 40UL)) goto b3;
+ return -1UL;
+b3: if ((s)*(u*)(va + 40UL) <= (s)*(u*)(vb + 40UL)) goto b5;
+ return 1UL;
+b5: if ((s)*(u*)(va + 48UL) >= (s)*(u*)(vb + 48UL)) goto b7;
+ return -1UL;
+b7: if ((s)*(u*)(va + 48UL) <= (s)*(u*)(vb + 48UL)) goto b9;
+ return 1UL;
+b9: if ((s)*(u*)(va + 56UL) >= (s)*(u*)(vb + 56UL)) goto b11;
+ return -1UL;
+b11: if ((s)*(u*)(va + 56UL) <= (s)*(u*)(vb + 56UL)) goto b13;
+ return 1UL;
+b13: return 0UL;
+}
u zlalr_items(u vlc) {
+ u vi = 0;
+ u vinit_state[8] = {0};
+ u v3 = 0;
+ u v4 = 0;
+ u v5 = 0;
+ u v6 = 0;
+ u v7 = 0;
+ u v8 = 0;
+ u v9 = 0;
+ u v10 = 0;
+ u v11 = 0;
+ u v12 = 0;
+ u v13 = 0;
+ u v14 = 0;
+ u v15 = 0;
+ v3 = (u)zlalr_mkitemset;
+ v4 = vlc;
+ v5 = ((u(*)())v3)(v4);
+ vi = v5;
+ v6 = (u)zlalr_assoc;
+ v7 = vlc;
+ v8 = vi;
+ v9 = (u)vinit_state;
+ v10 = ((u(*)())v6)(v7, v8, v9);
+ v10;
+ *(u*)(vlc + 64UL) = vi;
+ *(u*)(vlc + 72UL) = vi;
+b3: vi = *(u*)(vlc + 72UL);
+ if (!vi) goto b9;
+ v11 = 0UL;
+b10: if (!v11) goto b7;
return 0UL;
+b7: *(u*)(vlc + 72UL) = *(u*)(vi + 40UL);
+ v12 = (u)zlalr_goto;
+ v13 = vlc;
+ v14 = vi;
+ v15 = ((u(*)())v12)(v13, v14);
+ v15;
+ goto b3;
+b9: v11 = 1UL;
+ goto b10;
+}
+u zlalr_itemsetcmp(u va, u vb) {
+ u vx = 0;
+ u vy = 0;
+ u vdir = 0;
+ u v5 = 0;
+ u v6 = 0;
+ u v7 = 0;
+ u v8 = 0;
+ u v9 = 0;
+ u v10 = 0;
+ u v11 = 0;
+ u v12 = 0;
+ u v13 = 0;
+ u v14 = 0;
+ u v15 = 0;
+ u v16 = 0;
+ u v17 = 0;
+ u v18 = 0;
+ u v19 = 0;
+ u v20 = 0;
+ u v21 = 0;
+ u v22 = 0;
+ u v23 = 0;
+ u v24 = 0;
+ u v25 = 0;
+ v5 = (u)zrb_first;
+ v6 = *(u*)(va + 32UL);
+ v7 = ((u(*)())v5)(v6);
+ vx = v7;
+ v8 = (u)zrb_first;
+ v9 = *(u*)(vb + 32UL);
+ v10 = ((u(*)())v8)(v9);
+ vy = v10;
+b3: if (!vx) goto b13;
+ v12 = 0UL;
+b14: if (!v12) goto b9;
+ if (!vy) goto b16;
+ v13 = 0UL;
+b17: if (!v13) goto b9;
+ v11 = 1UL;
+b11: if (!v11) goto b7;
+ return 0UL;
+b7: if (!vx) goto b21;
+ v14 = 0UL;
+b22: if (!v14) goto b19;
+ return -1UL;
+b19: if (!vy) goto b26;
+ v15 = 0UL;
+b27: if (!v15) goto b24;
+ return 1UL;
+b24: v16 = (u)zlalr_itemcmp;
+ v17 = vx;
+ v18 = vy;
+ v19 = ((u(*)())v16)(v17, v18);
+ vdir = v19;
+ if (vdir == 0UL) goto b31;
+ return vdir;
+b31: v20 = (u)zrb_next;
+ v21 = vx + 0UL;
+ v22 = ((u(*)())v20)(v21);
+ vx = v22;
+ v23 = (u)zrb_next;
+ v24 = vy + 0UL;
+ v25 = ((u(*)())v23)(v24);
+ vy = v25;
+ goto b3;
+b26: v15 = 1UL;
+ goto b27;
+b21: v14 = 1UL;
+ goto b22;
+b9: v11 = 0UL;
+ goto b11;
+b16: v13 = 1UL;
+ goto b17;
+b13: v12 = 1UL;
+ goto b14;
+}
+u zlalr_linkout(u vlc, u vout, u vsym, u vt) {
+ u vp = 0;
+ u vlink = 0;
+ u vd = 0;
+ u vdir = 0;
+ u v8 = 0;
+ u v9 = 0;
+ u v10 = 0;
+ u v11 = 0;
+ u v12 = 0;
+ u v13 = 0;
+ u v14 = 0;
+ u v15 = 0;
+ u v16 = 0;
+ u v17 = 0;
+ u v18 = 0;
+ u v19 = 0;
+ u v20 = 0;
+ u v21 = 0;
+ u v22 = 0;
+ u v23 = 0;
+ u v24 = 0;
+ u v25 = 0;
+ u v26 = 0;
+ u v27 = 0;
+ u v28 = 0;
+ u v29 = 0;
+ u v30 = 0;
+ vp = 0UL;
+ vlink = vout;
+b1: vd = *(u*)vlink;
+ if (!vd) goto b7;
+ v8 = 0UL;
+b8: if (!v8) goto b5;
+ v13 = (u)zalloc;
+ v14 = *(u*)(vlc + 0UL);
+ v15 = 64UL;
+ v16 = ((u(*)())v13)(v14, v15);
+ vd = v16;
+ *(u*)(vd + 32UL) = *(u*)(vsym + 32UL);
+ *(u*)(vd + 40UL) = *(u*)(vsym + 40UL);
+ *(u*)(vd + 48UL) = *(u*)(vsym + 48UL);
+ v17 = (u)zlalr_mkitemset;
+ v18 = vlc;
+ v19 = ((u(*)())v17)(v18);
+ *(u*)(vd + 56UL) = v19;
+ v20 = (u)zrb_link;
+ v21 = vout;
+ v22 = vlink;
+ v23 = vp;
+ v24 = vd + 0UL;
+ v25 = ((u(*)())v20)(v21, v22, v23, v24);
+ v25;
+ v26 = (u)zlalr_assoc;
+ v27 = vlc;
+ v28 = *(u*)(vd + 56UL);
+ v29 = vt;
+ v30 = ((u(*)())v26)(v27, v28, v29);
+ v30;
+ return 0UL;
+b5: v9 = (u)zlalr_pointcmp;
+ v10 = vsym;
+ v11 = vd;
+ v12 = ((u(*)())v9)(v10, v11);
+ vdir = v12;
+ if ((s)vdir >= (s)0UL) goto b12;
+ vlink = vd + 0UL + 16UL;
+ vp = vd + 0UL;
+b10: goto b1;
+b12: if ((s)vdir <= (s)0UL) goto b14;
+ vlink = vd + 0UL + 24UL;
+ vp = vd + 0UL;
+ goto b10;
+b14: return 0UL;
+b7: v8 = 1UL;
+ goto b8;
}
u zlalr_lookup(u vlc, u vname, u vnew) {
u vp = 0;
@@ -26358,6 +26788,55 @@ b14: vlink = vd + 0UL + 24UL;
b7: v7 = 1UL;
goto b8;
}
+u zlalr_memoset(u vlc, u vi) {
+ u vp = 0;
+ u vlink = 0;
+ u vd = 0;
+ u vdir = 0;
+ u v6 = 0;
+ u v7 = 0;
+ u v8 = 0;
+ u v9 = 0;
+ u v10 = 0;
+ u v11 = 0;
+ u v12 = 0;
+ u v13 = 0;
+ u v14 = 0;
+ u v15 = 0;
+ u v16 = 0;
+ vp = 0UL;
+ vlink = vlc + 56UL;
+b1: vd = *(u*)vlink;
+ if (!vd) goto b7;
+ v6 = 0UL;
+b8: if (!v6) goto b5;
+ v11 = (u)zrb_link;
+ v12 = vlc + 56UL;
+ v13 = vlink;
+ v14 = vp;
+ v15 = vi + 0UL;
+ v16 = ((u(*)())v11)(v12, v13, v14, v15);
+ v16;
+ *(u*)(vi + 40UL) = *(u*)(vlc + 72UL);
+ *(u*)(vlc + 72UL) = vi;
+ return vi;
+b5: v7 = (u)zlalr_itemsetcmp;
+ v8 = vi;
+ v9 = vd;
+ v10 = ((u(*)())v7)(v8, v9);
+ vdir = v10;
+ if ((s)vdir >= (s)0UL) goto b12;
+ vlink = vd + 0UL + 16UL;
+ vp = vd + 0UL;
+b10: goto b1;
+b12: if ((s)vdir <= (s)0UL) goto b14;
+ vlink = vd + 0UL + 24UL;
+ vp = vd + 0UL;
+ goto b10;
+b14: return vd;
+b7: v6 = 1UL;
+ goto b8;
+}
u zlalr_mkalt(u vlc, u vp) {
u va = 0;
u v3 = 0;
@@ -26388,6 +26867,19 @@ u zlalr_mkalt(u vlc, u vp) {
*(u*)(vp + 56UL) = *(u*)(vp + 56UL) + 1UL;
return va;
}
+u zlalr_mkitemset(u vlc) {
+ u vi = 0;
+ u v2 = 0;
+ u v3 = 0;
+ u v4 = 0;
+ u v5 = 0;
+ v2 = (u)zalloc;
+ v3 = *(u*)(vlc + 0UL);
+ v4 = 64UL;
+ v5 = ((u(*)())v2)(v3, v4);
+ vi = v5;
+ return vi;
+}
u zlalr_mkprod(u vlc) {
u vp = 0;
u v2 = 0;
@@ -26452,6 +26944,17 @@ b5: v5 = (u)zlalr_mkalt;
b7: v4 = 1UL;
goto b8;
}
+u zlalr_pointcmp(u va, u vb) {
+ if ((s)*(u*)(va + 32UL) >= (s)*(u*)(vb + 32UL)) goto b3;
+ return -1UL;
+b3: if ((s)*(u*)(va + 32UL) <= (s)*(u*)(vb + 32UL)) goto b5;
+ return 1UL;
+b5: if ((s)*(u*)(va + 40UL) >= (s)*(u*)(vb + 40UL)) goto b7;
+ return -1UL;
+b7: if ((s)*(u*)(va + 40UL) <= (s)*(u*)(vb + 40UL)) goto b9;
+ return 1UL;
+b9: return 0UL;
+}
u zlalr_primary(u vlc, u va, u vpn) {
u vv = 0;
u vs = 0;
diff --git a/lalr.om b/lalr.om
@@ -1,16 +1,27 @@
-// The dragon book is a good reference.
// Aho, A.V., Sethi, R. and Ullman, J.D. (2007) Compilers: Principles, techniques, and Tools. Reading, Mass: Addison-Wesley.
struct lalr_item {
+ node: rbnode;
+ queue_next: *lalr_item;
prod: int;
alt: int;
point: int;
}
+struct lalr_itemset {
+ node: rbnode;
+ items: *rbnode;
+ goto_next: *lalr_itemset;
+ goto_out: *rbnode;
+ mark: int;
+}
+
struct lalr_point {
+ node: rbnode;
term: int;
id: int;
name: *byte;
+ out: *lalr_itemset;
}
struct lalr_alt {
@@ -38,6 +49,12 @@ struct lalr_compiler {
prod: **lalr_prod;
prod_len: int;
prod_cap: int;
+
+ sets: *rbnode;
+ root: *lalr_itemset;
+ goto_queue: *lalr_itemset;
+
+ mark: int;
}
func lalr_compiler(c: *compiler, pn: *peg_node, err: *file) {
@@ -282,7 +299,7 @@ func lalr_alt_nonterminal(lc: *lalr_compiler, a: *lalr_alt, s: *lalr_prod) {
ensure_arr(lc.a, (&a.point) as **void, &a.point_cap, a.point_len + 1, sizeof(*a.point));
i = a.point_len;
a.point_len = a.point_len + 1;
- a.point[i].term = 1;
+ a.point[i].term = 0;
a.point[i].id = s.id;
a.point[i].name = s.name;
}
@@ -346,18 +363,352 @@ func lalr_show(lc: *lalr_compiler) {
}
}
+func lalr_mkitemset(lc: *lalr_compiler): *lalr_itemset {
+ var i: *lalr_itemset;
+ i = alloc(lc.a, sizeof(*i)) as *lalr_itemset;
+ return i;
+}
+
+func lalr_itemcmp(a: *lalr_item, b: *lalr_item): int {
+ if a.prod < b.prod {
+ return -1;
+ } else if a.prod > b.prod {
+ return 1;
+ } else if a.alt < b.alt {
+ return -1;
+ } else if a.alt > b.alt {
+ return 1;
+ } else if a.point < b.point {
+ return -1;
+ } else if a.point > b.point {
+ return 1;
+ }
+ return 0;
+}
+
+func lalr_itemsetcmp(a: *lalr_itemset, b: *lalr_itemset): int {
+ var x: *lalr_item;
+ var y: *lalr_item;
+ var dir: int;
+ x = rb_first(a.items) as *lalr_item;
+ y = rb_first(b.items) as *lalr_item;
+ loop {
+ if !x && !y {
+ return 0;
+ } else if !x {
+ return -1;
+ } else if !y {
+ return 1;
+ }
+ dir = lalr_itemcmp(x, y);
+ if dir != 0 {
+ return dir;
+ }
+ x = rb_next(&x.node) as *lalr_item;
+ y = rb_next(&y.node) as *lalr_item;
+ }
+}
+
+func lalr_assoc(lc: *lalr_compiler, i: *lalr_itemset, t: *lalr_item): *lalr_item {
+ var p: *rbnode;
+ var link: **rbnode;
+ var d: *lalr_item;
+ var dir: int;
+ p = nil;
+ link = &i.items;
+ loop {
+ d = (*link) as *lalr_item;
+ if !d {
+ break;
+ }
+ dir = lalr_itemcmp(t, d);
+ if dir < 0 {
+ link = &d.node.left;
+ p = &d.node;
+ } else if dir > 0 {
+ link = &d.node.right;
+ p = &d.node;
+ } else {
+ return nil;
+ }
+ }
+ d = alloc(lc.a, sizeof(*d)) as *lalr_item;
+ d.prod = t.prod;
+ d.alt = t.alt;
+ d.point = t.point;
+ rb_link(&i.items, link, p, &d.node);
+ return d;
+}
+
func lalr_items(lc: *lalr_compiler) {
- // CLOSURE(I)
- // J = I
- // for each [A->a.Bb] in J
- // for each production B->z
- // add [B->.z] to J
- // GOTO(I, X)
- // CLOSURE({[A->aX.b] such that [A->a.Xb] in I})
- // ITEMS(G)
- // C = CLOSURE({[S'->.S]})
- // for each I in C
- // for each symbol x
- // if GOTO(I,x) is not empty
- // add GOTO(I,x) to C
+ var i: *lalr_itemset;
+ var init_state: lalr_item;
+
+ i = lalr_mkitemset(lc);
+ lalr_assoc(lc, i, &init_state);
+ lc.root = i;
+ lc.goto_queue = i;
+
+ loop {
+ i = lc.goto_queue;
+ if !i {
+ break;
+ }
+ lc.goto_queue = i.goto_next;
+ lalr_goto(lc, i);
+ }
+}
+
+func lalr_goto(lc: *lalr_compiler, i: *lalr_itemset) {
+ var t: *lalr_item;
+ var a: *lalr_item;
+ var seen: *lalr_itemset;
+ var queue: *lalr_item;
+ var prod: *lalr_prod;
+ var alt: *lalr_alt;
+ var sym: *lalr_point;
+ var r: lalr_item;
+ var j: int;
+
+ seen = lalr_mkitemset(lc);
+
+ // Queue up the items from the current state
+ t = rb_first(i.items) as *lalr_item;
+ loop {
+ if !t {
+ break;
+ }
+ a = lalr_assoc(lc, seen, t);
+ if a {
+ a.queue_next = queue;
+ queue = a;
+ }
+ t = rb_next(&t.node) as *lalr_item;
+ }
+
+ loop {
+ t = queue;
+ if !t {
+ break;
+ }
+ queue = t.queue_next;
+
+ alt = lc.prod[t.prod].alt[t.alt];
+ if t.point == alt.point_len {
+ continue;
+ }
+
+ // That symbol is the edge in the graph
+ sym = &alt.point[t.point];
+
+ r.prod = t.prod;
+ r.alt = t.alt;
+ r.point = t.point + 1;
+
+ a = lalr_assoc(lc, seen, &r);
+ if a {
+ a.queue_next = queue;
+ queue = a;
+ }
+
+ lalr_linkout(lc, &i.goto_out, sym, &r);
+ if sym.term {
+ continue;
+ }
+
+ prod = lc.prod[sym.id];
+ j = 0;
+ loop {
+ if j == prod.alt_len {
+ break;
+ }
+
+ r.prod = sym.id;
+ r.alt = j;
+ r.point = 0;
+
+ a = lalr_assoc(lc, seen, &r);
+ if a {
+ a.queue_next = queue;
+ queue = a;
+ }
+
+ j = j + 1;
+ }
+ }
+
+ sym = rb_first(i.goto_out) as *lalr_point;
+ loop {
+ if !sym {
+ break;
+ }
+ sym.out = lalr_memoset(lc, sym.out);
+ sym = rb_next(&sym.node) as *lalr_point;
+ }
+}
+
+func lalr_pointcmp(a: *lalr_point, b: *lalr_point): int {
+ if a.term < b.term {
+ return -1;
+ } else if a.term > b.term {
+ return 1;
+ } else if a.id < b.id {
+ return -1;
+ } else if a.id > b.id {
+ return 1;
+ }
+ return 0;
+}
+
+func lalr_linkout(lc: *lalr_compiler, out: **rbnode, sym: *lalr_point, t: *lalr_item) {
+ var p: *rbnode;
+ var link: **rbnode;
+ var d: *lalr_point;
+ var dir: int;
+ p = nil;
+ link = out;
+ loop {
+ d = (*link) as *lalr_point;
+ if !d {
+ break;
+ }
+ dir = lalr_pointcmp(sym, d);
+ if dir < 0 {
+ link = &d.node.left;
+ p = &d.node;
+ } else if dir > 0 {
+ link = &d.node.right;
+ p = &d.node;
+ } else {
+ return;
+ }
+ }
+ d = alloc(lc.a, sizeof(*d)) as *lalr_point;
+ d.term = sym.term;
+ d.id = sym.id;
+ d.name = sym.name;
+ d.out = lalr_mkitemset(lc);
+ rb_link(out, link, p, &d.node);
+ lalr_assoc(lc, d.out, t);
+}
+
+func lalr_memoset(lc: *lalr_compiler, i: *lalr_itemset): *lalr_itemset {
+ var p: *rbnode;
+ var link: **rbnode;
+ var d: *lalr_itemset;
+ var dir: int;
+ p = nil;
+ link = &lc.sets;
+ loop {
+ d = (*link) as *lalr_itemset;
+ if !d {
+ break;
+ }
+ dir = lalr_itemsetcmp(i, d);
+ if dir < 0 {
+ link = &d.node.left;
+ p = &d.node;
+ } else if dir > 0 {
+ link = &d.node.right;
+ p = &d.node;
+ } else {
+ return d;
+ }
+ }
+ rb_link(&lc.sets, link, p, &i.node);
+ i.goto_next = lc.goto_queue;
+ lc.goto_queue = i;
+ return i;
+}
+
+func lalr_showlr(lc: *lalr_compiler) {
+ lalr_showlr2(lc, lc.root);
+}
+
+func lalr_showlr2(lc: *lalr_compiler, i: *lalr_itemset): int {
+ var t: *lalr_item;
+ var sym: *lalr_point;
+ var prod: *lalr_prod;
+ var alt: *lalr_alt;
+ var j: int;
+ var out: *file;
+ var k: int;
+
+ if i.mark {
+ return i.mark;
+ }
+ lc.mark = lc.mark + 1;
+ i.mark = lc.mark;
+
+ fputd(out, i.mark);
+ fputs(out, "{");
+
+ t = rb_first(i.items) as *lalr_item;
+ loop {
+ if !t {
+ break;
+ }
+
+ prod = lc.prod[t.prod];
+ alt = prod.alt[t.alt];
+
+ fputs(out, "[");
+ if prod.name {
+ fputs(out, prod.name);
+ } else {
+ fputd(out, prod.id);
+ }
+
+ fputs(out, "->");
+ k = 0;
+ loop {
+ if k == t.point {
+ fputs(out, "!");
+ }
+ if k == alt.point_len {
+ break;
+ }
+ sym = &alt.point[k];
+ if sym.name {
+ fputs(out, sym.name);
+ } else {
+ fputd(out, sym.id);
+ }
+ k = k + 1;
+ if k != alt.point_len && k != t.point {
+ fputc(out, ' ');
+ }
+ }
+ fputs(out, "]");
+
+ t = rb_next(&t.node) as *lalr_item;
+
+ if t {
+ fputs(out, ",");
+ }
+ }
+
+ fputs(out, "};\n");
+
+ sym = rb_first(i.goto_out) as *lalr_point;
+ loop {
+ if !sym {
+ break;
+ }
+ j = lalr_showlr2(lc, sym.out);
+ fputd(out, i.mark);
+ fputs(out, "->");
+ fputd(out, j);
+ fputs(out, "[");
+ if sym.name {
+ fputs(out, sym.name);
+ } else {
+ fputd(out, sym.id);
+ }
+ fputs(out, "]");
+ fputs(out, ";\n");
+ sym = rb_next(&sym.node) as *lalr_point;
+ }
+
+ return i.mark;
}
