Nikedown's Blog

词法分析器

词法分析
字数统计: 3k阅读时长: 13 min
2019/03/31 Share

什么是词法分析：

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

定义词法分析的标识符、保留字和符号等等

  • 第一类：标识符 letter(letter | digit)* 无穷集
  • 第二类：常数 (digit)+ 无穷集
  • 第三类：保留字(32)
    “include”, “break”, “case”, “char”, “const”, “continue”,
    “default”, “do”, “double”, “else”, “stdio”, “extern”,
    “float”, “for”, “goto”, “if”, “int”, “long”, “static”,
    “register”, “return”, “short”, “signed”, “sizeof”, “void”,
    “struct”, “switch”, “typedef”, “union”, “unsigned”,
    “volatile”, “while”
  • 第四类：界符 ‘/*’、‘//’、 () { } [ ] “ “ ‘ 等
  • 第五类：运算符 <、<=、>、>=、=、+、-、*、/、^、等

程序的流程

  • 词法分析程序打开源文件，读取文件内容，直至遇上’\0’文件结束符，然后读取结束。
  • 对读取的文件进行预处理，从头到尾进行扫描，去除//和/ /的内容，以及一些无用的、影响程序执行的符号如换行符、回车符、制表符等。但是千万注意不要在这个时候去除空格，因为空格在词法分析中有用，比如说int i=3;这个语句，如果去除空格就变成了“inti=3”,这样就失去了程序的本意，因此不能在这个时候去除空格。
  • 选下面就要对源文件从头到尾进行扫描了，从头开始扫描，这个时候扫描程序首先要询问当前的字符是不是空格，若是空格，则继续扫描下一个字符，直至不是空格，然后询问这个字符是不是字母，若是则进行标识符和保留字的识别；若这个字符为数字，则进行数字的判断。否则，依次对这个字符可能的情况进行判断，若是将所有可能都走了一遍还是没有知道它是谁，则认定为错误符号，输出该错误符号，然后结束。每次成功识别了一个单词后，单词都会存在token[ ]中。然后确定这个单词的种别码，最后进行下一个单词的识别。这就是扫描程序进行的工作，可以说这个程序彻底实现了确定有限自动机的某些功能，比如说识别标识符，识别数字等。为了简单起见，这里的数字只是整数。
  • 主控程序主要负责对每次识别的种别码syn进行判断，对于不同的单词种别做出不同的反应，如对于标识符则将其插入标识符表中。对于保留字则输出该保留字的种别码和助记符，等等吧。直至遇到syn=0;程序结束。

流程图

程序代码

先建立编码表，保留字表，符号表和标识符表

  • 编码表：
    <\0,0>
    1~32:include ~ while
    33~74：+ ~ !
    90：常数
    100：标识符
    （注意：编码表为自己所定义的，是对应每一个可识别字符，一旦定义就不要轻易改动，因为这会影响到之后的程序，一旦改动，之后的程序也要改动相应的代码，以符合新的编码表）

  • 保留字表：

    1
    2
    3
    4
    5
    6
    7
    8
      static char Reservedword[32][20] = {
    	 "include", "break", "case", "char", "const", "continue",
    	  "default", "do", "double", "else", "stdio", "extern",
    	  "float", "for", "goto", "if", "int", "long",
    	  "register", "return", "short", "signed", "sizeof", "static",
    	  "struct", "switch", "typedef", "union", "unsigned", "void",
    	  "volatile", "while"
    };

  • 符号表

    1
    2
    3
    4
    5
    6
    7
    static char Operator[42][10] = {
    	  ";", "(", ")", "^", ",", "\"", "\'", "#",
    	  "%", "~",  "[", "]", "{", "}", ".", "\?", 
    	  ":","\\","+","+=","++", "-","-=","--", "*",
    	  "*=", "/","/=", "<", "<=", ">", ">=", "=",
    	  "==","!=", "&","&&", "|", "||", "<<", ">>",  "!"
    };

  • 标识符表

    1
    static char Identifier[100][20] = { "" };

判断函数

  • 查找保留字
    1
    2
    3
    4
    5
    6
    7
    8
    9
    int SearchReservedword(char Reservedword[][20], char s[])
    {
    	for (int i = 0; i < 32; i++)
    	{
    		if (strcmp(Reservedword[i], s) == 0)
    			return i + 1;
    	}
    	return -1;
    }

遍历Reservedword数组查找保留字是否在数组中，返回保留字在数组中的位置（主意：返回时i的值要加1，对应编码表的编码）

  • 判断是否为字母
    1
    2
    3
    4
    5
    6
    7
    bool IsLetter(char s)
    {
    	if (s >= 'a'&&s <= 'z' || s >= 'A'&&s <= 'Z' || s == '_')
    		return true;
    	else
    		return false;
    }

（加入对符号的判断，因为标识符可以以大小写字母和开头）

  • 判断是否为数字
    1
    2
    3
    4
    5
    6
    7
    bool IsNum(char s)
    {
    	if (s >= '0'&&s <= '9')
    		return true;
    	else
    		return false;
    }

程序关键函数

  • 预处理函数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    void Clearnotes(char resourse[], int item)
    {
    	char newsourse[10000] = { "" };//存放消除注释后的字符串
    	int flag = 0;//新数组下标
    	for (int i = 0; i < item; i++)
    	{
    		if (resourse[i] == '/'&&resourse[i + 1] == '/')
    		{
    			while (resourse[i] != '\n')
    				i++;
    		}
    		if (resourse[i] == '/'&&resourse[i + 1] == '*')
    		{
    			i += 2;//跳过/*符号
    			while (resourse[i] != '*'&&resourse[i + 1] != '/')
    			{
    				i++;
    				if (resourse[i] == '\0')//未找到注释结束符，说明代码出错
    				{
    					printf("代码出错\n");
    					exit(0);
    				}
    			}
    		}
                  if(resourse[i]!='\n'&&resourse[i]!='\t'&&resourse[i]!='\v'&&resourse[i]!='\r')//过滤掉水平制表符，回车，回车换行符，垂直指标符
    		{
    			newsourse[flag++] = resourse[i];
    		}
    	}
    	strcpy(resourse, newsourse);
    }

函数的作用是过滤掉无用字符，像一些对程序代码本身没有用的注释和符号，便于下一步对程序中单词的识别，需要注意的是c语言中的注释有单行注释和多行注释，单行注释只需要识别最后的换行符就行了，而多行注释则要识别注释结束符，并且要判断是否存在注释结束符，判断的方式也很简单，只需要判断在找到结束符前是否遇到’\0’就行了。

  • 单词识别函数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    void LexicalAnalysis(char resourse[], int &flag,char target[], int &item)
    {
    	char x;
    	int count = 0;
    	for (int i = 0; i < 20; i++)//每次清空target数组
    		target[i] = '\0';
    	while (resourse[item] == ' ')//跳过空格
    	{
    		item++;
    		x = resourse[item];
    	}
    	if (resourse[item] == '\0')
    	{
    		flag = 0;
    		return;
    	}		
    	else if(resourse[item] == ';' || resourse[item] == '(' || resourse[item] == ')' || resourse[item] == '^' || resourse[item] == ',' || resourse[item] == '\"' || resourse[item] == '\'' || resourse[item] == '~' || resourse[item] == '#' || resourse[item] == '%' || resourse[item] == '['|| resourse[item] == ']' || resourse[item] == '{' || resourse[item] == '}' || resourse[item] == '\\' || resourse[item] == '.' || resourse[item] == '\?' || resourse[item] == ':')
    	{
    		target[0] = resourse[item];
    		for (int i = 0; i < 42; i++)
    		{
    			if (strcmp(target, Operator[i])==0)
    			{
    				flag = 33 + i;
    				break;
    			}
    		}
    		item++;
    		return;
    	}
    	else if (resourse[item] == '+')
    	{//+,++,+=
    		item++;
    		if (resourse[item] == '+')
    			flag = 53;
    		else if (resourse[item] == '=')
    			flag = 52;
    		else
    		{
    			flag = 51;
    			item--;
    		}		
    		item++;
    		return;
    	}
    	else if (resourse[item] == '-')
    	{
    		item++;
    		if (resourse[item] == '-')
    			flag = 56;
    		else if (resourse[item] == '=')
    			flag = 55;
    		else
    		{
    			flag = 54;
    			item--;
    		}			
    		item++;
    		return;
    	}
    	else if (resourse[item] == '*')
    	{
    		item++;
    		if (resourse[item] == '=')
    			flag = 58;
    		else
    		{
    			flag = 57;
    			item--;
    		}			
    		item++;
    		return;
    	}
    	else if (resourse[item] == '/')
    	{
    		item++;
    		if (resourse[item] == '=')
    			flag = 60;
    		else
    		{
    			flag = 59;
    			item--;
    		}
    		item++;
    		return;
    	}
    	else if (resourse[item] == '<')
    	{
    		item++;
    		if (resourse[item] == '=')
    			flag = 62;
    		else if (resourse[item] == '<')
    			flag = 72;
    		else
    		{
    			flag = 61;
    			item--;
    		}
    		item++;
    		return;
    	}
    	else if (resourse[item] == '>')
    	{
    		item++;
    		if (resourse[item] == '=')
    			flag = 64;
    		else if (resourse[item] == '>')
    			flag = 73;
    		else
    		{
    			flag = 63;
    			item--;
    		}
    		item++;
    		return;
    	}
    	else if (resourse[item] == '=')
    	{
    		item++;
    		if (resourse[item] == '=')
    			flag = 66;
    		else
    		{
    			flag = 65;
    			item--;
    		}
    		item++;
    		return;
    	}
    	else if (resourse[item] == '!')
    	{
    		item++;
    		if (resourse[item] == '=')
    			flag = 67;
    		else
    		{
    			flag = 74;
    			item--;
    		}
    		item++;
    		return;
    	}
    	else if (resourse[item] == '&')
    	{
    		item++;
    		if (resourse[item] == '&')
    			flag = 69;
    		else
    		{
    			flag = 68;
    			item--;
    		}
    		item++;
    		return;
    	}
    	else if (resourse[item] == '|')
    	{
    		item++;
    		if (resourse[item] == '|')
    			flag = 71;
    		else
    		{
    			flag = 70;
    			item--;
    		}
    		item++;
    		return;
    	}
    	else if (IsLetter(resourse[item]))
    	{
    		target[count] = resourse[item];
    		count++;
    		item++;
    	while (IsLetter(resourse[item]) || IsNum(resourse[item]))
    	{
    		target[count] = resourse[item];
    		count++;
    		item++;
    	}
    		flag = SearchReservedword(Reservedword, target);
    		if (flag == -1)
    			flag = 100;
    		return;
    	}
    	else if (IsNum(resourse[item]))
    	{
    		while (IsNum(resourse[item]))
    		{
    			target[count] = resourse[item];
    			count++;
    			item++;
    		}
    		flag = 90;
    		return;
    	}
    	else
    	{
    		printf("无法识别\n");
    		exit(0);
    	}
    }

该函数是整个程序的核心，对代码进行识别，通过改变flag的值来对单词进行分类，具体的分类是对应自己定义的编码表，因为程序中会存在双字符符号，例如+,++,+=之类的符号，所以要对+号的下一位进行判断才能确定该符号为什么符号，这样的话在判断后就要直接返回该符号具体的编码，而不是通过查询符号表数组来解决（注意：最后要考虑字符无法识别的情况，像出现标识符以数字开头的情况，这样就违背了标识符的定义，属于无法识别的字符）

  • 主函数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    int main()
    {
    	char resourse[10000] = {""};
    	char target[20] = { "" };
    	int i = 0;//记录数组长度
    	int flag = -1;//0：程序结束符号，1~32：保留字，33~74：符号，90：常数，100：标识符
    	FILE *f1, *f2;
    	if ((f1 = fopen("F:\\test\\test.cpp", "r"))==NULL)
    	{
    		printf("读取文件test失败\n");
    		exit(0);
    	}
    	if ((f2 = fopen("F:\\test\\text2.txt", "w+")) == NULL)
    	{
    		printf("读取文件text2失败\n");
    		exit(0);
    	}
    	while (true)//读取f1中的内容
    	{
    		if (feof(f1))
    			break;
    		resourse[i] = fgetc(f1);
    		i++;
    	}
    	fclose(f1);
    	cout << resourse << endl;
    	resourse[i] = '\0';
    	Clearnotes(resourse, i);
    	i = 0;
    	while (flag != 0)
    	{
    		LexicalAnalysis(resourse, flag, target, i);
    		if (flag == 100)
    		{
    			for (int j = 0; j < 100; j++)
    			{
    				if (strcmp(Identifier[j], target)==0)//标识符已经在表中
    					break;
    				else if (strcmp(Identifier[j], "") == 0)//未写入，将标识符写入表中
    				{
    					strcpy(Identifier[j], target);
    					break;
    				}
    			}
    			fprintf(f2, "（标识符，%s）\n", target);
    		}
    		else if (flag >= 1 && flag <= 32)
    		{
    			fprintf(f2, "（保留字：%s)\n", Reservedword[flag - 1]);
    		}
    		else if(flag==99)
    			fprintf(f2, "（常数，%s）\n", target);
    		else if (flag >= 33 && flag <= 74)
    		{
    			fprintf(f2, "（符号，%s）\n", Operator[flag - 33]);
    		}
    	}
    	fclose(f2);
    	return 0;
    }

主函数的主要作用是接收识别函数的返回值，并将其二元组形式输入到指定文件中。

注意事项

  • 编码表为自己所定义，本程序的编码表不够完全，可根据需要自行添加，但要一一对应，并且最好是不要轻易更改。
  • 对于每一个函数最好是有相应的测试代码进行测试，这样会大大减小代码出错的可能性和减轻最后代码错误查找的工作量。
  • 由于代码很长，很容易出现一些代码编写的错误，例如某一个’==’写成’=’号之类的，并且程序中存在很多变量，要非常注意这些变量的改变是否符合逻辑。

[参考博客：]
[1]:https://www.cnblogs.com/zyrblog/p/6885922.html

[GitHub仓库链接：]
[1]:https://github.com/nikedown/Lexical-analyzer

原文作者：nikedown

发表日期：March 31st 2019, 10:23:44 pm

更新日期：April 18th 2019, 5:34:12 pm

CATALOG
  1. 1. 什么是词法分析：
  2. 2. 定义词法分析的标识符、保留字和符号等等
  3. 3. 程序的流程
  4. 4. 流程图
  5. 5. 程序代码
    1. 5.1. 先建立编码表，保留字表，符号表和标识符表
    2. 5.2. 判断函数
    3. 5.3. 程序关键函数
    4. 5.4. 注意事项
Total : 12
2019
Blender学习 茶壶建模 Blender准备工作 渲染参数改进 茶壶渲染 纹理与简单的展UV操作 给茶壶上纹理 搭建git服务器 Nginx安装 阿里云服务器入门 词法分析
Blender 服务器 Nginx 其他