C指针原理(41)-递归(2)

编译:

dp@dp:~ % gcc bfi.c -o bfi

bfi.c: In function 'interpret':

bfi.c:35: warning: incompatible implicit declaration of built-in function 'exit'

bfi.c:40: warning: incompatible implicit declaration of built-in function 'exit'

dp@dp:~ % 

下面的hello.b输出经典的hello,world:

+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-]

<.#>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>++++++++[

<++++>-]<+.[-]++++++++++.

用刚生成的bf语言解释器运行它:

dp@dp:~ % ./bfi hello.b

Hello World!

prime.b完成指定整数内质数的计算:

===================================================================

======================== OUTPUT STRING ============================

===================================================================

++++++++[<++++++++>-]<++++++++++++++++.[-]

++++++++++[<++++++++++>-]<++++++++++++++.[-]

++++++++++[<++++++++++>-]<+++++.[-]

++++++++++[<++++++++++>-]<+++++++++.[-]

++++++++++[<++++++++++>-]<+.[-]

++++++++++[<++++++++++>-]<+++++++++++++++.[-]

+++++[<+++++>-]<+++++++.[-]

++++++++++[<++++++++++>-]<+++++++++++++++++.[-]

++++++++++[<++++++++++>-]<++++++++++++.[-]

+++++[<+++++>-]<+++++++.[-]

++++++++++[<++++++++++>-]<++++++++++++++++.[-]

++++++++++[<++++++++++>-]<+++++++++++.[-]

+++++++[<+++++++>-]<+++++++++.[-]

+++++[<+++++>-]<+++++++.[-]

===================================================================

======================== INPUT NUMBER  ============================

===================================================================

+                          cont=1

[

 -                         cont=0

 >,

 ======SUB10======

 ----------

 [                         not 10

  <+>                      cont=1

  =====SUB38======

  ----------

  ----------

  ----------

  --------

  >

  =====MUL10=======

  [>+>+<<-]>>[<<+>>-]<     dup

  >>>+++++++++

  [

   <<<

   [>+>+<<-]>>[<<+>>-]<    dup

   [<<+>>-]

   >>-

  ]

  <<<[-]<

  ======RMOVE1======

  <

  [>+<-]

 ]

 <

]

>[<<+>>-]<<

===================================================================

======================= PROCESS NUMBER  ===========================

===================================================================

==== ==== ==== ====

numd numu teid teiu

==== ==== ==== ====

+<-

