注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Tsecer的回音岛

Tsecer的博客

 
 
 

日志

 
 

GNU grep实现的一些相关问题  

2014-08-27 20:47:02|  分类: GNU工具链源码分 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一、DFA匹配的结束态处理
在学习编译原理中正则表达式实现时就可以预见到,对于使用NFA-->>DFA实现的正则表达式来说,它对输入的匹配默认使用的是最长匹配。对于常见的a.*b类型模式,accbbbbbb类型输入,遇到第一个b时,此时按照传统的正则表达式,此时DFA已经遇到了一个包含了结束状态的DFA节点,此时整个匹配已经可以结束。但是事实上通过验证C库中的正则表达式实现可以发现,这个匹配的整个结果依然是整个输入字符串,而不是accb这个最早到达终点态的状态。既然如此,glibc中对于这个地方的实现就需要做特殊处理,而不是使用DFA默认的匹配及终止规则(也就是教科书中描述的转换及匹配方法)。
看下glibc中以经典的ken Thompson实现,它对于包含结束状态的这种情况的特殊处理代码为glibc-2.6\posix\regexec.c:
check_matching (re_match_context_t *mctx, int fl_longest_match,
int *p_match_first)
  while (!re_string_eoi (&mctx->input))
    {
……

      if (cur_state == NULL)
{
 /* Reached the invalid state or an error.  Try to recover a valid
    state using the state log, if available and if we have not
    already found a valid (even if not the longest) match.  */
 if (BE (err != REG_NOERROR, 0))
   return -2;

 if (mctx->state_log == NULL
     || (match && !fl_longest_match)
     || (cur_state = find_recover_state (&err, mctx)) == NULL)
   break;
}
……
      if (cur_state->halt)
{
 /* Reached a halt state.
    Check the halt state can satisfy the current context.  */
 if (!cur_state->has_constraint
     || check_halt_state_context (mctx, cur_state,
  re_string_cur_idx (&mctx->input)))
   {
     /* We found an appropriate halt state.  */
     match_last = re_string_cur_idx (&mctx->input);
     match = 1;

     /* We found a match, do not modify match_first below.  */
     p_match_first = NULL;
     if (!fl_longest_match)
break;
   }
}
……
    }

  if (p_match_first)
    *p_match_first += next_start_idx;

  return match_last;
这里可以看到对于结束状态(代码中为“停机”halt状态)进行了特殊处理,当遇到结束状态时并不是马上结束,而是先记下当前匹配的结束位置,再继续进行状态转换(也就是匹配字符串的移入),直到遇到整个输入的结束(re_string_eoi (&mctx->input))或者当前模式的字符串不能被状态接受未知(cur_state == NULL)。
二、子表达式(subexp)及前向引用(backref)
这种表达式通常以a(.*)\1的形式出现,其中的(.*)就是子表达式,而接下来的backref就是对之前已经匹配的子表达式的引用。在正则表达式解析的过程中,'('使用一个OP_OPEN_SUBEXP节点表示,')'使用一个OP_CLOSE_SUBEXP节点表示,'\n'类型的前向引用使用一个OP_BACK_REF节点表示。在语法匹配过程中,对于子表达式开始和结束的匹配,需要记录下子表达式匹配的位置。这个具体操作在
check_matching-->>merge_state_with_log--->>check_subexp_matching_top--->>match_ctx_add_subtop
在其中记录了匹配开始的位置
  mctx->sub_tops[mctx->nsub_tops]->node = node;
  mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
