2012年(32)
分类: Python/Ruby
2012-03-02 12:54:50
代码下载: git clone git://git.code.sf.net/p/redy/code redy-code
这一章的内容有:
- 运算符号的识别
- 状态矩阵的缺点
- 新的识别方法--状态链
(2)状态机在Redy中,总其有这么一些运算符号:
- '(' ')' '[' ']' '.' ','
- '+' '-' '~'
- '*' '/' '%'
- '<<' '>>'
- '<' '>' '<=' '>='
- '==' '!='
- '&' '^' '|'
- 'and' 'or' 'not'
- '=' '+=' '-=' '*=' '/=' '%='
- '&=' '^=' '|=' '>>=' '<<=
其中运算符'and' , 'or' , 'not' 这三个,我们用把它归在变量识别里面,每当扫描器扫描到一个变量的单词时,扫描器会对该单词重新判断,看它是否真的是变量,或者还是关键字
其中蓝色状态表示终态,总共有34个。开始状态为OperatorBegin。状态图中的状态总共有36个
对于运算符来说,输入类型有这么19种,加上除以下字符以外的字符,,那么总其有20种
- '(' ')' '[' ']' '.' ','
- '+' '-' '~' '*' '/' '%'
- '<' '>' '=' '!'
- '&' '^' '|
(4)新的识别方法--状态链如果用状态矩阵来处理的话,就需要维护一个36*20的数组,处理起来是一件很吓人的事情,如果不小心输错数据,要找出错误很难。当我们需要识别某一种结构简单的单词时,状态矩阵是一种非常常用的方法,前面的文章讲述了怎么用状态矩阵的方法来识别变量,字符串,注释。但这次情况不同,这次我们需要识别运算符,和前面几个比起来,状态与输入类型的数量都要大的多,虽然运算符也可以用状态矩阵来处理,带来的一定的难度。仔细观察,可以上面的状态图看出,虽然输入类型有20种,但是除开始状态OperatorBegin能在多种输入类型下,能发生状态转移,其它状态只能接受一种或两种输入类型,例如,对于状态图中的状态LessThan来说,他只能在字符'<'与字符'='下能发生状态转移,其余字符都不能让LessThan发生状态转换下面我介绍一种新的识别方法来实现状态机模型。
和状态矩阵一样,状态链也是实现状态机模型的一种方法,但是不同的是状态矩阵关心是状态机模型的整体结构,而状态链不同,状态链由多个状态链连接在一起,每一个状态不用去了解自己属于的是那一个状态机,状态机的整体结构是怎样的,它关心自己在可以接受哪一些输入的类型,以及在该输入类型下面转移到的后继状态。
状态链的核心是状态,我们用一 个结构体来表示
- typedef int (*input_map)(char); /*输入类型映射函数*/
- struct state
- {
- char* s_name; /*状态名称*/
- int s_token; /*单词类型,用于后面的语法识别*/
- int s_inputs_num; /*输入类型的数量*/
- char* s_input_map; /*输入类型的映射数组,如果该值为0,则用s_input_func函数指针来判断输入类型*/
- input_map s_input_func; /*输入类型的函数指针*/
- struct state** s_targets; /*后继状态数组*/
- int s_final; /*该状态是否终态*/
- };
结构体 struct state总共有7个成员:
- s_name 用于指向状态名称的字符串,
- s_token 表于单词的类型,用于后面的语法分析
- s_inputs_num 输入类型的数量
- s_input_map 用于映射输入字符的类型,如果为0,则用s_input_func函数指针来判断输入字符的类型。
- s_input_func 用于判断字符的输入类型,只有当s_input_map为0时,该成员函数才会被调用。
- s_targets 后断状态数组,输入类型为1的字符的后继状态为s_tartgets[1],输入类型为n的字符的后继状态为s_targets[n]。
- s_final 指明该状态是否为终态
结构体state中,成员s_input_map与s_input_func都是用于判断字符的输入类型,但当输入类型只有一个或两个的时,使用s_input_map需要建立一个长度为256的一组数组,使用一个函数来判断却只需要一两行找码。但是在输入类型很多的情况下,使用s_input_func变得繁琐,一大堆意大利拉面的代码。接着,用一个函数来获取后继状态
- /*返回状态s在识别字符c后,转移到的状态*/
- static inline struct state* state_next(struct state* s,char c)
- {
- int input_type;
- if(s->s_input_map) /*如果该状态有输入类型映射数组,则用该忽略s_input_func*/
- {
- input_type=s->s_input_map[c]; /*得到输入类型*/
- }
- else /*如果类型映射数组不存在,则用该函数指针获取输入类型*/
- {
- input_type=s->s_input_func(c); /*得到输入类型*/
- }
- return s->s_targets[input_type]; /*返回后继状态*/
- }
虽然采用状态链的方法,不再用去维护一个34*20的状态矩阵,但是要维持34个状态的信息还是挺多的,不过仔细观察状态图,会发现,有很多状态者非常相似。(a)状态Comma , Period , Reverse, L_RB , R_RB, L_SB , R_SB,都是从OperatorBegin转换过来,并且没有后继状态,我们用宏定义处理,以减少复杂度。
- extern struct state lex_state_err;
- extern struct state* lex_state_err_array[];
- extern char input_map_other[];
- #define INIT_FINAL_STATE(name,token) {#name,token,1,input_map_other,0,lex_state_err_array,1}
- #define OP_FINAL_STATE(name,token) \
- struct state name=INIT_FINAL_STATE(name,token)
- OP_FINAL_STATE(op_comma,TOKEN_COMMA);
- OP_FINAL_STATE(op_period,TOKEN_PERIOD);
- OP_FINAL_STATE(op_l_rb,TOKEN_L_RB);
- OP_FINAL_STATE(op_r_rb,TOKEN_R_RB);
- OP_FINAL_STATE(op_l_sb,TOKEN_L_SB);
- OP_FINAL_STATE(op_r_sb,TOKEN_R_SB);
- 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组状态基本上一样,所以也用宏定义。
- static char op_input_map_equal[ASCII_NUM]=
- {
- 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,
- 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,
- 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,
- 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,
- 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,
- 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,
- 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,
- 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
- };
- #define __INIT_OPERATOR_ASSIGN_TRANSLATE(name,token,target_array,final) \
- struct state name= \
- { \
- #name, \
- token,2,op_input_map_equal,0,target_array,final,\
- }\
- #define INIT_OPERATOR_ASSIGN_TRANSLATE(first,token1,final,last,token2) \
- static struct state* operator_private_name_state_array_##first[]=\
- {&lex_state_err,&last}; \
- __INIT_OPERATOR_ASSIGN_TRANSLATE(first,token1,operator_private_name_state_array_##first,final); \
- OP_FINAL_STATE(last,token2)
- INIT_OPERATOR_ASSIGN_TRANSLATE(op_not_equal_begin,TOKEN_UNKOWN,0,op_not_equal,TOKEN_NOT_EQUAL);
- INIT_OPERATOR_ASSIGN_TRANSLATE(op_bits_and,TOKEN_BITS_AND,1,op_assign_bits_and,TOKEN_A_BITS_AND);
- INIT_OPERATOR_ASSIGN_TRANSLATE(op_bits_or,TOKEN_BITS_OR,1,op_assign_bits_or,TOKEN_A_BITS_OR);
- INIT_OPERATOR_ASSIGN_TRANSLATE(op_bits_xor,TOKEN_BITS_XOR,1,op_assign_bits_xor,TOKEN_A_BITS_XOR);
- INIT_OPERATOR_ASSIGN_TRANSLATE(op_multiply,TOKEN_MUL,1,op_assign_multiply,TOKEN_A_MUL);
- INIT_OPERATOR_ASSIGN_TRANSLATE(op_mod,TOKEN_MOD,1,op_assign_mod,TOKEN_A_MOD);
- INIT_OPERATOR_ASSIGN_TRANSLATE(op_minus,TOKEN_MINUS,1,op_assign_minus,TOKEN_A_MINUS);
- INIT_OPERATOR_ASSIGN_TRANSLATE(op_plus,TOKEN_PLUS,1,op_assign_plus,TOKEN_A_PLUS);
- INIT_OPERATOR_ASSIGN_TRANSLATE(op_divide,TOKEN_DIVIDE,1,op_assign_divide,TOKEN_A_DIVIDE);
- INIT_OPERATOR_ASSIGN_TRANSLATE(op_assign,TOKEN_ASSIGN,1,op_equal,TOKEN_EQUAL);
(c)状态(LessThan,LeftShift,LessEqual,LeftShiftAssign), (GreaterThan,GreaterEqual,RightShift,RightShiftAssign),这两组状态也相似,下面我们再看这8个状态的程序
- INIT_OPERATOR_ASSIGN_TRANSLATE(op_right_shift,TOKEN_RS,1,op_assign_right_shift,TOKEN_A_RS);
- OP_FINAL_STATE(op_greater_equal,TOKEN_GE);
- static struct state* op_greater_than_targets[]=
- {
- &lex_state_err,
- &op_greater_equal,
- &op_right_shift,
- };
- int op_input_map_greater_than(char c)
- {
- if(c=='=') return 1;
- else if(c=='>') return 2;
- else return 0;
- }
- struct state op_greater_than=
- {
- "op_greater_than",
- TOKEN_GT,
- 3,
- 0,
- op_input_map_greater_than,
- op_greater_than_targets,
- 1,
- };
- INIT_OPERATOR_ASSIGN_TRANSLATE(op_left_shift,TOKEN_LS,1,op_assign_left_shift,TOKEN_A_LS);
- OP_FINAL_STATE(op_less_equal,TOKEN_LE);
- static struct state* op_less_than_targets[]=
- {
- &lex_state_err,
- &op_less_equal,
- &op_left_shift,
- };
- int op_input_map_less_than(char c)
- {
- if(c=='=') return 1;
- else if (c=='<') return 2;
- else return 0;
- }
- struct state op_less_than=
- {
- "op_less_than",
- TOKEN_LT,
- 3,
- 0,
- op_input_map_less_than,
- op_less_than_targets,
- 1,
- };
(d)最后还有一个状态BeginState,由于BeginState可以接受20种不同类型的输入,所以对于BeginState,我们使用输入映射数组来获取输入的类型。
- enum OP_INPUT_TYPE
- {
- OP_OTHER=0,
- OP_COMMA,
- OP_PERIOD,
- OP_REVERSE,
- OP_L_RB,
- OP_R_RB,
- OP_L_SB,
- OP_R_SB,
- OP_EXCLAMATION,
- OP_AMPERSAND,
- OP_BAR,
- OP_CARET,
- OP_STAR,
- OP_PERCENT,
- OP_MINUS,
- OP_PLUS,
- OP_DIVIDE,
- OP_EQUAL,
- OP_GREATER,
- OP_LESS,
- OP_INPUT_NUM
- };
- char op_input_map_begin[ASCII_NUM]=
- {
- 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,
- 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,
- 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,
- 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,
- 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,
- 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,
- 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,
- 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
- };
- struct state* op_begin_targets[]=
- {
- &lex_state_err,
- &op_comma,
- &op_period,
- &op_reverse,
- &op_l_rb,
- &op_r_rb,
- &op_l_sb,
- &op_r_sb,
- &op_not_equal_begin,
- &op_bits_and,
- &op_bits_or,
- &op_bits_xor,
- &op_multiply,
- &op_mod,
- &op_minus,
- &op_plus,
- &op_divide,
- &op_assign,
- &op_greater_than,
- &op_less_than,
- };
- struct state op_begin=
- {
- "oper_begin",
- TOKEN_UNKOWN,
- OP_INPUT_NUM,
- op_input_map_begin,
- 0,
- op_begin_targets,
- 0
- };
到目前为止,已经用状态链的方法实现了运算符状态机的模型,但上面只是一大堆的数据,要把这一堆数据用起来,就需要写一个读得懂这一堆数据的驱动程序。
驱动程序为:
- /*返回值-1则表示识别错误,其它值表示能识别的最大位置*/
- int driver(struct state* s,char* str,struct state* info)
- {
- int length=strlen(str);
- int i;
- struct state* cur_st=s; /*当前状态*/
- struct state* next_st; /*下一状态*/
- int last_final=-1;
- for(i=0;i<length;i++)
- {
- next_st=state_next(cur_st,str[i]); /*获得下一状态*/
- if(next_st==&lex_state_err) /*如果返回状态为lex_state_err,则表明需要错误处理*/
- {
- return last_final;
- }
- else
- {
- cur_st=next_st;
- if(cur_st->s_final) /*判继该状态是否为终态*/
- {
- last_final=i; /*如果为终态,则保存识别的信息*/
- *info=*cur_st;
- }
- }
- }
- return last_final;
- };
和状态矩阵的驱动程序比起来,还是有一点小小的变化。(6)运行结果
关于运算符识的代码,可以在tutorial/lexical/ssl_operator文件夹中找到.
到现在为上,总共介绍了两种识别方法,一种为状态矩阵,一种为状态链,状态矩阵适合于状态与输入类型都较少的状态机。状态链适合于状态状态数量与输入类型较多,但是大部分状态都只在较少的输入状态下发生状态转移的状态机。在Redy中是使用的状态链的方法进行词法识别的。到目前为止,总共介绍了变量,字符串,注释,运算符的识别方法,这几个词文识别起来都非常容易,后面的文章会给大家介绍怎么去识别整数,浮点数。