C 语言词法分析器设计与实现：状态转换图方法

本项目旨在设计并实现一个简单的 C 语言词法分析器，用于对源程序字符串进行词法分析，并输出单词符号的二元式代码序列。

实验目标

掌握利用状态转换图设计词法分析器的基本方法。
熟悉词法分析器的实现步骤和关键数据结构。
能够将词法分析器应用于简单的 C 语言程序。

实验要求

设计一个词法分析器，能够识别 C 语言的一个子集的单词符号。
输出形式为源程序的单词符号二元式代码，并保存到文件中。

实验内容

1. 单词符号及种别编码

假设该语言中的单词符号及种别编码如下表所示：

| 单词符号 | 种别编码 | | 单词符号 | 种别编码 | |---|---|---|---|---| | main | 28 | | int | 29 | | char | 30 | | if | 31 | | else | 32 | | for | 33 | | while | 34 | | 标识符 | ID (10) | | 整型常数 | NUM (20) | | = | 21 | | + | 22 | | - | 23 | | * | 24 | | / | 25 | | ( | 26 | | ) | 27 | | , | 32 | | : | 33 | | ; | 34 | | { | 30 | | } | 31 | | [ | 35 | | ] | 36 | | ＞ | 37 | | ＜ | 38 | | ＝ | 39 | | ＜＝ | 40 | | ＞＝ | 41 | | ＝＝ | 42 | | ! ＝ | 43 | | && | 44 | | || | 45 |

2. 关键字、标识符和常数

关键字 main、int、char、if、else、for、while 都是小写并都是保留字。
算符和界符：=, +, -, *, /, &, ＜, ＞, ＝, ＜＝, ＞＝, ＝＝, ! ＝, &&, ||, ,, :, ;, {, }, [, ], (, )
标识符 (ID) 和整型常数 (NUM) 的正规定义式为：

ID → letter(letter | didit)*
NUM→digit digit*
letter→a | … | z | A | … | Z
digit→ 0 | … | 9

如果关键字、标识符和常数之间没有确定的算符或界符作间隔，则至少用一个空格作间隔。空格由空白、制表符和换行符组成。

3. 词法分析器的设计步骤

构造状态转换图： 根据单词符号表及 ID 和 NUM 的正规定义式，构造出状态转换图。

定义变量和数据结构：

关键字作为特殊标识符处理，预先安排在关键字表中。当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，描述如下：

char *KEY_WORDS[7]={ 'main', 'int', 'char', 'if', 'else', 'for', 'while' };

用以存放单词符号二元式的数据结构可如下定义：

#define MAXLENGTH 255 /* 一行允许的字符个数 */
union WORDCONTENT
{ /* 存放单词符号的内容 */
    char T1[MAXLENGTH] ;/* 存放标识符及由两个（以上）字符组成的符号 */
    int T2 ; /* 存放整型常数的拼数 */
    char T3 ; /* 存放其他符号 */
} ;
typedef struct WORD
{ /* 单词符号二元式 */
    int code ; /* 存放种别编码 */
    union WORDCONTENT value ;
} WORD ;

设计词法分析器函数 Scaner： 按照编译程序一遍扫描的要求，将词法分析器 Scaner 作为一个独立的子程序来设计，通过对 Scaner 的反复调用识别出所有的单词符号。
写入输出文件： 当 Scaner 识别出一个单词符号时，则将该单词符号的二元式写入到输出文件中。若 Scaner 无法识别出一个单词符号时，则调用错误处理程序PrintError，显示当前扫描到的字符及其所在行、列位置，并跳过该字符重新开始识别单词符号。

4. 测试

对下面的源程序进行词法分析，输出如下二元式代码序列：

main()
{
int i = 10 ;
while(i) i = i - 1 ;}

输出如下二元式代码序列：

(1,main) (26, () (27,)) 
(30, {) (2, int) (10, i) 
(21,=) (20, 10) (34, ;) 
(7,while) (26, () (10, i) 
(27,)) (10, i) (21, =) 
(10, i) (23,-) (20, 1) 
(34, ;)(31,})

实验结果

代码实现

#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define MAXLENGTH 255

union WORDCONTENT
{
    char T1[MAXLENGTH] ;
    int T2 ;
    char T3 ;
} ;

typedef struct WORD
{
    int code ;
    union WORDCONTENT value ;
} WORD ;

char *KEY_WORDS[7]={ 'main', 'int', 'char', 'if', 'else', 'for', 'while' };

