本章，我們將繼續(xù)擴(kuò)展我們的解釋器，使其支持乘除運(yùn)算符和運(yùn)算符優(yōu)先級(jí)，我們將更加深入編譯原理，加入文法分析（ grammar analysis ）。

文法與文法分析

等一下，什么是文法？
OK，國內(nèi)的編譯原理教材是翻譯得有點(diǎn)隨心所欲以至于當(dāng)年上學(xué)的時(shí)候總是云里霧里，還是英文材料更好理解一些，不過中文語境確實(shí)很難精確表達(dá)syntax跟grammar，簡單來說，文法（ grammar ）是描述語法的語法，是一種元語法（ meta syntax ），
文法的描述方式參考BNF，我們不會(huì)嚴(yán)格地遵守BNF，而是在這個(gè)基礎(chǔ)上稍微擴(kuò)展一些，使用EBNF。
對(duì)于我們的多位數(shù)加減乘除語言，有如下文法：

expr : factor((PLUS | MINUS | MULTI | DIV)factor)*
factor : INTEGER

其中，冒號(hào)左側(cè)的符號(hào)被稱為head，相對(duì)的，右側(cè)是body，類似PLUS/MINUS/MULTI/DIV/INTEGER這樣的變量被稱為終端（terminals），它們類似編程語言的保留字，是不需要進(jìn)一步展開的，而相對(duì)的expr/factor則是非終端（non-terminals），非終端代表了我們的文法還沒結(jié)束，需要進(jìn)一步展開，比如factor要展開成INTEGER，文法分析才結(jié)束。
expr作為第一行的head，又叫做起始變量（start symbol），它是我們文法所描述的語法的起點(diǎn)，而expr后面，冒號(hào)右側(cè)的內(nèi)容則是推斷expr相對(duì)應(yīng)的語法的文法，可以看到它具有類似正則表達(dá)式的符號(hào)，這里，它表示一個(gè)factor后面跟著零個(gè)或多個(gè)(PLUS | MINUS | MULTI | DIV)factor的組合，而factor本身則由第二行文法定義，它代表一個(gè)整數(shù)。
現(xiàn)在我們對(duì)輸入"3"進(jìn)行文法分析：

expr
factor((PLUS | MINUS | MULTI | DIV)factor)*
factor
INTEGER

最終，我們得到"3"這個(gè)輸入對(duì)應(yīng)的語法就是一個(gè)INTEGER，那么對(duì)于3+3這樣的呢？

expr
factor((PLUS | MINUS | MULTI | DIV)factor)*
factor PLUS factor((PLUS | MINUS | MULTI | DIV)factor)*
factor PLUS factor
INTEGER PLUS INTEGER

可以看到，文法最終展開成了由terminals構(gòu)成的語法。

運(yùn)算符優(yōu)先級(jí)

當(dāng)我們加入乘除運(yùn)算以后，運(yùn)算符優(yōu)先級(jí)就成了我們的解釋器所必須的一項(xiàng)特性，對(duì)于運(yùn)算符優(yōu)先級(jí)，我們可以畫一張表來表示，這也是文法的一部分，將來我們需要實(shí)現(xiàn)文法分析器時(shí)，這將至關(guān)重要：

其中associative代表這個(gè)運(yùn)算符是跟它的左邊還是右邊的factor相關(guān)聯(lián)的，我們統(tǒng)一使用left，即：

1 / 3 + 3 = ( 1 / 3 ) + 3

如果是right的話就變成：

1 / 3 + 3 = 1 / ( 3 + 3 )

這顯然不符合常識(shí)。
接下來，我們要把這個(gè)表轉(zhuǎn)化成文法，通過以下兩條規(guī)則：

• 對(duì)于每一個(gè)運(yùn)算符優(yōu)先級(jí)，定義一條非終端( non-terminal )規(guī)則，其中包含當(dāng)前優(yōu)先級(jí)的終端運(yùn)算符和下一個(gè)優(yōu)先級(jí)的非終端head；
• 為非終端的基本單元?jiǎng)?chuàng)建一條規(guī)則，對(duì)于我們的解釋器來說，就是factor : INTEGER
  最終，我們修改文法為：

expr : term((PLUS | MINUS)term)*
term : factor((MULTI | DIV)factor)*
factor : INTEGER

