博客

【编译原理】词法分析（自定义标识符、常数、关键字、界符识别）代码实现

  • Post author:
  • Post category:其他


1.前言

本篇博客实现一个编译原理的词法分析器，能够识别用户自定义标识符、常数、字符串、关键字、界符。

词法分析包括：用户自定义标识符、常数、字符串、关键字、界符的识别。用户自定义符号，顾名思义就是自己定义的变量名；函数名，常数包括整数、浮点数、科学计数；字符串包括‘ ’、” “两种形式的字符串；关键字就是程序内置的关键字，如int、main等；界符就是各类符号，如运算符、{}、[]等。

词法分析的任务是，给定输入，识别输入序列中的单词，并将其正确分类。对于重复出现的单词，应该保证唯一性。

词法分析说容易也容易，人一眼就可以看出来一个”词“是属于哪一类的，然而让计算机来做就需要抽象出规则。常用的词法分析处理思路就是使用DFA，这在常数识别上体现得淋漓尽致。

2.代码实现

2.1 Word类型

Word类型是原字符序列经过分析后得到的单词序列。其中val值（整数\浮点）是为了日后计算，在这里没有使用。 

/**
 * kind:识别种类 id:序号 name:自定义名|字符串|字符 val:常数值
 * */
struct Word
{
    int kind;
    string name = "";
    int val1;
    double val2;
} word_list[1000];

2.2 Token类型

Token类型是符号表的数据结构类型。符号表采用链表的数组实现。 

struct Token
{
    int kind, id;//单词类型，单词序号
    string tkval = "";//单词字符串值
    Token *next = NULL;
} token_list[7]; //0号不用，1-6分别表示6种不同单词类型

kind类型：1–用户自定义标识符，2–字符，3–字符串，4–常数，5–关键字，6–界符。

2.3 用户自定义标识符识别&关键字识别

之所以这二者同时做，是因为自定义标识符和关键字的识别很像，但是自定义标识符要避免与关键字的冲突。因此，二者结合来识别就很有必要。检查方式就是首先识别单词，再在Token链表里查关键字那栏有没有这个单词。 

