在前面的旅程中，我们已经实现了词法分析器。词法分析器可将源代码转变为记号流，以供语法分析器使用。所以现在就让我们启程，朝着下一站——语法分析器出发吧。
1. 什么是语法什么是语法呢？提到词法分析器，我们能够立即联想到一个个看得见摸得着的词；而提到语法分析器，又能联想到什么呢？
词法和语法的关系，就像扑克牌和打扑克牌的游戏规则之间的关系一样：词法决定了扑克牌的印刷、张数、花色、点数等等，而语法则决定了我们应该如何打出这些扑克牌，以赢得游戏胜利；这在编程语言中就是：词法决定了代码中能够出现哪些词，而语法决定了这些词的正确组织方式。由此可见：词法是具象的，而语法是抽象的。
2. 怎么表示语法正如我们通过一段文字描述某种游戏规则一样，我们也可以用一段文字来描述一个语法。请看：
句子的语法： 1. 一个句子，由主语 + 谓语 + 宾语构成 2. 主语是：“程序员” 3. 谓语是：“没有” 4. 宾语是：“头发”显然，这就是一套语法了。但是我们发现，这种白话文式的语法表示显然不是我们编译器一贯的作风嘛。针对这个问题，巴科斯及后人提出了用于表示语法的“巴科斯范式”和“拓展的巴科斯范式”。拓展的巴科斯范式的主要规则如下：
1. 用“::=”符号表示“是”，或“由...构成”的意思。说的专业点，叫“推导出” 2. 用“|”符号表示“或”的意思 3. 用“[ ... ]”表示中括号中的内容是可选的 4. 用“{ ... }”表示大括号中的内容可以出现0至无穷多次的重复现在，就让我们用“拓展的巴科斯范式”来描述我们的语法吧：
句子的语法： 1. 句子 ::= 主语 谓语 宾语 2. 主语 ::= “程序员” 3. 谓语 ::= “没有” 4. 宾语 ::= “头发” 3. 语法怎么使用我们已经有了语法，现在的问题是，语法有什么用处？又该怎么发挥这些用处呢？
首先，我们显然可以做这样一件事：判定一个记号流是否符合语法。请看：
假如我们有记号流：（“程序员”，“有很多”，“头发”），我们从语法的第一条开始，我们知道：“句子 ::= 主语 谓语 宾语”，这句话代表什么呢？其代表着：我们需要先看到一个主语，再看到一个谓语，最后看到一个宾语，如果都看到了，我们就认为这段记号流是符合语法的，否则，只要有任何一个地方不符合要求，我们就认为这段记号流是不符合语法的。那么问题来了，主语、谓语、宾语又分别是什么？显然，接下来的三条语法告诉了我们答案。我们首先检查主语，根据语法规则，我们知道：主语必须是“程序员”，记号流呢？嗯，第一个记号确实是“程序员”，我们接着往下看；语法规则又告诉我们：谓语必须是“没有”，而此时的记号是“有很多”，这就不对了，后面也不用看了，我们可以立即判定：（“程序员”，“有很多”，“头发”）这个记号流是不符合语法的。
接下来的故事就不用我多说了吧。经过一番小小的努力，我们终于发现：只有：（“程序员”，“没有”，“头发”）这个记号流是符合语法的。
确实符合语法了，然后呢？正如前面的章节所说，此时，我们就可以将这段记号流立体化，变为一棵抽象语法树了。这棵抽象语法树长什么样呢。请看：
句子 / | \ 程序员（主语） 没有（谓语） 头发（宾语）一句话解释：语法长什么样，语法树就长什么样。
将上面的模型变为代码，我们就得到了抽象语法树节点的定义。请看：
struct AST { // Attribute TOKEN_TYPE tokenType; string tokenStr; vector<AST *> subList; int lineNo; // Constructor explicit AST(TOKEN_TYPE _tokenType, const string &_tokenStr = "", const vector<AST *> &_subList = {}, int _lineNo = 0); explicit AST(const Token *tokenPtr); // Destructor ~AST(); }; AST::AST(TOKEN_TYPE _tokenType, const string &_tokenStr, const vector<AST *> &_subList, int _lineNo): tokenType(_tokenType), tokenStr (_tokenStr), subList (_subList), lineNo (_lineNo) {} AST::AST(const Token *tokenPtr): tokenType(tokenPtr->tokenType), tokenStr (tokenPtr->tokenStr), lineNo (tokenPtr->lineNo) {} AST::~AST() { for (auto subPtr: subList) { delete subPtr; } }可见，抽象语法树节点的定义和前面Token类的定义是高度相似的。抽象语法树节点也需要标记的类别、标记字符串，以及标记所在的行数。此外，抽象语法树节点还需要一个vector，以保存这个节点的所有子节点。
4. 语法错误的表示当我们遇到上文中的语法错误时，我们就需要一个能够报告此问题的工具函数，实现如下：
void InvalidToken(const Token *invalidTokenPtr) { printf("Invalid token: %s in line %d\n", invalidTokenPtr->tokenStr.c_str(), invalidTokenPtr->lineNo); exit(1); }这个函数的实现很简单，这里就不讨论了。
5. 消除左递归这巴科斯范式可不是省油的灯啊。这一节和下一节，我们将分别来看看巴科斯范式中的两个常见问题。首先来看消除左递归。
假设有以下语法：
Six ::= Six '6' | '6'这个语法说了什么？其表示，一个“Six”可以推导出一个“Six '6'”；而“Six”又是什么？是“Six '6'”；而“Six”又是什么？是“Six '6'”...
怎么回事？我们连一个记号字符串都还没看到呢，就光顾着在这无限循环了，这就是“左递归”问题，是我们需要消除的。