正如我们在上一章中学到的，编译器通常分为两个部分——前端和后端。在本章中，我们将实现一个编程语言的前端——即主要处理源语言的部分。我们将学习现实世界编译器使用的技术，并将它们应用到我们的编程语言中。

我们的旅程将从定义我们编程语言的语法开始，以抽象语法树（AST）结束，AST将成为代码生成的基础。您可以使用这种方法为任何您想要实现编译器的编程语言。

在本章中，您将学习以下内容：

定义一个真实的编程语言，您将了解tinylang语言，这是真实编程语言的一个子集，您将为其实现编译器前端组织编译器项目的目录结构了解如何处理编译器的多个输入文件处理用户消息并以愉快的方式通知他们问题的技巧使用模块化组件构建词法分析器从语法规则派生出递归下降解析器以执行语法分析通过创建AST并分析其特性来执行语义分析通过本章获得的技能，您将能够为任何编程语言构建编译器前端。

定义一个真实的编程语言 真实的编程语言比上一章中的简单calc语言带来了更多的挑战。为了详细了解，我们将在本章及后续章节中使用Modula-2的一个微小子集。Modula-2设计精良，可选支持泛型和面向对象编程（OOP）。然而，我们不会在本书中创建一个完整的Modula-2编译器。因此，我们将这个子集称为tinylang。

让我们从一个tinylang程序的例子开始。以下函数使用欧几里得算法计算最大公约数：

MODULE Gcd;PROCEDURE GCD(a, b: INTEGER) : INTEGER;VAR t: INTEGER;BEGIN  IF b = 0 THEN    RETURN a;  END;  WHILE b # 0 DO    t := a MOD b;    a := b;    b := t;  END;  RETURN a;END GCD;END Gcd.

现在我们已经对语言中的程序外观有了感觉，让我们快速浏览一下本章中使用的tinylang子集的语法。在接下来的几节中，我们将使用这个语法从中派生出词法分析器和解析器：

compilationUnit  : "MODULE" identifier ";" ( import )* block identifier "." ;Import : ( "FROM" identifier )? "IMPORT" identList ";" ;Block  : ( declaration )* ( "BEGIN" statementSequence )? "END" ;

在Modula-2中，编译单元以MODULE关键字开始，后跟模块的名称。模块的内容可以有导入模块的列表、声明和一个在初始化时运行的语句块：

declaration  : "CONST" ( constantDeclaration ";" )*  | "VAR" ( variableDeclaration ";" )*  | procedureDeclaration ";" ;

声明引入了常量、变量和过程。常量的声明以前缀CONST关键字开始。类似地，变量声明以VAR关键字开始。常量的声明非常简单：

constantDeclaration : identifier "=" expression ;

标识符是常量的名称。值来源于一个表达式，该表达式必须在编译时可计算。变量的声明稍微复杂一些：

variableDeclaration : identList ":" qualident ;qualident : identifier ( "." identifier )* ;identList : identifier ( "," identifier)* ;

为了能够一次性声明多个变量，使用了一个标识符列表。类型名称可能来自另一个模块，在这种情况下，它以前一个模块的名称为前缀。这称为限定标识符。过程需要最详细的信息：

procedureDeclaration  : "PROCEDURE" identifier ( formalParameters )? ";"    block identifier ;formalParameters  : "(" ( formalParameterList )? ")" ( ":" qualident )? ;formalParameterList  : formalParameter (";" formalParameter )* ;formalParameter : ( "VAR" )? identList ":" qualident ;

上述代码展示了如何声明常量、变量和过程。过程可以有参数和返回类型。普通参数按值传递，VAR参数按引用传递。缺少的块规则的另一部分是statementSequence，它是单个语句的列表：

statementSequence  : statement ( ";" statement )* ;

如果一个语句后面跟着另一个语句，则由分号分隔。再次，只支持Modula-2语句的一个子集：

statement  : qualident ( ":=" expression | ( "(" ( expList )? ")" )? )  | ifStatement | whileStatement | "RETURN" ( expression )? ;

