原创文章，转载、引用请注明出处！

2019-05-20更新专题设计内容。

目标任务

要求

以下为正则文法所描述的 C 语言子集单词符号的示例，请补充单词符号: ++，–， >>, <<, += , -= ,*=, /= ，&&(逻辑与)，||(逻辑或)，!(逻辑非)等等，给出补充后描述C语言子集单词符号的正则文法，设计并实现其词法分析程序。

<标识符>-> 字母— <标识符>字母— <标识符>数字
<无符号整数>-> 数字— <无符号整数>数字
<单字符分界符>-> + – —* —;—, —(-) —{—}
<双字符分界符>-> <大于>=—<小于>=—<小于>>—<感叹号>=—<等于>=—<斜竖>*
<小于>-> <
<等于>-> =
<大于>-> >
<斜竖>-> /
<感叹号>-> !

该语言的保留字 :void、int、float、double、if、else、for、do、while 等等(也可补充)。

设计说明

(1)可将该语言设计成大小写不敏感，也可设计成大小写敏感，用户定义的标识符最长不超过 32 个字符;
(2)字母为 a-z A-Z，数字为 0-9;
(3)可以对上述文法进行扩充和改造;
(4)“/*……*/”和“//”(一行内)为程序的注释部分。

设计要求

(1)给出各单词符号的类别编码;
(2)词法分析程序应能发现输入串中的错误;
(3)词法分析作为单独一遍编写，词法分析结果为二元式序列组成的中间文件;
(4) 设计两个测试用例(尽可能完备)，并给出测试结果。

解答

词法分析器

词法分析是编译程序进行编译时第一个要进行的任务，主要是对源程序进行编译预处理（去除注释、无用的回车换行找到包含的文件等）之后，对整个源程序进行分解，分解成一个个单词，这些单词大致可五类，分别是标识符、保留字、常数、运算符、界符。以便为下面的语法分析和语义分析做准备。

词法分析面向的对象是单个的字符，目的是把它们组成有效的单词（字符串）。另外，由于词法分析器在编译器中负责读取源程序，因此除了识别词素之外，它还会完成一些其他任务，比如过滤掉源程序中的注释和空白，将编译器生成的错误消息与源程序的位置关联起来等。

设计思想

根据对词法分析器的解释可知，一个词法分析器需要实现以下基本功能：

（1）识别词素：将字符所组成的词正确分割且加以分类；
（2）错误指示：将编译器生成的错误消息与源程序的位置关联起来。

而词法分析过程中有一些不必要的过程，这些过程虽然不是词法分析的核心思想，但是合理运用有助于更好的完成这一任务：

（1）过滤源程序中的无用字符（注释和空白等）；
（2）词法分析一旦遇到错误不一定要直接停止，而是跳过错误部分继续后面的分析（一处错误并不一定导致其后的内容错误）。

以结构化程序思想看待上述设计思想，就可以用这样的流程来实现词法分析器程序：

对于目标内容中的每一个字符都进行上述处理，然后按照处理顺序将词素识别出来，加以区分；将无法识别的词素认定为错误，定出位置即可。

明晰了程序流程之后，接下来的问题是：如何识别词素？换言之，什么样的词素在我们看来才是“正确”的？由于我们编写的是C语言字符集的词法分析程序，那么首先可以确定的是：符合c语言词法规则的词是我们需要加以识别的。

而C语言的词法规则是极其复杂的，即使我们所写的是简化版字符集，一样也有很多内容需要我们去完善，直接编写势必会使代码复杂度增加，且没有统一的代码规则规定我们的判断条件。

在学习过编译原理的文法之后，我们都知道，只有满足字符集文法规则的终结字符才可以被识别成为正确。

所以词法分析程序的更深层目标应该是完善我们要编写的字符集的规则，并把它转化成文法规则，以计算机代码表示。这样，针对特定字符时，我们的查找就有了方向。

代码流程描述

函数调用流程如下：

文件结构及函数简介如下：

字符集及其规则描述

首先给出扩充后的字符集及其编码：

