Redy语法分析--扫描器的设计与实现

返回文档首页

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

这一章的内容有：

扫描器的设计与实现

（1）扫描器的设计与实现

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

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

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

#define SCANNER_DEFALUT_LITERIAL_SIZE 128
struct scanner
{
    struct lex_file* s_lf;
    int s_cur_token;
    int s_line;
    char* s_cur_literal;
    int s_literial_size;

};

扫描器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来初始化扫描器

static void sc_init(struct scanner* sc,struct lex_file* lf)
{
    sc->s_lf=lf;
    sc->s_cur_token=TOKEN_UNKOWN;
    sc->s_line=1;
    sc->s_cur_literal=(char*)malloc(SCANNER_DEFALUT_LITERIAL_SIZE);
    sc->s_literial_size=SCANNER_DEFALUT_LITERIAL_SIZE;
}


struct scanner* sc_create(char* filename)
{
    struct lex_file* lf=lf_create(filename);
    if(lf==NULL)
    {
        WARN("Open file[%s] Failed",filename);
        return NULL;
    }
    struct scanner* sc=(struct scanner*)malloc(sizeof(*sc));
    sc_init(sc,lf);
    return sc;

}
struct scanner* sc_stream_create(FILE* file)
{
    struct lex_file* lf=lf_stream_create(file);
    if(lf==NULL)
    {
        WARN("Create Scanner Failed");
        return NULL;
    }
    struct scanner* sc=(struct scanner*)malloc(sizeof(*sc));
    sc_init(sc,lf);
    return sc;
}

扫描器的销毁：

void sc_destory(struct scanner* sc)
{
    lf_destory(sc->s_lf);
    free(sc->s_cur_literal);
    free(sc);

}

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

扫描器对采用我们前面的状态机字符序列进行识别，状态机的开始状态为me_begin，扫描器从输入缓冲区得到一个字符，然后调用函数state_next得到当前状态的后继状态，后继状态有这么三种情况

1. 终态，说明扫描器已经扫描到了一个词文，但是扫描器是采用最大识别的方法，所以扫描器还有往后扫描，看能不能扫描到长度更大的词文，如果不能，则需要回到该位置，所以需要调用函数lf_mark对当前位置进行标记，以便回到该位置。
2. 错误状态(lex_state_err)，说明扫描器扫描的字符序列已经不能构成一个词文了，所以这时需要停止扫描，然后在进行判断看以前时否到达过终态，如果没有则说明我们源程序中出现了错误的字符序例。如果到达过，则返回以前识别到的词文。
3. 普通状态，继续往下扫描

在最后，扫描器把扫描的词文通过函数sc_set_cur_literial复制到成员s_cur_literal里面。

static void sc_set_cur_literial(struct scanner* sc,char* buf,int length)
{
    if(sc->s_literial_size<length+1)
    {
        char* new_space=(char*)malloc(length+1);
        free(sc->s_cur_literal);
        sc->s_cur_literal=new_space;
    }
    memcpy(sc->s_cur_literal,buf,length);
    sc->s_cur_literal[length]='\0';
}

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

    char cur;
    char next=lf_next_char(lf);
    struct state* cur_state=&me_begin;
    struct state* next_state;
    struct state* finnal_state=NULL;
    while(1)
    {
        cur=next;


        if(cur==EOF)
        {
            sc->s_cur_token=TOKEN_EOF;
            break;
        }
        if(cur=='\n')
        {
            sc->s_line++;
        }
        next_state=state_next(cur_state,cur);
        if(next_state==&lex_state_err)
        {
            if(finnal_state==NULL)
            {
                sc->s_cur_token=TOKEN_ERR;
            }
            else
            {
                sc->s_cur_token=finnal_state->s_token;
            }
            break;
        }


        if(state_final(next_state))
        {
            finnal_state=next_state;
            lf_mark(lf);
        }
        next=lf_next_char(lf);
        cur_state=next_state;
    }

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

    return sc->s_cur_token;
}

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

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

    int token;
    int i=0;
    while(1)
    {
        i++;
        if(i%5==0)
        {
            printf("\n");
        }
        token=sc_next_token(sc);
        if(token==TOKEN_EOF)
        {
            break;
        }
        if(token==TOKEN_ERR)
        {
            goto err;
        }
        if(token==TOKEN_ID)
        {
            if(symbol_type(sc_token_string(sc))==TOKEN_ID)
            {
                printf("{variable,%s} ",sc_token_string(sc));
            }
            else
            {
                printf("{keyword,%s} ",sc_token_string(sc));
            }
            continue;
        }
        if(token==TOKEN_ANNO)
        {
            continue;

        }
        if(token==TOKEN_WS)
        {
            continue;
        }
        if(token==TOKEN_NEWLINE)
        {
            printf("{newline} ");
            continue;
        }
        printf("{%s,%s} ",token_name(token),sc_token_string(sc));
    };

    return 0;
err:
    printf("err token at line %d\n",sc->s_line);
    return -1;
}

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

Redy程序：

a=random()
b=random()
if a+b/2==557
    a.inc()
    if a/2
        a.dec()
    else
        a.inc()
    end
elif a+b/3==6
    a.dec()
else
    b=a/2
end
print a
print b

运行结果

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

返回文档首页