Chinaunix首页 | 论坛 | 博客
  • 博客访问: 240472
  • 博文数量: 32
  • 博客积分: 424
  • 博客等级: 准尉
  • 技术积分: 465
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-02 10:23
文章分类

全部博文(32)

文章存档

2012年(32)

分类: Python/Ruby

2012-03-02 21:08:58


代码下载: git clone git://git.code.sf.net/p/redy/code redy-code

这一章的内容有:
扫描器的设计与实现

(1)扫描器的设计与实现

在上一章里面,我给介绍的怎么去实现一个高效的输入缓冲区,也对扫描器作了一个简单的介绍。扫描器对语言的源码进行扫描,识别出由这些字符序列组成的单词,用于在后面的语法分析。

在Redy中基本的单词由浮点数,整数,长整数,运算符,变量,字符串,关键字组成,扫描器的任务是从输入字符序列中识别出一个接一个的单词

第一步,用一个结构体来表示扫描器

  1. #define SCANNER_DEFALUT_LITERIAL_SIZE 128
  2. struct scanner
  3. {
  4.     struct lex_file* s_lf;
  5.     int s_cur_token;
  6.     int s_line;
  7.     char* s_cur_literal;
  8.     int s_literial_size;

  9. };

扫描器struct scanner总共有5个成员,其中
  1. s_lf指向扫描文件的输入缓冲区
  2. s_cur_token表示扫描器当前识别到的词文
  3. s_line表示扫描器当前描扫到源文件的每几行,用于描扫到错误词文时,能准确的给出错误的位置
  4. s_cur_literal表于当前识别到的词文的内容
  5. s_literial_size表于s_cur_literal的空间的大小

第二步,实现扫描器的创建与销毁
扫描器的创建有两种方式,第一种为给定一个文件名来创建扫描器,第二种是从已经打开的文件来创建扫描器,这两个函数都调用sc_init来初始化扫描器
  1. static void sc_init(struct scanner* sc,struct lex_file* lf)
  2. {
  3.     sc->s_lf=lf;
  4.     sc->s_cur_token=TOKEN_UNKOWN;
  5.     sc->s_line=1;
  6.     sc->s_cur_literal=(char*)malloc(SCANNER_DEFALUT_LITERIAL_SIZE);
  7.     sc->s_literial_size=SCANNER_DEFALUT_LITERIAL_SIZE;
  8. }


  9. struct scanner* sc_create(char* filename)
  10. {
  11.     struct lex_file* lf=lf_create(filename);
  12.     if(lf==NULL)
  13.     {
  14.         WARN("Open file[%s] Failed",filename);
  15.         return NULL;
  16.     }
  17.     struct scanner* sc=(struct scanner*)malloc(sizeof(*sc));
  18.     sc_init(sc,lf);
  19.     return sc;

  20. }
  21. struct scanner* sc_stream_create(FILE* file)
  22. {
  23.     struct lex_file* lf=lf_stream_create(file);
  24.     if(lf==NULL)
  25.     {
  26.         WARN("Create Scanner Failed");
  27.         return NULL;
  28.     }
  29.     struct scanner* sc=(struct scanner*)malloc(sizeof(*sc));
  30.     sc_init(sc,lf);
  31.     return sc;
  32. }

扫描器的销毁:
  1. void sc_destory(struct scanner* sc)
  2. {
  3.     lf_destory(sc->s_lf);
  4.     free(sc->s_cur_literal);
  5.     free(sc);

  6. }

第三步,实现扫描器对源文件的扫描,并且返回扫描到的一个词文

扫描器对采用我们前面的状态机字符序列进行识别,状态机的开始状态为me_begin,扫描器从输入缓冲区得到一个字符,然后调用函数state_next得到当前状态的后继状态,后继状态有这么三种情况
  1. 终态,说明扫描器已经扫描到了一个词文,但是扫描器是采用最大识别的方法,所以扫描器还有往后扫描,看能不能扫描到长度更大的词文,如果不能,则需要回到该位置,所以需要调用函数lf_mark对当前位置进行标记,以便回到该位置。
  2. 错误状态(lex_state_err),说明扫描器扫描的字符序列已经不能构成一个词文了,所以这时需要停止扫描,然后在进行判断看以前时否到达过终态,如果没有则说明我们源程序中出现了错误的字符序例。如果到达过,则返回以前识别到的词文。
  3. 普通状态,继续往下扫描
