本章，我们将继续扩展我们的解释器，使其支持乘除运算符和运算符优先级，我们将更加深入编译原理，加入文法分析（ grammar analysis ）。
文法与文法分析
等一下，什么是文法？
OK，国内的编译原理教材是翻译得有点随心所欲以至于当年上学的时候总是云里雾里，还是英文材料更好理解一些，不过中文语境确实很难精确表达syntax跟grammar，简单来说，文法（ grammar ）是描述语法的语法，是一种元语法（ meta syntax ），
文法的描述方式参考BNF，我们不会严格地遵守BNF，而是在这个基础上稍微扩展一些，使用EBNF。
对于我们的多位数加减乘除语言，有如下文法：
expr : factor((PLUS | MINUS | MULTI | DIV)factor)*
factor : INTEGER
其中，冒号左侧的符号被称为head，相对的，右侧是body，类似PLUS/MINUS/MULTI/DIV/INTEGER这样的变量被称为终端（terminals），它们类似编程语言的保留字，是不需要进一步展开的，而相对的expr/factor则是非终端（non-terminals），非终端代表了我们的文法还没结束，需要进一步展开，比如factor要展开成INTEGER，文法分析才结束。
expr作为第一行的head，又叫做起始变量（start symbol），它是我们文法所描述的语法的起点，而expr后面，冒号右侧的内容则是推断expr相对应的语法的文法，可以看到它具有类似正则表达式的符号，这里，它表示一个factor后面跟着零个或多个(PLUS | MINUS | MULTI | DIV)factor的组合，而factor本身则由第二行文法定义，它代表一个整数。
现在我们对输入"3"进行文法分析：
expr
factor((PLUS | MINUS | MULTI | DIV)factor)*
factor
INTEGER
最终，我们得到"3"这个输入对应的语法就是一个INTEGER，那么对于3+3这样的呢？
expr
factor((PLUS | MINUS | MULTI | DIV)factor)*
factor PLUS factor((PLUS | MINUS | MULTI | DIV)factor)*
factor PLUS factor
INTEGER PLUS INTEGER
可以看到，文法最终展开成了由terminals构成的语法。
运算符优先级
当我们加入乘除运算以后，运算符优先级就成了我们的解释器所必须的一项特性，对于运算符优先级，我们可以画一张表来表示，这也是文法的一部分，将来我们需要实现文法分析器时，这将至关重要：
| precedence level | associative | operators |
|---|---|---|
| 2 | left | +, - |
| 1 | left | *, / |
其中associative代表这个运算符是跟它的左边还是右边的factor相关联的，我们统一使用left，即：
1 / 3 + 3 = ( 1 / 3 ) + 3
如果是right的话就变成：
1 / 3 + 3 = 1 / ( 3 + 3 )
这显然不符合常识。
接下来，我们要把这个表转化成文法，通过以下两条规则：
- 对于每一个运算符优先级，定义一条非终端( non-terminal )规则，其中包含当前优先级的终端运算符和下一个优先级的非终端head；
- 为非终端的基本单元创建一条规则，对于我们的解释器来说，就是factor : INTEGER
最终，我们修改文法为：
expr : term((PLUS | MINUS)term)*
term : factor((MULTI | DIV)factor)*
factor : INTEGER
这里的逻辑在于：解释expr之前，一定要先解释term，所以term中所包含的terminals的优先级是高于expr中的terminals的，以此类推，可以实现多重优先级。
实现
这一次，我们正式实现一个词法分析器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只需要负责解析输入的字符串，并按顺序输出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;
}
上面是根据之前定义的文法所写的语法分析器，可以看到term和factor这种non-terminal，分别实现了对应的函数，最后通过start symbol：expr调用。
括号的文法
OK，让我们向上面的文法中添加一点点东西：
expr : term((PLUS | MINUS)term)*
term : factor((MULTI | DIV)factor)*
factor : INTEGER | LPAREN expr RPAREN
我们添加LPAREN和RPAREN两个terminals，分别代表左右括号，并且仅仅将factor的body扩展了一点，如此，便从文法上实现了括号运算符。
是不是很神奇？
还记得我们怎么实现乘除的优先级吗？
对于任何一条文法规则，其non-terminal符号总是比该规则本身优先级更高，所以对于factor这个规则，当它的模式为LPAREN expr RPAREN时，expr中的内容的优先级总是高于调用factor的non-terminal。
然后，根据我们的手工文法分析，向解释器中添加括号相关的代码即可，它只修改了factor，所以我们的Interpreter也只需要修改factor，除此以外再添加左右括号的词法分析即可。
首先，升级词法分析器，向Lexer.cpp的getNextToken的switch中添加如下cases：
case '(':
tokenType = TokenType::TT_LPAREN;
tokenValue = "(";
break;
case ')':
tokenType = TokenType::TT_RPAREN;
tokenValue = ")";
break;
然后升级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函数，我们成功实现了括号运算符，这就是文法的作用。
这一章，我们了解了文法，并且通过手工文法分析，实现了一个解释器，添加了乘除括号和运算符优先级的特性，把词法分析独立出来从而实现了更清晰的结构。
