---

C语言
实验环境：Visual Studio 2019
author：zoxiii

---

1、实验内容

  写出完整词法分析器程序，并用一段程序语句进行调试、运行。

2、前期准备

2.1 待分析的C语言子集的词法

单词大概可分为的5类：标识符、保留字、常数、运算符、界符。

1. 标识符：以字母开头的包含字母和数字的符号
2. 保留字：while、if、else、switch、case
3. 常数：数字0~9
4. 运算符：+、-、*、<、<=、==、=
5. 界符：;
6. 需略除的：空格、制表符、换行符

2.2 C语言子集的单词符号表示表

  首先根据我们要构造的C语言子集的简单词法分析器，列出所要实现的单词符号以及它们的种别编码和内码值。
  为了方便记忆，还添加了助记符来表示单词符号。具体如下表：

单词符号	种别编码	助记符	内码值
while	1	while	–
if	2	if	–
else	3	else	–
switch	4	switch	–
case	5	case	–
标识符	6	id	id在符号表中的位置
常数	7	num	num在常数表中的位置
+	8	+	–
-	9	-	–
*	10	*	–
<=	11	relop	LE
<	11	relop	LT
==	11	relop	EQ
=	12	=	–
;	13	;	–

2.3 C语言子集对应的状态转换图

  根据需要构造的词法分析器的单词符号，设计了对应的状态转换图。其中，首先对输入串预处理，去除空格、制表符等，再根据单子符号表得到状态转换图，并分析每种状态应输出的单词二元组信息。

图1-C语言子集对应的状态转换图

3、分析过程

3.1 词法分析子程序

  对于前期分析要实现的词法分析器需引入相应的变量和函数：
  变量如下：
（1） token：用来存放构成单词符号的字符串；
（2） ch：用来存放每一次词法分析获取的字符；
（3） ptr_token：单词缓冲区指针；
  函数如下：
（1） void Getchar()：将下一输入字符读到ch中，扫描指针前移一字符位置；
（2） void getbe()：检查ch中的字符是否为空白。若是，则调用Getchar直至ch中为非空字符为止 ；
（3） void concatenation()：将ch中的字符连接到token之后作为新的字符串；
（4） bool letter()：判断ch中的字符是否为字母,是则返回true(1),不是则返回false(0)；
（5） bool digit()：判断ch中的字符是否为数字,是则返回true(1),不是则返回false(0)；
（6） int reserve()：按token中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返回0值（假定0不是保留字的编码）；
（7） void retract()：将扫描指针回退一个字符位置，将ch置为空白字符；
（8） void buildlist()：将标识符登录到符号表中或将常数登录到常数表中；
（9） void error()：出现非法字符，词法分析出错，显示出错的字符；
（10） void LexicalAnalysis()：词法分析过程函数；
  扫描子程序的主要流程图如下图2所示：

图2-词法分析子程序流程图

3.2 主程序

  主程序流程较为简单，如下图图3所示。但在之前需要在程序开始时定义一些全局变量，如关键字数组、需分析的语句数组、空的标识符表数组、常数表数组等以及相应的数组指针，便于后面的词法分析。

图3-主程序流程图

3.3 源代码

