Redy词法分析--运算符的识别

返回文档首页

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

这一章的内容有：

1. 运算符号的识别
2. 状态矩阵的缺点
3. 新的识别方法－－状态链

（１）简介

在Redy中，总其有这么一些运算符号：

'(' ')' '[' ']' '.' ','
    '+'  '-'  '~'
    '*' '/' '%'
    '<<' '>>'
    '<' '>' '<=' '>='
    '==' '!='
    '&' '^' '|'
    'and' 'or' 'not'
    '=' '+=' '-=' '*=' '/=' '%='
    '&=' '^=' '|=' '>>=' '<<=

其中运算符'and' , 'or'  , 'not' 这三个，我们用把它归在变量识别里面，每当扫描器扫描到一个变量的单词时，扫描器会对该单词重新判断，看它是否真的是变量，或者还是关键字

（２）状态机

其中蓝色状态表示终态，总共有34个。开始状态为OperatorBegin。

状态图中的状态总共有36个

（３）状态矩阵

对于运算符来说，输入类型有这么１９种，加上除以下字符以外的字符，，那么总其有20种

'('    ')'    '['    ']'    '.'    ','
'+'    '-'    '~'    '*'    '/'    '%'
'<'    '>'    '='    '!'
'&'    '^'    '|

如果用状态矩阵来处理的话，就需要维护一个36*20的数组，处理起来是一件很吓人的事情，如果不小心输错数据，要找出错误很难。

当我们需要识别某一种结构简单的单词时，状态矩阵是一种非常常用的方法，前面的文章讲述了怎么用状态矩阵的方法来识别变量，字符串，注释。但这次情况不同，这次我们需要识别运算符，和前面几个比起来，状态与输入类型的数量都要大的多，虽然运算符也可以用状态矩阵来处理，带来的一定的难度。仔细观察，可以上面的状态图看出，虽然输入类型有20种，但是除开始状态OperatorBegin能在多种输入类型下，能发生状态转移，其它状态只能接受一种或两种输入类型，例如，对于状态图中的状态LessThan来说，他只能在字符'<'与字符'='下能发生状态转移，其余字符都不能让LessThan发生状态转换

下面我介绍一种新的识别方法来实现状态机模型。

（4）新的识别方法－－状态链

和状态矩阵一样，状态链也是实现状态机模型的一种方法，但是不同的是状态矩阵关心是状态机模型的整体结构，而状态链不同，状态链由多个状态链连接在一起，每一个状态不用去了解自己属于的是那一个状态机，状态机的整体结构是怎样的，它关心自己在可以接受哪一些输入的类型，以及在该输入类型下面转移到的后继状态。

状态链的核心是状态，我们用一 个结构体来表示

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个成员：

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  后断状态数组，输入类型为１的字符的后继状态为s_tartgets[1]，输入类型为n的字符的后继状态为s_targets[n]。
7. 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) 这几９组状态基本上一样，所以也用宏定义。

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)，这两组状态也相似，下面我们再看这８个状态的程序

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可以接受２０种不同类型的输入，所以对于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中是使用的状态链的方法进行词法识别的。

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

返回文档首页