如果正则表达式中使用了backref,它的一个重要特点是真正的匹配内容在匹配完成之前没有办法被确定,进而DFA无法在读入待匹配字符串之前完整构建出来。
三、GNU grep的内部执行流程
对于fgrep,也就是纯粹字符串匹配的表达式,它执行的是kwset的匹配,这个匹配在接下来再详细讨论。对于包含正则表达式的匹配,grep根据grep的特点同样做了优化,由于默认情况下,一行中只要有一个匹配被满足,整行就会处于被选中状态,这里不用考虑最长匹配的问题;对于要求只显示匹配内容的调用(-o)或者高亮显示匹配内容的配置,根据正则表达式匹配的规则,此时必须进行最长匹配,并且必须显示匹配的内容。
在grep的执行过程中,可能进行三个步骤的匹配,首先根据编译生成的dfa来生成一条每个匹配必定包含的字串dfamust,即包含该dfamust字串是输入匹配的必要条件,这个dfamust的字串在dfa生成之后通过dfamust来生成,在生成时选用最为谨慎的条件,例如对于模式'a\(a*\|c*\)b'来说,它生成的must为单字符’a‘。对于一个输入,如果它没有包含must字符串,可以直接过滤掉该行输入。
通过kwset匹配之后,再次进行DFA匹配,这个DFA匹配有一个问题,就是说在匹配的过程中它没有处理最长匹配的问题(它同样也不处理前向引用问题,即\1之类的引用),这一点和POSIX中匹配的规则不符,但是如果此次调用是只要匹配就显示整行的话,只要匹配任意一个终态即可结束。如果dfaexec没有匹配,也可以返回本行匹配失败。
如果DFA匹配成功并且其中包含有前向引用则可以直接返回成功,如果包含前向引用,此时需要经过最为严格的regexec匹配,这个函数在glibc中默认带有该函数的实现,但是grep中也自带了一个regexc文件,默认这个文件并不生效,可以在配置configure时通过--with-included-regex来使能grep自带reg库。在这个函数中并没有处理只显示匹配内容的-o选项,这个选项是在prline函数,也就是输出匹配行时再进行严格的regexec匹配。
四、GNU grep中kwset方法的基本原理
1、关键字集合匹配
其中关键的思想来自于ftp://163.13.200.222/assistant/bearhero/prog/%A8%E4%A5%A6/ac_bm.pdf这篇论文《Efficient String Matching:  An Aid to Bibliographic Search》,这种算法在wiki上也叫做Aho–Corasick string matching algorithm算法。这篇文章的第一作者是Alfred Aho,是经典编译原理教材龙书作者,也是文本处理工具awk中a所代表的意义。文章发表在1975年,那个时候中国还处在那个十年没有结束的时期。文章中的伪代码看起来更像是PASCAL语言,在这篇文章中,作者描述了从一个文件中搜索一组关键字(keyword set)的一种算法,它是经典的单字符串匹配的KMP算法向字符串集合的一种扩充。
其思想是根据关键字列表,构造出一个确定有限状态自动机,从而在匹配失败的时候不用从头开始逐次匹配,而是使用当前到达的信息来减少不必要的冗余匹配检测。在该状态机中,有三种类型关键的函数(跳转表),a)、goto函数。到达某个节点之后,如果输入字符串能够被接收,则执行goto指令,也就是状态机的状态转换;b)、fail函数。如果失败,并不是pattern和string均回退到上次开始位置,而是利用计算的历史信息来复用尽可能多的信息。和KMP算法一样,这个算法改进的关键在于这个fail的跳转位置。c)、匹配状态。如果到达状态机的一个终止状态,则表示成功匹配了一个关键字,那么该关键字就可以输出了,也就是完成了一次匹配动作。
fail函数的构建使用了广度优先搜索算法。fail函数的本质是说:对于state s,假设fail(s)=n,从根节点到n节点匹配的字符串为strn,从根节点到s节点生成的字符串为strs,则strn是所有从根节点到中间节点生成的字符串中和strs后半部分(以strs最后一个字符结束)匹配度最长的字符串,这一点和KMP算法相同,对于状态s,它的下一个关键字使用的字符为a,当a不被匹配时,首先回退到s的fail状态fail(s),如果fail(s)能够接受a,则新状态的fail状态就是g(fail(s),a),fail(s)不接收a,需要再次回退,并尝试a,直到回到原点或者a被接收。
以作者给出的例子,关键字为{he,she,hers,his},说明下第一个fail状态是如何生成的,对于"she"这个字符,"s"解析之后遇到h,由于fail("s")是原点,并且原点可以接收"h",当前态g("s")面对"h"也可以被接收,所以fail("sh")就是root到"h"这个状态;之后的生成就可以在这个归纳的基础上进一步增加。
2、kwset使用的方法
在grep的kwset的注释中,说明了它主要使用的是《A String Matching Algorithm Fast on the Average》这篇文章,这篇文章是汇总了BM匹配方法和AHO算法,主要的改进在于状态机的构建不是以KMP算法为基础进行扩展,而是使用另一种更加高效的BM算法,BM算法的特点就是匹配是从右向左开始的,所以状态机的根节点到叶子节点也是关键字的逆序排列。作者说的这篇论文在网络上可以搜索到,但不是很清晰,而且里面的描述没有前面说的文章描述的那么清楚,所以这里只是大致理解它的实现思路,细节没有进一步深入。
五、grep内置正则表达式处理
1、指令集及状态机
grep自带的正则表达式匹配库直观上来说就是将一个输入的正则表达式转换为一个虚拟机指令,这些指令列在regex.c文件的re_opcode_t枚举类型中。这个虚拟机指令的生成有一个特点,就是没有使用递归,在pattern解析的过程中直接生成虚拟机指令。这样的问题就在于一些跳转位置的backpatch实现会比较麻烦。通常来说,汇编指令对于if (cond) {doSomething}的处理是 test cond; jump after_doSometing if cond not true。如果在pattern解析的时候直接生成这种跳转指令,那么after_doSometing的位置在这条指令生成的时候还不能确定,回填是一个大问题,加上pattern中相同类型内容的递归包含结构等问题。
2、虚拟机指令生成的两个基本操作
该虚拟机编译器使用两种基本的指令生成动作,一种是直接存储,也就是覆盖式添加指令(store_XX),另一种是插入式(insert_XX)指令。它们的区别在于insert时首先会将插入位置当前代码到当前结束位置的代码整体向后移动,空出待插入指令占用的位置。如果指令的生成能够保证当前所有跳转指令都使用相对跳转,并且不会有跳转跨越插入代码位置,那么这个插入动作并不会影响代码逻辑。
3、失败时回溯(backtrace)
对于pattern中的匹配,默认都是使用最长匹配,并且没有lookahead,这种方法的问题就是容易撞墙,撞墙也并不可怕,只要知道如何回溯就可以了。最为简单的回溯就是我们使用的递归方法,她使用的是处理器自带的堆栈结构进行回溯,对于regexec这种简单的虚拟机来说,它的堆栈功能就非常薄弱,它通常使用on_failure_jump指令来主动的在回退堆栈中压入下次失败需要回退的位置。在整个虚拟机指令中,它没有对每次匹配失败定义特定的处理指令,它假设在任何时候如果匹配失败,则直接从失败堆栈中弹出最近一次压入的失败位置并继续执行。从代码上看,在匹配的执行过程中任何位置如果遇到失败,则直接跳转到fail标签处,该处代码就是从堆栈中弹出之前压入的错误位置继续执行。
4、对于alternative(|)的处理方法
主要在regex_compile函数的handle_alt标签处。对于alt操作符来说,它主要生成两条指令,一条是通过insert,在这个alt对应的表达式插入一个回溯点快照动作,也就是前面说的on_failure_jump指令,注意这个地方是通过插入生成的。对于模式 exp1 | exp2,在解析到'|'时,需要在exp1的开始生成一个回溯点,也就是当exp1匹配失败之后,跳转到exp2的开始,而这个位置就是当前位置。这里还有一条指令,就是jump_past_alt指令,如果exp1匹配成功,整个exp2的匹配就需要被跳过。此处跳过之后,回溯点依然被保留,因为只是在这个范围内使用某个alt匹配成功,如果后面匹配不成功还要回退。例如模式(a|ab)c,输入字符串abc,当进行alt匹配时,第一个a表达式可以完成匹配,但是在匹配完成之后,遇到abc中的b,此时alt中已经完成的匹配还是要回退,所以此处插入的jump_past_alt指令并没有执行POP_FAILURE_POINT,而是将最近的回溯堆栈一直保存。
5、对于*,+,?数量型匹配的实现
主要代码在regex_compile函数的handle_plus标签处。对于这种类型的匹配,它同样是主要生成两条指令,一条是在整个结构的开始insert一条回溯点入栈动作,在当前位置可能会加上一条maybe_pop_jump指令。这条指令是一条优化指令,现在看起来非常做作,它的功能是根据之前重复的开始字符和接下来的待匹配内容来确定这个回溯点是否可能被用到,例如说a*b这条指令,在a开始的回溯点如果匹配成功,接下来是b,那么这个栈中的回溯点就不会被用到,因为即时把这个堆栈中的a弹出来,也不可能满足和接下来的b的匹配,所以此时直接把它从回溯点堆栈中消耗掉。以输入"abbb",模式'a*b'为例,此处打印的debug信息为
0x530603: EXECUTING exactn 1.