#include<iostream>
#include<string.h>
using namespace std;
//声明数组变量+指针
char input[] = "Hello World;I am XXX;x=5;y=9;if x<y	x=y;else   x=x; case 7  x>7;";  //需要分析的词句
const char *keyword[] = {"while","if","else","switch","case"};//关键字
int keyword_length=sizeof(keyword)/sizeof(char*);
int ptr_input = 0; //测试程序数组指针
int ptr_token;     //读取到的字符数组指针
char ch;         //字符变量，存放最新读入的源程序字符
char token[255] = "";  //字符数组，存放构成单词符号的字符串
//声明buildlist的相关变量+指针
int num_table[50] = { 0 }; //常数表，存放构成的常数
int ptr_num=0;              //常数表指针
char id_table[255][255] = {0};//标识符表，存放构成的标识符
int ptr_id=0;                           //标识符表指针
int ptr_present;                        //当前指针
//声明函数定义 
void Getchar();//将下一输入字符读到ch中，扫描指针前移一字符位置
void getbe();//检查ch中的字符是否为空白。若是，则调用Getchar直至ch中为非空字符为止 
void concatenation();//将ch中的字符连接到token之后作为新的字符串
bool letter();//判断ch中的字符是否为字母,是则返回true(1),不是则返回false(0)
bool digit();//判断ch中的字符是否为数字,是则返回true(1),不是则返回false(0)
int reserve();//按token中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返回0值（假定0不是保留字的编码）
void retract();//将扫描指针回退一个字符位置，将ch置为空白字符
void buildlist();//将标识符登录到符号表中或将常数登录到常数表中
void error();//出现非法字符，词法分析出错，显示错误信息
void LexicalAnalysis();//词法分析过程函数
/**
 * 函数功能：从输入缓冲区下一输入字符读到ch中，并将扫描指针前移一字符位置。
 */
void Getchar()
{
	ch = input[ptr_input];
	ptr_input++;
} 
/**
 * 函数功能：检查ch中的字符是否为空白；若是，则调用Getchar直至ch中为非空字符为止。
 */
void getbe()
{
	while (ch == ' '||ch == '\t')
	        Getchar();
} 
/**
 * 函数功能：将ch中的字符连接到token之后作为新的字符串
 */
void concatenation()
{
	token[ptr_token] = ch;
	ptr_token++;
	token[ptr_token] = '\0';
} 
/**
 * 函数功能：判断ch中的字符是否为字母,是则返回true(1),不是则返回false(0)
 */
bool letter()
{
	if (ch >= 'a'&&ch <= 'z' || ch >= 'A'&&ch <= 'Z')
		return 1;
	else
		return 0;
}
/**
 * 函数功能：判断ch中的字符是否为数字,是则返回true(1),不是则返回false(0)
 */
bool digit()
{
	if (ch >= '0'&&ch <= '9')
		return 1;
	else
		return 0;
} 
/**
 * 函数功能：按token中的字符串查找保留字表，若它是一个保留字则返回它的编码，否则返回0值（假定0不是保留字的编码）
 */
int reserve()
{
	int i = 0;
	while(i < keyword_length)
	{
		if (!strcmp(keyword[i], token))
			return i + 1;   //如果相等，则返回该关键字的种别编码
		i++;
	}
	return 0;       //如果不是关键字，则返回0
} 
/**
 * 函数功能：将扫描指针回退一个字符位置，将ch置为空白字符
 */
void retract()
{
	ptr_input--;
}
/**
 * 函数功能：出现非法字符，词法分析出错，显示错误信息
 */
void error()
{
        cout<<"Illegal character:"<<ch<<endl;
}
/**
 * 函数功能：将标识符登录到符号表中或将常数登录到常数表中
 */    
void buildlist()
{ 
        char ch_head=token[0]-'0';
        if(ch_head >= 0 && ch_head <= 9)
        {
                int j=0;
                while(j < ptr_num)
                {
                        if(atoi(token)==num_table[j])
                        {
                                ptr_present=j;
                                break;
                        }
                        j++;
                }
                if(j==ptr_num)
                {
                        num_table[ptr_num]=atoi(token);
                        ptr_present=ptr_num;
                        ptr_num++;
                }
        }
        else
        {
                int i = 0;
	        while(i < ptr_id)
	        {
		        if (!strcmp(id_table[i], token))
                        {
                                ptr_present = i;
			        break;
                        }
		        i++;
	        }
                if(i==ptr_id)
                {
                        strcpy(id_table[ptr_id],token);
                        ptr_present=ptr_id;
                        ptr_id++;       
                }
        }
}
/**
 * 函数功能：词法分析过程函数
 */