這里的邏輯在于：解釋expr之前，一定要先解釋term，所以term中所包含的terminals的優(yōu)先級(jí)是高于expr中的terminals的，以此類推，可以實(shí)現(xiàn)多重優(yōu)先級(jí)。

實(shí)現(xiàn)

這一次，我們正式實(shí)現(xiàn)一個(gè)詞法分析器Lexer:

#pragma once
#include <string>
#include <memory>
#include "Token.h"

class Lexer
{
private:
    size_t currentPos;
    std::string text;
    char currentChar;
private:
    void advance();
    void skipWhiteSpaces();
    int integer();
    bool isSpace(char c);
    bool isDigit(char c);
    void raiseError();
public:
    Lexer(std::string txt);
    TokenPtr getNextTokenPtr();
};

typedef std::shared_ptr<Lexer> LexerPtr;

#include "Lexer.h"
#include "LexerException.h"
using namespace std;
void Lexer::advance()
{
    currentPos += 1;
    if (currentPos >= strlen(text.c_str())) 
    {
        currentChar = '\0';
        return;
    }
    currentChar = text.c_str()[currentPos];
}

void Lexer::skipWhiteSpaces()
{
    while (isSpace(currentChar))
    {
        advance();
    }
}

int Lexer::integer()
{
    int result = 0;
    while (isDigit(currentChar))
    {
        result *= 10;
        result += currentChar - '0';
        advance();
    }
    return result;
}

bool Lexer::isSpace(char c)
{
    return c == ' ' || c == '\t';
}

bool Lexer::isDigit(char c)
{
    return c >= '0' && c <= '9';
}

void Lexer::raiseError()
{
    throw LexerException();
}

Lexer::Lexer(std::string txt) :text(txt)
{
    currentChar = txt.c_str()[0];
    currentPos = 0;
}

TokenPtr Lexer::getNextTokenPtr()
{
    while (currentChar != '\0' && currentPos < strlen(text.c_str()))
    {
        if (isSpace(currentChar))
        {
            skipWhiteSpaces();
        }

        TokenType tokenType;
        TokenValue tokenValue;

        if (isDigit(currentChar)) 
        {
            return make_shared<Token>(TokenType::TT_INTEGER,integer());
        }

        switch (currentChar)
        {
        case '+':
            tokenType = TokenType::TT_PLUS;
            tokenValue = "+";
            break;
        case '-':
            tokenType = TokenType::TT_MINUS;
            tokenValue = "-";
            break;
        case '*':
            tokenType = TokenType::TT_MULTI;
            tokenValue = "*";
            break;
        case '/':
            tokenType = TokenType::TT_DIV;
            tokenValue = "/";
            break;
        default:
            raiseError();
            break;
        }

        advance();
        return make_shared<Token>(tokenType, tokenValue);
    }
    return make_shared<Token>(TokenType::TT_EOF, NULL);
}

把詞法分析的邏輯從之前的interpreter中剝離了出來，這樣，Lexer只需要負(fù)責(zé)解析輸入的字符串，并按順序輸出Token，其余的邏輯不需要它考慮。
而interperter則可以更加專注于語法分析：

#pragma once
#include "Token.h"
#include "Lexer.h"

class Interpreter
{
private:
    LexerPtr lexerPtr;
    TokenPtr currentTokenPtr;
private:
    void eat(TokenType type);
    void raiseError(std::string content);
    TokenValue term();
    TokenValue factor();
public:
    Interpreter(std::string txt);
    int expr();
};

#include "Interpreter.h"
#include "InterpreterException.h"
using namespace std;

void Interpreter::eat(TokenType type)
{
    if (currentTokenPtr->getType() != type)
    {
        raiseError("syntax error");
    }
    currentTokenPtr = lexerPtr->getNextTokenPtr();
}


void Interpreter::raiseError(std::string content = "")
{
    throw InterpreterException(content);
}

TokenValue Interpreter::term()
{
    TokenValue result = factor();
    while (currentTokenPtr->getType() == TokenType::TT_MULTI ||
        currentTokenPtr->getType() == TokenType::TT_DIV) 
    {
        TokenPtr tokenPtr = currentTokenPtr;
        eat(tokenPtr->getType());
        switch (tokenPtr->getType())
        {
        case TokenType::TT_MULTI:
            result = get<int>(result) * get<int>(factor());
            break;
        case TokenType::TT_DIV:
            result = get<int>(result) / get<int>(factor());
            break;
        }
    }
    return result;
}