0x530606: EXECUTING maybe_pop_jump -9.
  b != a => pop_failure_jump.
EXECUTING pop_failure_jump.
POP_FAILURE_POINT:
  Before pop, next avail: 5
                    size: 5
  Popping failure id: 1
  Popping string 0x534000: `abbb'
  Popping pattern 0x530609:
0:      /exactn/1/b
3:      end of pattern.
  Popping high active reg: 256
  Popping  low active reg: 257
对应代码为
            else if ((re_opcode_t) *p2 == exactn
#ifdef MBS_SUPPORT
    || (re_opcode_t) *p2 == exactn_bin
#endif
    || (bufp->newline_anchor && (re_opcode_t) *p2 == endline))
     {
register US_CHAR_TYPE c
                  = *p2 == (US_CHAR_TYPE) endline ? '\n' : p2[2];

                if (((re_opcode_t) p1[1+OFFSET_ADDRESS_SIZE] == exactn
#ifdef MBS_SUPPORT
    || (re_opcode_t) p1[1+OFFSET_ADDRESS_SIZE] == exactn_bin
#endif
   ) && p1[3+OFFSET_ADDRESS_SIZE] != c)
                  {
     p[-(1+OFFSET_ADDRESS_SIZE)] = (US_CHAR_TYPE)
     pop_failure_jump;
#ifdef MBS_SUPPORT
   if (MB_CUR_MAX != 1)
     DEBUG_PRINT3 ("  %C != %C => pop_failure_jump.\n",
   (wint_t) c,
   (wint_t) p1[3+OFFSET_ADDRESS_SIZE]);
   else
#endif
     DEBUG_PRINT3 ("  %c != %c => pop_failure_jump.\n",
   (char) c,
   (char) p1[3+OFFSET_ADDRESS_SIZE]);
                  }

#ifndef MBS_SUPPORT
else if ((re_opcode_t) p1[3] == charset
|| (re_opcode_t) p1[3] == charset_not)
 {
   int not = (re_opcode_t) p1[3] == charset_not;

   if (c < (unsigned) (p1[4] * BYTEWIDTH)
&& p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
     not = !not;

                    /* `not' is equal to 1 if c would match, which means
                        that we can't change to pop_failure_jump.  */
   if (!not)
                      {
         p[-3] = (unsigned char) pop_failure_jump;
                        DEBUG_PRINT1 ("  No match => pop_failure_jump.\n");
                      }
 }