可将上述字符分为三类：标识符（保留字）及数字、单字符、双字符。对于不可衍生出双字符的单字符而言，只要检测到的单字符存在于上述定义表中即可匹配成功。而部分单字符的衍生字符和标识符（保留字）及数字的长度往往不止一个字符，那么就要对它们的词法规则作出规定，这样的规定既要符号现实的c语言词法规则，也要能被我们的代码结构（条件判断语句）所识别。

规则如下：

<标识符>→字母|<标识符>字母|<标识符>数字
<无符号整数>→数字|数字<无符号整数>
<等号>→==|=
<叹号>→!=|!
<大于号>→>>|>=|>
<小于号>→<<|<=|<
<并>→&&|&
<或>→|| | |

与其他规则不同的是，需要对不符合上述规则的进行错误指出，因为仅有上述字符在进行组合是会出现“组合错误”，比如“&|”，再比如“><”等。

代码分析

代码中有几个重要的部分：文件读取后的过滤函数、判断字符的4个函数和指出错误的函数。

首先是过滤函数。在预处理阶段要进行源程序字符串的无用字符过滤，这里的无用字符指的是：各种各样的格式字符（\n，\t等）以及注释。对于格式字符，设置条件判断语句，遇到后直接跳过录入即可。这里需要注意的是，空格不可去除，因为有部分空格是作为词法的分割而不是格式的部分，去除会导致词法错误；对于注释而言，c语言的词法中有两种注释：//……和/*……*/，针对第一种，只要遇到，就跳过从注释符到下一个最近的换行符之间的所有内容；对于第二种，遇到/*后，就跳过从该符号到下一个最近的*/之间的所有内容。具体及注释内容如下：

//过滤内容中的注释和无用内容
void filterResource(char formerAllCode[], int pAllCode){
    char tempALlCode[100000];
    int count = 0;
    for (int i = 0; i <= pAllCode; i++){
        //去除单行注释 //......
        if (formerAllCode[i]=='/'&&formerAllCode[i+1]=='/'){
            while (formerAllCode[i] != '\n'){
                i++;
            }
        }
        //去除多行注释 /*......*/
        if (formerAllCode[i] == '/'&&formerAllCode[i + 1] == '*'){
            i+=2;
            while (formerAllCode[i] != '*' || formerAllCode[i + 1] != '/'){
                i++;
                if (formerAllCode[i] == '$'){
                    //如果在文件结束的时候都没有匹配到*/，说明注释符号有误
                    //程序直接结束，提示用户检查文件内容
                    cout<<"FUNC ERROR(filterResource)"<<endl;
                    exit(0);
                }
            }
            i+=2;
        }
        //去除无用格式字符
        //空格不可去除，有部分空格是作为词法的分割而不是格式的部分，去除会导致词法错误
        if (formerAllCode[i] != '\n'&&formerAllCode[i] != '\t'&&formerAllCode[i] != '\v'&&formerAllCode[i] != '\r'){
            //至此，剩下的内容为合法内容
            tempALlCode[count++] = formerAllCode[i];
        }
    }
    tempALlCode[count] = '\0';
    strcpy(formerAllCode, tempALlCode);
    LoadAfterFilterInfo();
}

接下来是判断字符是否正确的4个扫描函数。其中Sacnner函数按顺序调用其他的三个函数，判断顺序依次是：是否是标识符（保留字）和常数、是否是单字符、是否是双字符。

对于标识符（保留字）和常数的判断，需要注意的问题是如果一个字串被识别为标识符，它的第一位就不可以是数字，这种情况就是错误的：char a[123a456]。此处需要对这样的情况加以区分，因为如果不加以区分的话会有两种结果：一是将123a456看作一个标识符，另一是将123和456看作两个常数，a看作一个标识符。而对于我们来说，这两种看法在实际的c语言编程中都是错误的。

