发现

一直在用正则，但是如何写一个正则，没有什么头绪，在网上搜索时发现MuJS，作者发布了一版正则实现，不过是C语言写的，里面使用了不少操作内存地址的用法，调试起来不是很舒服，我想能不能移植到JavaScript上面呢？

移植

这样调试起来会方便许多，随即开始移植，经历了两天左右初版就移植完成了，肯定还有Bug，后续再说吧，总算调试器来不是那么不舒服了。

结果

算是移植成功了吧，大多是按照C语言原写法做的处理，有的地方做了符合JavaScript的处理，但是没有完全按照JavaScript来进行处理，还是有遗憾！仓库在这里。希望对大家有帮助 ！

代码

  1. /* regcomp flags */
  2. const REG_ICASE = 1
  3. const REG_NEWLINE = 2
  5. /* regexec flags */
  6. const REG_NOTBOL = 4
  8. /* limits */
  9. const REG_MAXSUB = 10
  11. const ESCAPES = "BbDdSsWw^$\\.*+?()[]{}|0123456789"
  13. let REPINF = 255
  14. let MAXSUB = REG_MAXSUB
  15. let MAXPROG = (32 << 10)
  17. L_CHAR = 256
  18. L_CCLASS = 257 /* character class */
  19. L_NCCLASS = 258 /* negative character class */
  20. L_NC = 259 /* "(?:" no capture */
  21. L_PLA = 300 /* "(?=" positive lookahead */
  22. L_NLA = 301 /* "(?!" negative lookahead */
  23. L_WORD = 302 /* "\b" word boundary */
  24. L_NWORD = 303 /* "\B" non-word boundary */
  25. L_REF = 304 /* "\1" back-reference */
  26. L_COUNT = 305 /* {M,N} */
  29. /* Parse */
  32. P_CAT = 0
  33. P_ALT = 1
  34. P_REP = 2
  35. P_BOL = 3
  36. P_EOL = 4
  37. P_WORD = 5
  38. P_NWORD = 6
  39. P_PAR = 7
  40. P_PLA = 8
  41. P_NLA = 9
  42. P_ANY = 10
  43. P_CHAR = 11
  44. P_CCLASS = 12
  45. P_NCCLASS = 13
  46. P_REF = 14
  49. /* Compile */
  52. I_END = 0;
  53. I_JUMP = 1;
  54. I_SPLIT = 2;
  55. I_PLA = 3;
  56. I_NLA = 4;
  57. I_ANYNL = 5;
  58. I_ANY = 6;
  59. I_CHAR = 7;
  60. I_CCLASS = 8;
  61. I_NCCLASS = 9;
  62. I_REF = 10;
  63. I_BOL = 11;
  64. I_EOL = 12;
  65. I_WORD = 13;
  66. I_NWORD = 14;
  67. I_LPAR = 15;
  68. I_RPAR = 16
  70. let ccclass_memory = []
  71. for (let i = 0; i < 16; i++) {
  72.     ccclass_memory.push({
  73.         end: 3452816845, // 参考C语言
  74.         spans: Array(64).fill(3452816845)
  75.     })
  76. }
  78. let g = {
  79.     sub: [],
  80.     prog: {
  81.         cclass: ccclass_memory
  82.     }
  83. }
  85. // 由于JavaScript中无法使用指针访问内存地址，在移植C语言程序时，使用数组中放置空对象模拟一片内存空间，暂时先放100个内存单元
  86. let memory = []
  87. for (let i = 0; i < 100; i++) {
  88.     memory.push({})
  89. }
  91. function recomp(pattern, cflags) {
  92.     console.log(pattern)
  93.     let node;
  94.     let split;
  95.     let jump;
  96.     let i = 0;
  97.     let j = 0;
  99.     g.pstart = null;
  100.     // g.prog = {}; // 分配内存
  102.     n = pattern.length * 2;
  103.     if (n > 0) {
  104.         // 分配内存
  105.         g.pstart = g.pend = {}
  106.     }
  107.     g.source = pattern;
  108.     g.ncclass = 0;
  109.     g.nsub = 1;
  110.     for (i = 1; i < MAXSUB; ++i) {
  111.         g.sub[i] = 0;
  112.     }
  114.     g.prog.flags = cflags;
  116.     next()
  117.     node = parsealt();
  118.     if (g.lookahead === ')')
  119.         die("unmatched ')'");
  120.     // if (g.lookahead != 0) // c语言最后为0
  121.     if (g.lookahead != 0) // c语言和JavaScript非严格等号相同 "" == 0 为true
  122.         die("syntax error");
  124.     n = 6 + count(node);
  125.     if (n < 0 || n > MAXPROG)
  126.         die("program too large");
  128.     g.prog.nsub = g.nsub;
  130.     g.prog.start = g.prog.end = memory[0];
  132.     split = emit(g.prog, I_SPLIT);
  133.     let splitIndex = memory.indexOf(split);
  134.     split.x = memory[splitIndex + 3];
  135.     split.y = memory[splitIndex + 1];
  136.     emit(g.prog, I_ANYNL);
  137.     jump = emit(g.prog, I_JUMP);
  138.     jump.x = split;
  139.     emit(g.prog, I_LPAR);
  140.     compile(g.prog, node);
  141.     emit(g.prog, I_RPAR);
  142.     emit(g.prog, I_END);
  144.     // free(g.pstart);
  146.     // if (errorp) *errorp = NULL;
  148.     return g.prog;
  149. }
  152. function toupperrune(c) {
  153.     /* TODO: Add unicode support */
  154.     if (c >= 'a' && c <= 'z')
  155.         return c - 'a' + 'A';
  156.     return c;
  157. }
  159. function canon(c) {
  160.     let u = toupperrune(c);
  161.     if (c >= 128 && u < 128)
  162.         return c;
  163.     return u;
  164. }
  166. function compile(prog, node) {
  167.     let inst, split, jump;
  168.     let i;
  169.     let flag = true
  171.     if (!node)
  172.         return;
  174.     loop:
  175.         while (flag) {
  176.             switch (node.type) {
  177.                 case P_CAT:
  178.                     compile(prog, node.x);
  179.                     node = node.y;
  180.                     continue loop;
  182.                 case P_ALT:
  183.                     split = emit(prog, I_SPLIT);
  184.                     compile(prog, node.x);
  185.                     jump = emit(prog, I_JUMP);
  186.                     compile(prog, node.y);
  187.                     let splitIndex = memory.indexOf(split);
  188.                     let jumpIndex = memory.indexOf(jump);
  189.                     split.x = memory[splitIndex + 1];
  190.                     split.y = memory[jumpIndex + 1];
  191.                     jump.x = prog.end;
  192.                     flag = false;
  193.                     break;
  195.                 case P_REP:
  196.                     for (i = 0; i < node.m; ++i) {
  197.                         inst = prog.end;
  198.                         compile(prog, node.x);
  199.                     }
  200.                     if (node.m == node.n) {
  201.                         flag = false;
  202.                         break;
  203.                     }
  204.                     if (node.n < REPINF) {
  205.                         for (i = node.m; i < node.n; ++i) {
  206.                             split = emit(prog, I_SPLIT);
  207.                             compile(prog, node.x);
  208.                             if (node.ng) {
  209.                                 let splitIndex = memory.indexOf(split);
  210.                                 split.y = memory[splitIndex + 1];
  211.                                 split.x = prog.end;
  212.                             } else {
  213.                                 let splitIndex = memory.indexOf(split);
  214.                                 split.x = memory[splitIndex + 1];
  215.                                 split.y = prog.end;
  216.                             }
  217.                         }
  218.                     } else if (node.m == 0) {
  219.                         split = emit(prog, I_SPLIT);
  220.                         compile(prog, node.x);
  221.                         jump = emit(prog, I_JUMP);
  222.                         if (node.ng) {
  223.                             let splitIndex = memory.indexOf(split);
  224.                             split.y = memory[splitIndex + 1];
  225.                             split.x = prog.end;
  226.                         } else {
  227.                             let splitIndex = memory.indexOf(split);
  228.                             split.x = memory[splitIndex + 1];
  229.                             split.y = prog.end;
  230.                         }
  231.                         jump.x = split;
  232.                     } else {
  233.                         split = emit(prog, I_SPLIT);
  234.                         if (node.ng) {
  235.                             split.y = inst;
  236.                             split.x = prog.end;
  237.                         } else {
  238.                             split.x = inst;
  239.                             split.y = prog.end;
  240.                         }
  241.                     }
  242.                     flag = false;
  243.                     break;
  245.                 case P_BOL:
  246.                     emit(prog, I_BOL);
  247.                     flag = false;
  248.                     break;
  249.                 case P_EOL:
  250.                     emit(prog, I_EOL);
  251.                     flag = false;
  252.                     break;
  253.                 case P_WORD:
  254.                     emit(prog, I_WORD);
  255.                     flag = false;
  256.                     break;
  257.                 case P_NWORD:
  258.                     emit(prog, I_NWORD);
  259.                     flag = false;
  260.                     break;
  262.                 case P_PAR:
  263.                     inst = emit(prog, I_LPAR);
  264.                     inst.n = node.n;
  265.                     compile(prog, node.x);
  266.                     inst = emit(prog, I_RPAR);
  267.                     inst.n = node.n;
  268.                     flag = false;
  269.                     break;
  270.                 case P_PLA:
  271.                     split = emit(prog, I_PLA);
  272.                     compile(prog, node.x);
  273.                     emit(prog, I_END);
  274.                     splitIndex = memory.indexOf(split);
  275.                     split.x = memory[splitIndex + 1];
  276.                     split.y = prog.end;
  277.                     flag = false;
  278.                     break;
  279.                 case P_NLA:
  280.                     split = emit(prog, I_NLA);
  281.                     compile(prog, node.x);
  282.                     emit(prog, I_END);
  283.                     splitIndex = memory.indexOf(split);
  284.                     split.x = memory[splitIndex + 1];
  285.                     split.y = prog.end;
  286.                     flag = false;
  287.                     break;
  289.                 case P_ANY:
  290.                     emit(prog, I_ANY);
  291.                     flag = false;
  292.                     break;
  293.                 case P_CHAR:
  294.                     inst = emit(prog, I_CHAR);
  295.                     inst.c = (prog.flags & REG_ICASE) ? canon(node.c) : node.c;
  296.                     flag = false;
  297.                     break;
  298.                 case P_CCLASS:
  299.                     inst = emit(prog, I_CCLASS);
  300.                     inst.cc = node.cc;
  301.                     flag = false;
  302.                     break;
  303.                 case P_NCCLASS:
  304.                     inst = emit(prog, I_NCCLASS);
  305.                     inst.cc = node.cc;
  306.                     flag = false;
  307.                     break;
  308.                 case P_REF:
  309.                     inst = emit(prog, I_REF);
  310.                     inst.n = node.n;
  311.                     flag = false;
  312.                     break;
  313.             }
  314.         }
  316. }
  318. function count(node) {
  319.     let min, max, n;
  320.     if (!node) return 0;
  321.     switch (node.type) {
  322.         default:
  323.             return 1;
  324.         case P_CAT:
  325.             return count(node.x) + count(node.y);
  326.         case P_ALT:
  327.             return count(node.x) + count(node.y) + 2;
  328.         case P_REP:
  329.             min = node.m;
  330.             max = node.n;
  331.             if (min == max) n = count(node.x) * min;
  332.             else if (max < REPINF) n = count(node.x) * max + (max - min);
  333.             else n = count(node.x) * (min + 1) + 2;
  334.             if (n > MAXPROG) die("program too large");
  335.             return n;
  336.         case P_PAR:
  337.             return count(node.x) + 2;
  338.         case P_PLA:
  339.             return count(node.x) + 2;
  340.         case P_NLA:
  341.             return count(node.x) + 2;
  342.     }
  343. }
  345. function emit(prog, opcode) {
  346.     // Reinst *inst = prog.end++;
  347.     let inst = prog.end; // 先将地址赋值给inst
  348.     let index = memory.indexOf(prog.end); // 在模拟内存中寻找索引
  349.     prog.end = memory[index + 1]; // 将模拟内存中的下一个地址赋值给end
  350.     inst.opcode = opcode;
  351.     inst.n = 0;
  352.     inst.c = 0;
  353.     inst.cc = null;
  354.     inst.x = inst.y = null;
  355.     return inst;
  356. }
  358. function accept(t) {
  359.     if (g.lookahead == t) {
  360.         next();
  361.         return 1;
  362.     }
  363.     return 0;
  364. }
  366. function newnode(type) {
  367.     // let node = g.pend++;
  368.     let node = {}
  369.     node.type = type;
  370.     node.cc = null;
  371.     node.c = 0;
  372.     node.ng = 0;
  373.     node.m = 0;
  374.     node.n = 0;
  375.     node.x = node.y = null;
  376.     return node;
  377. }
  380. function parseatom() {
  381.     let atom;
  382.     if (g.lookahead == L_CHAR) {
  383.         atom = newnode(P_CHAR);
  384.         atom.c = g.yychar;
  385.         next();
  386.         return atom;
  387.     }
  388.     if (g.lookahead == L_CCLASS) {
  389.         atom = newnode(P_CCLASS);
  390.         atom.cc = g.yycc;
  391.         next();
  392.         return atom;
  393.     }
  394.     if (g.lookahead == L_NCCLASS) {
  395.         atom = newnode(P_NCCLASS);
  396.         atom.cc = g.yycc;
  397.         next();
  398.         return atom;
  399.     }
  400.     if (g.lookahead == L_REF) {
  401.         atom = newnode(P_REF);
  402.         if (g.yychar == '' || g.yychar > g.nsub || !g.sub[g.yychar])
  403.             die("invalid back-reference");
  404.         atom.n = g.yychar;
  405.         atom.x = g.sub[g.yychar];
  406.         next();
  407.         return atom;
  408.     }
  409.     if (accept('.'))
  410.         return newnode(P_ANY);
  411.     if (accept('(')) {
  412.         atom = newnode(P_PAR);
  413.         if (g.nsub == MAXSUB)
  414.             die("too many captures");
  415.         atom.n = g.nsub++;
  416.         atom.x = parsealt();
  417.         g.sub[atom.n] = atom;
  418.         if (!accept(')'))
  419.             die("unmatched '('");
  420.         return atom;
  421.     }
  422.     if (accept(L_NC)) {
  423.         atom = parsealt();
  424.         if (!accept(')'))
  425.             die("unmatched '('");
  426.         return atom;
  427.     }
  428.     if (accept(L_PLA)) {
  429.         atom = newnode(P_PLA);
  430.         atom.x = parsealt();
  431.         if (!accept(')'))
  432.             die("unmatched '('");
  433.         return atom;
  434.     }
  435.     if (accept(L_NLA)) {
  436.         atom = newnode(P_NLA);
  437.         atom.x = parsealt();
  438.         if (!accept(')'))
  439.             die("unmatched '('");
  440.         return atom;
  441.     }
  442.     die("syntax error");
  443.     return null;
  444. }
  446. function parserep() {
  447.     let atom;
  449.     if (accept('^')) return newnode(P_BOL);
  450.     if (accept('$')) return newnode(P_EOL);
  451.     if (accept(L_WORD)) return newnode(P_WORD);
  452.     if (accept(L_NWORD)) return newnode(P_NWORD);
  454.     atom = parseatom();
  455.     if (g.lookahead == L_COUNT) {
  456.         let min = g.yymin,
  457.             max = g.yymax;
  458.         next();
  459.         if (max < min)
  460.             die("invalid quantifier");
  461.         return newrep(atom, accept('?'), min, max);
  462.     }
  463.     if (accept('*')) return newrep(atom, accept('?'), 0, REPINF);
  464.     if (accept('+')) return newrep(atom, accept('?'), 1, REPINF);
  465.     if (accept('?')) return newrep(atom, accept('?'), 0, 1);
  466.     return atom;
  467. }
  469. function parsecat() {
  470.     let cat, head, tail = {};
  471.     if (g.lookahead && g.lookahead != '|' && g.lookahead != ')') {
  472.         /* Build a right-leaning tree by splicing in new 'cat' at the tail. */
  473.         head = parserep();
  474.         tail.point = head; // ??
  475.         let prev = head;
  476.         while (g.lookahead && g.lookahead != '|' && g.lookahead != ')') {
  477.             cat = newnode(P_CAT);
  478.             cat.x = tail.point;
  479.             cat.y = parserep();
  481.             if (prev.x === tail.point) {
  482.                 tail.all.x = cat
  483.                 prev = cat
  484.             } else if (prev.y === tail.point) {
  485.                 tail.all.y = cat
  486.                 prev = cat
  487.             } else if (prev === tail.point) {
  488.                 head = cat
  489.                 prev = cat
  490.             }
  491.             tail.point = cat.y;
  492.             tail.all = cat;
  493.         }
  494.         return head;
  495.     }
  496.     return null;
  497. }
  499. function empty(node) {
  500.     if (!node) return 1;
  501.     switch (node.type) {
  502.         default:
  503.             return 1;
  504.         case P_CAT:
  505.             return empty(node.x) && empty(node.y);
  506.         case P_ALT:
  507.             return empty(node.x) || empty(node.y);
  508.         case P_REP:
  509.             return empty(node.x) || node.m == 0;
  510.         case P_PAR:
  511.             return empty(node.x);
  512.         case P_REF:
  513.             return empty(node.x);
  514.         case P_ANY:
  515.         case P_CHAR:
  516.         case P_CCLASS:
  517.         case P_NCCLASS:
  518.             return 0;
  519.     }
  520. }
  522. function newrep(atom, ng, min, max) {
  523.     let rep = newnode(P_REP);
  524.     if (max == REPINF && empty(atom))
  525.         die("infinite loop matching the empty string");
  526.     rep.ng = ng;
  527.     rep.m = min;
  528.     rep.n = max;
  529.     rep.x = atom;
  530.     return rep;
  531. }
  533. function parsealt() {
  534.     let alt, x;
  535.     alt = parsecat();
  536.     while (accept('|')) {
  537.         x = alt;
  538.         alt = newnode(P_ALT);
  539.         alt.x = x;
  540.         alt.y = parsecat();
  541.     }
  542.     return alt;
  543. }
  545. function next() {
  546.     g.lookahead = lex();
  547. }
  549. function chartorune(r, s, key) {
  550.     /* TODO: Add UTF-8 decoding */
  551.     r[key] = s.slice(0, 1);
  552.     return 1;
  553. }
  556. function incclasscanon(cc, c) {
  557.     let p, r;
  558.     for (p = cc.spans; p < cc.end; p += 2)
  559.         for (r = p[0]; r <= p[1]; ++r)
  560.             if (c == canon(r))
  561.                 return 1;
  562.     return 0;
  563. }
  565. function incclass(cc, c) {
  566.     let p;
  567.     // for (p = cc.spans; p < cc.end; p += 2)
  568.     for (p = 0; p < cc.end; p += 2)
  569.         if (cc.spans[p] <= c && c <= cc.spans[p + 1])
  570.             return 1;
  571.     return 0;
  572. }
  574. function isnewline(c) {
  575.     return c == 0xA || c == 0xD || c == 0x2028 || c == 0x2029;
  576. }
  578. function iswordchar(c) {
  579.     return c == '_' ||
  580.         (c >= 'a' && c <= 'z') ||
  581.         (c >= 'A' && c <= 'Z') ||
  582.         (c >= '0' && c <= '9');
  583. }
  585. function die(message) {
  586.     g.error = message;
  587.     throw new Error(message);
  588.     // longjmp(g.kaboom, 1);
  589. }
  591. function hex(c) {
  592.     if (c >= '0' && c <= '9') return c - '0';
  593.     if (c >= 'a' && c <= 'f') return c - 'a' + 0xA;
  594.     if (c >= 'A' && c <= 'F') return c - 'A' + 0xA;
  595.     die("invalid escape sequence");
  596.     return 0;
  597. }
  599. function nextrune() {
  600.     g.source = g.source.slice(chartorune(g, g.source, "yychar"), g.source.length);
  601.     if (g.yychar == '\\') {
  602.         g.source = g.source.slice(chartorune(g, g.source, "yychar"), g.source.length);
  603.         switch (g.yychar) {
  604.             case 0:
  605.                 die("unterminated escape sequence");
  606.                 break;
  607.             case 'f':
  608.                 g.yychar = '\f';
  609.                 return 0;
  610.             case 'n':
  611.                 g.yychar = '\n';
  612.                 return 0;
  613.             case 'r':
  614.                 g.yychar = '\r';
  615.                 return 0;
  616.             case 't':
  617.                 g.yychar = '\t';
  618.                 return 0;
  619.             case 'v':
  620.                 g.yychar = '\v';
  621.                 return 0;
  622.             case 'c':
  623.                 g.yychar = (g.source++) & 31;
  624.                 return 0;
  625.             case 'x':
  626.                 g.yychar = hex(g.source++) << 4;
  627.                 g.yychar += hex(g.source++);
  628.                 if (g.yychar == '') { // ??
  629.                     g.yychar = '0';
  630.                     return 1;
  631.                 }
  632.                 return 0;
  633.             case 'u':
  634.                 g.yychar = hex(g.source++) << 12;
  635.                 g.yychar += hex(g.source++) << 8;
  636.                 g.yychar += hex(g.source++) << 4;
  637.                 g.yychar += hex(g.source++);
  638.                 if (g.yychar == '') { // ??
  639.                     g.yychar = '0';
  640.                     return 1;
  641.                 }
  642.                 return 0;
  643.         }
  644.         if (ESCAPES.includes(g.yychar)) {
  645.             return 1;
  646.         }
  647.         // if (strchr(ESCAPES, g.yychar)) // strchr 该函数返回在字符串 str 中第一次出现字符 c 的位置，如果未找到该字符则返回 NULL。
  648.         //     return 1;
  649.         if (isunicodeletter(g.yychar) || g.yychar == '_') /* check identity escape */
  650.             die("invalid escape character");
  651.         return 0;
  652.     }
  653.     return 0;
  654. }
  656. function newcclass() {
  657.     // #define nelem(a) (sizeof (a) / sizeof (a)[0]) 求数组长度
  658.     // if (g.ncclass >= nelem(g.prog.cclass))
  659.     if (g.ncclass >= g.prog.cclass.length)
  660.         die("too many character classes");
  661.     // g.yycc = g.prog.cclass + g.ncclass++;
  662.     g.yycc = ccclass_memory[g.ncclass++];
  663.     g.yycc.end = g.yycc.spans[0]; // ??
  664.     rangeIndex = 0; // 新的[]区间，索引清零
  665. }
  667. function addranges_d() {
  668.     addrange('0', '9');
  669. }
  671. function addranges_D() {
  672.     addrange(0, '0' - 1);
  673.     addrange('9' + 1, 0xFFFF);
  674. }
  676. function addranges_W() {
  677.     addrange(0, '0' - 1);
  678.     addrange('9' + 1, 'A' - 1);
  679.     addrange('Z' + 1, '_' - 1);
  680.     addrange('_' + 1, 'a' - 1);
  681.     addrange('z' + 1, 0xFFFF);
  682. }
  684. function addranges_w() {
  685.     addrange('0', '9');
  686.     addrange('A', 'Z');
  687.     addrange('_', '_');
  688.     addrange('a', 'z');
  689. }
  691. function addranges_S() {
  692.     addrange(0, 0x9 - 1);
  693.     addrange(0x9 + 1, 0xA - 1);
  694.     addrange(0xD + 1, 0x20 - 1);
  695.     addrange(0x20 + 1, 0xA0 - 1);
  696.     addrange(0xA0 + 1, 0x2028 - 1);
  697.     addrange(0x2029 + 1, 0xFEFF - 1);
  698.     addrange(0xFEFF + 1, 0xFFFF);
  699. }
  701. function addranges_s() {
  702.     addrange(0x9, 0x9);
  703.     addrange(0xA, 0xD);
  704.     addrange(0x20, 0x20);
  705.     addrange(0xA0, 0xA0);
  706.     addrange(0x2028, 0x2029);
  707.     addrange(0xFEFF, 0xFEFF);
  708. }
  710. let rangeIndex = 0; // 为了避免复杂，以JavaScript的方式实现了相同功能
  712. function addrange(a, b) {
  713.     if (a > b)
  714.         die("invalid character class range");
  715.     // if (g.yycc.end + 2 == g.yycc.spans + nelem(g.yycc.spans))
  716.     //      die("too many character class ranges");
  717.     // g.yycc.end++ = a;
  718.     // g.yycc.end++ = b;
  720.     if (rangeIndex + 2 == 1 + g.yycc.spans.length) { // ??
  721.         die("too many character class ranges");
  722.     }
  724.     // ??
  725.     g.yycc.spans[rangeIndex++] = a;
  726.     g.yycc.spans[rangeIndex++] = b;
  727.     g.yycc.end = rangeIndex; // 无法访问指针，使用JavaScript的方式解决
  728. }
  730. function isalpharune(c) {
  731.     /* TODO: Add unicode support */
  732.     return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z');
  733. }
  735. function isunicodeletter(c) {
  736.     return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || isalpharune(c);
  737. }
  739. function lexclass() {
  740.     let type = L_CCLASS;
  741.     let quoted, havesave, havedash;
  742.     let save = 0;
  744.     newcclass();
  746.     quoted = nextrune();
  747.     if (!quoted && g.yychar == '^') {
  748.         type = L_NCCLASS;
  749.         quoted = nextrune();
  750.     }
  752.     havesave = havedash = 0;
  753.     for (;;) {
  754.         // if (g.yychar == 0)
  755.         if (g.yychar == '')
  756.             die("unterminated character class");
  757.         if (!quoted && g.yychar == ']')
  758.             break;
  760.         if (!quoted && g.yychar == '-') {
  761.             if (havesave) {
  762.                 if (havedash) {
  763.                     addrange(save, '-');
  764.                     havesave = havedash = 0;
  765.                 } else {
  766.                     havedash = 1;
  767.                 }
  768.             } else {
  769.                 save = '-';
  770.                 havesave = 1;
  771.             }
  772.         } else if (quoted && "DSWdsw".includes(g.yychar)) {
  773.             if (havesave) {
  774.                 addrange(save, save);
  775.                 if (havedash)
  776.                     addrange('-', '-');
  777.             }
  778.             switch (g.yychar) {
  779.                 case 'd':
  780.                     addranges_d();
  781.                     break;
  782.                 case 's':
  783.                     addranges_s();
  784.                     break;
  785.                 case 'w':
  786.                     addranges_w();
  787.                     break;
  788.                 case 'D':
  789.                     addranges_D();
  790.                     break;
  791.                 case 'S':
  792.                     addranges_S();
  793.                     break;
  794.                 case 'W':
  795.                     addranges_W();
  796.                     break;
  797.             }
  798.             havesave = havedash = 0;
  799.         } else {
  800.             if (quoted) {
  801.                 if (g.yychar == 'b')
  802.                     g.yychar = '\b';
  803.                 else if (g.yychar == '0')
  804.                     g.yychar = 0;
  805.                 /* else identity escape */
  806.             }
  807.             if (havesave) {
  808.                 if (havedash) {
  809.                     addrange(save, g.yychar);
  810.                     havesave = havedash = 0;
  811.                 } else {
  812.                     addrange(save, save);
  813.                     save = g.yychar;
  814.                 }
  815.             } else {
  816.                 save = g.yychar;
  817.                 havesave = 1;
  818.             }
  819.         }
  821.         quoted = nextrune();
  822.     }
  824.     if (havesave) {
  825.         addrange(save, save);
  826.         if (havedash)
  827.             addrange('-', '-');
  828.     }
  830.     return type;
  831. }
  835. function lex() {
  836.     let quoted = nextrune();
  837.     if (quoted) {
  838.         switch (g.yychar) {
  839.             case 'b':
  840.                 return L_WORD;
  841.             case 'B':
  842.                 return L_NWORD;
  843.             case 'd':
  844.                 newcclass();
  845.                 addranges_d();
  846.                 return L_CCLASS;
  847.             case 's':
  848.                 newcclass();
  849.                 addranges_s();
  850.                 return L_CCLASS;
  851.             case 'w':
  852.                 newcclass();
  853.                 addranges_w();
  854.                 return L_CCLASS;
  855.             case 'D':
  856.                 newcclass();
  857.                 addranges_d();
  858.                 return L_NCCLASS;
  859.             case 'S':
  860.                 newcclass();
  861.                 addranges_s();
  862.                 return L_NCCLASS;
  863.             case 'W':
  864.                 newcclass();
  865.                 addranges_w();
  866.                 return L_NCCLASS;
  867.             case '0':
  868.                 g.yychar = 0;
  869.                 return L_CHAR;
  870.         }
  871.         if (g.yychar >= '0' && g.yychar <= '9') {
  872.             g.yychar -= '0';
  873.             if (g.source >= '0' && g.source <= '9')
  874.                 g.yychar = g.yychar * 10 + g.source++ - '0';
  875.             return L_REF;
  876.         }
  877.         return L_CHAR;
  878.     }
  880.     switch (g.yychar) {
  881.         case 0: // C里面最后是0
  882.         case "":
  883.         case '$':
  884.         case ')':
  885.         case '*':
  886.         case '+':
  887.         case '.':
  888.         case '?':
  889.         case '^':
  890.         case '|':
  891.             return g.yychar;
  892.     }
  894.     if (g.yychar == '{')
  895.         return lexcount();
  896.     if (g.yychar == '[')
  897.         return lexclass();
  898.     if (g.yychar == '(') {
  899.         if (g.source[0] == '?') {
  900.             if (g.source[1] == ':') {
  901.                 // g.source += 2;
  902.                 g.source = g.source.slice(2, g.source.length);
  903.                 return L_NC;
  904.             }
  905.             if (g.source[1] == '=') {
  906.                 // g.source += 2;
  907.                 g.source = g.source.slice(2, g.source.length);
  908.                 return L_PLA;
  909.             }
  910.             if (g.source[1] == '!') {
  911.                 // g.source += 2;
  912.                 g.source = g.source.slice(2, g.source.length);
  913.                 return L_NLA;
  914.             }
  915.         }
  916.         return '(';
  917.     }
  919.     return L_CHAR;
  920. }
  922. function strncmpcanon(a, b, n) {
  923.     let ra, rb;
  924.     let c;
  925.     let tempra = {
  926.         ra: ra
  927.     }
  928.     let temprb = {
  929.         rb: rb
  930.     }
  931.     while (n--) {
  932.         if (!a) return -1;
  933.         if (!b) return 1;
  934.         a = a.slice(chartorune(tempra, a, "ra"), a.length);
  935.         ra = tempra.ra;
  936.         b = b.slice(chartorune(temprb, b, "rb"), b.length);
  937.         rb = temprb.rb;
  938.         c = canon(ra) - canon(rb);
  939.         if (c)
  940.             return c;
  941.     }
  942.     return 0;
  943. }
  945. function strncmp(str1, str2, n) {
  946.     str1 = str1.substring(0, n);
  947.     str2 = str2.substring(0, n);
  948.     return ((str1 == str2) ? 0 :
  949.         ((str1 > str2) ? 1 : -1));
  950. }
  952. function match(pc, sp, bol, flags, out) {
  953.     let scratch;
  954.     let i;
  955.     let c;
  956.     let tempc = {
  957.         c: c
  958.     }
  959.     let pcIndex;
  961.     for (;;) {
  962.         switch (pc.opcode) {
  963.             case I_END:
  964.                 return 1;
  965.             case I_JUMP:
  966.                 pc = pc.x;
  967.                 break;
  968.             case I_SPLIT:
  969.                 scratch = out;
  970.                 if (match(pc.x, sp, bol, flags, scratch)) {
  971.                     out = scratch;
  972.                     return 1;
  973.                 }
  974.                 pc = pc.y;
  975.                 break;
  977.             case I_PLA:
  978.                 if (!match(pc.x, sp, bol, flags, out))
  979.                     return 0;
  980.                 pc = pc.y;
  981.                 break;
  982.             case I_NLA:
  983.                 scratch = out;
  984.                 if (match(pc.x, sp, bol, flags, scratch))
  985.                     return 0;
  986.                 pc = pc.y;
  987.                 break;
  989.             case I_ANYNL:
  990.                 sp = sp.slice(chartorune(tempc, sp, "c"), sp.length);
  991.                 c = tempc.c;
  992.                 if (c == '') // JavaScript中不使用严格等号 "" == 0 为true
  993.                     return 0;
  994.                 pcIndex = memory.indexOf(pc);
  995.                 pc = memory[pcIndex + 1];
  996.                 break;
  997.             case I_ANY:
  998.                 sp = sp.slice(chartorune(tempc, sp, "c"), sp.length);
  999.                 c = tempc.c;
  1000.                 if (c == '')
  1001.                     return 0;
  1002.                 if (isnewline(c))
  1003.                     return 0;
  1004.                 pcIndex = memory.indexOf(pc);
  1005.                 pc = memory[pcIndex + 1];
  1006.                 break;
  1007.             case I_CHAR:
  1008.                 sp = sp.slice(chartorune(tempc, sp, "c"), sp.length);
  1009.                 c = tempc.c;
  1010.                 if (c == '')
  1011.                     return 0;
  1012.                 if (flags & REG_ICASE)
  1013.                     c = canon(c);
  1014.                 if (c != pc.c)
  1015.                     return 0;
  1016.                 pcIndex = memory.indexOf(pc);
  1017.                 pc = memory[pcIndex + 1];
  1018.                 break;
  1019.             case I_CCLASS:
  1020.                 sp = sp.slice(chartorune(tempc, sp, "c"), sp.length);
  1021.                 c = tempc.c;
  1022.                 if (c == '')
  1023.                     return 0;
  1024.                 if (flags & REG_ICASE) {
  1025.                     if (!incclasscanon(pc.cc, canon(c)))
  1026.                         return 0;
  1027.                 } else {
  1028.                     if (!incclass(pc.cc, c))
  1029.                         return 0;
  1030.                 }
  1031.                 pcIndex = memory.indexOf(pc);
  1032.                 pc = memory[pcIndex + 1];
  1033.                 break;
  1034.             case I_NCCLASS:
  1035.                 sp = sp.slice(chartorune(tempc, sp, "c"), sp.length);
  1036.                 c = tempc.c;
  1037.                 if (c == '')
  1038.                     return 0;
  1039.                 if (flags & REG_ICASE) {
  1040.                     if (incclasscanon(pc.cc, canon(c)))
  1041.                         return 0;
  1042.                 } else {
  1043.                     if (incclass(pc.cc, c))
  1044.                         return 0;
  1045.                 }
  1046.                 pcIndex = memory.indexOf(pc);
  1047.                 pc = memory[pcIndex + 1];
  1048.                 break;
  1049.             case I_REF:
  1050.                 i = out.sub[pc.n].sp.length - out.sub[pc.n].ep.length;
  1051.                 if (flags & REG_ICASE) {
  1052.                     if (strncmpcanon(sp, out.sub[pc.n].sp, i))
  1053.                         return 0;
  1054.                 } else {
  1055.                     if (strncmp(sp, out.sub[pc.n].sp, i))
  1056.                         return 0;
  1057.                 }
  1058.                 if (i > 0)
  1059.                     sp = sp.slice(i, sp.length);
  1060.                 pcIndex = memory.indexOf(pc);
  1061.                 pc = memory[pcIndex + 1];
  1062.                 break;
  1064.             case I_BOL:
  1065.                 if (sp == bol && !(flags & REG_NOTBOL)) {
  1066.                     pcIndex = memory.indexOf(pc);
  1067.                     pc = memory[pcIndex + 1];
  1068.                     break;
  1069.                 }
  1070.                 if (flags & REG_NEWLINE) {
  1071.                     // 如果有Bug，修复建议，sp > bol之间的比较，在C语言中，sp与bol是char*指针，即内存地址，
  1072.                     // sp > bol若为true，则表示sp的内存地址（指针）较大，实际存储的有效字符个数（内存地址开头到\0之间的字符）是sp比bol少的
  1073.                     // 这和JavaScript里面字符串比较很大不同
  1074.                     // if (sp > bol && isnewline(sp[-1])) { // 原C代码
  1075.                     if (sp.length < bol.length /*改为字符串长度比较*/ && isnewline(sp[-1])) {
  1076.                         pcIndex = memory.indexOf(pc);
  1077.                         pc = memory[pcIndex + 1];
  1078.                         break;
  1079.                     }
  1080.                 }
  1081.                 return 0;
  1082.             case I_EOL:
  1083.                 if (sp == '') { // 在C语言和JavaScript非严格等号里面成立
  1084.                     pcIndex = memory.indexOf(pc);
  1085.                     pc = memory[pcIndex + 1];
  1086.                     break;
  1087.                 }
  1088.                 if (flags & REG_NEWLINE) {
  1089.                     if (isnewline(sp)) {
  1090.                         pcIndex = memory.indexOf(pc);
  1091.                         pc = memory[pcIndex + 1];
  1092.                         break;
  1093.                     }
  1094.                 }
  1095.                 return 0;
  1096.             case I_WORD:
  1097.                 // i = sp > bol && iswordchar(sp[-1]);
  1098.                 if (sp.length < bol.length) {
  1099.                     let index = bol.indexOf(sp);
  1100.                     i = iswordchar(bol[index - 1]);
  1101.                 }
  1102.                 i ^= iswordchar(sp[0]);
  1103.                 if (!i)
  1104.                     return 0;
  1105.                 pcIndex = memory.indexOf(pc);
  1106.                 pc = memory[pcIndex + 1];
  1107.                 break;
  1108.             case I_NWORD:
  1109.                 // i = sp > bol && iswordchar(sp[-1]);
  1110.                 if (sp.length < bol.length) {
  1111.                     let index = bol.indexOf(sp);
  1112.                     i = iswordchar(bol[index - 1]);
  1113.                 }
  1114.                 i ^= iswordchar(sp[0]);
  1115.                 if (i)
  1116.                     return 0;
  1117.                 pcIndex = memory.indexOf(pc);
  1118.                 pc = memory[pcIndex + 1];
  1119.                 break;
  1121.             case I_LPAR:
  1122.                 out.sub[pc.n].sp = sp;
  1123.                 pcIndex = memory.indexOf(pc);
  1124.                 pc = memory[pcIndex + 1];
  1125.                 break;
  1126.             case I_RPAR:
  1127.                 out.sub[pc.n].ep = sp;
  1128.                 pcIndex = memory.indexOf(pc);
  1129.                 pc = memory[pcIndex + 1];
  1130.                 break;
  1131.             default:
  1132.                 return 0;
  1133.         }
  1134.     }
  1135. }
  1137. function regexec(prog, sp, sub, eflags) {
  1138.     let scratch;
  1139.     let i;
  1141.     if (!sub)
  1142.         sub = scratch;
  1144.     sub.nsub = prog.nsub;
  1145.     for (i = 0; i < MAXSUB; ++i) {
  1146.         if (!sub.sub[i]) {
  1147.             sub.sub[i] = {}
  1148.         }
  1149.         // sub.sub[i].sp = sub.sub[i].ep = null;
  1150.         sub.sub[i].sp = sub.sub[i].ep = "";
  1151.     }
  1153.     return !match(prog.start, sp, sp, prog.flags | eflags, sub);
  1154. }
  1156. function main() {
  1157.     let m = {
  1158.         sub: []
  1159.     }
  1161.     // let p = recomp(String.raw `.+\/(.+\..+)$`, 0);
  1162.     // let s = "/root/temp/hello.mp3";
  1164.     // let p = recomp(String.raw `\B..`, 0);
  1165.     // let s = "noonday";
  1167.     let p = recomp(String.raw `^((?:[_a-zA-Z])+(?:[_a-zA-Z\d])*)[ ]*(?:\((.*)\))`, 0);
  1168.     let s = "_foo0_  (x,y)";
  1170.     console.log("nsub =", p.nsub)
  1171.     if (!regexec(p, s, m, 0)) {
  1172.         for (i = 0; i < m.nsub; ++i) {
  1173.             let n = m.sub[i].sp.length - m.sub[i].ep.length;
  1174.             if (n > 0)
  1175.                 console.log("match %d: s=%d e=%d n=%d '%s'\n", i, (s.length - m.sub[i].sp.length), (s.length - m.sub[i].ep.length), n, m.sub[i].sp.slice(0, n));
  1176.             else
  1177.                 console.log("match %d: n=0 ''\n", i);
  1178.         }
  1179.     } else {
  1180.         console.log("no match\n");
  1181.     }
  1183. }
  1185. main()