#endif /* not MBS_SUPPORT */
     }
6、一个典型匹配的debug输出
有点长,整个摘录作为备份
harry@tsecer:  echo "abbb" | /data/harry/harrywork/grep-2.5/src/grep 'a\(a*\|c*\|b\)b'  -o

Compiling pattern: a\(a*\|c*\|b\)b

Compiled pattern: 
0:      /exactn/1/a
3:      /start_memory/1/0
6:      /on_failure_jump to 21
9:      /on_failure_jump to 18
12:     /exactn/1/a
15:     /maybe_pop_jump to 9
18:     /jump_past_alt to 33
21:     /on_failure_jump to 36
24:     /on_failure_jump to 33
27:     /exactn/1/c
30:     /maybe_pop_jump to 24
33:     /jump_past_alt to 39
36:     /exactn/1/b
39:     /push_dummy_failure
40:     /stop_memory/1/0
43:     /exactn/1/b
46:     end of pattern.
46 bytes used/64 bytes allocated.
re_nsub: 1      regs_alloc: 0   can_be_null: 0  newline_anchor: 1
no_sub: 0       not_bol: 0      not_eol: 0      syntax: b06
dfamust:
 0:a 1:a 2:STAR 3:c 4:STAR 5:OR 6:b 7:OR 8:CAT 9:b 10:CAT 11:END 12:CAT
 node: 0:a
  in: "a"
  is: "a"
  left: "a"
  right: "a"
 node: 1:a
  in: "a"
  is: "a"
  left: "a"
  right: "a"
 node: 2:STAR
  in:
  is: ""
  left: ""
  right: ""
 node: 3:c
  in: "c"
  is: "c"
  left: "c"
  right: "c"
 node: 4:STAR
  in:
  is: ""
  left: ""
  right: ""
 node: 5:OR
  in:
  is: ""
  left: ""
  right: ""
 node: 6:b
  in: "b"
  is: "b"
  left: "b"
  right: "b"
 node: 7:OR
  in:
  is: ""
  left: ""
  right: ""
 node: 8:CAT
  in: "a"
  is: ""
  left: "a"
  right: ""
 node: 9:b
  in: "b"
  is: "b"
  left: "b"
  right: "b"
 node: 10:CAT
  in: "a" "b"
  is: ""
  left: "a"
  right: "b"