//标识符（保留字）和常数判断
void scanner_CharOrDigt(int &count){
    if (IsChar(SourceProgram[pAllCode])){
        //首字符为字母
        symbols[count++] = SourceProgram[pAllCode];
        pAllCode+=1;
        while (IsChar(SourceProgram[pAllCode]) || IsDigit(SourceProgram[pAllCode])){
            //后跟字母或数字
            symbols[count++] = SourceProgram[pAllCode];
            pAllCode+=1;
        }
        symbols[count] = '\0';
        //判断是否是保留字
        if ((symbolsNumber=getSymbolNumber(typeTable, symbols)) == -1){
            symbolsNumber = 100;
            ifSuccess=true;
        }
        return;
    }
    else if (IsDigit(SourceProgram[pAllCode])){
        //首字符为数字
        while (IsDigit(SourceProgram[pAllCode])){
            //后跟数字
            symbols[count++] = SourceProgram[pAllCode];
            pAllCode+=1;
        }
        symbols[count] = '\0';
        if(!IsChar(SourceProgram[pAllCode])){
            symbolsNumber = 99;
            ifSuccess=true;
        }
        else{
            //如果在首字符为数字的情况下发现后有字母，整个标识符都会被判断是错误的
            //组合错误
            combinationError(symbols);
            //跳过该行
            JumpErrorLine();
        }
        return;
    }
}

对于单字符的判断很简单，仅需要一个条件语句即可。

对于双字符的判断要运用到超前分析，如果不是双字符但符合单字符的情况，就要将数组指针前移。

本程序将词法的错误分为两类：一是未知字符错误：出现了系统中没有定义的字符，最简单的例子就是在代码中输出提示信息含有中文字符，因为所有的中文字符是没有在上面的字符集里的，所以会报此错误；另一是组合错误，即字符之间的组合出现错误，上面的123a456就是一种组合错误，常见的组合错误还有&|等。需要注意的是，并不是所有的字符组合都是有错误的，比如+-和-+，它们在判断的时候应该属于两个单字符，但是+和-都可以作为双字符的第一个字符。对于大多数的这种情况来说，应该是语法分析需要完成的内容，在本程序里，之需要对这种情况做单字符判断即可。

//输出未定义字符错误信息
void undefinedError(char ch){
    cout<<"----------------"<<endl;
    cout<<"["<<ErrorCounter<<"]"<<endl;
    ErrorCounter+=1;
    cout<<"错误种类:未定义字符错误"<<endl;
    cout<<"错误语句->  "<<CodeOfEveryLine[pLineCounter]<<endl<<"错误位置->  "<<ch<<endl;
    cout<<"----------------"<<endl;
}

//输出组合错误信息
void combinationError(char *symbols){
    symbols[1]=SourceProgram[pAllCode];
    symbols[2]='\0';
    ifErrorLine=true;
    cout<<"----------------"<<endl;
    cout<<"["<<ErrorCounter<<"]"<<endl;
    ErrorCounter+=1;
    cout<<"错误种类:组合错误"<<endl;
    cout<<"错误语句->  "<<CodeOfEveryLine[pLineCounter]<<endl<<"错误位置->  "<<symbols<<endl;
    cout<<"----------------"<<endl;
}

结果测试

以两个错误信息输出函数为测试代码，将代码放入SourceProgram.txt中：

运行程序，发现该代码段无错误：

查看ResultofLexicalAnalysis.txt文件（二元组）：

修改代码，人为的添加几处错误：

代码运行结果如下：

上述测试证明了该程序可按设计本意顺利完成各项功能：对于添加的三处错误，第一处是组合错误，后两处是未定义字符错误（/346是UTF-8字符集，用三个字节表示一个汉字）。

原例题

题目

某操作系统下合法的文件名规则为:device:name.extention,其中第一部分(device:)和第三部分(.extention)可缺省，若 device、name 和 extention，编程序完成文件名的识别。
编写程序完成以下“无符号数”的识别和计算：G[<无符号数>]: 右线性正则文法

<无符号数> → d <余留无符号数> ∣. <小数部分> ∣d

<余留无符号数> → d <余留无符号数> ∣. <十进小数> ∣ E <指数部分> ∣ . ∣ d

<十进小数> → E<指数部分> ∣d <十进小数> ∣ d

<小数部分> → d <十进小数> ∣ d

<指数部分> → d <余留指数部分> ∣+ <整指数> ∣ - <整指数> ∣ d

<整指数> → d <余留整指数> ∣ d

<余留整指数> → d <余留整指数> ∣ d 其中 d:代表数字 0-9

解题思路