在最后,扫描器把扫描的词文通过函数sc_set_cur_literial复制到成员s_cur_literal里面。
  1. static void sc_set_cur_literial(struct scanner* sc,char* buf,int length)
  2. {
  3.     if(sc->s_literial_size<length+1)
  4.     {
  5.         char* new_space=(char*)malloc(length+1);
  6.         free(sc->s_cur_literal);
  7.         sc->s_cur_literal=new_space;
  8.     }
  9.     memcpy(sc->s_cur_literal,buf,length);
  10.     sc->s_cur_literal[length]='\0';
  11. }

  12. int sc_next_token(struct scanner* sc)
  13. {
  14.     struct lex_file* lf=sc->s_lf;

  15.     char cur;
  16.     char next=lf_next_char(lf);
  17.     struct state* cur_state=&me_begin;
  18.     struct state* next_state;
  19.     struct state* finnal_state=NULL;
  20.     while(1)
  21.     {
  22.         cur=next;


  23.         if(cur==EOF)
  24.         {
  25.             sc->s_cur_token=TOKEN_EOF;
  26.             break;
  27.         }
  28.         if(cur=='\n')
  29.         {
  30.             sc->s_line++;
  31.         }
  32.         next_state=state_next(cur_state,cur);
  33.         if(next_state==&lex_state_err)
  34.         {
  35.             if(finnal_state==NULL)
  36.             {
  37.                 sc->s_cur_token=TOKEN_ERR;
  38.             }
  39.             else
  40.             {
  41.                 sc->s_cur_token=finnal_state->s_token;
  42.             }
  43.             break;
  44.         }


  45.         if(state_final(next_state))
  46.         {
  47.             finnal_state=next_state;
  48.             lf_mark(lf);
  49.         }
  50.         next=lf_next_char(lf);
  51.         cur_state=next_state;
  52.     }

  53.     sc_set_cur_literial(sc,lf->l_buf+lf->l_begin,lf->l_mark-lf->l_begin);
  54.     lf_reset_to_mark(lf);

  55.     return sc->s_cur_token;
  56. }

第四步,写一个小程序来测试的扫描器

  1. int main(int argc,char** argv)
  2. {
  3.     if(argc<2)
  4.     {
  5.         printf("usage %s [filename]\n",argv[0]);
  6.         exit(0);
  7.     }
  8.     struct scanner* sc=sc_create(argv[1]);

  9.     int token;
  10.     int i=0;
  11.     while(1)
  12.     {
  13.         i++;
  14.         if(i%5==0)
  15.         {
  16.             printf("\n");
  17.         }
  18.         token=sc_next_token(sc);
  19.         if(token==TOKEN_EOF)
  20.         {
  21.             break;
  22.         }
  23.         if(token==TOKEN_ERR)
  24.         {
  25.             goto err;
  26.         }
  27.         if(token==TOKEN_ID)
  28.         {
  29.             if(symbol_type(sc_token_string(sc))==TOKEN_ID)
  30.             {
  31.                 printf("{variable,%s} ",sc_token_string(sc));
  32.             }
  33.             else
  34.             {
  35.                 printf("{keyword,%s} ",sc_token_string(sc));
  36.             }
  37.             continue;
  38.         }
  39.         if(token==TOKEN_ANNO)
  40.         {
  41.             continue;

  42.         }
  43.         if(token==TOKEN_WS)
  44.         {
  45.             continue;
  46.         }
  47.         if(token==TOKEN_NEWLINE)
  48.         {
  49.             printf("{newline} ");
  50.             continue;
  51.         }
  52.         printf("{%s,%s} ",token_name(token),sc_token_string(sc));
  53.     };

  54.     return 0;
  55. err:
  56.     printf("err token at line %d\n",sc->s_line);
  57.     return -1;
  58. }


运行结果:现在我们用扫描器来扫描Redy的一段小程序,来看看效果怎么样。

Redy程序:
  1. a=random()
  2. b=random()
  3. if a+b/2==557
  4.     a.inc()
  5.     if a/2
  6.         a.dec()
  7.     else
  8.         a.inc()
  9.     end
  10. elif a+b/3==6
  11.     a.dec()
  12. else
  13.     b=a/2
  14. end
  15. print a
  16. print b
运行结果


以上程序大家可以在文件夹tutorial/lexical/scanner下面找到,对程序编译后,可以在bin目录下找到可执行文件,测试数据放在debug_data文件夹下面

返回文档首页





阅读(1411) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~