上一篇我們實現(xiàn)了一個簡單的加法計算器，并且了解了基本的詞法分析、詞法分析器的概念。本篇我們將要對之前實現(xiàn)的加法計算器進行擴展，我們?yōu)樗砑右韵聨讉€功能
- 計算減法
- 能自動識別并跳過空白字符
- 不再局限于單個整數(shù)，而是能計算多位整數(shù)
提供一些工具函數(shù)
首先為了支持減法，我們需要重新定義一下TokenType這個類型，也就是需要給 - 定義一個標志?，F(xiàn)在我們的TokenType的定義如下
typedef enum e_TokenType
{
CINT = 0,
PLUS,
MINUS,
END_OF_FILE
}ETokenType;
由于需要支持多個整數(shù)，所以我們也不知道最終會有多少個字符，因此我們提供一個END_OF_FILE 表示我們訪問到了最后一個字符，此時應該退出詞法分析的過程。
另外因為整數(shù)個數(shù)不再確定，我們也就不能按照之前的提供一個固定大小的數(shù)組。雖然可以提供一個足夠大的空間來作為存儲數(shù)字的緩沖，但是數(shù)字少了會浪費空間。而且考慮到之后要支持自定義變量和函數(shù)，采用固定長度緩沖的方式就很難找到合適的大小，太大顯得浪費空間，太小有時候無法容納得下用戶定義的變量和函數(shù)名。因此這里我們采用動態(tài)長度的字符緩沖來保存。我們提供一個DyncString 的結構來保存這些內容
#define DEFAULT_BUFFER_SIZE 16
// 動態(tài)字符串結構，用于保存任意長度的字符串
typedef struct DyncString
{
int nLength; // 字符長度
int capacity; //實際分配的空間大小
char* pszBuf; //保存字符串的緩沖
}DyncString, *LPDyncString;
// 動態(tài)字符串初始化
// str: 被初始化的字符串
// size: 初始化字符串緩沖的大小，如果給0則按照默認大小分配空間
void dyncstring_init(LPDyncString str, int size);
// 動態(tài)字符串空間釋放
void dyncstring_free(LPDyncString str);
//重分配動態(tài)字符串大小
void dyncstring_resize(LPDyncString str, int newSize);
//往動態(tài)字符串中添加字符
void dyncstring_catch(LPDyncString str, char c);
// 重置動態(tài)數(shù)組
void dyncstring_reset(LPDyncString str);
它們的實現(xiàn)如下
/*----------------------------動態(tài)數(shù)組的操作函數(shù)-------------------------------*/
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("分配內存失敗\n");
}
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 動態(tài)數(shù)組的操作函數(shù)-------------------------------*/
另外提供一些額外的工具函數(shù)，他們的定義如下
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 == '\t' || c == '\r' || c == '\n');
}
主要算法
我們還是延續(xù)之前的算法，一個字符一個字符的解析，只是現(xiàn)在需要額外的將多個整數(shù)添加到一塊作為一個整數(shù)處理。而且需要添加跳過空格的處理。
首先我們對上次的代碼進行一定程度的重構。我們添加一個函數(shù)專門用來獲取下一個字符
char get_next_char()
{
// 如果到達字符串尾部，索引不再增加
if (g_pPosition == '\0')
{
return '\0';
}
else
{
char c = *g_pPosition;
g_pPosition++;
return c;
}
}
expr() 函數(shù)里面大部分結構不變，主要算法仍然是按次序獲取第一個整數(shù)、獲取算術運算符、獲取第二個整數(shù)。只是現(xiàn)在的整數(shù)都變成了采用 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("首個操作數(shù)必須是整數(shù)\n");
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("第二個字符必須是操作符， 當前只支持+/-\n");
dyncstring_free(&token.value);
return -1;
}
if (get_next_token(&token) && token.type == CINT)
{
val2 = atoi(token.value.pszBuf);
}
else
{
printf("操作符后需要跟一個整數(shù)\n");
dyncstring_free(&token.value);
return -1;
}
switch (oper)
{
case PLUS:
{
printf("%d+%d=%d\n", val1, val2, val1 + val2);
}
break;
case MINUS:
{
printf("%d-%d=%d\n", val1, val2, val1 - val2);
}
break;
default:
printf("未知的操作!\n");
break;
}
dyncstring_free(&token.value);
}
最后就是最終要的 get_next_token 函數(shù)了。這個函數(shù)最主要的修改就是添加了解析整數(shù)和跳過空格的功能
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 ('\0' == c)
{
pToken->type = END_OF_FILE;
}
else
{
return false;
}
return true;
}
在這個函數(shù)中我們先獲取第一個字符，如果字符是整數(shù)則獲取后面的整數(shù)并直接拼接為一個完整的整數(shù)。如果是空格則跳過接下來的空格。這兩個是可能要處理多個字符所以這里使用了單獨的函數(shù)來處理。其余只處理單個字符可以直接返回。
parser_number 和 skip_whitespace 函數(shù)比較簡單，主要的過程是不斷從輸入中取出字符，如果是空格則直接將索引往后移動，如果是整數(shù)則像對應的整數(shù)字符串中將整數(shù)字符加入。
void skip_whitespace()
{
char c = '\0';
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();
}
// 遇到不是數(shù)字的，下次要取用它，這里需要重復取用上次取出的字符
g_pPosition--;
}
唯一需要注意的是，最后都有一個 g_pPosition-- 的操作。因為當我們發(fā)現(xiàn)下一個字符不符合條件的時候，它已經過了最后一個數(shù)字或者空格了，此時應該已經退回到get_next_token 函數(shù)中了，這個函數(shù)第一步就是獲取下一個字符，因此會產生字符串被跳過的現(xiàn)象。所以這里我們執(zhí)行 -- 退回到上一個位置，這樣再取下一個就不會有問題了。
最后為了能夠獲取空格的輸入，我們將之前的scanf 改成 gets。這樣就大功告成了。
我們來測試一下結果
最后的總結
最后來一個總結。本篇我們對上一次的加法計算器進行了簡單的改造，支持加減法、能跳過空格并且能夠計算多位整數(shù)。
在上一篇文章中，我們提到了Token，并且說過，像 get_next_token 這樣給字符串每個部分打上Token的過程就是詞法分析。get_next_token 這部分代碼可以被稱之為詞法分析器。這篇我們再來介紹一下其他的概念。
- 詞位(lexeme):
詞位的中文解釋是語言詞匯的基本單位。例如漢語的詞位是漢字，英語的詞位是基本的英文字母。對于我們這個加法計算器來說基本的詞位就是數(shù)字以及+\-這兩個符號 - parsing（語法分析）和 parser（語法分析器）
我們所編寫的expr函數(shù)主要工作流程是根據(jù)token來組織代碼行為。它的本質就是從Token流中識別出對應的結構，并將結構翻譯為具體的行為。例如這里找到的結構是CINT oper CINT。并且將兩個int按照oper指定的運算符進行算術運算。這個將Token流中識別出對應的結構的過程我們稱之為語法分析，完成語法分析的組件被稱之為語法分析器。expr函數(shù)中即實現(xiàn)了語法分析的功能，也實現(xiàn)了解釋執(zhí)行的功能。