[

 >+

 ======DUP======

 [>+>+<<-]>>[<<+>>-]<

 >+<--

 >>>>>>>>+<<<<<<<<   isprime=1

 [

  >+

  <-

  =====DUP3=====

  <[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<<

  =====DUP2=====

  >[>>+>+<<<-]>>>[<<<+>>>-]<<< <

  >>>

  ====DIVIDES=======

  [>+>+<<-]>>[<<+>>-]<   DUP i=div

  

  <<

  [

    >>>>>+               bool=1

    <<<

    [>+>+<<-]>>[<<+>>-]< DUP

    [>>[-]<<-]           IF i THEN bool=0

    >>

    [                    IF i=0

      <<<<

      [>+>+<<-]>>[<<+>>-]< i=div

      >>>

      -                  bool=0

    ]

    <<<

    -                    DEC i

    <<

    -

  ]

  

  +>>[<<[-]>>-]<<          

  >[-]<                  CLR div

  =====END DIVIDES====

  [>>>>>>[-]<<<<<<-]     if divides then isprime=0

  <<

  >>[-]>[-]<<<

 ]

 >>>>>>>>

 [

  -

  <<<<<<<[-]<<

  [>>+>+<<<-]>>>[<<<+>>>-]<<<

  >>

  ===================================================================

  ======================== OUTPUT NUMBER  ===========================

  ===================================================================

  [>+<-]>

  [

   ======DUP======

   [>+>+<<-]>>[<<+>>-]<

  

  

   ======MOD10====

   >+++++++++<

   [

    >>>+<<              bool= 1

    [>+>[-]<<-]         bool= ten==0

    >[<+>-]             ten = tmp

    >[<<++++++++++>>-]  if ten=0 ten=10

    <<-                 dec ten     

    <-                  dec num

   ]

   +++++++++            num=9

   >[<->-]<             dec num by ten

  

   =======RROT======

      [>+<-]

   <  [>+<-]

   <  [>+<-]

   >>>[<<<+>>>-]

   <

  

   =======DIV10========

   >+++++++++<

   [

    >>>+<<                bool= 1

    [>+>[-]<<-]           bool= ten==0

    >[<+>-]               ten = tmp

    >[<<++++++++++>>>+<-] if ten=0 ten=10  inc div

    <<-                   dec ten     

    <-                    dec num

   ]

   >>>>[<<<<+>>>>-]<<<<   copy div to num

   >[-]<                  clear ten

  

   =======INC1=========

   <+>

  ]

  

  <

  [

   =======MOVER=========

   [>+<-]

  

   =======ADD48========

   +++++++[<+++++++>-]<->

  

   =======PUTC=======

   <.[-]>

  

   ======MOVEL2========

   >[<<+>>-]<

  

   <-

  ]

  >++++[<++++++++>-]<.[-]

  ===================================================================

  =========================== END FOR ===============================

  ===================================================================

  >>>>>>>

 ]

 <<<<<<<<

 >[-]<

  [-]

 <<-

]

======LF========

++++++++++.[-]

用刚编译生成的bf语言解释器运行它:

dp@dp:~ % ./bfi prime.b

Primes up to: 20

2 3 5 7 11 13 17 19 

BF解释器分析:

1、main函数以只读方式打开BF语言的源代码文件,然后,将BF源文件按字节逐个拷入数组f中,并在最后加上字符串的结束标志0,最后,以数组f为参数,调用interpret函数解释执行BF语言源代码。

if((z=fopen(argv[1],"r"))) {

while( (b=getc(z))>0 )

*s++=b;

*s=0;

interpret(f);

}

2、BF语言的解释器以数组为数据中心进行计算,在它的计算模型中,需要一个指向数组的指针,通过这个指针的移动以及对指针指向内容的操作完成所有的计算。因此,程序在开头处声明了解释器的核心:数组a与f,数据a存放BF指令所操作的数据,数组f存放BF语言代码文件,同时声明指针变量s指向f数组的第一个元素。

char a[5000], f[5000], b, o, *s=f;

3、interpret函数解析

这个函数是实现BF语言解释执行的关键。interpret函数接受数组指针c(指存放向BF语言源代码的数组),然后通过while语句逐个字符提取BF源代码(因为BF源代码中每个字符就是一条指令),通过swith...case...语句块判断BF指令(<、>、+、-、.、,、[、]),执行BF指令。

这些指令分为非跳转指令与跳转指令:

(1)非跳转指令完成了除循环外的其它功能。比如移动指针(指针指变量p,比如代码中的“ p--”以及“p++”)、对数组(数组指变量a,比如代码中的“a[p]++”以及“a[p]--”)的操作、输出(代码中的“putchar(a[p]); fflush(stdout); break;”)和输入(代码中的“case ','”标示的语句块)。

void interpret(char *c)

{

char *d; int tmp;

r++;

while( *c ) {

      //if(strchr("<>+-,.[]\n",c))printf("%c",c);

      switch(o=1,*c++) {

      case '<': p--;        break;

      case '>': p++;        break;

      case '+': a[p]++;     break;

      case '-': a[p]--;     break;

      case '.': putchar(a[p]); fflush(stdout); break;

      case ',': 

    tmp=getchar();

    if (tmp == EOF) a[p]=0; 

    else a[p]=tmp;

................

        .................

}

r--;

}

(2)跳转指令完成了循环功能。在循环指令的解释执行过程中,使用了递归机制完成了BF语言的“[”与”]” 指令的解释,“[”标示着一段循环的开始,而“]”标示着一段循环的结束,这意味着循环可以嵌套,可以由多个“[”与”]” 指令组成多层循环。

[

如果指针指向的单元值为零,向后跳转到对应的]指令的次一指令处

]

如果指针指向的单元值不为零,向前跳转到对应的[指令的次一指令处

因为可能存在多种循环,所以必须找到本次循环开始的“[”对应的“]”处,循环的条件通过指针指向的单元值来决定,只要指针指向的内容为0,则循环结束,否则循环继续。

通过下面这段语句,完成对应“[”的“]”的查找,寻找的过程中,更新下一步要执行的BF指令指针(for循环语句中的“c++”):

for( b=1,d=c; b && *c; c++ )

b+=c=='[', b-=c==']';

找到循环的结束处后,对指针指向的单元值( 下面代码中的“a[p]”)进行判断,只要单元值不为0,则递归调用interpret函数进行下一条指令的解释:

while( a[p] )

interpret(d);

为防止循环的符号不对应,比如说,最后多了循环结束标志”]”,则出现了异常,程序非正常退出,如下面代码所示:

case ']':

puts("UNBALANCED BRACKETS"), exit(0);   

对这2个指令的解释的全部代码如下:

void interpret(char *c)

{

char *d; int tmp;

r++;

while( *c ) {

      ............

          case '[':

for( b=1,d=c; b && *c; c++ )

b+=c=='[', b-=c==']';

if(!b) {

c[-1]=0;

while( a[p] )

interpret(d);

c[-1]=']';

break;

}

case ']':

puts("UNBALANCED BRACKETS"), exit(0);   

              .................................

上一篇:第四章学习小结


下一篇:【转载】C#将图片转换为二进制流调用