result a
dfaanalyze:
 0:a 1:a 2:STAR 3:c 4:STAR 5:OR 6:b 7:OR 8:CAT 9:b 10:CAT 11:END 12:CAT
node 0:a
 nullable: no
 firstpos: 0:a
 lastpos: 0:a
node 1:a
 nullable: no
 firstpos: 1:a
 lastpos: 1:a
node 2:STAR
 nullable: yes
 firstpos: 1:a
 lastpos: 1:a
node 3:c
 nullable: no
 firstpos: 3:c
 lastpos: 3:c
node 4:STAR
 nullable: yes
 firstpos: 3:c
 lastpos: 3:c
node 5:OR
 nullable: yes
 firstpos: 1:a 3:c
 lastpos: 1:a 3:c
node 6:b
 nullable: no
 firstpos: 6:b
 lastpos: 6:b
node 7:OR
 nullable: yes
 firstpos: 1:a 3:c 6:b
 lastpos: 1:a 3:c 6:b
node 8:CAT
 nullable: no
 firstpos: 0:a
 lastpos: 0:a 1:a 3:c 6:b
node 9:b
 nullable: no
 firstpos: 9:b
 lastpos: 9:b
node 10:CAT
 nullable: no
 firstpos: 0:a
 lastpos: 9:b
node 11:END
 nullable: no
 firstpos: 11:END
 lastpos: 11:END
node 12:CAT
 nullable: no
 firstpos: 0:a
 lastpos: 11:END
follows(0:a): 1:a 3:c 6:b 9:b
follows(1:a): 1:a 9:b
follows(3:c): 3:c 9:b
follows(6:b): 9:b
follows(9:b): 11:END
follows(11:END):


