编译原理-词法分析
1. 实验目的
设计、编写并调试一个词法分析程序，加深对词法分析原理的理解
2. 实验要求
2.1 待分析的简单语言的词法
- 关键字：begin，if，then，while，do，end
所有关键字都是小写 - 运算符和界符：:,=,+,-,*,/,<,<=,<>,>,>=,=,;,(,),#
- 其他单词是标识符（id）和整型常数（NUM），通过以下正规式定义：
ID = letter(letter|digit)*
NUM = digit digit* - 空格由空白、制表符和换行符组成。空格一般用来分隔ID、NUM、运算符、界符和关键字，词法分析阶段通常被忽视
2.2 各种单词符号对应的种别码
| 单词符号 | 种别码 | 单词符号 | 种别码 |
|---|---|---|---|
| begin | 1 | : | 17 |
| if | 2 | := | 18 |
| then | 3 | < | 20 |
| while | 4 | <> | 21 |
| do | 5 | <= | 22 |
| end | 6 | > | 23 |
| letter(letter digit)* | 10 | >= | 24 |
| digit digit* | 11 | = | 25 |
| + | 13 | ; | 26 |
| - | 14 | ( | 27 |
| * | 15 | ) | 28 |
| / | 16 | # | 0 |
| [ | 29 | ] | 30 |
| { | 31 | } | 32 |
| , | 33 | != | 40 |
| == | 39 |
2.3 词法分析程序的功能
输入：所给文法的源程序字符串
输出：二元组(syn,token或sum)构成的序列
其中：syn为单词种别码；token为存放的单词自身字符串；sum为整型常数
例如： 对源程序
begin x:=9; if x > 0 then x:=2 * x + 1 / 3; end #
的源文件，经词法分析后输出如下序列：
(1,begin)(10,‘x’)(18,:=)(11,9)(26,😉(2,if)…
3. 词法分析程序的算法思想
算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字种类，拼出相应地单词符号
3.1 主程序示意图
主程序示意图如图所示，其中初值包括如下两个方面
-
关键字表的初值
关键字作为特殊标识符处理，把它们预先安排在一张表各中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符，关键字表为一个字符串数组，描述如下：char* rwtab[] = {“begin”,“if”,“then”,“while”,“do”,“end”,_KEY_WORD_END}; //关键字数组
-
程序中需要用到的主要变量为syn,token和sum
3.2 扫描子程序的算法思想
首先设置3个变量：
- token用来存放构成单词符号的字符串
- sum用来存放整型单词
- syn用来存放单词符号的 种别码
扫描子程序主要部分流程如图：
4. 词法分析程序的C语言程序框架
最终代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// #include <iostream>#define _KEY_WORD_END "waiting for your expanding" // 定义关键字结束标志// 单词二元组的结构
typedef struct
{int typenum;char* word;
}WORD;//函数声明
char m_getch();
void getbc();
void concat();
int letter();
int digit();
int reserve();
void retract();
char *dtb();
WORD *scaner();char input[255]; //输入换缓冲区
char token[255] = ""; //单词缓冲区
int p_input; //输入换缓冲区指针
int p_token; //单词缓冲区指针char ch; //当前读入字符
char* rwtab[] = {"begin","if","then","while","do","end",_KEY_WORD_END}; //关键字数组WORD* scaner(); //词法扫描函数，获得一个单词int main(void)
{// printf("111");int over = 1;WORD* oneword = new WORD; //new为c++中的关键字 在使用new进行内存分配时，需要包含相关类型的头文件。#include <iostream>while (1){printf("Enter Your words(end with #):");scanf("%[^#]s",input); //读入源程序字符串到缓冲区，以#结束，允许多行输入p_input = 0;printf("Your words: \n %s \n",input);while (over < 1000 && over != -1) {oneword = scaner(); //获得新单词 if(oneword -> typenum < 1000){printf("(%d,%s)",oneword -> typenum,oneword -> word); //打印种别码和单词本身的值}over = oneword -> typenum;free(oneword);}over = 1;// printf("\n press # to exit: \n"); //#号退出程序// scanf("%[^#]s",input);while(getchar() != '\n'){}printf("\npress # to exit:");if(getchar() == 35){return 0;}while(getchar() != '\n'){}}
}// 从输入缓冲区读取一个字符到ch中
char m_getch()
{ch = input[p_input];p_input = p_input + 1;return(ch);
}// 去掉空白符号
void getbc()
{while(ch == ' ' || ch == 10){ch = input[p_input];p_input = p_input + 1;}
}//拼写单词
void concat()
{token[p_token] = ch;p_token = p_token + 1;token[p_token] = '\0';
}//判断是否字母
int letter()
{if(ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z')return 1;else return 0;
}//判断是否数字
int digit()
{if(ch >= '0' && ch <= '9')return 1;else return 0;
}// 检索关键字表格
int reserve(){int i = 0;while(strcmp(rwtab[i],_KEY_WORD_END)){if(!strcmp(rwtab[i],token)){return i + 1;}i = i + 1;}return 10;
}//回退一个字符
void retract()
{p_input = p_input - 1;
}//数字转换成二进制
char* dtb(char *buffer)
{int j = 0;int flag = 0;int k = (sizeof(char)<<3) - 1;char temp = ch - '0';for(int i = 0; i < (sizeof(char)<<3); i++,k--){if((temp >> k & 0x01) == 0){if(flag == 1){buffer[j++] = 0 + '0';} }else{flag = 1;buffer[j++] = (temp >> k & 0x01) + '0';}}buffer[j] = 0;return buffer;
}WORD* scaner()
{WORD* myword = new WORD;myword -> typenum = 10;myword -> word = "";p_token = 0;m_getch();getbc();if(letter()){while (letter() || digit()){concat();m_getch();}retract();myword -> typenum = reserve();myword -> word = token;return (myword);}else if(digit()){while (digit()){concat();m_getch();}retract();myword ->typenum = 11;myword -> word = token;return (myword);}else switch (ch){case '=' : m_getch();if(ch == '='){myword -> typenum = 39; // == 的种别码为39myword -> word = "==";return (myword);}retract();myword -> typenum = 25; // = 的种别码为25myword -> word = "=";return (myword);break;case '+' : myword -> typenum = 13; // + 的种别码为13myword -> word = "+";return (myword);break;case '-' : myword -> typenum = 14; // - 的种别码为14myword -> word = "-";return (myword);break;case '*' : myword -> typenum = 15; // * 的种别码为15myword -> word = "*";return (myword);break;case '/' : myword -> typenum = 16; // / 的种别码为16myword -> word = "/";return (myword);break;case '(' : myword -> typenum = 27;myword -> word = "(";return (myword);break;case ')' : myword -> typenum = 28;myword -> word = ")";return (myword);break;case '[' : myword -> typenum = 29;myword -> word = "[";return (myword);break;case ']' : myword -> typenum = 30;myword -> word = "]";return (myword);break;case '{' : myword -> typenum = 31;myword -> word = "{";return (myword);break;case '}' : myword -> typenum = 32;myword -> word = "}";return (myword);break;case ',' : myword -> typenum = 33;myword -> word = ",";return (myword);break;case ':' : m_getch();if(ch == '='){myword -> typenum = 18;myword -> word = ":=";return (myword);}retract();myword -> typenum = 17;myword -> word = ":";return (myword);break;case ';' : myword -> typenum = 26;myword -> word = ";";return (myword);break;case '>' : m_getch();if(ch == '='){myword -> typenum = 24;myword -> word = ">=";return (myword);}retract();myword -> typenum = 23;myword -> word = ">";return (myword);break;case '<' : m_getch();if(ch == '='){myword -> typenum = 22;myword -> word = "<=";return (myword);}retract();myword -> typenum = 20;myword -> word = "<";return (myword);break;case '!' : m_getch();if(ch == '='){myword -> typenum = 40;myword -> word = "!=";return (myword);}retract();myword -> typenum = -1;myword -> word = "ERROR";return (myword);break;case '\0' : myword -> typenum = 1000;myword -> word = "OVER";return (myword);break;default:myword -> typenum = 0;myword -> word = "#";return (myword);}
}
5. 实验结果
输入源程序后得出结果：
press # to exit:
输入其他字符，继续输入源程序：
6. 实验小结
-
关键词new出错
改进：将c源程序改为c++
原因：new为c++中的关键字 在使用new进行内存分配时，需要包含相关类型的头文件。#include <iostream> -
void main()出错
error: '::main' must return 'int'
解决方式：将void main改为int main(void) -
数字转换二进制
十进制转二进制代码//数字转换成二进制 char* dtb(char *buffer) {int j = 0;int flag = 0;int k = (sizeof(char)<<3) - 1;char temp = ch - '0';for(int i = 0; i < (sizeof(char)<<3); i++,k--){if((temp >> k & 0x01) == 0){if(flag == 1){buffer[j++] = 0 + '0';} }else{flag = 1;buffer[j++] = (temp >> k & 0x01) + '0';}}buffer[j] = 0;return buffer; } -
增加
：=的判断case ':' : m_getch();if(ch == '='){myword -> typenum = 18;myword -> word = ":=";return (myword);}retract();myword -> typenum = 17;myword -> word = ":";return (myword);break; -
程序运行后会自动退出，无法满足按#退出
解决方式：修改main函数int main(void) {// printf("111");int over = 1;WORD* oneword = new WORD; //new为c++中的关键字 在使用new进行内存分配时，需要包含相关类型的头文件。#include <iostream>while (1){printf("Enter Your words(end with #):");scanf("%[^#]s",input); //读入源程序字符串到缓冲区，以#结束，允许多行输入p_input = 0;printf("Your words: \n %s \n",input);while (over < 1000 && over != -1) {oneword = scaner(); //获得新单词 if(oneword -> typenum < 1000){printf("(%d,%s)",oneword -> typenum,oneword -> word); //打印种别码和单词本身的值}over = oneword -> typenum;free(oneword);}over = 1;// printf("\n press # to exit: \n"); //#号退出程序// scanf("%[^#]s",input);while(getchar() != '\n'){}printf("\npress # to exit:");if(getchar() == 35){return 0;}while(getchar() != '\n'){}} }
