如何使用递归下降解析器解析C++的模板语法？

Question

在出于学习目的编写 C++ 解析器时，我有一个问题。

int a, b;
template <typename T> T Foo() {}
int main() {
    bool x = a < b;
    auto y = Foo<int>();
}

这里，

<

中的

a <

符号是小于运算符。但在

Foo<

中，这意味着模板参数的开始。两者本质上都是标识符，在表达式中后跟

<

符号。递归下降解析器可以处理这种情况吗？或者只有像 LR 解析器这样更强大的解析器才能处理这个问题？

Answer 1

递归下降解析器 比 LR 解析器“更强大”，而不是更弱。 递归下降解析器通常写成 图灵完备 编程语言（例如 C++），而 LR 解析器 只有 的理论幂 下推自动机。 现在，递归下降解析器通常也有一个常规的、自顶向下的 结构类似于

LL 解析器

， 由于 LL 不如 LR 强大，因此怀疑是可以理解的 递归下降也不太强大。但是，因为它可以访问 传统编程语言的所有功能， 递归下降解析器可以使用非常强大的前瞻技术， 仅受可判定性的限制，包括任意回溯（即 本质上使用解析器作为其自己的前瞻机制）。 无论如何，典型的递归下降解析器如何处理 C++ 左尖括号歧义？首先我们要知道我们想要什么 完成，为此，C++17 17.2 ([temp.names]) 第 3 段说：

当一个名称被认为是一个

template-name

，并且后面跟着 a <，

<

始终被视为a的分隔符

template-argument-list

并且永远不要用作小于运算符。 [...]

因此，在表达式上下文中，如果我们看到：

identifier <

然后我们需要查找

identifier

来确定是否应该 “被视为模板名称”（其规则在段落中 2 同一部分，并且有一些微妙之处我将省略），即 主要通过查找中的标识符来确定

符号表

。如果是 发现引用了一个模板，那么我们将 < 视为开始一个 模板参数列表，否则作为小于运算符。该技术的具体示例可以在 Clang 解析器中找到。 在

Parser::ParseUnqualifiedId

,
我们有：

  // unqualified-id:
  //   identifier
  //   template-id (when it hasn't already been annotated)
  if (Tok.is(tok::identifier)) {
  ParseIdentifier:
    // Consume the identifier.
    IdentifierInfo *Id = Tok.getIdentifierInfo();
    SourceLocation IdLoc = ConsumeToken();

    [...]

    // If the next token is a '<', we may have a template.
    TemplateTy Template;
    if (Tok.is(tok::less))
      return ParseUnqualifiedIdTemplateId(
          SS, ObjectType, ObjectHadErrors,
          TemplateKWLoc ? *TemplateKWLoc : SourceLocation(), Id, IdLoc,
          EnteringContext, Result, TemplateSpecified);

然后

ParseUnqualifiedIdTemplateId

包含检查标识符是否为模板的代码：

      TNK = Actions.isTemplateName(getCurScope(), SS,
                                   TemplateKWLoc.isValid(), Id,
                                   ObjectType, EnteringContext, Template,
                                   MemberOfUnknownSpecialization);

并且，如果 

TNK

指示找到模板，则解析该模板的代码 模板参数列表：

  // Parse the enclosed template argument list.
  SourceLocation LAngleLoc, RAngleLoc;
  TemplateArgList TemplateArgs;
  if (ParseTemplateIdAfterTemplateName(true, LAngleLoc, TemplateArgs, RAngleLoc,
                                       Template))
    return true;

同时，我没有显示的周围代码处理以下情况
该名称不被视为模板名称。在这种情况下，它设置

Result

仅为标识符，然后返回

false

。那个（也许 意外地）意味着“成功解析”，并且冒泡到

Parser::tryParseCXXIdExpression

单独处理标识符， 将

<

保留为输入令牌流中的下一个令牌，其中 最终将被视为小于。在其他情况下也必须做出类似的决定，并且 其他需要更多机制来处理的歧义（包括 直角括号歧义，这是它自己的蠕虫罐），但是这个 代码说明了基本思想：当面临困难的选择时， 一项一项地检查可能性，注意隔离任何解析器 由未成功的推测解析引起的状态变化。

但是，在解释了基本思想之后，我应该注意解析 C++ 是

极其

困难，比我所使用的任何其他语言都困难得多 意识到。如果您是一位经验丰富的语言实现者，渴望 “最终boss”挑战将需要数年甚至数十年才能完成， 大胆试试吧。但如果你只是想学习基础知识，我强烈 建议选择不同的语言。