Entering re_match_2.
The compiled pattern is:
0:      /exactn/1/a
3:      /start_memory/1/0
6:      /on_failure_jump to 21
9:      /on_failure_jump to 18
12:     /exactn/1/a
15:     /maybe_pop_jump to 9
18:     /jump_past_alt to 33
21:     /on_failure_jump to 36
24:     /on_failure_jump to 33
27:     /exactn/1/c
30:     /maybe_pop_jump to 24
33:     /jump_past_alt to 39
36:     /exactn/1/b
39:     /push_dummy_failure
40:     /stop_memory/1/0
43:     /exactn/1/b
46:     end of pattern.
The string to match is: `abbb'

0x530600: EXECUTING exactn 1.

0x530603: EXECUTING start_memory 1 (0):
  old_regstart: -39744
  regstart: 1

0x530606: EXECUTING on_failure_jump 12 (to 0x530615):

PUSH_FAILURE_POINT #1:
  Before push, next avail: 0
                     size: 5
  slots needed: 8
     available: 5

  Doubled stack; size now: 10
  slots available: 10

  Pushing reg: 1
    start: 0x534001
    end: 0x52a4c0
    info: 0x530ae4
       match_null=0 active=1 matched_something=0 ever_matched=0
  Pushing  low active reg: 1
  Pushing high active reg: 1
  Pushing pattern 0x530615:
0:      /on_failure_jump to 15
3:      /on_failure_jump to 12
6:      /exactn/1/c
9:      /maybe_pop_jump to 3
12:     /jump_past_alt to 18
15:     /exactn/1/b
18:     /push_dummy_failure
19:     /stop_memory/1/0
22:     /exactn/1/b
25:     end of pattern.
  Pushing string 0x534001: `bbb'
  Pushing failure id: 1

0x530609: EXECUTING on_failure_jump 6 (to 0x530612):

PUSH_FAILURE_POINT #2:
  Before push, next avail: 8
                     size: 10
  slots needed: 8
     available: 2

  Doubled stack; size now: 20
  slots available: 12

  Pushing reg: 1
    start: 0x534001
    end: 0x52a4c0
    info: 0x530ae4
       match_null=0 active=1 matched_something=0 ever_matched=0
  Pushing  low active reg: 1
  Pushing high active reg: 1
  Pushing pattern 0x530612:
0:      /jump_past_alt to 15
3:      /on_failure_jump to 18
6:      /on_failure_jump to 15
9:      /exactn/1/c
12:     /maybe_pop_jump to 6
15:     /jump_past_alt to 21
18:     /exactn/1/b
21:     /push_dummy_failure
22:     /stop_memory/1/0
25:     /exactn/1/b
28:     end of pattern.
  Pushing string 0x534001: `bbb'
  Pushing failure id: 2

0x53060c: EXECUTING exactn 1.

FAIL:
POP_FAILURE_POINT:
  Before pop, next avail: 16
                    size: 20
  Popping failure id: 2
  Popping string 0x534001: `bbb'
  Popping pattern 0x530612:
0:      /jump_past_alt to 15
3:      /on_failure_jump to 18
6:      /on_failure_jump to 15
9:      /exactn/1/c
12:     /maybe_pop_jump to 6
15:     /jump_past_alt to 21
18:     /exactn/1/b
21:     /push_dummy_failure
22:     /stop_memory/1/0
25:     /exactn/1/b
28:     end of pattern.
  Popping high active reg: 1
  Popping  low active reg: 1
    Popping reg: 1
      info: 0x530ae4
      end: 0x52a4c0
      start: 0x534001

0x530612: EXECUTING jump_past_alt.

0x530613: EXECUTING jump 12 (to 0x530621).

0x530621: EXECUTING jump_past_alt.

0x530622: EXECUTING jump 3 (to 0x530627).

0x530627: EXECUTING push_dummy_failure.

PUSH_FAILURE_POINT #3:
  Before push, next avail: 8
                     size: 20
  slots needed: 8
     available: 12

  Pushing reg: 1
    start: 0x534001
    end: 0x52a4c0
    info: 0x530ae4
       match_null=0 active=1 matched_something=0 ever_matched=0
  Pushing  low active reg: 1
  Pushing high active reg: 1
  Pushing pattern (nil):