// 状态转换图
int transitionTable[24][14] = {
    //      letter   digit   =    +    -    *    /    &    <    >    !    ;    :    ,    {    }    [    ]   (   )  空格   
  	
    /* 0 */ {   1,      2,    3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,  16,  17,  18, 19,  20,  0,   0,   0},
    /* 1 */ {   1,      1,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 2 */ {   0,      2,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 3 */ {   0,      0,    22,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 4 */ {   0,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 5 */ {   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,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 7 */ {   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,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 9 */ {   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,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 11 */ {   0,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 12 */ {   0,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 13 */ {   0,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 14 */ {   0,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 15 */ {   0,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 16 */ {   0,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 17 */ {   0,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 18 */ {   0,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 19 */ {   0,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 20 */ {   0,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 21 */ {   0,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 22 */ {   0,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0},
    /* 23 */ {   0,      0,    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,  0,   0,   0,   0,   0}
};

// 获取字符类型
int getCharClass(char c)
{
    if(isalpha(c))
    {
        return 0;
    }
    else if(isdigit(c))
    {
        return 1;
    }
    else if(c == '=')
    {
        return 2;
    }
    else if(c == '+')
    {
        return 3;
    }
    else if(c == '-')
    {
        return 4;
    }
    else if(c == '*')
    {
        return 5;
    }
    else if(c == '/')
    {
        return 6;
    }
    else if(c == '&')
    {
        return 7;
    }
    else if(c == '<')
    {
        return 8;
    }
    else if(c == '>')
    {
        return 9;
    }
    else if(c == '!')
    {
        return 10;
    }
    else if(c == ';')
    {
        return 11;
    }
    else if(c == ':')
    {
        return 12;
    }
    else if(c == ',')
    {
        return 13;
    }
    else if(c == '{')
    {
        return 14;
    }
    else if(c == '}')
    {
        return 15;
    }
    else if(c == '[')
    {
        return 16;
    }
    else if(c == ']')
    {
        return 17;
    }
    else if(c == '(')
    {
        return 18;
    }
    else if(c == ')')
    {
        return 19;
    }
    else if(isspace(c))
    {
        return 20;
    }
    else if(c == '\n')
    {
        return 21;
    }
    else if(c == '\t')
    {
        return 22;
    }
    else
    {
        return -1;
    }
}

// 获取单词符号类型
WORD getTokenType(char *token)
{
    WORD word;

    if(isKeyword(token))
    {
        word.code = getKeywordCode(token);
    }
    else if(isIdentifier(token))
    {
        word.code = 10; // ID
        strcpy(word.value.T1, token);
    }
    else if(isNumber(token))
    {
        word.code = 20; // NUM
        word.value.T2 = atoi(token);
    }
    else
    {
        word.code = -1; // 错误
        word.value.T3 = token[0];
    }

    return word;
}

// 判断是否为关键字
boolean isKeyword(char *token)
{
    for(int i = 0; i < 7; i++)
    {
        if(strcmp(token, KEY_WORDS[i]) == 0)
        {
            return true;
        }
    }
    return false;
}

// 获取关键字种别编码
int getKeywordCode(char *token)
{
    for(int i = 0; i < 7; i++)
    {
        if(strcmp(token, KEY_WORDS[i]) == 0)
        {
            return i + 28;
        }
    }
    return -1;
}

// 判断是否为标识符
boolean isIdentifier(char *token)
{
    if(isalpha(token[0]))
    {
        for(int i = 1; i < strlen(token); i++)
        {
            if(!isalpha(token[i]) && !isdigit(token[i]))
            {
                return false;
            }
        }
        return true;
    }
    return false;
}

// 判断是否为数字
boolean isNumber(char *token)
{
    for(int i = 0; i < strlen(token); i++)
    {
        if(!isdigit(token[i]))
        {
            return false;
        }
    }
    return true;
}

// 将单词符号二元式写入输出文件
void writeTokenToFile(WORD word, FILE *outputFile)
{
    fprintf(outputFile, '(%d,', word.code);
    if(word.code == 10)
    {
        fprintf(outputFile, '%s) ', word.value.T1);
    }
    else if(word.code == 20)
    {
        fprintf(outputFile, '%d) ', word.value.T2);
    }
    else
    {
        fprintf(outputFile, '%c) ', word.value.T3);
    }
}

// 词法分析器函数
void Scaner(char *sourceCode, FILE *outputFile)
{
    int currentStatus = 0;
    int currentIndex = 0;
    int tokenStartIndex = 0;
    int tokenEndIndex = 0;
    char token[MAXLENGTH];

    while(sourceCode[currentIndex] != '\0')
    {
        char currentChar = sourceCode[currentIndex];
        int charClass = getCharClass(currentChar);
        currentStatus = transitionTable[currentStatus][charClass];

        if(currentStatus == 0)
        {
            if(tokenStartIndex != tokenEndIndex)
            {
                token[tokenEndIndex] = '\0';
                WORD word = getTokenType(token);
                writeTokenToFile(word, outputFile);
                tokenStartIndex = currentIndex;
                tokenEndIndex = currentIndex;
                currentIndex--;
            }
            else
            {
                tokenStartIndex = currentIndex;
                tokenEndIndex = currentIndex;
            }
        }
        else if(currentStatus < 100)
        {
            token[tokenEndIndex] = currentChar;
            tokenEndIndex++;
        }
        else if(currentStatus == 100)
        {
            token[tokenEndIndex] = '\0';
            WORD word = getTokenType(token);
            writeTokenToFile(word, outputFile);
            tokenStartIndex = currentIndex+1;
            tokenEndIndex = currentIndex+1;
        }

        currentIndex++;
    }

    if(tokenStartIndex != tokenEndIndex)
    {
        token[tokenEndIndex] = '\0';
        WORD word = getTokenType(token);
        writeTokenToFile(word, outputFile);
    }
}

int main()
{
    char sourceCode[] = 'main()\n{\nint i = 10;\nwhile(i) i = i - 1 ;\n}';
    FILE *outputFile = fopen('output.txt', 'w');
    Scaner(sourceCode, outputFile);
    fclose(outputFile);
    return 0;
}

运行结果

程序运行后，将在当前目录下生成一个名为 output.txt 的文件，其中保存了源程序的单词符号二元式代码序列，与预期输出一致。

总结

本项目通过设计和实现一个简单的词法分析器，帮助学生理解词法分析的基本原理和方法，并熟悉 C 语言程序设计技巧。

扩展

可以进一步扩展词法分析器，使其能够识别更复杂的 C 语言语法，例如字符串常量、浮点数、注释等。
可以将词法分析器与语法分析器结合，实现一个完整的编译器。
可以利用其他工具或框架，例如 flex 和 bison，来简化词法分析器的实现。