词法分析是编译程序进行编译时第一个要进行的任务，主要是对源程序进行编译预处理（去除注释、无用的回车换行找到包含的文件等）之后，对整个源程序进行分解，分解成一个个单词，这些单词有且只有五类，分别是标识符、保留字、常数、运算符、界符。以便为下面的语法分析和语义分析做准备。可以说词法分析面向的对象是单个的字符，目的是把它们组成有效的单词（字符串）；而语法的分析则是利用词法分析的结果作为输入来分析是否符合语法规则并且进行语法制导下的语义分析，最后产生四元组(中间代码)，进行优化（可有可无）之后最终生成目标代码。

对于我们来说，词法分析程序的逻辑是十分简单的：通过循环的方式按顺序逐个识别输入的字符，如果某一个字符没有错误，那就进入下一个字符的识别，一旦发现有错就直接跳出，报错即可。

在此思想下，我们需要考虑的问题是：我们怎么“识别”当前字符到底是对的还是错的？

在学习过编译原理的文法之后，我们都知道，只有满足文法规则的终结字符才可以被识别（右线性正则文法）。那么我们又怎么把抽象的文法规则具像化到代码中去？

状态转换图可以帮我们解决这个问题。我们都知道，状态转换图可以更加高效的表示文法。文法或许不好用计算机代码直接解释，但是自动机所化成的状态转换图就可以利用我们在数据结构中所学习的图论的知识来转化，仅需要很简单的结构体就可以完成：

//存储状态转换图中点->边->点的结构
struct Edge{
    int from, to, next;
    char value;
}edge[100];

有了存储结构之后，我们就要使用循环的方式对输入进来的字符串进行检查。从入口状态开始检查第一个终结字符，直到检查完成即可。每往下进行一个字符，对应着状态转换图中状态的转换；每个字符的转换都必须符合提前设置好的状态转换图。如果从当前字符无法转换到下一个字符且当前字符不是最后一个字符或者检查完成的最后一个状态不是终结状态，就判定整个字符串匹配失败。

void judge(){
    cout<<"请键入字符串("<<end_sentence<<"退出):\n";
    for(;;){
        cout<<"\n["<<round++<<"]: ";
        cin >> print_sentence;
        if(print_sentence == end_sentence){
            cout<<"退出"<<endl;
            break;
        }
        //当前状态标号
        int now=0; 
        //标记是否是合法的串
        bool flag=true; 
        for(int i = 0; i < print_sentence.length() && flag; i++){
            char value = print_sentence[i];
            if (judge_VT(value))
                value = vt_represent;
            flag = false;
            for(int j = node[now]; j != -1; j = edge[j].next)
                if (edge[j].value == value){
                    flag = true;
                    now = edge[j].to;
                    break;
                }
        }
        if(!isFinal[now]){
            flag = false;
        }
        if(flag){
            cout<<"正确"<<endl;
        }
        else{
            cout<<"错误"<<endl;
        }
    }
}

上述过程中，我们需要函数来帮我们识别除了特殊符号外的终结符。识别过后的终结符直接更换为更一般的符号代替，简化代码流程：

//识别0-9
bool judge_VT(char x){
    return (x >= '0' && x <= '9');
}
//识别所有字母
bool judge_VT(char x){
    return ((x >= 'A' && x <= 'Z') || (x >= 'a' && x <= 'z'));
}

状态转换图

此思想下所需要的状态转换图没有必要是最简化的，由于输入的长度一定是有限的，转换图中拥有回路亦可得出答案。

例题1的状态转换图如下所示：

例题1的状态转换图

转换为代码中的变量如下：

int node[6];//状态节点，0~5
int cnt;
bool isFinal[6]; //判断一个状态是不是终态
int counter=9;
int vn_left[]={0,1,1,1,2,3,4,4,5};
char vt[]={vt_represent,vt_represent,':','.',vt_represent,vt_represent,'.',vt_represent,vt_represent,};
int vn_right[]={1,1,2,3,4,5,3,4,5};
void setFinal(){
    isFinal[1] = isFinal[4] = isFinal[5] = true;
}

例题2的状态转换图如下所示：

例题2的状态转换图

转换为代码中的变量如下：

