原本以为CodeMirror6只是把5改写成contenteditable,没想到还新增了一个解析器生成工具lezer

lezer的由来可见作者博客上的介绍。 其灵感来自于tree-sitter

System Guide

Overview

Lezer是JS写就的解析器系统。给定一个规范的语法描述,它可以生成一个解析表集合,可以用来对输入的文本生成措辞树。

Lezer生成的措辞树并不是非常抽象的措辞树,没有包含足够的信息。每个节点只包含一个类型,开始和结束位置,一个扁平的下级节点序列。写作语法的时候,可以选择把哪个产生式保存成节点,其他的则会变成不可见。

处于Lezer的使用目的,它生成的信息非常紧实,也不在乎解析是否细致入微。

解析的时候可以增量式,自带错误恢复策略。

实现办法基于tree-sitter,以及Tim Wagner和Susan Graham的增量式解析(12)。

Parser Algorithm

解析基于LR(1965年Donal Knuth发明的)。

解析算法抽象诠释了语法,记录解析器的各种可能的状态。如果一个号牌可以激发多种行动,那么解析就会失败,因为无法知道该采取哪一种行动。为了更加了解LR,可以参考https://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf的第9章。

Ambiguity

Error Recovery

Incremental Parsing

解析的结果可以以树分段的形式缓存起来,并可以注解上当下发生的文档改动。解析过程中,这些信息会被尽可以重用。

Contextual Tokenization

传统意义上,号牌生成器和解析器是分开的。

Lezer支持基于上下文的号牌读取。也就是说,号牌可以重叠,只要它们不出现在语法中相同的位置。

也可以定义外部的号牌划分器。

Writing a Grammar

Building a Grammar

Running the Parser

最简单的方式,是调用生成的解析器的parse方法,可以得到一个Tree例现。

复杂一点的,可以通过startParse方法,创建一个parse对象,用于表示解析的进程。然后重复调用advance方法,知道你觉得解析够了。当没法解析的时候advance会放回Tree。

解析的情境中会带一个Stack例现合集,每个代表单个解析状态。如果解析无歧义,只会有一个stack。当尝试多条解析路径的时候,会有多个例现。一般不需要关系这个,只有外部的号牌划分的时候才需要。

解析消耗的是Input,也就是类似于字符串的数据结构。可以直接传一个字符串给parse,让其自行封装成Input。如果你的数据不太像字符串,那么需要自行封装成Input。

外部号牌划分器可以访问到wrapper,然后调用一个方法来确认一个号牌。

Working with Trees

措辞树采用了特殊设计

  • 包含的节点并不对应于语法中命名的规则,但是使用+*操作符来标注可重复性,这对增量解析尤为有用
  • 包含小结点的分块存储在紧实的16比特数组中,每个节点只录编其类型id,开始位置,结束位置,以及下级节点们的终止位置。

所以提供了SyntaxNode和Treecursor来方便访问这些节点。前者提供对上下级节点的方便访问,后者类似,但更为遍历而设计。

Syntax Nodes

每个节点例现知道自己的类型,所处的位置,上级节点,以及所倚靠的结构,可以用来访问其下级节点。topNode返回树的顶层节点。

可以使用nexSibling或者firstChild等访问器来获取邻近的节点。

resolve方法可以用来获取所辖的,在指定位置之前,之上,之后的节点。

Tree Cursors

SyntaxNode会为每个访问的节点生成一个新的标物,使用过多会造成浪费。游标则无此问题。

游标聚焦在某个节点,可以告知其类型和位置。然后可以朝邻近节点移动。如果移动成功,会改变游标状态;不成功,状态不变。

游标的next和prev方法可以帮助实现前序遍历。

Node Groups

不像其他解析器,Lezer不组织管理一个节点的下属。

为了提供些许帮助,节点可以设置一个分组。

SyntaxNode提供了getChild和getChildren来辅助。获取Expression分组的下属:

let elements = arrayNode.getChildren("Expression")

Reference Manual

分为几个npm料包:

  • @lezer/common: 数据结构相关
  • @lezer/lr:LR解析器的运行时
  • @lezer/highlight:将高亮信息添加到措辞树
  • @lezer/generator:解析器生成工具

@lezer/common module

Trees

  • Tree,一片措辞树,保存为Tree以及TreeBuffer标物,后者储存细节信息,主要是为了节省内存。但是也给使用带来了不方便。所以客户端一般会更偏向于使用TreeCursor或者SyntaxNode。

    • new Tree(…)创建一颗新的Tree
    • 成员
      • type
      • children
      • positions,children的偏移
      • length,这片树的长度
      • cursor(),获取TreeCursor
      • cursorAt()
      • topNode,返回SyntaxNode
      • resolve,返回SyntaxNode
      • resolveInner,返回syntaxNode
      • iterate,遍历这片树上的成员
      • prop 获取节点上的node prop
      • propValues,……
      • balance,再平衡
    • 静态成员
      • empty,空树
      • build,建构一片树
  • SyntaxNodeRef接口,SyntaxNode和TreeCursor所拥有的辖属集合

    • from, to,节点范围
    • type
    • name
    • tree,如果是tree buffer则返回null
    • node,返回SyntaxNode
  • SyntaxNode接口扩展了yntaxNodeRef

    • parent
    • firstChild, lastChild
    • childAfter, ChildBefore
    • enter,进入某个位置上的子节点
    • nextSibling,prevSibling
    • cursor,返回TreeCursor
    • resolve、resolveInner,返回SyntaxNode
    • enterUnfinishedNodesBefore,返回SyntaxNode
    • toTree,返回Tree
    • getChild(),返回给定类型的第一个子节点
    • getChildren()
    • matchContext()
  • TreeCursor标类实现了SyntaxNodeRef,方法主要用于在树中移动

  • NodeWeakMap<T>标类,提供一种方法,将量值关联到树片上

    • set
    • get
    • cursorSet
    • cursorGet
  • NodeType标类,措辞树中的每个节点都关联一个NodeType

  • NodeSet标类,相当于一个索引为16位的数组

  • NodeProp<T>,每个node type或者单独的树都可以使用props关联元数据

  • TreeBuffer标类,为每个节点关联四元组(type、start、end、endIndex)

  • BufferCursor接口,用于遍历tree buffer,初始指向最后一个元素,每次调用next()移到前一个元素

    • pos
    • id
    • start, end
    • size
    • next(), fork()

Parsing

  • Parser是一个抽象的标类
    • parse方法,解析生成整颗措辞树
    • startParse方法,返回PartialParse接口,传入fragment可以启用部分解析,可以使用ranges指定需要解析的范围合集
    • createParse抽象方法,需要派生类实现,被startParse调用用于解析
  • Input是一个接口,用于给Parser提供输入
  • PartialParse是一个接口,用于控制局部解析

(未完待续)