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

全部博文(32)

文章存档

2012年(32)

分类: Python/Ruby

2012-03-02 12:54:50


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

这一章的内容有:
  1. 运算符号的识别
  2. 状态矩阵的缺点
  3. 新的识别方法--状态链

(1)简介
在Redy中,总其有这么一些运算符号:
  1. '(' ')' '[' ']' '.' ','
  2.     '+' '-' '~'
  3.     '*' '/' '%'
  4.     '<<' '>>'
  5.     '<' '>' '<=' '>='
  6.     '==' '!='
  7.     '&' '^' '|'
  8.     'and' 'or' 'not'
  9.     '=' '+=' '-=' '*=' '/=' '%='
  10.     '&=' '^=' '|=' '>>=' '<<=
其中运算符'and' , 'or'  , 'not' 这三个,我们用把它归在变量识别里面,每当扫描器扫描到一个变量的单词时,扫描器会对该单词重新判断,看它是否真的是变量,或者还是关键字
(2)状态机


其中蓝色状态表示终态,总共有34个。开始状态为OperatorBegin。
状态图中的状态总共有36个

(3)状态矩阵
对于运算符来说,输入类型有这么19种,加上除以下字符以外的字符,,那么总其有20种
  1. '(' ')' '[' ']' '.' ','
  2. '+' '-' '~' '*' '/' '%'
  3. '<' '>' '=' '!'
  4. '&' '^' '|
如果用状态矩阵来处理的话,就需要维护一个36*20的数组,处理起来是一件很吓人的事情,如果不小心输错数据,要找出错误很难。
当我们需要识别某一种结构简单的单词时,状态矩阵是一种非常常用的方法,前面的文章讲述了怎么用状态矩阵的方法来识别变量,字符串,注释。但这次情况不同,这次我们需要识别运算符,和前面几个比起来,状态与输入类型的数量都要大的多,虽然运算符也可以用状态矩阵来处理,带来的一定的难度。仔细观察,可以上面的状态图看出,虽然输入类型有20种,但是除开始状态OperatorBegin能在多种输入类型下,能发生状态转移,其它状态只能接受一种或两种输入类型,例如,对于状态图中的状态LessThan来说,他只能在字符'<'与字符'='下能发生状态转移,其余字符都不能让LessThan发生状态转换
下面我介绍一种新的识别方法来实现状态机模型。
(4)新的识别方法--状态链
和状态矩阵一样,状态链也是实现状态机模型的一种方法,但是不同的是状态矩阵关心是状态机模型的整体结构,而状态链不同,状态链由多个状态链连接在一起,每一个状态不用去了解自己属于的是那一个状态机,状态机的整体结构是怎样的,它关心自己在可以接受哪一些输入的类型,以及在该输入类型下面转移到的后继状态。
状态链的核心是状态,我们用一 个结构体来表示
  1. typedef int (*input_map)(char); /*输入类型映射函数*/

  2. struct state
  3. {
  4.     char* s_name;                /*状态名称*/
  5.     int s_token;                /*单词类型,用于后面的语法识别*/
  6.     int s_inputs_num;            /*输入类型的数量*/

  7.     char* s_input_map; /*输入类型的映射数组,如果该值为0,则用s_input_func函数指针来判断输入类型*/
  8.     input_map s_input_func; /*输入类型的函数指针*/

  9.     struct state** s_targets; /*后继状态数组*/
  10.     int s_final; /*该状态是否终态*/
  11. };
结构体 struct state总共有7个成员:
  1. s_name 用于指向状态名称的字符串,
  2. s_token  表于单词的类型,用于后面的语法分析
  3. s_inputs_num 输入类型的数量
  4. s_input_map 用于映射输入字符的类型,如果为0,则用s_input_func函数指针来判断输入字符的类型。
  5. s_input_func  用于判断字符的输入类型,只有当s_input_map为0时,该成员函数才会被调用。
  6. s_targets  后断状态数组,输入类型为1的字符的后继状态为s_tartgets[1],输入类型为n的字符的后继状态为s_targets[n]。
  7. s_final  指明该状态是否为终态
