原本以为CodeMirror6只是把5改写成contenteditable,没想到还新增了一个解析器生成工具lezer。
lezer的由来可见作者博客上的介绍。 其灵感来自于tree-sitter
System Guide
Overview
Lezer是JS写就的解析器系统。给定一个规范的语法描述,它可以生成一个解析表集合,可以用来对输入的文本生成措辞树。
Lezer生成的措辞树并不是非常抽象的措辞树,没有包含足够的信息。每个节点只包含一个类型,开始和结束位置,一个扁平的下级节点序列。写作语法的时候,可以选择把哪个产生式保存成节点,其他的则会变成不可见。
处于Lezer的使用目的,它生成的信息非常紧实,也不在乎解析是否细致入微。
解析的时候可以增量式,自带错误恢复策略。
实现办法基于tree-sitter,以及Tim Wagner和Susan Graham的增量式解析(1,2)。
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是一个接口,用于控制局部解析
(未完待续)