编译原理之词法分析程序

实验课上实现了对词法分析程序的编写。整个过程中,最为困难的就是对整个编译过程的设计。在这里整理一下我的整个从设计到实现过程以及中间出现的问题。

问题描述

假定一种高级程序设计语言中的单词主要包括关键字begin、end、for、if、then、else标识符整数六种关系运算符,试构造能识别这些单词的词法分析程序。

下面是各类单词符号以及编码对应表

编译原理之词法分析程序

最后我们将实现输入一段代码,然后输出键值对的形式:

输入:
if myid >= 15 then x = y
输出:
(IF, " ")
(ID, "myid")
(GE, " ")
(INT, "15")
(THEN, " ")
(ID, "x")
(EQ, " ")
(ID, "y")

状态转换图

首先同时也是最为复杂的就是如何设计状态转换图。

根据我们过去使用过的各种编程语言,再结合上面所给的类型表格,可以简单分为几种情况:

1.字母开头
1.1 关键字
1.2 标识符(字母开头的字母数字串)
2.数字开头: 整数
3.比较符号: 关系运算符

那么现在就是如何将上面的情况转换成图了。

编译原理之词法分析程序

通过对第一种情况的翻译,我们会得到上面的状态转换图。可以发现,当我们将各种情况都列好以后,转换图好像也没有想象的那么难了。

然后跟上面的方法一样,我们将得到一个较为完整的转换图:

编译原理之词法分析程序

可以看到,上面的转换图不仅包含了转换的条件,同时,也标明了转换过程中用到的方法。这也是我们下一步要解决的。

功能函数

状态转换图中一共有这么几个功能函数:GETCHAR(读取一个字符)CAT(拼接单词)LOOKUP(检查是否为关键字)RETRACT(回退一个字符)OUT(输出)

然后就到我们要实际编写代码的时候了。

1.GETCHAR

由于在实现这个程序的时候,设计是由文件中读取出源程序,然后输出到控制台上。所以会用到一些文件的读取操作。相应的,C语言的类库中有一些已经写好的函数,所以我们可以直接拿来用:

char ch = fgetc(fp);

fp是一个函数指针,fgetc函数的作用就是读取一个字符,然后将指针向后移动一个。

2.CAT

拼接的实现是利用了字符数组实现的:

char TOKEN[20];

定义一个数组用来存放单词,然后就可以将上面获取的单词依次存如数组中。

TOKEN[i] = ch;      // 保存字符
i++;

当然,这需要一个循环:

while (isalnum(ch)) {
    TOKEN[i] = ch;      // 保存字符
    i++;                // 长度加一
    ch = fgetc(fp);     // 读取下一个字符
}

3.LOOKUP

这个的实现也比较简单,只需要按顺序比价保留字列表,看时候与刚刚扫描出的单词匹配就可以了。

int lookup(char *token) {
    int n = 0;

    // 依次比较所有保留字
    while (strcmp(KeyWordTable[n], KEY_WORD_END)) {

        // 比较token所指向的关键字和保留字表中哪个关键字相符
        if (!strcmp(KeyWordTable[n], token)) {
            return n + 1;     // 返回关键字对应的编码
        }
        n++;
    }
    return 0;               // 单词不是关键字,而是标识符
}

4.RETRACT

同读取一样,这个的实现也是借助于类库中的方法:

fseek(fp, -1, 1);       // 将文件指针指向当前位置的前一个位置

5.OUT

最后输出的功能就比较简单了,只要将所有的情况都不遗漏,就可以了。

switch (code) {
        case BEGIN:
            cout << "(BEGIN, \" \")" << endl;
            break;
        case END:
            cout << "(END, \" \")" << endl;
            break;
        case IF:
            cout << "(IF, \" \")" << endl;
            break;
        case THEN:
            cout << "(THEN, \" \")" << endl;
            break;
        case ELSE:
            cout << "(ELSE, \" \")" << endl;
            break;
        case ID:
            cout << "(ID, \"" << value << "\")" << endl;
            break;
        case INT:
            cout << "(INT, \"" << value << "\")" << endl;
            break;
        case LT:
            cout << "(LT, \" \")" << endl;
            break;
        case LE:
            cout << "(LE, \" \")" << endl;
            break;
        case EQ:
            cout << "(EQ, \" \")" << endl;
            break;
        case NE:
            cout << "(NE, \" \")" << endl;
            break;
        case GT:
            cout << "(GT, \" \")" << endl;
            break;
        case GE:
            cout << "(GE, \" \")" << endl;
            break;
        default:
            cout << "编码错误!" << endl;
            break;
    }
}

总结

通过对编译原理的学习,越发感觉思维的重要性。

当我们有了思想后,代码实现不过只是一个工具而已。

相关推荐