(null)
  Pushing string (nil): `(null)'
  Pushing failure id: 3

0x530628: EXECUTING stop_memory 1 (0):
      old_regend: -39744
      regend: 1

0x53062b: EXECUTING exactn 1.

0x53062e: end of pattern ... backtracking.

SAVING match as best so far.

FAIL:
POP_FAILURE_POINT:
  Before pop, next avail: 16
                    size: 20
  Popping failure id: 3
  Popping string 0x534002: `bb'
  Popping pattern (nil):
(null)
  Popping high active reg: 1
  Popping  low active reg: 1
    Popping reg: 1
      info: 0x530ae4
      end: 0x52a4c0
      start: 0x534001

FAIL:
POP_FAILURE_POINT:
  Before pop, next avail: 8
                    size: 20
  Popping failure id: 1
  Popping string 0x534001: `bbb'
  Popping pattern 0x530615:
0:      /on_failure_jump to 15
3:      /on_failure_jump to 12
6:      /exactn/1/c
9:      /maybe_pop_jump to 3
12:     /jump_past_alt to 18
15:     /exactn/1/b
18:     /push_dummy_failure
19:     /stop_memory/1/0
22:     /exactn/1/b
25:     end of pattern.
  Popping high active reg: 1
  Popping  low active reg: 1
    Popping reg: 1
      info: 0x530ae4
      end: 0x52a4c0
      start: 0x534001

0x530615: EXECUTING on_failure_jump 12 (to 0x530624):

PUSH_FAILURE_POINT #4:
  Before push, next avail: 0
                     size: 20
  slots needed: 8
     available: 20

  Pushing reg: 1
    start: 0x534001
    end: 0x52a4c0
    info: 0x530ae4
       match_null=0 active=1 matched_something=0 ever_matched=0
  Pushing  low active reg: 1
  Pushing high active reg: 1
  Pushing pattern 0x530624:
0:      /exactn/1/b
3:      /push_dummy_failure
4:      /stop_memory/1/0
7:      /exactn/1/b
10:     end of pattern.
  Pushing string 0x534001: `bbb'
  Pushing failure id: 4

0x530618: EXECUTING on_failure_jump 6 (to 0x530621):

PUSH_FAILURE_POINT #5:
  Before push, next avail: 8
                     size: 20
  slots needed: 8
     available: 12

  Pushing reg: 1
    start: 0x534001
    end: 0x52a4c0
    info: 0x530ae4
       match_null=0 active=1 matched_something=0 ever_matched=0
  Pushing  low active reg: 1
  Pushing high active reg: 1
  Pushing pattern 0x530621:
0:      /jump_past_alt to 6
3:      /exactn/1/b
6:      /push_dummy_failure
7:      /stop_memory/1/0
10:     /exactn/1/b
13:     end of pattern.
  Pushing string 0x534001: `bbb'
  Pushing failure id: 5

0x53061b: EXECUTING exactn 1.

FAIL:
POP_FAILURE_POINT:
  Before pop, next avail: 16
                    size: 20
  Popping failure id: 5
  Popping string 0x534001: `bbb'
  Popping pattern 0x530621:
0:      /jump_past_alt to 6
3:      /exactn/1/b
6:      /push_dummy_failure
7:      /stop_memory/1/0
10:     /exactn/1/b
13:     end of pattern.
  Popping high active reg: 1
  Popping  low active reg: 1
    Popping reg: 1
      info: 0x530ae4
      end: 0x52a4c0
      start: 0x534001

0x530621: EXECUTING jump_past_alt.

0x530622: EXECUTING jump 3 (to 0x530627).

0x530627: EXECUTING push_dummy_failure.

PUSH_FAILURE_POINT #6:
  Before push, next avail: 8
                     size: 20
  slots needed: 8
     available: 12

  Pushing reg: 1
    start: 0x534001
    end: 0x52a4c0
    info: 0x530ae4
       match_null=0 active=1 matched_something=0 ever_matched=0
  Pushing  low active reg: 1
  Pushing high active reg: 1
  Pushing pattern (nil):