结构体state中,成员s_input_map与s_input_func都是用于判断字符的输入类型,但当输入类型只有一个或两个的时,使用s_input_map需要建立一个长度为256的一组数组,使用一个函数来判断却只需要一两行找码。但是在输入类型很多的情况下,使用s_input_func变得繁琐,一大堆意大利拉面的代码。

接着,用一个函数来获取后继状态
  1. /*返回状态s在识别字符c后,转移到的状态*/
  2. static inline struct state* state_next(struct state* s,char c)
  3. {
  4.     int input_type;
  5.     if(s->s_input_map)            /*如果该状态有输入类型映射数组,则用该忽略s_input_func*/
  6.     {
  7.         input_type=s->s_input_map[c]; /*得到输入类型*/
  8.     }
  9.     else /*如果类型映射数组不存在,则用该函数指针获取输入类型*/
  10.     {
  11.         input_type=s->s_input_func(c); /*得到输入类型*/
  12.     }
  13.     return s->s_targets[input_type]; /*返回后继状态*/
  14. }
(5)构造状态链
虽然采用状态链的方法,不再用去维护一个34*20的状态矩阵,但是要维持34个状态的信息还是挺多的,不过仔细观察状态图,会发现,有很多状态者非常相似。

(a)状态Comma , Period , Reverse, L_RB ,  R_RB, L_SB , R_SB,都是从OperatorBegin转换过来,并且没有后继状态,我们用宏定义处理,以减少复杂度。
  1. extern struct state lex_state_err;
  2. extern struct state* lex_state_err_array[];
  3. extern char input_map_other[];

  4. #define INIT_FINAL_STATE(name,token) {#name,token,1,input_map_other,0,lex_state_err_array,1}

  5. #define OP_FINAL_STATE(name,token) \
  6.     struct state name=INIT_FINAL_STATE(name,token)


  7. OP_FINAL_STATE(op_comma,TOKEN_COMMA);
  8. OP_FINAL_STATE(op_period,TOKEN_PERIOD);
  9. OP_FINAL_STATE(op_l_rb,TOKEN_L_RB);
  10. OP_FINAL_STATE(op_r_rb,TOKEN_R_RB);
  11. OP_FINAL_STATE(op_l_sb,TOKEN_L_SB);
  12. OP_FINAL_STATE(op_r_sb,TOKEN_R_SB);
  13. OP_FINAL_STATE(op_reverse,TOKEN_REVERSE);