这个规则的第一部分描述了赋值或过程调用。后面跟着:=的限定标识符是赋值。如果它后面跟着(，那么它就是过程调用。其他语句是常见的控制语句：

ifStatement  : "IF" expression "THEN" statementSequence    ( "ELSE" statementSequence )? "END" ;

IF语句的语法也简化了，因为它只能有一个ELSE块。有了那个语句，我们可以有条件地保护一个语句：

whileStatement  : "WHILE" expression "DO" statementSequence "END" ;

WHILE语句描述了一个由条件保护的循环。与IF语句一起，这使我们能够用tinylang编写简单的算法。最后，缺少表达式的定义：

expList  : expression ( "," expression )* ;expression  : simpleExpression ( relation simpleExpression )? ;relation  : "=" | "#" | "<" | "<=" | ">" | ">=" ;simpleExpression  : ( "+" | "-" )? term ( addOperator term )* ;addOperator  : "+" | "-" | "OR" ;term  : factor ( mulOperator factor )* ;mulOperator  : "*" | "/" | "DIV" | "MOD" | "AND" ;factor  : integer_literal | "(" expression ")" | "NOT" factor  | qualident ( "(" ( expList )? ")" )? ;

表达式语法与上一章中的calc非常相似。只支持INTEGER和BOOLEAN数据类型。

此外，还使用了标识符和integer_literal令牌。标识符是以字母或下划线开头的名称，后跟字母、数字和下划线。整数字面量是一系列十进制数字或一系列十六进制数字，后跟字母H。

这些已经是很多规则了，我们只涵盖了Modula-2的一部分！尽管如此，仍然可以在该子集中编写小型应用程序。让我们实现tinylang的编译器！

创建项目布局 tinylang的项目布局遵循我们在第1章“安装LLVM”中提出的方法。每个组件的源代码位于lib目录的子目录中，头文件位于include/tinylang的子目录中。子目录以组件命名。在第1章“安装LLVM”中，我们只创建了Basic组件。

从上一章中，我们知道我们需要实现一个词法分析器、一个解析器、一个AST和一个语义分析器。每个都是自己的组件，分别称为Lexer、Parser、AST和Sema。本章将使用的目录布局如下所示：

图3.1 - tinylang项目的目录布局 图3.1 - tinylang项目的目录布局

组件具有明确定义的依赖关系。Lexer仅依赖于Basic。Parser依赖于Basic、Lexer、AST和Sema。Sema仅依赖于Basic和AST。明确定义的依赖关系有助于我们重用组件。

让我们更仔细地看看实现！

管理编译器的输入文件 一个真正的编译器需要处理许多文件。通常，开发者通过调用编译器并指定主编译单元的名称来调用编译器。这个编译单元可以通过例如C中的#include指令，Python或Modula-2中的import语句来引用其他文件。导入的模块可以导入其他模块，以此类推。所有这些文件都必须加载到内存中，并通过编译器的分析阶段。在开发过程中，开发者可能会犯语法或语义错误。当检测到这些错误时，应打印包括源代码行和标记的错误消息。这个基本组件并不简单。

幸运的是，LLVM提供了一个解决方案：llvm::SourceMgr类。通过调用AddNewSourceBuffer()方法将新源文件添加到SourceMgr。或者，可以通过调用AddIncludeFile()方法加载文件。两种方法都返回一个用于标识缓冲区的ID。您可以使用此ID检索相关文件的内存缓冲区的指针。要定义文件中的位置，可以使用llvm::SMLoc类。这个类封装了指向缓冲区的指针。各种PrintMessage()方法允许您向用户发出错误和其他信息消息。

为用户处理消息 缺少的只是一个集中定义消息的方法。在大型软件（如编译器）中，您不希望将消息字符串散布在各处。如果需要更改消息或将其翻译成另一种语言，那么您最好将它们放在一个集中的地方！

一个简单的方法是，每条消息都有一个ID（枚举成员）、一个严重性级别，如Error或Warning，以及一个包含消息的字符串。在您的代码中，您只引用消息ID。严重性级别和消息字符串仅在打印消息时使用。这三个项目（ID、安全级别和消息）必须一致管理。LLVM库使用预处理器来解决这个问题。数据存储在带有.def后缀的文件中，并包装在宏名称中。该文件通常被包含多次，每次对宏的定义都不同。定义位于include/tinylang/Basic/Diagnostic.def文件路径中，如下所示：

#ifndef DIAG#define DIAG(ID, Level, Msg)#endifDIAG(err_sym_declared, Error, "symbol {0} already declared")#undef DIAG

第一个宏参数ID是枚举标签，第二个参数Level是严重性，第三个参数Msg是消息文本。有了这个定义，我们可以定义一个DiagnosticsEngine类来发出错误消息。接口位于include/tinylang/Basic/Diagnostic.h文件中：

#ifndef TINYLANG_BASIC_DIAGNOSTIC_H#define TINYLANG_BASIC_DIAGNOSTIC_H#include "tinylang/Basic/LLVM.h"#include "llvm/ADT/StringRef.h"#include "llvm/Support/FormatVariadic.h"#include "llvm/Support/SMLoc.h"#include "llvm/Support/SourceMgr.h"#include "llvm/Support/raw_ostream.h"#include <utility>namespace tinylang {

在包含必要的头文件后，可以使用Diagnostic.def来定义枚举。为了避免污染全局命名空间，使用了一个名为diag的嵌套命名空间：

namespace diag {enum {#define DIAG(ID, Level, Msg) ID,#include "tinylang/Basic/Diagnostic.def"};} // namespace diag

DiagnosticsEngine类使用SourceMgr实例通过report()方法发出消息。消息可以有参数。为了实现这个功能，使用了LLVM提供的可变格式支持。通过静态方法检索消息文本和严重性级别。作为奖励，发出的错误消息数量也被计数：

class DiagnosticsEngine {  static const char *getDiagnosticText(unsigned DiagID);  static SourceMgr::DiagKind  getDiagnosticKind(unsigned DiagID);  SourceMgr &SrcMgr;  unsigned NumErrors;public:  DiagnosticsEngine(SourceMgr &SrcMgr)      : SrcMgr(SrcMgr), NumErrors(0) {}  unsigned nunErrors() { return NumErrors; }  template <typename... Args>  void report(SMLoc Loc, unsigned DiagID,              Args &&... Arguments) {    std::string Msg =        llvm::formatv(getDiagnosticText(DiagID),                      std::forward<Args>(Arguments)...)            .str();    SourceMgr::DiagKind Kind = getDiagnosticKind(DiagID);    SrcMgr.PrintMessage(Loc, Kind, Msg);    NumErrors += (Kind == SourceMgr::DK_Error);  }};} // namespace tinylang#endif

通过这个实现，我们已经实现了类的大部分。只剩下getDiagnosticText()和getDiagnosticKind()缺失。它们在lib/Basic/Diagnostic.cpp文件中定义，也使用Diagnostic.def文件：

#include "tinylang/Basic/Diagnostic.h"using namespace tinylang;namespace {const char *DiagnosticText[] = {#define DIAG(ID, Level, Msg) Msg,#include "tinylang/Basic/Diagnostic.def"};As in the header file, the DIAG macro is defined to retrieve the desired part. Here, we define an array that holds the text messages. Therefore, the DIAG macro only returns the Msg part. We use the same approach for the level:SourceMgr::DiagKind DiagnosticKind[] = {#define DIAG(ID, Level, Msg) SourceMgr::DK_##Level,include "tinylang/Basic/Diagnostic.def"};} // namespaceNot surprisingly, both functions simply index the array to return the desired data:const char *DiagnosticsEngine::getDiagnosticText(unsigned DiagID) {  return DiagnosticText[DiagID];}SourceMgr::DiagKindDiagnosticsEngine::getDiagnosticKind(unsigned DiagID) {  return DiagnosticKind[DiagID];}

SourceMgr和DiagnosticsEngine类的组合为其他组件提供了一个很好的基础。我们首先将在词法分析器中使用它们！

构建词法分析器 正如我们从上一章中了解到的，我们需要一个Token类和一个Lexer类。此外，还需要一个TokenKind枚举，为每个标记类提供一个唯一的数字。将所有内容放在一个头文件和实现文件中并不可扩展，所以让我们将这些项移动。TokenKind可以普遍使用，并放置在Basic组件中。Token和Lexer类属于Lexer组件，但放置在不同的头文件和实现文件中。

有三种不同类型的标记：关键字、标点符号和代表许多值的标记。例如，CONST关键字、;分隔符和ident标记，每个都代表源代码中的标识符。每个标记都需要一个枚举成员名称。关键字和标点符号有自然显示名称，可以用于消息。

就像许多编程语言一样，关键字是标识符的一个子集。为了将标记分类为关键字，我们需要一个关键字过滤器，该过滤器检查找到的标识符是否确实是关键字。这与C或C++中的行为相同，其中关键字也是标识符的一个子集。编程语言的发展可能会引入新的关键字。例如，原始的K&R C语言没有使用enum关键字定义枚举。因此，应该有一个标志指示关键字的语言级别。

我们收集了几件信息，所有这些都属于TokenKind枚举的成员：枚举成员的标签、标点符号的拼写以及关键字的标志。为了诊断消息，我们在名为include/tinylang/Basic/TokenKinds.def的.def文件中集中存储信息，如下所示。需要注意的一点是，关键字以kw_为前缀：

#ifndef TOK#define TOK(ID)#endif#ifndef PUNCTUATOR#define PUNCTUATOR(ID, SP) TOK(ID)#endif#ifndef KEYWORD#define KEYWORD(ID, FLAG) TOK(kw_ ## ID)#endifTOK(unknown)TOK(eof)TOK(identifier)TOK(integer_literal)PUNCTUATOR(plus, "+")PUNCTUATOR(minus, "-")// ...KEYWORD(BEGIN, KEYALL)KEYWORD(CONST, KEYALL)// ...#undef KEYWORD#undef PUNCTUATOR#undef TOK

有了这些集中定义，很容易在include/tinylang/Basic/TokenKinds.h文件中创建TokenKind枚举。同样，枚举被放入自己的命名空间tok中：

#ifndef TINYLANG_BASIC_TOKENKINDS_H#define TINYLANG_BASIC_TOKENKINDS_Hnamespace tinylang {  namespace tok {    enum TokenKind : unsigned short {#define TOK(ID) ID,#include "TokenKinds.def"      NUM_TOKENS    };    const char *getTokenName(TokenKind Kind);    const char *getPunctuatorSpelling(TokenKind Kind);    const char *getKeywordSpelling(TokenKind Kind);  }}#endif

实现文件lib/Basic/TokenKinds.cpp也使用.def文件检索名称：

#include "tinylang/Basic/TokenKinds.h"#include "llvm/Support/ErrorHandling.h"using namespace tinylang;static const char * const TokNames[] = {#define TOK(ID) #ID,#define KEYWORD(ID, FLAG) #ID,#include "tinylang/Basic/TokenKinds.def"  nullptr};

标记的文本名称从其枚举标签ID派生。有两个特点：

首先，我们需要定义TOK和KEYWORD宏，因为KEYWORD的默认定义不使用TOK宏 其次，在数组的末尾添加了一个nullptr值，以适应添加的NUM_TOKENS枚举成员：

const char *tok::getTokenName(TokenKind Kind) {  return TokNames[Kind];}

我们采用略有不同的方法在getPunctuatorSpelling()和getKeywordSpelling()函数中。这些函数仅在枚举的子集中返回有意义的值。可以通过使用switch语句实现，默认情况下返回一个空指针值：

const char *tok::getPunctuatorSpelling(TokenKind Kind) {  switch (Kind) {#define PUNCTUATOR(ID, SP) case ID: return SP;#include "tinylang/Basic/TokenKinds.def"    default: break;  }  return nullptr;}const char *tok::getKeywordSpelling(TokenKind Kind) {  switch (Kind) {#define KEYWORD(ID, FLAG) case kw_ ## ID: return #ID;#include "tinylang/Basic/TokenKinds.def"    default: break;  }  return nullptr;}

提示

注意宏是如何定义的，以便从文件中检索必要的信息片段。

在上一章中，Token类在Lexer类的同一头文件中声明。为了使其更加通用，我们将把Token类放入其自己的头文件include/Lexer/Token.h中。与之前一样，Token存储指向标记开头的指针、其长度以及之前定义的标记类型：

class Token {  friend class Lexer;  const char *Ptr;  size_t Length;  tok::TokenKind Kind;public:  tok::TokenKind getKind() const { return Kind; }  size_t getLength() const { return Length; }  // SMLoc实例，用于在消息中表示标记的源位置，是从指向标记的指针创建的  SMLoc getLocation() const {    return SMLoc::getFromPointer(Ptr);  }  // getIdentifier()和getLiteralData()方法允许访问标记的文本，对于标识符和字面量数据  // 对于任何其他标记类型，访问文本并不是必要的，因为这是由标记类型暗示的  StringRef getIdentifier() {    assert(is(tok::identifier) &&           "Cannot get identifier of non-identifier");    return StringRef(Ptr, Length);  }  StringRef getLiteralData() {    assert(isOneOf(tok::integer_literal,                    tok::string_literal) &&           "Cannot get literal data of non-literal");    return StringRef(Ptr, Length);  }};

我们在include/Lexer/Lexer.h头文件中声明Lexer类，并将实现放在lib/Lexer/lexer.cpp文件中。结构与上一章中的calc语言相同。我们需要更仔细地查看两个细节：

首先，一些操作符共享相同的前缀——例如，<和<=。当当前字符我们查看的是<，那么我们必须在决定我们找到了哪个标记之前检查下一个字符。记住，输入需要以空字节结束。因此，如果当前字符有效，总是可以使用下一个字符：

case '<':  if (*(CurPtr + 1) == '=')    formTokenWithChars(token, CurPtr + 2,                        tok::lessequal);  else    formTokenWithChars(token, CurPtr + 1, tok::less);  break;

另一个细节是现在有更多的关键字。我们如何处理这个？一个简单且快速的解决方案是在关键字的哈希表中填充，这些关键字都存储在TokenKinds.def文件中。这可以在Lexer类的实例化期间完成。通过这种方法，也可以支持语言的不同级别，因为可以通过附加的标志过滤关键字。在这里，这种灵活性还不是必需的。在头文件中，关键字过滤器定义如下，使用llvm::StringMap实例作为哈希表：

class KeywordFilter {  llvm::StringMap<tok::TokenKind> HashTable;  void addKeyword(StringRef Keyword,                  tok::TokenKind TokenCode);public:  void addKeywords();  tok::TokenKind getKeyword(    StringRef Name,    tok::TokenKind DefaultTokenCode = tok::unknown) {    auto Result = HashTable.find(Name);    if (Result != HashTable.end())      return Result->second;    return DefaultTokenCode;  }};

在实现文件中，填充了关键字表：

void KeywordFilter::addKeyword(StringRef Keyword,                               tok::TokenKind TokenCode) {  HashTable.insert(std::make_pair(Keyword, TokenCode));}void KeywordFilter::addKeywords() {#define KEYWORD(NAME, FLAGS)  addKeyword(StringRef(#NAME), tok::kw_##NAME);#include "tinylang/Basic/TokenKinds.def"}

使用您刚刚了解到的技术，编写一个高效的词法分析器类并不困难。由于编译速度很重要，许多编译器使用手写的词法分析器，clang就是一个例子。

构建递归下降解析器 如上一章所示，解析器是从语法派生出来的。让我们回顾一下所有的构造规则。对于语法中的每一条规则，你都会创建一个以规则左侧非终结符命名的方法，以解析规则右侧的内容。遵循右侧的定义，你将执行以下操作：

对于每个非终结符，调用相应的方法 消耗每个标记 对于备选方案和可选或重复的组，检查前瞻标记（下一个未消耗的标记）以决定继续的位置 让我们将这些构造规则应用于以下语法规则：

ifStatement  : "IF" expression "THEN" statementSequence    ( "ELSE" statementSequence )? "END" ;

我们可以很容易地将其翻译成以下C++方法：

void Parser::parseIfStatement() {  consume(tok::kw_IF);  parseExpression();  consume(tok::kw_THEN);  parseStatementSequence();  if (Tok.is(tok::kw_ELSE)) {    advance();    parseStatementSequence();  }  consume(tok::kw_END);}

tinylang的整个语法都可以以这种方式转换成C++。一般来说，你必须小心避免一些陷阱，因为你在网上找到的大多数语法都不适合这种构造方式。

语法和解析器

有两种不同类型的解析器：自顶向下解析器和自底向上解析器。它们的名字来源于解析过程中规则处理的顺序。解析器的输入是由词法分析器生成的标记序列。

自顶向下解析器会扩展规则中左边最深（最左边）的符号，直到匹配到一个标记。如果所有标记都被消耗，并且所有符号都被扩展，那么解析就成功了。这正是tinylang解析器的工作方式。

自底向上解析器则相反：它查看标记序列，并尝试用语法中的符号替换这些标记。例如，如果下一个标记是IF、3、+和4，那么自底向上解析器将3 + 4标记替换为表达式符号，从而形成IF表达式序列。当看到所有属于IF语句的标记时，那么这个标记和符号序列就被替换为ifStatement符号。

如果所有标记都被消耗，并且只剩下起始符号，那么解析就成功了。虽然自顶向下解析器可以很容易地手工构建，但自底向上解析器则不是这样。

通过首先扩展哪些符号，可以以不同的方式对这两种类型的解析器进行特征化。两者都从左到右读取输入，但自顶向下解析器首先扩展最左边的符号，而自底向上解析器扩展最右边的符号。因此，自顶向下解析器也被称为LL解析器，而自底向上解析器被称为LR解析器。

为了从语法中派生出LL或LR解析器，语法必须具有某些属性。语法相应地被命名：你需要一个LL语法来构建LL解析器。

你可以在关于编译器构建的大学教科书中找到更多细节，例如Wilhelm、Seidl和Hack的《编译器设计。语法和语义分析》，Springer 2013年，以及Grune和Jacobs的《解析技术，实用指南》，Springer 2008年。

要寻找的一个问题是左递归规则。如果规则的右侧以与左侧相同的终结符开始，则称该规则为左递归。在表达式的语法中可以找到一个典型的例子：

expression : expression "+" term ;

如果从语法中还不清楚，那么将其翻译成C++就很明显了，这将导致无限递归：

Void Parser::parseExpression() {  parseExpression();  consume(tok::plus);  parseTerm();}

左递归也可以间接发生并涉及更多规则，这更加难以发现。这就是为什么存在一种算法可以检测并消除左递归。

注意

左递归规则仅对LL解析器（如tinylang的递归下降解析器）存在问题。原因是这些解析器首先扩展最左边的符号。相比之下，如果你使用解析器生成器生成一个首先扩展最右边符号的LR解析器，那么你应该避免使用右递归规则。

在每一步，解析器都只使用前瞻标记来决定如何继续。如果这个决定不能确定性地做出，那么语法就被称为有冲突。为了说明这一点，让我们看看C#中的using语句。就像在C++中一样，using语句可以用来在命名空间中使一个符号可见，例如using Math;。也可以为导入的符号定义一个别名名称，使用using M = Math;。在语法中，这可以这样表示：

usingStmt : "using" (ident "=")? ident ";" 

这里有一个问题：在解析器消耗了using关键字之后，前瞻标记是ident。然而，这些信息不足以让我们决定是否需要跳过或解析可选组。如果可选组可以开始的标记集与可选组之后的标记集重叠，这种情况总是会出现的。

让我们用一个备选方案而不是一个可选组重写规则：

usingStmt : "using" ( ident "=" ident | ident ) ";" ;

现在，有一个不同的冲突：两个备选方案都以相同的标记开始。仅查看前瞻标记，解析器无法决定哪个备选方案是正确的。

这些冲突非常常见。因此，知道如何处理它们是很好的。一种方法是重写语法，使冲突消失。在前面的示例中，两个备选方案都以相同的标记开始。这可以被分解出来，得到以下规则：

usingStmt : "using" ident ("=" ident)? ";" ;

这种表述没有冲突，但还应该注意到它表达性较差。在另外两种表述中，哪个ident是别名名称，哪个ident是命名空间名称是显而易见的。在无冲突规则中，最左边的ident改变了它的角色。首先，它是命名空间名称，但如果跟随一个等号，那么它就变成了别名名称。

第二种方法是添加一个谓词来区分这两种情况。这个谓词，通常称为解析器，可以使用上下文信息进行决策（例如符号表中的名称查找），或者它可以查看一个以上的标记。让我们假设词法分析器有一个名为Token &peek(int n)的方法，它返回当前前瞻标记之后的第n个标记。在这里，等号的存在可以用作决策中的额外谓词：

if (Tok.is(tok::ident) && Lex.peek(0).is(tok::equal)) {  advance();  consume(tok::equal);}consume(tok::ident);

第三种方法是使用回溯。为此，你需要保存当前状态。然后，你必须尝试解析冲突组。如果这不成功，那么你需要回到保存的状态并尝试另一条路径。在这里，你正在寻找要应用的正确规则，这不像其他方法那样高效。因此，你应该只在系统化的方法中，你可以定义一个明确的标记集，这些标记指示错误恢复应该停止并尝试继续解析的位置。例如，在C语言风格的语法中，分号通常用作语句的终止符。因此，当你遇到语法错误时，你可以跳过所有标记，直到你遇到一个分号，然后假设分号之前的内容是完整的语句，并继续解析下一个语句。

在实现解析器时，你需要跟踪当前的解析状态，这样当发生错误时，你可以回退到错误发生之前的状态。这通常涉及到保存解析器的状态，包括当前的输入位置、已经消耗的标记和任何中间解析结果。然后，如果解析尝试失败，你可以恢复到这个状态并尝试不同的解析路径。

此外，错误恢复策略可以更加复杂和精细，例如：

错误报告：在检测到错误时，解析器可以生成错误消息，告知开发者或用户错误的类型和位置。这有助于快速定位和修复问题。错误提示：解析器可以提供关于如何修复错误的建议，例如建议缺少的标记或提示可能的语法结构。错误容忍：某些解析器设计为在遇到错误时继续尽可能地解析输入，而不是立即停止。这在处理大型文件或不完整的输入时非常有用。结构化错误恢复：在某些情况下，解析器可以利用语法的结构来更智能地恢复，例如，如果知道某些语句必须以特定的方式结束，解析器可以在检测到这些结构的结束时恢复。使用语法预测：解析器可以使用语法预测来决定在冲突情况下采用哪个规则。这通常涉及到分析语法并生成一个预测分析表，解析器使用这个表来决定在给定前瞻标记的情况下应该采取哪个规则。集成开发环境（IDE）支持：在IDE中，解析器的错误恢复功能可以与代码高亮、自动完成和其他编辑功能集成，以提供更流畅的用户体验。

在设计解析器时，考虑错误恢复策略是至关重要的，因为它直接影响到开发者和用户处理语法错误的能力。一个良好设计的错误恢复机制可以显著提高编程语言的可用性和调试效率。

最后，值得注意的是，错误恢复策略的选择和实现取决于具体的应用场景和要求。在某些情况下，可能需要一个健壮且复杂的错误恢复机制，而在其他情况下，一个简单且快速的机制可能更为合适。

对于每个非终结符，你需要计算可以跟随该非终结符的标记集合（称为FOLLOW集）。对于非终结符statement，可以跟随的标记有;、ELSE和END。因此，你必须在parseStatement()的错误恢复部分使用这个集合。这种方法假设语法错误可以局部处理。通常情况下，这是不可能的。因为解析器会跳过标记，可能会跳过很多，以至于到达输入的末尾。在这一点上，局部恢复是不可能的。

为了防止无意义的错误消息，调用方法需要被告知错误恢复尚未完成。这可以通过布尔值（bool）来完成。如果它返回true，这意味着错误恢复还没有完成，而false则意味着解析（包括可能的错误恢复）成功。

有许多方法可以扩展这个错误恢复方案。使用活跃调用者的FOLLOW集是一个流行的方法。以一个简单的例子为例，假设parseStatement()由parseStatementSequence()调用，而parseStatementSequence()本身由parseBlock()调用，并且从parseModule()开始。

在这里，每个相应的非终结符都有一个FOLLOW集。如果解析器在parseStatement()中检测到语法错误，那么将跳过标记，直到标记至少在活动调用者的FOLLOW集中的一个中。如果标记在statement的FOLLOW集中，则错误已在本地恢复，并向调用者返回false值。否则，返回true值，意味着必须继续错误恢复。实现此扩展的可能策略是传递std::bitset或std::tuple以表示当前FOLLOW集的并集给被调用者。

最后一个问题仍然悬而未决：我们如何调用错误恢复？在上一章中，使用了goto语句跳转到错误恢复块。这可行，但不是令人满意的解决方案。考虑到我们之前讨论的内容，我们可以在单独的方法中跳过标记。Clang有一个名为hasSkipUntil()的方法用于此目的；我们也为tinylang使用这个方法。

因为下一步是向解析器添加语义动作，所以拥有一个中心位置放置清理代码（如果必要的话）也是很好的。嵌套函数将非常适合于此。C++没有嵌套函数。相反，Lambda函数可以提供类似的目的。我们最初看到的parseIfStatement()方法，在添加了完整的错误恢复代码后，看起来如下：

bool Parser::parseIfStatement() {  auto _errorhandler = [this] {    return skipUntil(tok::semi, tok::kw_ELSE, tok::kw_END);  };  if (consume(tok::kw_IF))    return _errorhandler();  if (parseExpression(E))    return _errorhandler();  if (consume(tok::kw_THEN))    return _errorhandler();  if (parseStatementSequence(IfStmts))    return _errorhandler();  if (Tok.is(tok::kw_ELSE)) {    advance();    if (parseStatementSequence(ElseStmts))      return _errorhandler();  }  if (expect(tok::kw_END))    return _errorhandler();  return false;}

解析器和词法分析器生成器

手动构建解析器和词法分析器可能是一个繁琐的任务，特别是如果你尝试发明一种新的编程语言并且经常更改语法。幸运的是，一些工具可以自动化这项任务。

经典的Linux工具是flex（）和bison（）。flex从一组正则表达式生成词法分析器，而bison从语法描述生成LALR(1)解析器。这两个工具都生成C/C++源代码，并且可以一起使用。

另一个流行的工具是ANTLR（）。ANTLR可以从语法描述生成词法分析器、解析器和AST。生成的解析器属于LL(*)类，这意味着它是一个自顶向下的解析器，使用可变数量的前瞻来解决冲突。该工具是用Java编写的，但可以为许多流行语言生成源代码，包括C/C++。

所有这些工具都需要一些库支持。如果你正在寻找一个可以生成自包含词法分析器和解析器的工具，那么Coco/R（）可能是你需要的工具。Coco/R从LL(1)语法描述生成词法分析器和递归下降解析器，类似于本书中使用的那种。生成的文件基于一个模板文件，如果需要，你可以更改它。该工具是用C#编写的，但已经移植到C++、Java和其他语言。

有许多其他可用的工具，它们在支持的功能和输出语言方面差异很大。当然，在选择工具时，还需要考虑权衡。像bison这样的LALR(1)解析器生成器可以消耗广泛的语法，你在互联网上找到的自由语法通常是LALR(1)语法。

作为一个缺点，这些生成器生成的状态机需要在运行时进行解释，这可能比递归下降解析器慢。错误处理也更加复杂。bison对处理语法错误有基本支持，但正确使用需要深入理解解析器的工作原理。与此相比，ANTLR消耗的语法类略小，但可以自动生成错误处理，并且还可以生成AST。因此，重写语法以便与ANTLR一起使用可能会加快以后的开发速度。

执行语义分析

我们在上一节构建的解析器只检查输入的语法。下一步是添加执行语义分析的能力。在上一章的calc示例中，解析器构建了一个AST。在单独的阶段，语义分析器在这颗树上工作。这种方法总是可以使用的。在本节中，我们将使用一种略有不同的方法，并将解析器和语义分析器更紧密地交织在一起。

语义分析器需要做什么？让我们来看看：

对于每个声明，必须检查变量、对象等的名称，以确保它们没有在其他地方声明过。 对于表达式或语句中名称的每个出现，必须检查该名称已声明，并且所需的使用符合声明。 对于每个表达式，必须计算结果类型。还需要计算表达式是否为常量，如果是，它的值是什么。 对于赋值和参数传递，我们必须检查类型是否兼容。此外，我们必须检查IF和WHILE语句中的条件是否为布尔类型。

对于这样一个小的编程语言子集，已经有很多需要检查的内容了！

处理名称的作用域

首先，让我们看看名称的作用域。名称的作用域是名称可见的范围。像C语言一样，tinylang使用“先声明后使用”的模型。例如，变量B和X在模块级别声明为INTEGER类型：

VAR B, X: INTEGER;

在声明之前，这些变量是未知的，不能被使用。只有在声明之后才可能使用。在过程内部，可以声明更多的变量：

PROCEDURE Proc;VAR B: BOOLEAN;BEGIN  (* Statements *)END Proc;

在过程内部，在注释的位置，使用B指的是局部变量B，而使用X指的是全局变量X。局部变量B的作用域是Proc。如果在当前作用域中找不到名称，则在包含作用域或父作用域中继续搜索。因此，可以在过程内部使用变量X。在tinylang中，只有模块和过程会开启新的作用域。其他语言结构，如结构体和类，通常也会开启一个作用域。预定义的实体，如INTEGER类型和TRUE字面量，是在全局作用域中声明的，它包围了模块的作用域。

在tinylang中，只有名称是至关重要的。因此，作用域可以作为名称到其声明的映射来实现。如果名称尚未出现，只能插入新名称。对于查找，还必须知道包含或父作用域。接口（在include/tinylang/Sema/Scope.h文件中）如下所示：

#ifndef TINYLANG_SEMA_SCOPE_H#define TINYLANG_SEMA_SCOPE_H#include "tinylang/Basic/LLVM.h"#include "llvm/ADT/StringMap.h"#include "llvm/ADT/StringRef.h"namespace tinylang {class Decl;class Scope {  Scope *Parent;  StringMap<Decl *> Symbols;public:  Scope(Scope *Parent = nullptr) : Parent(Parent) {}  bool insert(Decl *Declaration);  Decl *lookup(StringRef Name);  Scope *getParent() { return Parent; }};} // namespace tinylang#endif

在lib/Sema/Scope.cpp文件中的实现如下：

#include "tinylang/Sema/Scope.h"#include "tinylang/AST/AST.h"using namespace tinylang;bool Scope::insert(Decl *Declaration) {  return Symbols      .insert(std::pair<StringRef, Decl *>(          Declaration->getName(), Declaration))      .second;}

请注意，StringMap::insert()方法不会覆盖现有条目。生成的std::pair的第二个成员指示表是否已更新。此信息返回给调用者。

为了实现对符号声明的搜索，lookup()方法在当前作用域中搜索，如果没有找到，则搜索由父成员链接的作用域：

Decl *Scope::lookup(StringRef Name) {  Scope *S = this;  while (S) {    StringMap<Decl *>::const_iterator I =        S->Symbols.find(Name);    if (I != S->Symbols.end())      return I->second;    S = S->getParent();  }  return nullptr;}

然后，变量声明被处理如下：

当前作用域是模块作用域。 查找INTEGER类型声明。如果没有找到声明，或者它不是一个类型声明，那么这是一个错误。 实例化一个名为VariableDeclaration的新AST节点，其重要属性是名称B和类型。 将名称B插入当前作用域，映射到声明实例。如果作用域中已经存在该名称，则这是一个错误。在这种情况下，不更改当前作用域的内容。 对X变量也执行相同的操作。 这里执行了两个任务。就像在calc示例中一样，构建了AST节点。同时，计算了节点的属性，如类型。为什么这是可能的？

语义分析器可以依赖两组不同的属性。作用域是从调用者继承的。类型声明可以通过评估类型声明的名称来计算（或合成）。语言的设计方式是这两组属性足以计算AST节点的所有属性。

一个重要的方面是“先声明后使用”的模型。如果一种语言允许在使用前使用名称，例如C++中类的成员，则不可能一次性计算AST节点的所有属性。在这种情况下，必须使用仅部分计算的属性或仅使用纯信息（如在calc示例中）构建AST节点。

然后必须访问AST一次或多次以确定缺失的信息。在tinylang（和Modula-2）的情况下，可以不使用AST构造——AST通过parseXXX()方法的调用层次结构间接表示。从AST生成代码更为常见，因此我们在这里也构建了一个AST。

在我们把各个部分组合在一起之前，我们需要理解LLVM使用运行时类型信息（RTTI）的风格。

使用 LLVM 风格的 RTTI 为 AST

AST（抽象语法树）节点是类层次结构的一部分。声明总是有一个名称。其他属性取决于正在声明的内容。如果声明了一个变量，则需要一个类型。常量声明需要一个类型、一个值等。当然，在运行时，你需要弄清楚你正在处理的是哪种声明。可以使用 C++ 的 dynamic_cast<> 运算符来实现这一点。问题在于，只有当 C++ 类附加了虚函数表（即它使用了虚函数）时，才可用所需的 RTTI。另一个缺点是 C++ RTTI 过于臃肿。为了避免这些缺点，LLVM 开发者引入了一种自制的 RTTI 风格，这种风格在整个 LLVM 库中使用。

我们层次结构的（抽象）基类是 Decl。为了实现 LLVM 风格的 RTTI，必须添加一个包含每个子类标签的公共枚举，并需要一个这种类型的私有成员和一个公共的 getter 函数。这个私有成员通常称为 Kind。在我们的例子中，它看起来像这样：

class Decl {public:  enum DeclKind { DK_Module, DK_Const, DK_Type,                  DK_Var, DK_Param, DK_Proc };private:  const DeclKind Kind;public:  DeclKind getKind() const { return Kind; }};

每个子类现在都需要一个特殊的函数成员，称为 classof。这个函数的目的是确定给定的实例是否是请求的类型。对于 VariableDeclaration，它的实现如下：

static bool classof(const Decl *D) {  return D->getKind() == DK_Var;}

现在，你可以使用特殊的模板 llvm::isa<> 来检查对象是否是请求的类型，使用 llvm::dyn_cast<> 来动态转换对象。存在更多的模板，但这两者是最常用的。有关其他模板的更多信息，请参阅 LLVM Programmer’s Manual。有关 LLVM 风格的更多高级用途，请参阅 HowToSetUpLLVMStyleRTTI。

创建语义分析器

有了这些知识，我们现在可以实施所有部分。首先，我们必须在 include/llvm/tinylang/AST/AST.h 文件中创建存储在 AST 节点中变量的定义。除了支持 LLVM 风格的 RTTI，基类还存储声明的名称、名称的位置和指向封闭声明的指针。后者在嵌套过程的代码生成期间是必需的。Decl 基类声明如下：

class Decl {public:  enum DeclKind { DK_Module, DK_Const, DK_Type,                  DK_Var, DK_Param, DK_Proc };private:  const DeclKind Kind;protected:  Decl *EnclosingDecl;  SMLoc Loc;  StringRef Name;public:  Decl(DeclKind Kind, Decl *EnclosingDecl, SMLoc Loc,       StringRef Name)      : Kind(Kind), EnclosingDecl(EnclosingDecl), Loc(Loc), Name(Name) {}  DeclKind getKind() const { return Kind; }  SMLoc getLocation() { return Loc; }  StringRef getName() { return Name; }  Decl *getEnclosingDecl() { return EnclosingDecl; }};

变量声明的声明只增加了一个指向类型声明的指针：

class TypeDeclaration;class VariableDeclaration : public Decl {  TypeDeclaration *Ty;public:  VariableDeclaration(Decl *EnclosingDecl, SMLoc Loc,                       StringRef Name, TypeDeclaration *Ty)      : Decl(DK_Var, EnclosingDecl, Loc, Name), Ty(Ty) {}  TypeDeclaration *getType() { return Ty; }  static bool classof(const Decl *D) {    return D->getKind() == DK_Var;  }};

解析器中的方法需要用语义动作和收集信息的变量来扩展：

bool Parser::parseVariableDeclaration(DeclList &Decls) {  auto _errorhandler = [this] {    while (!Tok.is(tok::semi)) {      advance();      if (Tok.is(tok::eof)) return true;    }    return false;  };  Decl *D = nullptr; IdentList Ids;  if (parseIdentList(Ids)) return _errorhandler();  if (consume(tok::colon)) return _errorhandler();  if (parseQualident(D)) return _errorhandler();  Actions.actOnVariableDeclaration(Decls, Ids, D);  return false;}

DeclList 是声明的列表，std::vector<Decl*>，IdentList 是位置和标识符的列表，std::vector<std::pair<SMLoc, StringRef>>。

parseQualident() 方法返回一个声明，在这个情况下，预期它是一个类型声明。

解析器类知道语义分析器类的一个实例，Sema，它存储在 Actions 成员中。调用 actOnVariableDeclaration() 运行语义分析器和 AST 构造。实现在 lib/Sema/Sema.cpp 文件中：

void Sema::actOnVariableDeclaration(DeclList &Decls,                                      IdentList &Ids,                                      Decl *D) {  if (TypeDeclaration *Ty = dyn_cast<TypeDeclaration>(D)) {    for (auto &[Loc, Name] : Ids) {      auto *Decl = new VariableDeclaration(CurrentDecl, Loc,                                           Name, Ty);      if (CurrentScope->insert(Decl))        Decls.push_back(Decl);      else        Diags.report(Loc, diag::err_symbold_declared, Name);    }  } else if (!Ids.empty()) {    SMLoc Loc = Ids.front().first;    Diags.report(Loc, diag::err_vardecl_requires_type);  }}

使用 llvm::dyn_cast<TypeDeclaration> 检查类型声明。如果它不是一个类型声明，那么打印错误消息。否则，对于 Ids 列表中的每个名称，实例化 VariableDeclaration 并将其添加到声明列表中。如果因为名称已经被声明而向当前范围添加变量失败，也会打印错误消息。

大多数其他实体的构造方式相同——语义分析的复杂性是唯一的区别。模块和过程需要更多的工作，因为它们开启了一个新的范围。开启一个新的范围很简单：只需要实例化一个新的 Scope 对象。一旦模块或过程被解析，就必须移除范围。

这必须可靠地完成，因为我们不想在语法错误的情况下将名称添加到错误的范围。这是 C++ 中资源获取即初始化（RAII）惯用法的经典应用。另一个复杂性来自于一个过程可以递归调用自身。因此，在使用过程之前，必须将过程的名称添加到当前范围中。语义分析器有两个方法来进入和离开范围。范围与声明相关联：

void Sema::enterScope(Decl *D) {  CurrentScope = new Scope(CurrentScope);  CurrentDecl = D;}void Sema::leaveScope() {  Scope *Parent = CurrentScope->getParent();  delete CurrentScope;  CurrentScope = Parent;  CurrentDecl = CurrentDecl->getEnclosingDecl();}

使用一个简单的辅助类来实现 RAII 惯用法：

class EnterDeclScope {  Sema &Semantics;public:  EnterDeclScope(Sema &Semantics, Decl *D)      : Semantics(Semantics) {    Semantics.enterScope(D);  }  ~EnterDeclScope() { Semantics.leaveScope(); }};

当解析模块或过程时，与语义分析器发生两次交互。第一次是在解析名称之后。在这里，构建了（几乎为空的）AST 节点并建立了一个新的范围：

bool Parser::parseProcedureDeclaration(/* … */) {  /* … */  if (consume(tok::kw_PROCEDURE)) return _errorhandler();  if (expect(tok::identifier)) return _errorhandler();  ProcedureDeclaration *D =      Actions.actOnProcedureDeclaration(          Tok.getLocation(), Tok.getIdentifier());  EnterDeclScope S(Actions, D);  /* … */}

语义分析器在当前范围中检查名称并返回 AST 节点：

ProcedureDeclaration *Sema::actOnProcedureDeclaration(SMLoc Loc, StringRef Name) {  ProcedureDeclaration *P =      new ProcedureDeclaration(CurrentDecl, Loc, Name);  if (!CurrentScope->insert(P))    Diags.report(Loc, diag::err_symbold_declared, Name);  return P;}

真正的工作是在解析了所有的声明和过程体之后完成的。你只需要检查过程声明末尾的名称是否等于过程的名称，以及用于返回类型的声明是否是类型声明：

void Sema::actOnProcedureDeclaration(    ProcedureDeclaration *ProcDecl, SMLoc Loc,    StringRef Name, FormalParamList &Params, Decl *RetType,    DeclList &Decls, StmtList &Stmts) {  if (Name != ProcDecl->getName()) {    Diags.report(Loc, diag::err_proc_identifier_not_equal);    Diags.report(ProcDecl->getLocation(),                 diag::note_proc_identifier_declaration);  }  ProcDecl->setDecls(Decls);  ProcDecl->setStmts(Stmts);  auto *RetTypeDecl =      dyn_cast_or_null<TypeDeclaration>(RetType);  if (!RetTypeDecl && RetType)    Diags.report(Loc, diag::err_returntype_must_be_type,                 Name);  else    ProcDecl->setRetType(RetTypeDecl);}

一些声明是固有存在的，不能由开发人员定义。这包括 BOOLEAN 和 INTEGER 类型以及 TRUE 和 FALSE 字面量。这些声明存在于全局范围中，必须以编程方式添加。Modula-2 还预定义了一些过程，如 INC 或 DEC，这些也可以添加到全局范围中。鉴于我们的类，初始化全局范围很简单：

void Sema::initialize() {  CurrentScope = new Scope();  CurrentDecl = nullptr;  IntegerType =      new TypeDeclaration(CurrentDecl, SMLoc(), "INTEGER");  BooleanType =      new TypeDeclaration(CurrentDecl, SMLoc(), "BOOLEAN");  TrueLiteral = new BooleanLiteral(true, BooleanType);  FalseLiteral = new BooleanLiteral(false, BooleanType);  TrueConst = new ConstantDeclaration(CurrentDecl, SMLoc(),                                      "TRUE", TrueLiteral);  FalseConst = new ConstantDeclaration(      CurrentDecl, SMLoc(), "FALSE", FalseLiteral);  CurrentScope->insert(IntegerType);  CurrentScope->insert(BooleanType);  CurrentScope->insert(TrueConst);  CurrentScope->insert(FalseConst);}

有了这个方案，tinylang 可以做所有必要的计算。例如，让我们看看如何计算一个表达式是否产生一个常量值：

我们必须确保字面量或对常量声明的引用是常量 如果表达式的两边都是常量，那么应用运算符也会产生一个常量 这些规则被嵌入到语义分析器中，同时为表达式创建 AST 节点。同样，类型和常量值也可以被计算。

需要注意的是，并非所有种类的计算都可以以这种方式完成。例如，要检测未初始化变量的使用，可以使用称为符号解释的方法。在其一般形式中，该方法需要通过 AST 进行特殊的遍历顺序，这在构造时是不可能的。好消息是，所提出的方法创建了一个完全装饰的 AST，准备进行代码生成。这个 AST 可以用于进一步的分析，只要可以根据需要打开或关闭昂贵的分析。

要使用前端进行实验，你还需要更新驱动程序。由于缺少代码生成，一个正确的 tinylang 程序不会产生任何输出。尽管如此，它可以用来探索错误恢复并引发语义错误：

#include "tinylang/Basic/Diagnostic.h"#include "tinylang/Basic/Version.h"#include "tinylang/Parser/Parser.h"#include "llvm/Support/InitLLVM.h"#include "llvm/Support/raw_ostream.h"using namespace tinylang;int main(int argc_, const char **argv_) {  llvm::InitLLVM X(argc_, argv_);  llvm::SmallVector<const char *, 256> argv(argv_ + 1,                                            argv_ + argc_);  llvm::outs() << "Tinylang "               << tinylang::getTinylangVersion() << "\n";  for (const char *F : argv) {    llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>>        FileOrErr = llvm::MemoryBuffer::getFile(F);    if (std::error_code BufferError =            FileOrErr.getError()) {      llvm::errs() << "Error reading " << F << ": "                   << BufferError.message() << "\n";      continue;    }    llvm::SourceMgr SrcMgr;    DiagnosticsEngine Diags(SrcMgr);    SrcMgr.AddNewSourceBuffer(std::move(*FileOrErr),                              llvm::SMLoc());    auto TheLexer = Lexer(SrcMgr, Diags);    auto TheSema = Sema(Diags);    auto TheParser = Parser(TheLexer, TheSema);    TheParser.parse();  }}

恭喜！你已经完成了 tinylang 的前端实现！你可以使用在“定义一个真正的编程语言”部分提供的示例程序 Gcd.mod 来运行前端：

$ tinylang Gcd.mod

当然，这是一个有效的程序，看起来什么都没有发生。确保修改文件并引发一些错误消息。我们将在下一章通过添加代码生成继续乐趣。

总结 在本章中，你学习了真实世界编译器在前端使用的技巧。从项目布局开始，你为词法分析器、解析器和语义分析器创建了单独的库。为了向用户输出消息，你扩展了一个现有的 LLVM 类，允许消息集中存储。词法分析器现在被分成了几个接口。

然后，你学习了如何根据语法描述构建递归下降解析器，了解了要避免的陷阱，并学习了如何使用生成器来完成这项工作。你构建的语义分析器在与解析器和 AST 构造交织的同时，执行了语言所需的所有语义检查。

你编码工作的结果是得到了一个完全装饰的 AST。你将在下一章中使用它来生成 IR 代码，最终生成目标代码。