void LexicalAnalysis()                  
{         
        ptr_token = 0;   //单词缓冲区指针
        Getchar();       //获取当前字符到ch中
        getbe();         //滤除空格
        if(letter())            //首字符为字母
        {
                while (letter() || digit ())
                {
                        concatenation();        //将当前读入的字符送入token数组
                        Getchar();              //获取下个字符
                }
                retract();    //扫描指针回退一个字符
                int index = reserve();//查询是否为关键字
                if (index==0)                   
                {

                        buildlist();//将标识符登录到符号表中
                        cout<<"(\t"<<"id"<<"\t,\t"<<ptr_present<<"\t)\tid_table["<<ptr_present<<"]="<<token<<"\n";//是标识符
                        //return (id,指向id的符号表入口指针);
                }
                else
                cout<<"(\t"<<keyword[index-1]<<"\t,\t"<<" "<<"\t)\n";//是关键字
                //return (关键字码, null);
        }
	else if (digit())  //首字符是数字
	{
                while (digit())
                {
                concatenation();
                Getchar();
                }
                retract();
                buildlist(); /*将常数登录到常数表中*/
                cout<<"(\t"<<"num"<<"\t,\t"<<ptr_present<<"\t)\tnum_table["<<ptr_present<<"]="<<token<<"\n";//是常数
                //return (num， num的常数表入口指针);
        }
        else switch (ch)
        {
                case '+':
                        cout<<"(\t"<<"'+'"<<"\t,\t"<<" "<<"\t)\n";//是"+"
                        //return ('+', null);
                        break;
                case '?':
                        cout<<"(\t  "<<"'-'"<<"\t,\t"<<" "<<"\t)\n";//是"-"
                        //return ('?', null);
                        break;
                case '*':
                        cout<<"(\t"<<"'*'"<<"\t,\t"<<" "<<"\t)\n";//是"*"
                        //return ('*', null);
                        break;
                case '<':
                        Getchar();
                        if (ch == '=')
                                cout<<"(\t"<<"relop"<<"\t,\t"<<"LE"<<"\t)\n";//是"<="
                                //return (relop,LE);
                        else
                        {
                                retract();
                                cout<<"(\t"<<"relop"<<"\t,\t"<<"LT"<<"\t)\n";//是"<"
                                //return (relop,LT);
                        }
                        break;
                case '=':
                        Getchar();
                        if (ch == '=')
                                cout<<"(\t"<<"relop"<<"\t,\t"<<"EQ"<<"\t)\n";//是"=="
                                //return (relop, EQ);
                        else
                        {
                                retract();
                                cout<<"(\t"<<"="<<"\t,\t"<<" "<<"\t)\n";//是"="
                                //return ('=', null);
                        }
                        break;
                case ';':
                        cout<<"(\t"<<";"<<"\t,\t"<<" "<<"\t)\n";//是";"
                        //return (';', null);
                        break;
                default:error();
        }
}
/**
 * 主函数
 */
int main()
{
        while(ptr_input<strlen(input))
                LexicalAnalysis();//进行词法分析
        return 0;
}

4、测试

  如下图图4所示为对程序语句

Hello World;
I am XXX;
x=5;y=9;
if x<y
	x=y;
else
   x=x;
 case 7
  x>7;

  进行词法分析得到的单词二元组。为便于观察，还将单词及其标识符表或常数表中的位置在二元组之后输出，便于观察结果是否正确。

图4-词法分析得到的单词二元组

5、遇到的问题

（1） 在建立标识符表和常数表时，一开始通过链表的方法来建立，如下建立了对应的标识符表和常数表：

struct NodeId
{
        int index_id;
	char node_id[255];
        NodeId *next;
};
struct NodeNum
{
	int index_num;
	char node_num[255];
        NodeNum *next;
};

但在运行过程中，由于链表是动态分配地址的，所以地址的变化导致每次往表中插入新的字符时都会改变地址，无法得到有效的表。
因此最终选择了使用初始化数组作为标识符和常数存储的位置则解决掉了这个问题。
（2） 再将标识符或常数登记到对应的表中时，忽略了token是有结束符号的，在匹配时一直没有成功。所以在每次匹配时都对得到的单词token处理，去掉结尾的结束符“0”，然后再进行匹配就可以了。

参考文献：《编译原理教程 (第4版)》 胡元义 2016