(b)状态(NotEqualBegin,NotEqual), (BitsAnd,BitsAndAssign),(BitsOr,BitsOrAssign),(BitsXor,BitsXorAssign), (multiply,multiplyAssign),(Mod,ModAssign), (Plus,PlusAssign), (Divide,DivideAssign), (Assign,Equal) 这几9组状态基本上一样,所以也用宏定义。
  1. static char op_input_map_equal[ASCII_NUM]=
  2. {
  3.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  4.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,
  5.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  6.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  7.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  8.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  9.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  10.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

  11. };


  12. #define __INIT_OPERATOR_ASSIGN_TRANSLATE(name,token,target_array,final) \
  13.     struct state name= \
  14. { \
  15. #name, \
  16.     token,2,op_input_map_equal,0,target_array,final,\
  17. }\

  18. #define INIT_OPERATOR_ASSIGN_TRANSLATE(first,token1,final,last,token2) \
  19.     static struct state* operator_private_name_state_array_##first[]=\
  20.     {&lex_state_err,&last}; \
  21.     __INIT_OPERATOR_ASSIGN_TRANSLATE(first,token1,operator_private_name_state_array_##first,final); \
  22.     OP_FINAL_STATE(last,token2)



  23. INIT_OPERATOR_ASSIGN_TRANSLATE(op_not_equal_begin,TOKEN_UNKOWN,0,op_not_equal,TOKEN_NOT_EQUAL);
  24. INIT_OPERATOR_ASSIGN_TRANSLATE(op_bits_and,TOKEN_BITS_AND,1,op_assign_bits_and,TOKEN_A_BITS_AND);
  25. INIT_OPERATOR_ASSIGN_TRANSLATE(op_bits_or,TOKEN_BITS_OR,1,op_assign_bits_or,TOKEN_A_BITS_OR);
  26. INIT_OPERATOR_ASSIGN_TRANSLATE(op_bits_xor,TOKEN_BITS_XOR,1,op_assign_bits_xor,TOKEN_A_BITS_XOR);
  27. INIT_OPERATOR_ASSIGN_TRANSLATE(op_multiply,TOKEN_MUL,1,op_assign_multiply,TOKEN_A_MUL);
  28. INIT_OPERATOR_ASSIGN_TRANSLATE(op_mod,TOKEN_MOD,1,op_assign_mod,TOKEN_A_MOD);
  29. INIT_OPERATOR_ASSIGN_TRANSLATE(op_minus,TOKEN_MINUS,1,op_assign_minus,TOKEN_A_MINUS);
  30. INIT_OPERATOR_ASSIGN_TRANSLATE(op_plus,TOKEN_PLUS,1,op_assign_plus,TOKEN_A_PLUS);
  31. INIT_OPERATOR_ASSIGN_TRANSLATE(op_divide,TOKEN_DIVIDE,1,op_assign_divide,TOKEN_A_DIVIDE);
  32. INIT_OPERATOR_ASSIGN_TRANSLATE(op_assign,TOKEN_ASSIGN,1,op_equal,TOKEN_EQUAL);
(c)状态(LessThan,LeftShift,LessEqual,LeftShiftAssign), (GreaterThan,GreaterEqual,RightShift,RightShiftAssign),这两组状态也相似,下面我们再看这8个状态的程序
  1. INIT_OPERATOR_ASSIGN_TRANSLATE(op_right_shift,TOKEN_RS,1,op_assign_right_shift,TOKEN_A_RS);
  2. OP_FINAL_STATE(op_greater_equal,TOKEN_GE);
  3. static struct state* op_greater_than_targets[]=
  4. {
  5.     &lex_state_err,
  6.     &op_greater_equal,
  7.     &op_right_shift,
  8. };


  9. int op_input_map_greater_than(char c)
  10. {
  11.     if(c=='=') return 1;
  12.     else if(c=='>') return 2;
  13.     else return 0;
  14. }


  15. struct state op_greater_than=
  16. {
  17.     "op_greater_than",
  18.     TOKEN_GT,
  19.     3,
  20.     0,
  21.     op_input_map_greater_than,
  22.     op_greater_than_targets,
  23.     1,
  24. };

  25. INIT_OPERATOR_ASSIGN_TRANSLATE(op_left_shift,TOKEN_LS,1,op_assign_left_shift,TOKEN_A_LS);
  26. OP_FINAL_STATE(op_less_equal,TOKEN_LE);

  27. static struct state* op_less_than_targets[]=
  28. {
  29.     &lex_state_err,
  30.     &op_less_equal,
  31.     &op_left_shift,
  32. };
  33. int op_input_map_less_than(char c)
  34. {
  35.     if(c=='=') return 1;
  36.     else if (c=='<') return 2;
  37.     else return 0;
  38. }



  39. struct state op_less_than=
  40. {
  41.     "op_less_than",
  42.     TOKEN_LT,
  43.     3,
  44.     0,
  45.     op_input_map_less_than,
  46.     op_less_than_targets,
  47.     1,
  48. };
(d)最后还有一个状态BeginState,由于BeginState可以接受20种不同类型的输入,所以对于BeginState,我们使用输入映射数组来获取输入的类型。
  1. enum OP_INPUT_TYPE
  2. {
  3.     OP_OTHER=0,
  4.     OP_COMMA,
  5.     OP_PERIOD,
  6.     OP_REVERSE,
  7.     OP_L_RB,
  8.     OP_R_RB,
  9.     OP_L_SB,
  10.     OP_R_SB,
  11.     OP_EXCLAMATION,
  12.     OP_AMPERSAND,
  13.     OP_BAR,
  14.     OP_CARET,
  15.     OP_STAR,
  16.     OP_PERCENT,
  17.     OP_MINUS,
  18.     OP_PLUS,
  19.     OP_DIVIDE,
  20.     OP_EQUAL,
  21.     OP_GREATER,
  22.     OP_LESS,
  23.     OP_INPUT_NUM
  24. };

  25. char op_input_map_begin[ASCII_NUM]=
  26. {
  27.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  28.     0,8,0,0,0,13,9,0,4,4,12,15,1,14,2,16,0,0,0,0,0,0,0,0,0,0,0,0,19,17,18,0,
  29.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,6,0,7,11,0,
  30.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10,0,3,0,
  31.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  32.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  33.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  34.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
  35. };

  36. struct state* op_begin_targets[]=
  37. {
  38.     &lex_state_err,
  39.     &op_comma,
  40.     &op_period,
  41.     &op_reverse,
  42.     &op_l_rb,
  43.     &op_r_rb,
  44.     &op_l_sb,
  45.     &op_r_sb,
  46.     &op_not_equal_begin,
  47.     &op_bits_and,
  48.     &op_bits_or,
  49.     &op_bits_xor,
  50.     &op_multiply,
  51.     &op_mod,
  52.     &op_minus,
  53.     &op_plus,
  54.     &op_divide,
  55.     &op_assign,
  56.     &op_greater_than,
  57.     &op_less_than,
  58. };
  59. struct state op_begin=
  60. {
  61.     "oper_begin",
  62.     TOKEN_UNKOWN,
  63.     OP_INPUT_NUM,
  64.     op_input_map_begin,
  65.     0,
  66.     op_begin_targets,
  67.     0
  68. };

到目前为止,已经用状态链的方法实现了运算符状态机的模型,但上面只是一大堆的数据,要把这一堆数据用起来,就需要写一个读得懂这一堆数据的驱动程序。
驱动程序为:
  1. /*返回值-1则表示识别错误,其它值表示能识别的最大位置*/
  2. int driver(struct state* s,char* str,struct state* info)
  3. {
  4.     int length=strlen(str);
  5.     int i;
  6.     struct state* cur_st=s; /*当前状态*/
  7.     struct state* next_st; /*下一状态*/
  8.     int last_final=-1;
  9.     for(i=0;i<length;i++)
  10.     {
  11.         next_st=state_next(cur_st,str[i]); /*获得下一状态*/
  12.         if(next_st==&lex_state_err) /*如果返回状态为lex_state_err,则表明需要错误处理*/
  13.         {
  14.             return last_final;
  15.         }
  16.         else
  17.         {
  18.             cur_st=next_st;
  19.             if(cur_st->s_final) /*判继该状态是否为终态*/
  20.             {
  21.                 last_final=i; /*如果为终态,则保存识别的信息*/
  22.                 *info=*cur_st;
  23.             }
  24.         }
  25.     }
  26.     return last_final;
  27. };
和状态矩阵的驱动程序比起来,还是有一点小小的变化。
(6)运行结果
关于运算符识的代码,可以在tutorial/lexical/ssl_operator文件夹中找到.
(7)结尾语
到现在为上,总共介绍了两种识别方法,一种为状态矩阵,一种为状态链,状态矩阵适合于状态与输入类型都较少的状态机。状态链适合于状态状态数量与输入类型较多,但是大部分状态都只在较少的输入状态下发生状态转移的状态机。在Redy中是使用的状态链的方法进行词法识别的。

到目前为止,总共介绍了变量,字符串,注释,运算符的识别方法,这几个词文识别起来都非常容易,后面的文章会给大家介绍怎么去识别整数,浮点数。











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

NosicLin2012-03-03 09:29:51

我要去水立方: 运算规则的分析更复杂了就.....
想比整数,浮点数来说,构造运算符识别的状态机要简单得多,但是由于运算符数量大多,构造出来的状态机的状态数量也比较多,所以显的比较复杂

我要去水立方2012-03-03 08:32:06

运算规则的分析更复杂了就