(null)
  Pushing string (nil): `(null)'
  Pushing failure id: 6

0x530628: EXECUTING stop_memory 1 (0):
      old_regend: -39744
      regend: 1

0x53062b: EXECUTING exactn 1.

0x53062e: end of pattern ... backtracking.

FAIL:
POP_FAILURE_POINT:
  Before pop, next avail: 16
                    size: 20
  Popping failure id: 6
  Popping string 0x534002: `bb'
  Popping pattern (nil):
(null)
  Popping high active reg: 1
  Popping  low active reg: 1
    Popping reg: 1
      info: 0x530ae4
      end: 0x52a4c0
      start: 0x534001

FAIL:
POP_FAILURE_POINT:
  Before pop, next avail: 8
                    size: 20
  Popping failure id: 4
  Popping string 0x534001: `bbb'
  Popping pattern 0x530624:
0:      /exactn/1/b
3:      /push_dummy_failure
4:      /stop_memory/1/0
7:      /exactn/1/b
10:     end of pattern.
  Popping high active reg: 1
  Popping  low active reg: 1
    Popping reg: 1
      info: 0x530ae4
      end: 0x52a4c0
      start: 0x534001

0x530624: EXECUTING exactn 1.

0x530627: EXECUTING push_dummy_failure.

PUSH_FAILURE_POINT #7:
  Before push, next avail: 0
                     size: 20
  slots needed: 8
     available: 20

  Pushing reg: 1
    start: 0x534001
    end: 0x52a4c0
    info: 0x530afc
       match_null=0 active=1 matched_something=1 ever_matched=1
  Pushing  low active reg: 1
  Pushing high active reg: 1
  Pushing pattern (nil):
(null)
  Pushing string (nil): `(null)'
  Pushing failure id: 7

0x530628: EXECUTING stop_memory 1 (0):
      old_regend: -39744
      regend: 2

0x53062b: EXECUTING exactn 1.

0x53062e: end of pattern ... backtracking.

SAVING match as best so far.

FAIL:
POP_FAILURE_POINT:
  Before pop, next avail: 8
                    size: 20
  Popping failure id: 7
  Popping string 0x534003: `b'
  Popping pattern (nil):
(null)
  Popping high active reg: 1
  Popping  low active reg: 1
    Popping reg: 1
      info: 0x530afc
      end: 0x52a4c0
      start: 0x534001
Restoring best registers.
Accepting match.
7 failure points pushed, 7 popped (0 remain).
7 registers pushed.
Returning 3 from re_match_2.
abb


Entering re_match_2.
The compiled pattern is:
0:      /exactn/1/a
3:      /start_memory/1/0
6:      /on_failure_jump to 21
9:      /on_failure_jump to 18
12:     /exactn/1/a
15:     /maybe_pop_jump to 9
18:     /jump_past_alt to 33
21:     /on_failure_jump to 36
24:     /on_failure_jump to 33
27:     /exactn/1/c
30:     /maybe_pop_jump to 24
33:     /jump_past_alt to 39
36:     /exactn/1/b
39:     /push_dummy_failure
40:     /stop_memory/1/0
43:     /exactn/1/b
46:     end of pattern.
The string to match is: `b'

0x530600: EXECUTING exactn 1.


Entering re_match_2.
The compiled pattern is:
0:      /exactn/1/a
3:      /start_memory/1/0
6:      /on_failure_jump to 21
9:      /on_failure_jump to 18
12:     /exactn/1/a
15:     /maybe_pop_jump to 9
18:     /jump_past_alt to 33
21:     /on_failure_jump to 36
24:     /on_failure_jump to 33
27:     /exactn/1/c
30:     /maybe_pop_jump to 24
33:     /jump_past_alt to 39
36:     /exactn/1/b
39:     /push_dummy_failure
40:     /stop_memory/1/0
43:     /exactn/1/b
46:     end of pattern.
The string to match is: `'

0x530600: EXECUTING exactn 1.
harry@tsecer:  
  评论这张
 
阅读(458)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017