从0开始自制解释器实现多位整数的加减法计算器

　　上一篇我们实现了一个简单的加法计算器，并且了解了基本的词法分析、词法分析器的概念。本篇我们将要对之前实现的加法计算器进行扩展，我们为它添加以下几个功能 计算减法 能自动识别并跳过空白字符 不再局限于单个整数，而是能计算多位整数 提供一些工具函数
　　首先为了支持减法，我们需要重新定义一下TokenType这个类型，也就是需要给  -   定义一个标志。现在我们的TokenType  的定义如下typedef enum e_TokenType {     CINT = 0,     PLUS,     MINUS,     END_OF_FILE }ETokenType;
　　由于需要支持多个整数，所以我们也不知道最终会有多少个字符，因此我们提供一个 END_OF_FILE   表示我们访问到了最后一个字符，此时应该退出词法分析的过程。
　　另外因为整数个数不再确定，我们也就不能按照之前的提供一个固定大小的数组。虽然可以提供一个足够大的空间来作为存储数字的缓冲，但是数字少了会浪费空间。而且考虑到之后要支持自定义变量和函数，采用固定长度缓冲的方式就很难找到合适的大小，太大显得浪费空间，太小有时候无法容纳得下用户定义的变量和函数名。因此这里我们采用动态长度的字符缓冲来保存。我们提供一个 DyncString   的结构来保存这些内容#define DEFAULT_BUFFER_SIZE 16  // 动态字符串结构，用于保存任意长度的字符串 typedef struct DyncString {     int nLength; // 字符长度     int capacity; //实际分配的空间大小     char* pszBuf; //保存字符串的缓冲 }DyncString, *LPDyncString;  // 动态字符串初始化 // str: 被初始化的字符串 // size: 初始化字符串缓冲的大小，如果给0则按照默认大小分配空间 void dyncstring_init(LPDyncString str, int size); // 动态字符串空间释放 void dyncstring_free(LPDyncString str); //重分配动态字符串大小 void dyncstring_resize(LPDyncString str, int newSize); //往动态字符串中添加字符 void dyncstring_catch(LPDyncString str, char c); // 重置动态数组 void dyncstring_reset(LPDyncString str);
　　它们的实现如下 /*----------------------------动态数组的操作函数-------------------------------*/ void dyncstring_init(LPDyncString str, int size) {     if (NULL == str)         return;      if (size == 0)         str->capacity = DEFAULT_BUFFER_SIZE;     else         str->capacity = size;     str->nLength = 0;     str->pszBuf = (char*)malloc(sizeof(char) * str->capacity);     if (NULL == str->pszBuf)     {         error(＂分配内存失败 ＂);     }      memset(str->pszBuf, 0x00, sizeof(char) * str->capacity); }  void dyncstring_free(LPDyncString str) {     if (NULL == str)         return;      str->capacity = 0;     str->nLength = 0;     if (str->pszBuf == NULL)         return;      free(str->pszBuf); }  void dyncstring_resize(LPDyncString str, int newSize) {     int size = str->capacity;     for (; size < newSize; size = size * 2);     char* pszStr = (char*)realloc(str->pszBuf, size);     str->capacity = size;     str->pszBuf = pszStr; }  void dyncstring_catch(LPDyncString str, char c) {     if (str->capacity == str->nLength + 1)     {         dyncstring_resize(str, str->capacity + 1);     }      str->pszBuf[str->nLength] = c;     str->nLength++; }  void dyncstring_reset(LPDyncString str) {     dyncstring_free(str);     dyncstring_init(str, DEFAULT_BUFFER_SIZE); } /*----------------------------End 动态数组的操作函数-------------------------------*/
　　另外提供一些额外的工具函数，他们的定义如下 void error(char* lpszFmt, ...) {     char szBuf[1024] = ＂＂;     va_list arg;     va_start(arg, lpszFmt);     vsnprintf(szBuf, 1024, lpszFmt, arg);     va_end(arg);      printf(szBuf);     exit(-1); }  bool is_digit(char c) {     return (c >= ＂0＂ && c <= ＂9＂); } bool is_space(char c) {     return (c == ＂ ＂ || c == ＂	＂ || c == ＂r＂ || c == ＂ ＂); } 主要算法
　　我们还是延续之前的算法，一个字符一个字符的解析，只是现在需要额外的将多个整数添加到一块作为一个整数处理。而且需要添加跳过空格的处理。
　　首先我们对上次的代码进行一定程度的重构。我们添加一个函数专门用来获取下一个字符 char get_next_char() {     // 如果到达字符串尾部，索引不再增加     if (g_pPosition == ＂＂)     {         return ＂＂;     }     else     {         char c = *g_pPosition;         g_pPosition++;         return c;     } }
　　expr()   函数里面大部分结构不变，主要算法仍然是按次序获取第一个整数、获取算术运算符、获取第二个整数。只是现在的整数都变成了采用 dyncstring 结构来存储int expr() {     int val1 = 0, val2 = 0;     Token token = { 0 };     dyncstring_init(&token.value, DEFAULT_BUFFER_SIZE);      if (get_next_token(&token) && token.type == CINT)     {         val1 = atoi(token.value.pszBuf);     }     else     {         printf(＂首个操作数必须是整数 ＂);         dyncstring_free(&token.value);         return -1;     }      int oper = 0;     if (get_next_token(&token) && (token.type == PLUS || token.type == MINUS))     {         oper = token.type;     }     else     {         printf(＂第二个字符必须是操作符， 当前只支持+/- ＂);         dyncstring_free(&token.value);         return -1;     }      if (get_next_token(&token) && token.type == CINT)     {         val2 = atoi(token.value.pszBuf);     }     else     {         printf(＂操作符后需要跟一个整数 ＂);         dyncstring_free(&token.value);         return -1;     }      switch (oper)     {     case PLUS:         {             printf(＂%d+%d=%d ＂, val1, val2, val1 + val2);         }         break;     case MINUS:         {             printf(＂%d-%d=%d ＂, val1, val2, val1 - val2);         }         break;     default:         printf(＂未知的操作! ＂);         break;     }      dyncstring_free(&token.value); }
　　最后就是最终要的  get_next_token   函数了。这个函数最主要的修改就是添加了解析整数和跳过空格的功能bool get_next_token(LPTOKEN pToken) {     char c = get_next_char();      dyncstring_reset(&pToken->value);     if (is_digit(c))     {         dyncstring_catch(&pToken->value, c);         pToken->type = CINT;         parser_number(&pToken->value);     }     else if (c == ＂+＂)     {         pToken->type = PLUS;         dyncstring_catch(&pToken->value, ＂+＂);     }     else if (c == ＂-＂)     {         pToken->type = MINUS;         dyncstring_catch(&pToken->value, ＂-＂);     }     else if(is_space(c))     {         skip_whitespace();         return get_next_token(pToken);     }     else if (＂＂ == c)     {         pToken->type = END_OF_FILE;     }     else     {         return false;     }     return true; }
　　在这个函数中我们先获取第一个字符，如果字符是整数则获取后面的整数并直接拼接为一个完整的整数。如果是空格则跳过接下来的空格。这两个是可能要处理多个字符所以这里使用了单独的函数来处理。其余只处理单个字符可以直接返回。
　　parser_number   和 skip_whitespace   函数比较简单，主要的过程是不断从输入中取出字符，如果是空格则直接将索引往后移动，如果是整数则像对应的整数字符串中将整数字符加入。void skip_whitespace() {     char c = ＂＂;     do     {         c = get_next_char();     } while (is_space(c));      // 遇到不是空白字符的，下次要取用它，这里需要重复取用上次取出的字符     g_pPosition--; }  void parser_number(LPDyncString dyncstr) {     char c = get_next_char();     while(is_digit(c))     {         dyncstring_catch(dyncstr, c);         c = get_next_char();     }      // 遇到不是数字的，下次要取用它，这里需要重复取用上次取出的字符     g_pPosition--; }
　　唯一需要注意的是，最后都有一个  g_pPosition--   的操作。因为当我们发现下一个字符不符合条件的时候，它已经过了最后一个数字或者空格了，此时应该已经退回到get_next_token   函数中了，这个函数第一步就是获取下一个字符，因此会产生字符串被跳过的现象。所以这里我们执行 --   退回到上一个位置，这样再取下一个就不会有问题了。
　　最后为了能够获取空格的输入，我们将之前的 scanf   改成 gets  。这样就大功告成了。
　　我们来测试一下结果
　　最后的总结
　　最后来一个总结。本篇我们对上一次的加法计算器进行了简单的改造，支持加减法、能跳过空格并且能够计算多位整数。
　　在上一篇文章中，我们提到了Token，并且说过，像  get_next_token   这样给字符串每个部分打上Token的过程就是词法分析。get_next_token   这部分代码可以被称之为词法分析器。这篇我们再来介绍一下其他的概念。词位(lexeme):
　　词位的中文解释是语言词汇的基本单位。例如汉语的词位是汉字，英语的词位是基本的英文字母。对于我们这个加法计算器来说基本的词位就是数字以及  +-   这两个符号parsing（语法分析）和 parser（语法分析器）
　　我们所编写的expr函数主要工作流程是根据token来组织代码行为。它的本质就是从Token流中识别出对应的结构，并将结构翻译为具体的行为。例如这里找到的结构是  CINT oper CINT  。并且将两个int   按照 oper   指定的运算符进行算术运算。这个将Token流中识别出对应的结构的过程我们称之为语法分析，完成语法分析的组件被称之为语法分析器。expr   函数中即实现了语法分析的功能，也实现了解释执行的功能。