Redy词法分析--变量的识别

返回文档首页

（一）简介

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

这一章内容有：

用状态矩阵的方法识别变量

（二）变量识别

1）命名规则

 Redy中变量的命名规则为：首字符必须为字母，下划线或者字符'@'，后面紧接数字，字母，下划线。

2）BNF文法

identifier ::=(letter|'_'|'@')(letter|digit|"_")*
digit ::='0'..'9'
letter ::=lowercase|uppercase
lowercase ::='a'..'z'
uppercase ::='A'..'Z'

3）状态图：

4）状态矩阵

对于变量来说，可以把字符分为这么几类：

1. 数字（digit）
2. 字母（letter）
3. 下划线（underline）
4. 符号＠（s_at）
5. 除上面字符以外其它字符（other）

状态有两个，一个为 identifier_begin，一个为identifier。其中开始状态为identifier_begin，结束状态为identifier

状态矩阵为：

状态\输入	Other	Digit	Letter	Underline	s_at
identifier_begin			identifier	identifier	identifier
identifier		identifier	identifier	identifier

其中空格的地方表示，在当前状态下，并不能识别该输入类型的字符。

5）程序数据

我们用一个一维数组来映射每个字符所属的类型：

#define ID_ERR 0
#define ID_DIGIT 1
#define ID_LETTER 2
#define ID_UNDERLINE 3
#define ID_S_AT 4
char identifier_type_map[ASSIC_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,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,
    4,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,0,0,3,
    0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,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 ID_STATE_TYPES 2
#define ID_INPUT_TYPES 5

#define ID_STATE_BEGIN 0
#define ID_STATE_IDENTIFIER 1
#define ID_STATE_ERROR -1

/*Other  |  Digit  |  Letter  |  Underline  | S_AT  */
int identifier_automaton[ID_STATE_TYPES*ID_INPUT_TYPES]=
{
    /*ID_STATE_BEGIN*/
    ID_STATE_ERROR,ID_STATE_ERROR,ID_STATE_IDENTIFIER,ID_STATE_IDENTIFIER,ID_STATE_IDENTIFIER,
    /* ID_STATE_IDENTIFIER*/
    ID_STATE_ERROR,ID_STATE_IDENTIFIER,ID_STATE_IDENTIFIER,ID_STATE_IDENTIFIER,ID_STATE_ERROR
};

然后再用一个一维数组来表示每一个状态是否为终态：

char id_state[ID_STATE_TYPES]={0,1};

现在我们经完成了大部份的数据。

6）驱动程序

上面这们用状态矩阵法实现了状态机模型，但是状态矩阵是只是一组数据，要让它变得有用，还需要一个驱动程序，驱动程序懂数据的逻辑。为了方面，我们用一个结构体来管理这一组数据

#define ASSIC_NUM 256
#define LEX_ERR -1
struct automaton
{
    int states_num;  /*状态的数量*/
    int inputs_num;  /*输入类型的数量*/
    char* type_map;  /*字符映射到输入类型的数组*/
    int begin_state;    /*开始状态*/
    int* states_matrix;   /*状态矩阵*/
    char* states_info;    /*状态信息*/
};

驱动程序为：

/*返回值－1则表示识别错误，其它值表示能识别的最大位置*/

int driver(struct automaton* am,char* str)
{
    int length=strlen(str);   /*字符串长度*/
    int i;
    int cur_state=am->begin_state;   /*得到开始状态*/
    int last_final=-1;
    for(i=0;i<length;i++)
    {
        int input_type=am->type_map[str[i]];     /*根据当前字符得到输入类型*/

        /*根据当前状态和输入类型，查状态转换表，得到下一个状态*/
        int next_state=am->states_matrix[cur_state*am->inputs_num+input_type];

        /*当前状态是否能识别当前输入类型*/
        if(next_state==LEX_ERR)
        {
            return last_final;
        }
        else
        {
            cur_state=next_state;
            /*如果当前状态为终态，则记录下来识别位置*/
            if(am->states_info[cur_state]==1)
            {
                last_final=i;
            }
        }
    }
    return last_final;
}

下面我们来写一个小的测试程序来验证我们的程序是否工作正常

int main()
{
    char buf[2048];
    char buf_copy[2048];
    printf("input:__quit__ exit\n");
    printf("input:");
    scanf("%s",buf);
    while(strcmp(buf,"__quit__")!=0)
    {
        int ret=driver(&am_id,buf);
        if(ret==-1)
        {
            printf("sorry,Error String\n");
        }
        else
        {
            memcpy(buf_copy,buf,ret+1);
            buf_copy[ret+1]='\0';
            printf("Recongise: %s\n",buf_copy);
            if(ret+1==strlen(buf))
            {
                printf("It's Variable\n");
            }
            else
            {
                printf("It's Not Variable\n");
            }
        }
        printf("\ninput:");
        scanf("%s",buf);
    }
    return 0;
}

（7）运行结果

上面的所有代码都位于：tutorial/lexical/identifier文件夹里面

返回文档首页