TokenValue Interpreter::factor()
{
    TokenPtr tokenPtr = currentTokenPtr;
    eat(TokenType::TT_INTEGER);
    return tokenPtr->getValue();
}

Interpreter::Interpreter(string txt)
{
    lexerPtr = make_shared<Lexer>(txt);
    currentTokenPtr = lexerPtr->getNextTokenPtr();
}

TokenValue Interpreter::expr()
{
    TokenValue result = term();
    while (currentTokenPtr->getType() == TokenType::TT_PLUS ||
        currentTokenPtr->getType() == TokenType::TT_MINUS) 
    {
        TokenPtr token = currentTokenPtr;
        switch (token->getType())
        {
        case TokenType::TT_PLUS:
            eat(TokenType::TT_PLUS);
            result = get<int>(result) + get<int>(term());
            break;
        case TokenType::TT_MINUS:
            eat(TokenType::TT_MINUS);
            result = get<int>(result) - get<int>(term());
            break;
        default:
            raiseError();
            break;
        }
    }
    return result;
}

上面是根據(jù)之前定義的文法所寫的語法分析器，可以看到term和factor這種non-terminal，分別實(shí)現(xiàn)了對(duì)應(yīng)的函數(shù)，最后通過start symbol：expr調(diào)用。

括號(hào)的文法

OK，讓我們向上面的文法中添加一點(diǎn)點(diǎn)東西：

expr : term((PLUS | MINUS)term)*
term : factor((MULTI | DIV)factor)*
factor : INTEGER | LPAREN expr RPAREN

我們添加LPAREN和RPAREN兩個(gè)terminals，分別代表左右括號(hào)，并且僅僅將factor的body擴(kuò)展了一點(diǎn)，如此，便從文法上實(shí)現(xiàn)了括號(hào)運(yùn)算符。
是不是很神奇？
還記得我們?cè)趺磳?shí)現(xiàn)乘除的優(yōu)先級(jí)嗎？
對(duì)于任何一條文法規(guī)則，其non-terminal符號(hào)總是比該規(guī)則本身優(yōu)先級(jí)更高，所以對(duì)于factor這個(gè)規(guī)則，當(dāng)它的模式為LPAREN expr RPAREN時(shí)，expr中的內(nèi)容的優(yōu)先級(jí)總是高于調(diào)用factor的non-terminal。
然后，根據(jù)我們的手工文法分析，向解釋器中添加括號(hào)相關(guān)的代碼即可，它只修改了factor，所以我們的Interpreter也只需要修改factor，除此以外再添加左右括號(hào)的詞法分析即可。
首先，升級(jí)詞法分析器，向Lexer.cpp的getNextToken的switch中添加如下cases：

case '(':
    tokenType = TokenType::TT_LPAREN;
    tokenValue = "(";
    break;
case ')':
    tokenType = TokenType::TT_RPAREN;
    tokenValue = ")";
    break;

然后升級(jí)Interpreter：

TokenValue Interpreter::factor()
{
    TokenPtr tokenPtr = currentTokenPtr;
    TokenValue result;
    switch (tokenPtr->getType())
    {
    case TokenType::TT_INTEGER:
        eat(TokenType::TT_INTEGER);
        return tokenPtr->getValue();
    case TokenType::TT_LPAREN:
        eat(TokenType::TT_LPAREN);
        result = expr();
        eat(TokenType::TT_RPAREN);
        return result;
    default:
        raiseError("syntax error");
        break;
    }
}

僅修改factor函數(shù)，我們成功實(shí)現(xiàn)了括號(hào)運(yùn)算符，這就是文法的作用。

這一章，我們了解了文法，并且通過手工文法分析，實(shí)現(xiàn)了一個(gè)解釋器，添加了乘除括號(hào)和運(yùn)算符優(yōu)先級(jí)的特性，把詞法分析獨(dú)立出來從而實(shí)現(xiàn)了更清晰的結(jié)構(gòu)。