/**
 * 标识符识别（用户自定义标识符1、关键字5）
*/
string judgeIdt(char &ch, ifstream &infile)
{
    string str = "";
    while (((ch >= 'a' && ch <= 'z') ||
            (ch >= 'A' && ch <= 'Z') ||
            (ch == '_') ||
            (ch >= '0' && ch <= '9')) &&
           (!infile.eof()))
    {
        str = str + ch;
        infile >> ch;
    }
    return str;
}
void judge(string word)
{
    if (ch == '_' || (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
    {
         string word = judgeIdt(ch, infile);
         if (findTK(word, 5) == NULL)
         {
              addTKList(word, 1); //用户自定义符号
         }
    }
}

2.4 字符&字符串识别

这部分处理得非常简单，在字符串符号之间一律视为”字符部分“，不考虑转义字符等情况。 

/**
 * 字符识别2
*/
string judegChs(char &ch, ifstream &infile)
{
    string str = "";
    str = str + ch;
    infile >> ch;
    while (ch != '\'' && !infile.eof())
    {
        str = str + ch;
        infile >> ch;
    }
    str = str + ch;
    infile >> ch;
    cout << "(" << str << "," << num2kind[2] << ")" << endl;
    return str;
}
/**
 * 字符串识别3
*/
string judgeStr(char &ch, ifstream &infile)
{
    string str = "";
    str = str + ch;
    infile >> ch;
    while (ch != '\"' && !infile.eof())
    {
        str = str + ch;
        infile >> ch;
    }
    str = str + ch;
    infile >> ch;
    cout << "(" << str << "," << num2kind[3] << ")" << endl;
    return str;
}

2.5 常数识别

这里不像之前，由于识别的问题对象很复杂，所以先设计一个DFA，再实现这个DFA即可，关于DFA我准备过几天再开一篇博客单独讲。 

/**
 * 常数识别4
*/
string judgeConst(char &ch, ifstream &infile)
{
    string str = "";
    int state = 0;
    bool flag = false;
    while (state != 7) //有限状态自动机，7为终止状态
    {
        switch (state)
        {
        case 0:
            if ((ch >= '0' && ch <= '9') || ch == '-')
            {
                state = 1;
                str += ch;
                infile >> ch;
            }
            break;
        case 1:
            if (ch >= '0' && ch <= '9')
            {
                state = 1;
                str += ch;
                infile >> ch;
            }
            else if (ch == 'e' || ch == 'E')
            {
                state = 4;
                str += ch;
                infile >> ch;
            }
            else if (ch == '.')
            {
                state = 2;
                str += ch;
                infile >> ch;
            }
            else
            {
                state = 7;
                flag = true;
            }
            break;
        case 2:
            if (ch >= '0' && ch <= '9')
            {
                state = 3;
                str += ch;
                infile >> ch;
            }
            break;
        case 3:
            if (ch == 'e' || ch == 'E')
            {
                state = 4;
                str += ch;
                infile >> ch;
            }
            else if (ch >= '0' && ch <= '9')
            {
                state = 3;
                str += ch;
                infile >> ch;
            }
            else
            {
                flag = true;
            }
            break;
        case 4:
            if (ch == '+' || ch == '-')
            {
                state = 5;
                str += ch;
                infile >> ch;
            }
            else if (ch >= '0' && ch <= '9')
            {
                state = 6;
                str += ch;
                infile >> ch;
            }
            break;
        case 5:
            if (ch >= '0' && ch <= '9')
            {
                state = 6;
                str += ch;
                infile >> ch;
            }
            break;
        case 6:
            if (ch >= '0' && ch <= '9')
            {
                state = 6;
                str += ch;
                infile >> ch;
            }
            if (ch < '0' || ch > '9')
            {
                state = 7;
            }
            break;
        case 7:
            flag = true;
            break;
        }
        if (flag)
            break;
    }
    cout << "(" << str << "," << num2kind[4] << ")" << endl;
    return str;
}

2.6 界符识别

界符需要结合自己定义的界符集合。比如我定义的集合是{+,-,*,/,>,<,>=,<=,==,{,},[,],(,)}，这里就要考虑>、>=等的区分问题。 

/**
 * 识别界符6
*/
string judgeDeli(char &ch, ifstream &infile)
{
    string str = "";
    if ((ch < 'a' || ch > 'z') && (ch < 'A' || ch > 'Z') && (ch < '0' || ch > '9'))
    {
        str = str + ch;
        infile >> ch;
    }
    if (ch == '=')
    {
        str = str + ch;
        infile >> ch;
    }
    return str;
}

2. 7 主控程序

这部分主要实现根据判断条件进行子程序的调用、输入文件、输出结果。 

int main()
{
    string fileName;
    char ch; //当前读入符号
    cout << "Please input the file name:" << endl;
    cin >> fileName;//确保文件在路径下
    ifstream infile;
    infile.open(fileName.data());
    assert(infile.is_open());
    infile >> noskipws;
    infile >> ch;
    initTKList();
    printf("The filtered words are as follows:\n");
    while (!infile.eof() && ch != EOF)
    {
        if (ch == '_' || (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) //标识符、关键字
        {
            string word = judgeIdt(ch, infile);
            if (findTK(word, 5) == NULL)
            {
                cout << "(" << word << "," << num2kind[1] << ")" << endl;
                addTKList(word, 1); //用户自定义符号
            }
            else
            {
                cout << "(" << word << "," << num2kind[5] << ")" << endl;
            }
        }
        else if (ch == '\n' || ch == '\t' || ch == ' ')//跳过空格、制表符、换行
        {
            infile >> ch;
        }
        else if ((ch >= '0' && ch <= '9') || ch == '-') //常数
        {
            string word = judgeConst(ch, infile);
            addTKList(word, 4);
        }
        else if (ch == '\'' || ch == '\"') //字符、字符串
        {
            if (ch == '\'')
            {
                string word = judegChs(ch, infile);
                addTKList(word, 2);
            }
            else
            {
                string word = judgeStr(ch, infile);
                addTKList(word, 3);
            }
        }
        else //界符
        {
            string word = judgeDeli(ch, infile);
            // addTKList(word, 6);
        }
    }
    printf("-------------------------------------------\n");
    showTKList();
    infile.close();
    system("pause");
    return 0;
}

3.结语

这个词法分析器是一个“总分结构”，各种识别功能我在子程序写好，然后在主控程序里调用即可。解释一下入口条件和出口条件：入口条件是主控程序的判断条件，指针读到的第一个字符决定主程序应该调用哪个子程序。出口条件是子程序执行期间的判断条件，决定何时单词识别结束、可以跳出。

实现词法分析解释了我学C语言时的困惑。比如，为什么用户自定义变量名不能以数字开头？——为了方便确定入口条件。

最后，常数识别这部分的实现过程我觉得是值得亲手实践的，实现这部分可以增强我们应用DFA的能力。


版权声明：本文为weixin_42455135原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。