设计有效的Tree-sitter语法

为Tree-sitter编写语法不仅仅是简单地翻译现有的上下文无关语法（CFG）。它需要一种深思熟虑的设计，在表达力、可读性和解析效率之间取得平衡。本文介绍了构建Tree-sitter语法的关键思想和实际示例。

良好的语法结构有助于Tree-sitter生成有用的语法树。理想情况下，树中的每个节点都应该与源语言中可识别的结构紧密对应。这确保了树易于分析和操作。

此外，Tree-sitter在接近LR(1)类的语法中表现最佳。虽然Tree-sitter使用GLR算法并支持通用CFG，但针对LR(1)类规则进行优化可以减少歧义并提高性能。

1、初始化语法规则

一个常见的起点是将语言构造分组为熟悉的类别：声明、定义、语句、表达式、类型和模式。以下是简单Go类语言的示例结构：

rules: {
  source_file: $ => repeat($._definition),
  _definition: $ => choice(
      $.function_definition
    ),
    function_definition: $ => seq(
      'func',
      $.identifier,
      $.parameter_list,
      $._type,
      $.block
    ),
    parameter_list: $ => seq('(', ')'),
    _type: $ => choice('bool'),
    block: $ => seq('{', repeat($._statement), '}'),
    _statement: $ => choice($.return_statement),
    return_statement: $ => seq('return', $._expression, ';'),
    _expression: $ => choice($.identifier, $.number),
    identifier: $ => /[a-z]+/,
    number: $ => /\d+/
  }

rules对象中的第一条规则成为语法的入口点。这个框架提供了清晰的概述，并使逐步扩展特定部分变得更容易。

2、构建子系统

一旦基本布局到位，您就可以添加更多细节。以下是扩展类型系统的示例：

_type: $ => choice(
  $.primitive_type,
  $.array_type,
  $.pointer_type
),
primitive_type: $ => choice('bool', 'int'),
array_type: $ => seq('[', ']', $._type),
pointer_type: $ => seq('*', $._type)

您可以为表达式、语句或任何其他构建类似的子系统。

3、扁平化深层表达式树

语言规范通常使用深度嵌套的规则来描述表达式优先级。例如，x + y可能通过多层表达式类型来表示。与其复制这种深度，您可以定义一个更扁平的结构：

_expression: $ => choice(
  $.identifier,
  $.unary_expression,
  $.binary_expression
),
unary_expression: $ => choice(
  seq('-', $._expression),
  seq('!', $._expression)
),
binary_expression: $ => choice(
  seq($._expression, '+', $._expression),
  seq($._expression, '*', $._expression)
)

然而，这种扁平化引入了歧义。Tree-sitter需要帮助来解决哪些操作绑定更紧密。

4、管理优先级

使用prec函数来指示规则应该绑定的紧密程度：

unary_expression: $ => prec(2, choice(
  seq('-', $._expression),
  seq('!', $._expression)
)),
binary_expression: $ => choice(
  prec.left(2, seq($._expression, '*', $._expression)),
  prec.left(1, seq($._expression, '+', $._expression))
)

prec.left确保左结合性。这让Tree-sitter将a * b * c解释为(a * b) * c。

5、使用冲突处理歧义

某些语言特性本质上是模糊的。例如，在JavaScript中，[x, y]可能是数组或解构模式。Tree-sitter支持多种解释：

conflicts: $ => [
  [$.array, $.array_pattern]
]

显式声明此类冲突允许Tree-sitter在解析期间探索两种解释。

6、隐藏规则

以前缀下划线开头的规则（例如_expression）在生成的语法树中是隐藏的。这些对于本身不代表有意义构建的中间或分组规则很有用。

7、使用字段命名子节点

字段有助于按名称识别语法节点的特定部分：

function_definition: $ => seq(
  'func',
  field('name', $.identifier),
  field('parameters', $.parameter_list),
  field('return_type', $._type),
  field('body', $.block)
)

这允许后续代码按名称检索子节点，而不是依赖于它们的位置。

8、Tree-sitter中的词法分析

解析涉及将源代码分词为有意义的片段。Tree-sitter在解析期间（按需）执行此操作。当多个令牌可能匹配时，它使用几条规则来解决选择哪个令牌的问题：

上下文感知：只考虑当前上下文中有效的令牌。
优先级：优先选择优先级更高的令牌。
长度：较长的匹配优先于较短的匹配。
特异性：字符串优先于正则表达式。
规则顺序：如果其他条件相等，则较早的规则优先。

9、关键字和单词令牌

语言通常同时具有关键字（如return）和通用标识符（如变量名）。为了解决歧义，Tree-sitter允许定义"单词"令牌：

word: $ => $.identifier

这使Tree-sitter能够识别关键字边界，并提高准确性和性能。例如，它确保instanceofSomething不会被误认为是关键字instanceof。

10、结束语

这些语法不仅改进了编辑器功能，如语法高亮和折叠，还实现了强大的静态分析和工具功能。

原文链接: Designing Effective Tree-sitter Grammars

汇智网翻译整理，转载请标明出处