int node[8];//状态节点，0~5
int cnt;
bool isFinal[8]; //判断一个状态是不是终态
int counter=17;
int vn_left[]={0,0,0,1,1,1,1,2,3,3,3,4,4,4,5,6,6};
char vt[]={vt_represent,'.','e', vt_represent,'.','e',vt_represent,vt_represent,vt_represent,'e',vt_represent,'+','-',vt_represent,vt_represent,vt_represent,vt_represent};
int vn_right[]={1,2,4,1,2,4,7,3,3,4,7,5,5,6,6,6,7};
void setFinal(){
    isFinal[1] = isFinal[3] = isFinal[6] = isFinal[7] = true;//标记终态
}

完整代码

除了上述的部分代码不一样外，这两道例题的思想是一样的，它们公用下面的程序。执行不同的程序就将另外一个程序的变量注释（注释中以标出），直接编译运行即可。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

//公共变量,用作提示信息和输入等
int round;
string print_sentence;
string end_sentence;
char vt_represent='d';

struct Edge{
    int from, to, next;
    char value;
}edge[100];

//////////////////////////第九题的变量及函数
//int node[6];//状态节点，0~5
//int cnt;
//bool isFinal[6]; //判断一个状态是不是终态
//int counter=9;
//int vn_left[]={0,1,1,1,2,3,4,4,5};
//char vt[]={vt_represent,vt_represent,':','.',vt_represent,vt_represent,'.',vt_represent,vt_represent,};
//int vn_right[]={1,1,2,3,4,5,3,4,5};
//bool judge_VT(char x){
//    return ((x >= 'A' && x <= 'Z') || (x >= 'a' && x <= 'z'));
//}
//void setFinal(){
//    isFinal[1] = isFinal[4] = isFinal[5] = true;
//}

//////////////////////////第十题的变量及函数
int node[8];//状态节点，0~5
int cnt;
bool isFinal[8]; //判断一个状态是不是终态
int counter=17;
int vn_left[]={0,0,0,1,1,1,1,2,3,3,3,4,4,4,5,6,6};
char vt[]={vt_represent,'.','e', vt_represent,'.','e',vt_represent,vt_represent,vt_represent,'e',vt_represent,'+','-',vt_represent,vt_represent,vt_represent,vt_represent};
int vn_right[]={1,2,4,1,2,4,7,3,3,4,7,5,5,6,6,6,7};
bool judge_VT(char x){
    return (x >= '0' && x <= '9');
}
void setFinal(){
    isFinal[1] = isFinal[3] = isFinal[6] = isFinal[7] = true;//标记终态
}

//////////////////////////公共函数

//插入边的函数
void insert(int from, int to, char value){
    edge[cnt].from = from;
    edge[cnt].to = to;
    edge[cnt].value = value;
    edge[cnt].next = node[from];
    node[from] = cnt++;
}

//初始化函数，用来构造自动机的状态转换
void init(){
    end_sentence="end";
    round=1;
    memset(node, -1, sizeof(node));
    memset(isFinal, false, sizeof(isFinal));
    setFinal();
    for(int i=0;i<counter;i++){
        insert(vn_left[i], vn_right[i], vt[i]);
    }
}

void judge(){
    cout<<"请键入字符串("<<end_sentence<<"退出):\n";
    for(;;){
        cout<<"\n["<<round++<<"]: ";
        cin >> print_sentence;
        if(print_sentence == end_sentence){
            cout<<"退出"<<endl;
            break;
        }
        int now=0; //now 当前状态
        bool flag=true; //标记是否是合法的串
        for(int i = 0; i < print_sentence.length() && flag; i++){
            char value = print_sentence[i];
            if (judge_VT(value))
                value = vt_represent;
            flag = false;
            for(int j = node[now]; j != -1; j = edge[j].next)
                if (edge[j].value == value){
                    flag = true;
                    now = edge[j].to;
                    break;
                }
        }
        if(!isFinal[now]){
            flag = false;
        }
        if(flag){
            cout<<"正确"<<endl;
        }
        else{
            cout<<"错误"<<endl;
        }
    }
}

int main(){
    init();
    judge();
    return 0;
}

运行结果

例题1的运行结果：

例题1的运行结果

例题2的运行结果：

例题2的运行结果