JuliaSyntax 设计解析Julia 新一代无损耗解析器的架构、ParseStream 与分层语法树【免费下载链接】juliaThe Julia Programming Language项目地址: https://gitcode.com/gh_mirrors/ju/julia本文基于 Julia 语言仓库内 JuliaSyntax/docs/src/design.md 设计文档撰写系统梳理 JuliaSyntax——Julia 官方新一代编译器前端——的设计目标、ParseStream流式解析核心、GreenNode/SyntaxNode/Expr三层树结构、错误恢复策略以及与旧版 flisp 参考解析器在行为上的全部已知差异。读完后你将理解 JuliaSyntax 如何做到“无损耗”lossless源码映射、为何放弃解析器生成器选择递归下降、以及它在宏扩展等后续降低lowering环节中要解决的开放难题并掌握结合 JuliaSyntax/src 源码逐层验证这些设计决策的方法。设计目标与总体取舍JuliaSyntax 的设计文档开头列出了七条明确目标对 Julia 代码进行无损耗lossless解析并具备精确的源码位置映射生产质量的错误恢复、诊断报告与单元测试解析器结构上贴近 Julia 原有的 flisp 参考解析器便于对照移植速度足够快可支撑交互式编辑场景把“编译作为 API”Compilation as an API作为能力支撑各类工具链逐步扩展到编译器前端的其余环节宏扩展、语法脱糖desugaring与其他降低步骤替换 Julia 现有的 flisp 参考前端。在此之上文档提出了三条“设计观点”它们决定了整个代码库的组织方式解析器实现与树数据结构解耦——由此产生ParseStream接口。解析阶段既不依赖也不产出任何具体树结构输出节点可以在解析完成后按需要后处理成各种树。树数据结构分层——用SyntaxNodeAST叠在GreenNode无损耗解析树之上以在无损耗性与抽象/通用性之间取得平衡并预留未来引入其他树类型的空间。不采用解析器生成器——“花哨的解析器生成器对生产级编译器而言价值仍然有限”。JuliaSyntax 使用的是朴素但灵活的手写递归下降解析器。这些观点在源码中得到了直接印证JuliaSyntax/src/JuliaSyntax.jl 把代码划分为core/parse_stream.jl、diagnostics.jl、source_files.jl、tree_cursors.jl与具体树类型无关、julia/tokenize.jl、parser.jl、kinds.jl等 Julia 语言特定逻辑与porcelain/green_node.jl、syntax_node.jl等树数据结构三层与文档描述的分层完全对应。同时 JuliaSyntax/README.md 说明 JuliaSyntax 自 Julia 1.10 起已成为默认的 Julia 解析器并且能够完整解析 Base、标准库与 General registry——这是“目标”走向落地的事实注脚。Parser 实现从源码文本到绿色树无损耗语法树的术语文档首先界定术语目标是“用树无损耗地表示源文本”称为lossless syntax tree。“concrete syntax tree”这个名词因同时被用于“包含所有消歧 hack 的完整形式文法解析树”而被有意避开以免歧义。JuliaSyntax采用**以递归下降为主mostly recursive descent**的解析器其高层结构刻意紧跟 flisp 参考解析器这样代码对熟悉旧解析器的人更易读、可减少移植引入的 bug也为设计诊断信息、树数据结构、兼容不同 Julia 版本等留下了灵活性。至于不用解析器生成器文档给出的理由是就解析本身而言生成器文法的表达力并不比手写高多少而真正繁重的“辅助代码”诊断、测试、边界情况无论如何都要手写生成器反而降低了这部分代码的灵活性。词法分析Lexing词法器是手写 lexer源自 JuliaSyntax/src/julia/tokenize.jl即导入并大幅修改过的 Tokenize.jl 代码。相对原版的关键改动含换行的空白被单独作为一种 token 类型发出对应代码中的KNewlineWs见 JuliaSyntax/src/core/parse_stream.jl 中对Whitespace/Comment/NewlineWs的区分处理字符串插值内部的 token与字符串本体分离发出字符串定界符是独立 token字符串本体始终是Stringkind新增as、var、doc等上下文相关关键字contextual keywords并归入关键字的子类增加了非终结符 kind文档自注这些“或许以后该再抽出去”;修复了若干 bug并为更新的 Julia 版本补充了词法规则。从源码看lexer 被内嵌在ParseStream里ParseStream结构体持有一个Tokenize.Lexer{IOBuffer}和一个lookaheadtoken 缓冲JuliaSyntax/src/core/parse_stream.jltoken 以约 100 个为一批缓冲进前瞻区_buffer_lookahead_tokens以平衡peek()快路径命中率与缓存污染。用 ParseStream 解析ParseStream是整个解析器最核心的创新一个流式 I/O 接口让解析器代码完全不必接触任何具体树数据结构。文档称这一设计“与 rust-analyzer 类似但实现更简单”。解析过程按递归下降进行输入输出两个方向约定如下输入解析器消费一个展平后的 token 列表用peek()查看 token、bump()消费 token输出解析器产出一串RawGreenNode用bump()把 token 转移到输出侧用position()/emit()标记非终结符节点诊断diagnostics作为独立的文本区段span发出空白与注释会被自动 bump无需显式处理——唯一例外是 space-sensitive 模式下语法上有意义的新行解析模式parser modes通过ParseState沿调用树向下传递。输出的每个节点记录字节跨度、以整型 tag 存储的语法kind和若干标志位节点要么存子节点数非终结符要么存原始 token kind终结符。kind tag 使节点成为一个“和类型sum type”只不过类型信息被显式地放在 Julia 类型系统之外追踪。在无损耗解析中输出节点必须覆盖全部输入文本。只要以“自然的方式”使用bump()/position()/emit()还能保证三条不变量节点干净嵌套子节点完全包含在父节点之内兄弟节点按源码顺序发出父节点在其所有子节点之后发出。这三条性质意味着输出节点序列正是 C# Roslyn 术语中“绿色树”green tree的后序遍历树结构隐含在节点跨度里。源码层面这些机制在 JuliaSyntax/src/core/parse_stream.jl 中可以逐条对照RawGreenNode只有三个字段head::SyntaxHeadkindflags、byte_span::UInt32、node_span_or_orig_kind::UInt32非终结符时为子节点数终结符时为原始 token kind见 parse_stream.jl#L130-L155非终结符标志NON_TERMINAL_FLAG自动由构造函数置位节点本身不可变、不存父指针、不存绝对位置因此可以缓存复用。peek()自动跳过注释与不含换行的空白parse_stream.jl#L480-L483skip_newlines参数决定换行是否也被跳过bump()把当前 token 从输入侧复制到输出侧并可附带 flags/错误parse_stream.jl#L720-L729position()返回(byte_index, node_index)二元游标parse_stream.jl#L829-L834emit(stream, mark, kind, flags)从mark处到最近一个已 bump token 的末尾生成非终结符节点node_span自动取 mark 之后已发出的节点数parse_stream.jl#L844-L865——这正是“父节点在子节点之后发出”这条不变量的实现机制诊断通过emit_diagnostic以字节区段形式推入stream.diagnostics与文档“diagnostics are emitted as separate text spans”一致一个值得注意的工程细节peek_count计数器会在连续 10 万次peek()而无任何bump()进展时报出The parser seems stuck at byte ...错误parse_stream.jl#L467-L470这是对“解析器死循环”的防护ParseStream构造函数支持String/SubString/IO/Vector{UInt8}/(ptr, len)多种输入并尽量零拷贝version参数可把目标语法版本设置为任意 v1.0的 Julia 版本“目标是为 v1.0 之后加入的所有 Julia 语法提供解析能力不兼容请求版本时发出错误”parse_stream.jl#L211-L234——这对应目标中“兼容不同 Julia 版本”的要求。树构建Tree constructionbuild_tree函数利用ParseStream输出中隐含的树结构来组装具体树。由于输出本身已是RawGreenNode的后序遍历、节点跨度已编码父子关系树构建是直接的。在此基础上文档定义了若干树类型的build_tree实现源码中分别落在build_tree(GreenNode, ...)—— JuliaSyntax/src/porcelain/green_node.jl#L154build_tree(SyntaxNode, ...)—— JuliaSyntax/src/porcelain/syntax_node.jl#L308build_tree(Expr, ...)—— JuliaSyntax/src/integration/expr.jl#L678把树转回标准 JuliaExpr以保持兼容从源码结构看当前代码还额外提供了build_tree(SyntaxTree, ...)JuliaSyntax/src/porcelain/syntax.jl#L881且在 JuliaSyntax/src/JuliaSyntax.jl 中被限制为 Julia ≥ 1.12 才加载——这是“未来可能需要其他树类型”这一预留的落地。错误恢复Error recovery解析器的职责是把源文本变成结构良好的层次结构对交互式工具而言即使源文本含错也必须如此恢复启发式就是解析器的一部分。具体来说JuliaSyntax应始终产出一棵**良构well formed**的绿色树给定Kind的GreenNode必须具有良定义的子节点布局。这保证GreenNode到SyntaxNode的转换是确定性的工具可以假设自己在处理一棵“mostly valid”的 AST。“mostly valid”意味着允许两类错误节点补全add当语法不完整时可以插入占位符。例如a (b *可以解析为(call-i a (call-i * b XXX))其中XXX是占位错误节点移除remove一段意外 token 可以收拢为错误节点的子节点在构建 AST 时当作语法 trivia 处理。例如a b end * c可解析为绿色树(call-i a b (error-t end * c))进而得到 AST(call a b)。文档强调要以“对下游工具最简”的方式编码这两种情况——这是一个开放问题当前方案是统一使用Kerror作为 kind并对意外语法置TRIVIA_FLAGTRIVIA_FLAG定义见 JuliaSyntax/src/core/parse_stream.jl#L9-L10。语法树三层结构与显式 kind为什么需要新树类型Julia 的ExprAST 既不能存精确源码位置也不能承载空白、注释等语法 trivia所以JuliaSyntax引入新的树类型。文档说当前处理三种树GreenNode——最小的无损耗语法树节点存 kind 与字节长度不存文本语法 trivia 包含在子节点列表中子节点严格按源码顺序排列。SyntaxNode——抽象语法树AST存绝对位置并指向源文本子节点严格按源码顺序叶节点存值value而非文本trivia 被忽略但非 trivia 节点与关联的GreenTree节点保持 1:1 映射。Expr——作为转换目标用于兼容性。源码中GreenNode是带head/span/children的普通 Julia 结构体JuliaSyntax/src/porcelain/green_node.jl#L9-L13并提供child_position_span等按路径定位子节点、计算绝对位置的 API而SyntaxNode的每个节点数据SyntaxData持有source::SourceFile、raw::GreenNode、byte_end与叶值valJuliaSyntax/src/porcelain/syntax_node.jl#L57-L62正好实现了“指向绿色树、可回溯源码”的设计。关于语法 kind 的更多讨论节点类型统一用显式存储的整数 tag“syntax kind”追踪。这在类型系统意义上构成和类型但类型在 Julia 类型系统之外显式追踪。这样做的好处操作语法节点的代码与数据结构从编译器视角始终是具体类型concretely typed可以控制数据布局把 kind 与其他标志位压缩进很少的 bit谓词如is_operator可以极其高效因为 kind 各 bit 的语义是已知的同一个 kind 可以应用于多种树数据结构也可以单独操作当全部 kind 在编译期封闭且已知时模式匹配代码是高效的。代价也有两点普通 Julia 派发无法表达“按 kind 派发”。所幸一个模式匹配宏可以非常优雅地表达这种在不可扩展 kind 集上的算法问题不大不同 kind 本来可以携带不同数据字段但语法树必须用能容纳所有 kind 的通用字段类比单字段的QuoteNodevs. 通用head/args字段的Expr。对只处理单一 kind 的代码这是劣势但对处理多种 kind 的通用代码一个通用但具体的布局反而可能更快。源码中这一设计体现为SyntaxHead(kind, flags)的组合JuliaSyntax/src/core/parse_stream.jl#L36-L57以及 JuliaSyntax/src/JuliaSyntax.jl 导出的head、is_trivia、is_prefix_call、is_infix_op_call、numeric_flags等一批基于标志位的谓词——“谓词极其高效”在这里是字面成立的。与 flisp 参考解析器的差异严格来说flisp 解析器并不完全是经典递归下降它经常回看并修改已经产出的输出树。JuliaSyntax 在可能的地方用 lookahead 取代这种模式因为在“解析器持续发出有严格源码顺序约束的节点流”这种工作方式下回改输出效果很差这类代码让人难以推理。但偶尔它确实能解决 Julia 代码无法用有限 lookahead 自顶向下消歧的真歧义比如括号内kw与的歧义。这些情况下作者选择容忍继续使用look_behind现名peek_behindJuliaSyntax/src/core/parse_stream.jl#L531-L561与reset_node!()JuliaSyntax/src/core/parse_stream.jl#L798-L802注释直白地写着 “This is a hack”这类“回改输出”的手段。代码结构移植时总体上避免了大型结构性改动几乎所有解析产生式production的函数名与 flisp 相同-换成_谓词加is_前缀。显著差异有两处parse-arglist与parse-paren-的一部分被合并为通用函数parse_brackets位于 JuliaSyntax/src/julia/parser.jl。它统一处理括号内,与;混用时 AST 发射的各种边角情况具体包括判断;是块语法分隔符还是关键字参数根据上下文判断是否发射parameter段根据上下文把键值对发射为kw或。parse-resword的进入方式被重排避免在parse-unary-prefix内部的parse-atom里解析保留字改为更早检测保留字并进入parse_resword。flisp 解析器的 bug文档列出了一批“看起来是 bug”的行为其中一些为兼容而被复制可能附带警告宏模块路径允许调用表达式带来奇怪的状态语义b() rand() 0.5 ? Base : Core b().info hi宏模块路径中位置错放如A.B.x被解析成怪异的坏 AST(macrocall (. A (quote (. B x))))理应被拒绝前缀运算符调用在(a;b,c)这类用逗号分隔关键字参数的情况下不工作产出的是元组const/global允许链式赋值但只有第一个绑定是 constconst a b 1这里a是 constb不是花括号内的ncat拼接语法产出奇怪的 AST{a ;; b}解析为(bracescat 2 a b)与{2 ; a ; b}相同按{a b}产出(bracescat (row a b))的类比它本应更接近(bracescat (nrow 2 a b))export a, \n $b被拒绝而export a, \n b正常解析try-catch-finally 中finally允许写在catch之前但总是最后执行“这大概是失误吧看起来非常糟糕”解析[x \n\n ]时 flisp 解析器会混乱而[x \n ]能正确解析为Expr(:vect)“也许在 1.7 修过了”f(x for x in in xs)重复的in竟然被接受且解析结果非常奇怪八进制转义序列饱和而不是报错\777得到\xff与Base.parse(::Type{Int}, ...)不一致以点开头且模块名是运算符的 import 路径如import .⋆被解析成点运算符(. .⋆)而按import .A的解析规则本应得到相对路径(. . ⋆)回看输出时忽略分组括号导致某些情况下结果怪异f(((((x1)))))被解析成带关键字x1的f调用但论起来它也许是赋值十六进制浮点字面量可以有尾部f如0x1p1f但毫无作用。flisp C 代码里这类情况会被当作 Float32 字面量曾有相关 PR 且属有意为之但 Julia 官方从未支持过这一点。该 bug 源于parse-number中(set! pred char-hex?)接受十六进制指数位——其中所有位都被判为非法唯独经isnumtok_base处理后尾随的f幸存索引处begin/end不被当作关键字。带类型的推导式起初与索引看起来相同但要等处理到fortoken 才能区分一旦处理过for把begin/end当关键字就是安全的。参考解析器只在for前有换行时才处理正确Any[foo(i) for i in x if begin true end ]这种写法可行而Any[foo(i) for i in x if begin true end ]则不行。JuliaSyntax 两种情况都正确处理。解析 / AST 的怪癖与毛病warts可疑但被允许的形式存在一些解析器很容易检测、但会留到降低阶段才拒绝的语法。为了构建 DSL这种“先允许”是合理且好的但有些形式即便对 DSL 也用处不大macro (x) end被允许但实际上没有匿名宏这回事abstract type A B end及其他子类型比较被允许但只有A : B有意义x where {S T}产出(where x (bracescat (row S T)))相当怪异[x for outer x in xs]能解析但此处的outer没有实际意义使用它是降低错误。kw与的不一致括号内解析keyval对时kw与的用法存在多处明显不一致点调用内外对元组关键字参数的解析不一致(a1,) # (tuple ( a 1)) f.(a1) # (tuple (kw a 1))调用中,与;混用会产出嵌套 parameter 的 AST解析结果怪异且很难用# (tuple (parameters (parameters e f) c d) a b) (a,b; c,d; e,f)长形式匿名函数的参数列表被解析为元组甚至块而非参数列表这一混乱似乎是在降低阶段被掩盖的。例如function (a;b) end中的(a;b)被解析为block这又进一步加剧了kw用法的不一致。其他怪癖带后缀运算符的解析不总是与不带后缀形式一致不清楚是设计还是失误[x y]得(hcat x ( y))而[x ₁y]得(hcat (call ₁ x y))global const x1被解析器归一化为(const (global ( x 1)))。对 AST 消费者有点用但反转源码顺序在转向无损耗解析器时相当别扭let绑定是否包在 block 里取决于特例# 特例不在 block 中 let x1 ; end # (let ( x 1) (block)) let x::1 ; end # (let (:: x 1) (block)) let x ; end # (let x (block)) # 在 block 中 let x1,y2 ; end # (let (block ( x 1) ( y 2) (block))) let x1 ; end # (let (block ( x 1)) (block))elseif的条件总在 block 里而if的条件不是。推测是 flisp 解析器需要插入行号节点所致if a xx elseif b yy end (if a (block xx) (elseif (block b) (block yy)))import 的点之间允许空格import . .A被允许与import ..A解析相同import A..产出(import (. A .))这基本是无意义的因为.不能是普通标识符raw 字符串的转义规则在字符串结尾附近的反斜杠上极其反直觉raw\\\\ 含四个反斜杠而raw\\\\只有两个。这是为让“所有字符串都可表示”的刻意特性能否改进尚不明确宏调用后的花括号中S{a b}非法但S{a,b}与S {a b}都能解析反过来S[a b]也能解析宏名与宏调用是对parse-atom/parse-call输出的后处理这导致一些惊人且存疑的构造竟然“能工作”(((((a))))) x得到(macrocall a x)这种荒诞结果中缀宏(x y) (macrocall x y)“好吧有点酷还有点奇怪的内在逻辑……但这是什么”括号还可以再嵌套(f(x)) (macrocall f x)宏模块路径允许开头如A.B.x而非A.B.x看起来是不必要的语法变体它使合法宏模块路径的解析更复杂并产生$.x y (macrocall ($ (quote x)) y)这类怪象——$先被当作宏名解析解析到.后才发现它其实是模块名而$在普通 Julia 代码里永远不可能是合法模块名毫无意义三重引号字符串可以当标识符var##被允许。考虑到它要套用复杂的重缩进deindentation规则不清楚这是不是必要的三重引号字符串重缩进在空白不匹配时行为怪异当内容只有空白时\\\\n \n \n \\\的结果是\n \n——中间一行空白没有被缩进而另外两行更长的却被缩进更自洽的做法应是 (a) 中间行完全去缩进或 (b) 所有行只去掉一个字符那才是公共前缀匿名函数参数解析不一致function (xs...) \n body end的参数列表解析为(... xs)而function (x) \n body end的参数列表解析为(tuple x)多维迭代器与扁平迭代器的区别微妙且可能过于宽松[(x,y) for x * in 1:10, y in 1:10]是多维迭代器[(x,y) for x * in 1:10 for y in 1:10]是扁平迭代器[(x,y) for x in 1:10, y in 1:10 if y x]也是扁平迭代器。最后这种情形最令人不安为什么不强制用第二种显式形式表示扁平连 pretty print 都不对julia :([(x,y) for x in 1:10, y in 1:10 if y x]) :([(x, y) for $(Expr(:filter, :(y x), :(x 1:10), :(y 1:10)))])字符字面量可以不转义直接写成而不必用\。与其他解析器/工具的对比与官方 Julia 编译器的关系官方 Julia 编译器前端就在 Julia 源码树中主要集中在少数文件解析器src/julia-parser.scm宏扩展src/ast.c 与 src/macroexpand.scm语法降低src/julia-syntax.scmflisp 运行时与 C 扩展src/flisp外加其他若干.scm/.c文件中的工具函数。参考前端存在两个问题说明重写的必要性不支持精确源码位置而现有数据结构裸 flisp 列表也难以直接扩展出位置信息修复它意味着几乎全部代码都要改它用 flisp 写成——一个美观、极简但晦涩的 Scheme 实现。学 Scheme 确实是理解 Julia 设计灵感的好途径但对 Julia 语言工具开发者是很大的门槛。除社区因素外内嵌 flisp 解释器与运行时自带独立的数据结构和 FFI既复杂又低效。flisp 没有用户级文档非 Scheme 背景者可参照 Racket 文档了解基础概念。与 JuliaParser.jl 的关系JuliaParser.jl 是 flisp 参考解析器的直接移植约在 Julia 0.5 时期被弃养。它不支持无损耗解析而补上该功能相当于完全重写。又因为它自 Julia-0.5 起已与参考解析器分叉作者认为不如直接从参考解析器重新出发。与 Tokenize.jl 的关系Tokenize.jl 是一个快速的 Julia 词法器。其代码被导入并用于 JuliaSyntax并做了一些重大修改见上文“词法分析”小节导入后的实现位于 JuliaSyntax/src/julia/tokenize.jl。与 CSTParser.jl 的关系CSTParser.jl 是一个大致上无损耗解析器目标与 JuliaParser 相近被 VSCode / LanguageServer / JuliaFormatter 生态广泛使用。它很有用但作者觉得其实现难以理解并想以一种全新尝试聚焦以下三点“生产就绪”好文档、测试、诊断与 flisp 解析器最大程度一致目标是把新解析器送进Core吸收 Julia 之外关于可组合解析与数据结构的新思想。特别是rust-analyzer的实现非常干净、文档完善是绝佳灵感来源树数据结构的可组合性树应该分层最底层是一个极轻量的绿色树类似 Roslyn 或 rust-analyzer相比之下 CSTParser 使用更重型的非分层结构。或者以及提供一个公共树 API配多个任务特化的具体实现。作者强调 JuliaSyntax 解析器的一个大优点解析代码与树数据结构完全分离为实验各种树表示形式留足了灵活性。同时作者希望 JuliaSyntax 接管宏扩展与其他降低步骤为核心语言与编辑器工具链提供同一套 API。与 tree-sitter-julia 的取舍用 tree-sitter 这类现代生产级解析器生成器是有趣的选项tree-sitter-julia 已有进展。但作者认为把真实语言边角情况与测试、“辅助代码”的工作量考虑进去后生成器文法的表达力只比手写解析器略高一点。另一方面手写解析器完全灵活且能与参考实现相互印证——JuliaSyntax 因此选择了手写路线。设计笔记原型、树设计与开放问题原型验证方法树数据结构设计颇具难度文档给出的分析框架是编译的符号部分前端对源文本做渐进的抽象与变换但过程中的错误要能回溯源码树必须是无损耗地表示源文本源文本的某些方面注释、大部分空白与解析无关有了表层语法的 AST 之后更多方面变得无关。好例子是2*(x y)里的括号以及2*x与2x中显式与隐式乘法号。存在多种分析analyses增强语法树的方式因用例而异且方法很多分析算法应能作用于任何树类型无视但不丢失它不认识的增强信息。这么多用例暗示“多个不同树类型 公共接口”可能优于“一个大而全的 AST”。作者决定通过原型若干关键工作流来验证语法变换挑一些宏来实现这是混合不同文件源树并保持精确源码位置的基本测试文档注明当时在test/syntax_interpolation.jl中完成格式化重新缩进一个文件测试 trivia 的处理重构一个重命名局部变量的 pass测试“编译管线更深层的信息如何挂到语法树上并用来修改源码”降低阶段的精确错误报告例如对[a, b] (c, d)做语法脱糖应报告“invalid assignment location[a, b]”并附精确源码位置或试一个降低更深层的例子如“macro definition not allowed inside a local scope”增量重解析给定一个字节范围替换重解析源文件。绿色树与 AST 的设计细节GreenNode要求结构上极简——为了效率与通用性不可变——为了效率与线程安全完整——为了保留解析器知识token 无关token agnostic——以支持任意源语言。最简方案是叶节点就是单个 token子节点按源码顺序。call的表示是 AST 与绿色树之间节点放置/迭代的难点中缀运算符 vs. 普通前缀函数调用。典型问题是a 1vs.(a, 1)更糟的是a 1 2vs.(a, 1, 2)。显然在 AST 的接口层需要抽象掉这种放置差异例如采用类似标准 Julia AST 的迭代顺序。设计新 AST 之所以棘手是因为与大多数语言不同现有Expr是每个宏扩展都在用的公开 API用户宏扩展插在源文本与降低之间且使用Expr会在很多方面丢失源码信息。文档列出几条可能的出路给Expr增加一些半隐藏字段指回Expr或其args来源的绿色树节点宏扩展期间沿用现有Expr然后在宏扩展后用启发式恢复源码信息——正确的卫生性hygiene或许能帮忙若新 AST 只对某种假设的“新式宏”开放opt-in也是可能的。修好卫生性应当与之配套。设计挑战字面量需要携带源码位置时如何让表达式操作保持合理一个可能的过渡方案是为少数需要的字面量类型提供包装SourceSymbol : AbstractSymbol SourceInt : Integer SourceString : AbstractString给符号附上源码位置或许能解决大部分卫生性问题。宏辅助函数使用符号字面量的问题仍在——总不能改变:x的语义一个思路是尝试在插值语法所在处捕获当前模块。例如:(y $x)在降低时展开为Core._expr(:call, :, :y, x)或许可以展开为类似Core._expr(:call, :, :y, _add_source_symbol(_module_we_are_lowering_into, x))错误恢复的进一步思考文档记录了若干“不太有条理”的恢复思路。不同类型的错误似乎包括不允许的语法如条件表达式缺少空格可以继续解析给节点打上错误标志后照常发出一个完整节点。某些情况下如中缀表达式尾部缺失发射一个零宽错误 token就能让上层产生式不必参与恢复就得到完整解析树当前上下文不允许的 token如parse_atom里的或中缀表达式内的闭合 token这里可以发出Kerror但无法继续深入解析树——必须弹出多个递归帧。“棘手”典型产生式结构如下function parse_foo(ps) mark position(ps) parse_bar(ps) # What if this fails? if peek(ps) Ksome-token bump(ps) parse_baz(ps) # What if this fails? emit(ps, mark, Kfoo) end end“missing end”问题更棘手因为中间语法都是合法的往往要到 EOF 才暴露问题function f() begin a 10 end # -- Indentation would be wrong if g() was an inner function of f. function g() end理想的恢复在这种情况下需要回溯弹回到正在解析f()的帧回溯解析事件直到找到缩进与父级嵌套不匹配的那个 function把 ParseStream 重置到调用g()之前的解析检查点发出错误并退出f()的解析重新开始解析想办法保证这一切不会导致无限递归 嵌套结构中缺逗号或缺右括号同样是难题。本地缩进有时能讲故事f(a, g(b, c # -- missing comma? d), e)f(a, g(b, c # -- missing closing ) ? d)但并不总是f(a, g(b, c # -- missing closing , ? d))当前体系里对诊断格外困难的问题还有字符串插值中破损的括号或双引号尤其是嵌套插值时。外部灵感Roslyn、rust-analyzer 与 RSLint设计文档的“Resources”部分记录了作者从工业界编译器项目中借鉴的设计C# Roslyn红绿树red-green trees的持久化与外观façade模型是绿色树术语的来源rust-analyzer与 JuliaSyntax 的思路最接近独立得出“绿色树布局 显式 trivia 节点”的结论。值得注意的是它其实有三棵树绿色树设计上与 JuliaSyntax 几乎完全相同包括 trivia 存储方式不过其团队当时仍在讨论改用 Roslyn 式 trivia 模型非类型化的红语法树类似但极简例如不尝试重排子节点类型化 AST 层每种表达式 head 一个类型其 AST 通过每次动态遍历子节点列表来查找子节点而不是依赖一个规范顺序或记住解析器已知的子节点位置。另外“解析器看不到空白节点空白在 TreeSink 层挂到树上”——这对 JuliaSyntax 有参考意义把空白挂到“有意义”token 上既麻烦又低效“实践中对 IDE 用途而言增量重解析其实没那么大意义从头解析已经足够快”作者还半开玩笑地问那为什么还实现了增量解析以及若干关于宏的评论——Rust 宏扩展与 Julia 差异很大看起来宏扩展可能与解析交织进行。 作者总结不确定 Julia 是否想要类型化 AST且必须正视Expr是既有公开接口这个事实——Expr2包装SyntaxNode是否可行RSLint基于 rust-analyzer 同一套解析基础设施与绿色树库的 JavaScript linter在大致共享这套架构下出错时回溯并重启解析器其实很简单——“事件流允许我们通过清空事件、把 token 源游标重置回某处来廉价地回溯解析器”其“错误恢复”章节讨论了多种恢复策略值得参考。诊断系统C 提案论文《P2429 - Concepts Error Messages for Humans》虽以 C 为中心但评审了 Elm、ReasonML、Flow、D、Rust 等编译器的错误报告质量Rust 侧则有rustc_errors::Diagnostic类型、诊断系统源码包括宏如何发出诊断、rustc_parse的diagnostics.rs可作参考。解析通识matklad 的《Modern parser generator》博文对手写解析器有大量实用建议鼓励把测试写成行内注释、Pratt 解析器用于运算符优先级、错误恢复讨论关于“解析 shell 风格字符串插值的状态词法器”oilshell 的一篇博文有相关笔记。有趣的研究性议题文档最后留下两个开放研究方向解析器恢复能否让解析器在遇到破损语法时学习快速且足够准确的恢复启发式而不是手写如何组织解析器使训练可行、模型注入又不侵入如果模型内嵌并与解析器协同工作能否让它足够紧凑使训练快速、模型本身极小格式化给定源码与语法树能否从语法树回归/学习一个缩进的生成模型源码格式化需要一堆“看起来好看”的启发式而机器学习系统恰好擅长启发式而且我们有海量训练数据——只需挑一些高质量、品味良好的手工格式化库即可。小结与源码导航JuliaSyntax 的设计可以概括为一条主线用与树结构解耦的ParseStream事件流做递归下降解析产出后序遍历的绿色树再按需用build_tree装配出无损耗的GreenNode、带源码位置的SyntaxNode或兼容用的Expr错误恢复通过补占位符与收拢Kerror节点保证输出永远是良构树。这一设计既继承 flisp 解析器的产生式结构以保证兼容性又在精确源码映射、版本兼容与可测试性上全面超越。想继续深入可以从这些仓库路径入手内容路径设计文档本文依据JuliaSyntax/docs/src/design.md模块入口与公共 APIJuliaSyntax/src/JuliaSyntax.jlParseStream、RawGreenNode、bump/emit/诊断JuliaSyntax/src/core/parse_stream.jl词法器改造自 TokenizeJuliaSyntax/src/julia/tokenize.jl递归下降解析器与parse_brackets等JuliaSyntax/src/julia/parser.jlparse!/parseall/parseatom/parsestmtJuliaSyntax/src/julia/parser_api.jlGreenNode与build_tree(GreenNode)JuliaSyntax/src/porcelain/green_node.jlSyntaxNode与build_tree(SyntaxNode)JuliaSyntax/src/porcelain/syntax_node.jlExpr转换目标JuliaSyntax/src/integration/expr.jl解析器行为测试含整包解析JuliaSyntax/testparser.jl、green_node.jl、syntax_node.jl、parse_packages.jl、fuzz_test.jl等旧 flisp 参考前端对照src/julia-parser.scm、src/julia-syntax.scm、src/macroexpand.scm、src/ast.c、src/flisp适用前提说明文中对当前代码行为的描述以本仓库JuliaSyntax/Project.toml 中标记为2.0.0-DEV兼容 Julia ≥ 1.0的实际代码为准设计文档部分表述反映的是设计阶段的方案例如树类型数量个别细节如SyntaxTree的引入已由后续代码演进扩展本文已按“从源码结构看”加以标注。【免费下载链接】juliaThe Julia Programming Language项目地址: https://gitcode.com/gh_mirrors/ju/julia创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
JuliaSyntax 设计解析Julia 新一代无损耗解析器的架构、ParseStream 与分层语法树【免费下载链接】juliaThe Julia Programming Language项目地址: https://gitcode.com/gh_mirrors/ju/julia本文基于 Julia 语言仓库内 JuliaSyntax/docs/src/design.md 设计文档撰写系统梳理 JuliaSyntax——Julia 官方新一代编译器前端——的设计目标、ParseStream流式解析核心、GreenNode/SyntaxNode/Expr三层树结构、错误恢复策略以及与旧版 flisp 参考解析器在行为上的全部已知差异。读完后你将理解 JuliaSyntax 如何做到“无损耗”lossless源码映射、为何放弃解析器生成器选择递归下降、以及它在宏扩展等后续降低lowering环节中要解决的开放难题并掌握结合 JuliaSyntax/src 源码逐层验证这些设计决策的方法。设计目标与总体取舍JuliaSyntax 的设计文档开头列出了七条明确目标对 Julia 代码进行无损耗lossless解析并具备精确的源码位置映射生产质量的错误恢复、诊断报告与单元测试解析器结构上贴近 Julia 原有的 flisp 参考解析器便于对照移植速度足够快可支撑交互式编辑场景把“编译作为 API”Compilation as an API作为能力支撑各类工具链逐步扩展到编译器前端的其余环节宏扩展、语法脱糖desugaring与其他降低步骤替换 Julia 现有的 flisp 参考前端。在此之上文档提出了三条“设计观点”它们决定了整个代码库的组织方式解析器实现与树数据结构解耦——由此产生ParseStream接口。解析阶段既不依赖也不产出任何具体树结构输出节点可以在解析完成后按需要后处理成各种树。树数据结构分层——用SyntaxNodeAST叠在GreenNode无损耗解析树之上以在无损耗性与抽象/通用性之间取得平衡并预留未来引入其他树类型的空间。不采用解析器生成器——“花哨的解析器生成器对生产级编译器而言价值仍然有限”。JuliaSyntax 使用的是朴素但灵活的手写递归下降解析器。这些观点在源码中得到了直接印证JuliaSyntax/src/JuliaSyntax.jl 把代码划分为core/parse_stream.jl、diagnostics.jl、source_files.jl、tree_cursors.jl与具体树类型无关、julia/tokenize.jl、parser.jl、kinds.jl等 Julia 语言特定逻辑与porcelain/green_node.jl、syntax_node.jl等树数据结构三层与文档描述的分层完全对应。同时 JuliaSyntax/README.md 说明 JuliaSyntax 自 Julia 1.10 起已成为默认的 Julia 解析器并且能够完整解析 Base、标准库与 General registry——这是“目标”走向落地的事实注脚。Parser 实现从源码文本到绿色树无损耗语法树的术语文档首先界定术语目标是“用树无损耗地表示源文本”称为lossless syntax tree。“concrete syntax tree”这个名词因同时被用于“包含所有消歧 hack 的完整形式文法解析树”而被有意避开以免歧义。JuliaSyntax采用**以递归下降为主mostly recursive descent**的解析器其高层结构刻意紧跟 flisp 参考解析器这样代码对熟悉旧解析器的人更易读、可减少移植引入的 bug也为设计诊断信息、树数据结构、兼容不同 Julia 版本等留下了灵活性。至于不用解析器生成器文档给出的理由是就解析本身而言生成器文法的表达力并不比手写高多少而真正繁重的“辅助代码”诊断、测试、边界情况无论如何都要手写生成器反而降低了这部分代码的灵活性。词法分析Lexing词法器是手写 lexer源自 JuliaSyntax/src/julia/tokenize.jl即导入并大幅修改过的 Tokenize.jl 代码。相对原版的关键改动含换行的空白被单独作为一种 token 类型发出对应代码中的KNewlineWs见 JuliaSyntax/src/core/parse_stream.jl 中对Whitespace/Comment/NewlineWs的区分处理字符串插值内部的 token与字符串本体分离发出字符串定界符是独立 token字符串本体始终是Stringkind新增as、var、doc等上下文相关关键字contextual keywords并归入关键字的子类增加了非终结符 kind文档自注这些“或许以后该再抽出去”;修复了若干 bug并为更新的 Julia 版本补充了词法规则。从源码看lexer 被内嵌在ParseStream里ParseStream结构体持有一个Tokenize.Lexer{IOBuffer}和一个lookaheadtoken 缓冲JuliaSyntax/src/core/parse_stream.jltoken 以约 100 个为一批缓冲进前瞻区_buffer_lookahead_tokens以平衡peek()快路径命中率与缓存污染。用 ParseStream 解析ParseStream是整个解析器最核心的创新一个流式 I/O 接口让解析器代码完全不必接触任何具体树数据结构。文档称这一设计“与 rust-analyzer 类似但实现更简单”。解析过程按递归下降进行输入输出两个方向约定如下输入解析器消费一个展平后的 token 列表用peek()查看 token、bump()消费 token输出解析器产出一串RawGreenNode用bump()把 token 转移到输出侧用position()/emit()标记非终结符节点诊断diagnostics作为独立的文本区段span发出空白与注释会被自动 bump无需显式处理——唯一例外是 space-sensitive 模式下语法上有意义的新行解析模式parser modes通过ParseState沿调用树向下传递。输出的每个节点记录字节跨度、以整型 tag 存储的语法kind和若干标志位节点要么存子节点数非终结符要么存原始 token kind终结符。kind tag 使节点成为一个“和类型sum type”只不过类型信息被显式地放在 Julia 类型系统之外追踪。在无损耗解析中输出节点必须覆盖全部输入文本。只要以“自然的方式”使用bump()/position()/emit()还能保证三条不变量节点干净嵌套子节点完全包含在父节点之内兄弟节点按源码顺序发出父节点在其所有子节点之后发出。这三条性质意味着输出节点序列正是 C# Roslyn 术语中“绿色树”green tree的后序遍历树结构隐含在节点跨度里。源码层面这些机制在 JuliaSyntax/src/core/parse_stream.jl 中可以逐条对照RawGreenNode只有三个字段head::SyntaxHeadkindflags、byte_span::UInt32、node_span_or_orig_kind::UInt32非终结符时为子节点数终结符时为原始 token kind见 parse_stream.jl#L130-L155非终结符标志NON_TERMINAL_FLAG自动由构造函数置位节点本身不可变、不存父指针、不存绝对位置因此可以缓存复用。peek()自动跳过注释与不含换行的空白parse_stream.jl#L480-L483skip_newlines参数决定换行是否也被跳过bump()把当前 token 从输入侧复制到输出侧并可附带 flags/错误parse_stream.jl#L720-L729position()返回(byte_index, node_index)二元游标parse_stream.jl#L829-L834emit(stream, mark, kind, flags)从mark处到最近一个已 bump token 的末尾生成非终结符节点node_span自动取 mark 之后已发出的节点数parse_stream.jl#L844-L865——这正是“父节点在子节点之后发出”这条不变量的实现机制诊断通过emit_diagnostic以字节区段形式推入stream.diagnostics与文档“diagnostics are emitted as separate text spans”一致一个值得注意的工程细节peek_count计数器会在连续 10 万次peek()而无任何bump()进展时报出The parser seems stuck at byte ...错误parse_stream.jl#L467-L470这是对“解析器死循环”的防护ParseStream构造函数支持String/SubString/IO/Vector{UInt8}/(ptr, len)多种输入并尽量零拷贝version参数可把目标语法版本设置为任意 v1.0的 Julia 版本“目标是为 v1.0 之后加入的所有 Julia 语法提供解析能力不兼容请求版本时发出错误”parse_stream.jl#L211-L234——这对应目标中“兼容不同 Julia 版本”的要求。树构建Tree constructionbuild_tree函数利用ParseStream输出中隐含的树结构来组装具体树。由于输出本身已是RawGreenNode的后序遍历、节点跨度已编码父子关系树构建是直接的。在此基础上文档定义了若干树类型的build_tree实现源码中分别落在build_tree(GreenNode, ...)—— JuliaSyntax/src/porcelain/green_node.jl#L154build_tree(SyntaxNode, ...)—— JuliaSyntax/src/porcelain/syntax_node.jl#L308build_tree(Expr, ...)—— JuliaSyntax/src/integration/expr.jl#L678把树转回标准 JuliaExpr以保持兼容从源码结构看当前代码还额外提供了build_tree(SyntaxTree, ...)JuliaSyntax/src/porcelain/syntax.jl#L881且在 JuliaSyntax/src/JuliaSyntax.jl 中被限制为 Julia ≥ 1.12 才加载——这是“未来可能需要其他树类型”这一预留的落地。错误恢复Error recovery解析器的职责是把源文本变成结构良好的层次结构对交互式工具而言即使源文本含错也必须如此恢复启发式就是解析器的一部分。具体来说JuliaSyntax应始终产出一棵**良构well formed**的绿色树给定Kind的GreenNode必须具有良定义的子节点布局。这保证GreenNode到SyntaxNode的转换是确定性的工具可以假设自己在处理一棵“mostly valid”的 AST。“mostly valid”意味着允许两类错误节点补全add当语法不完整时可以插入占位符。例如a (b *可以解析为(call-i a (call-i * b XXX))其中XXX是占位错误节点移除remove一段意外 token 可以收拢为错误节点的子节点在构建 AST 时当作语法 trivia 处理。例如a b end * c可解析为绿色树(call-i a b (error-t end * c))进而得到 AST(call a b)。文档强调要以“对下游工具最简”的方式编码这两种情况——这是一个开放问题当前方案是统一使用Kerror作为 kind并对意外语法置TRIVIA_FLAGTRIVIA_FLAG定义见 JuliaSyntax/src/core/parse_stream.jl#L9-L10。语法树三层结构与显式 kind为什么需要新树类型Julia 的ExprAST 既不能存精确源码位置也不能承载空白、注释等语法 trivia所以JuliaSyntax引入新的树类型。文档说当前处理三种树GreenNode——最小的无损耗语法树节点存 kind 与字节长度不存文本语法 trivia 包含在子节点列表中子节点严格按源码顺序排列。SyntaxNode——抽象语法树AST存绝对位置并指向源文本子节点严格按源码顺序叶节点存值value而非文本trivia 被忽略但非 trivia 节点与关联的GreenTree节点保持 1:1 映射。Expr——作为转换目标用于兼容性。源码中GreenNode是带head/span/children的普通 Julia 结构体JuliaSyntax/src/porcelain/green_node.jl#L9-L13并提供child_position_span等按路径定位子节点、计算绝对位置的 API而SyntaxNode的每个节点数据SyntaxData持有source::SourceFile、raw::GreenNode、byte_end与叶值valJuliaSyntax/src/porcelain/syntax_node.jl#L57-L62正好实现了“指向绿色树、可回溯源码”的设计。关于语法 kind 的更多讨论节点类型统一用显式存储的整数 tag“syntax kind”追踪。这在类型系统意义上构成和类型但类型在 Julia 类型系统之外显式追踪。这样做的好处操作语法节点的代码与数据结构从编译器视角始终是具体类型concretely typed可以控制数据布局把 kind 与其他标志位压缩进很少的 bit谓词如is_operator可以极其高效因为 kind 各 bit 的语义是已知的同一个 kind 可以应用于多种树数据结构也可以单独操作当全部 kind 在编译期封闭且已知时模式匹配代码是高效的。代价也有两点普通 Julia 派发无法表达“按 kind 派发”。所幸一个模式匹配宏可以非常优雅地表达这种在不可扩展 kind 集上的算法问题不大不同 kind 本来可以携带不同数据字段但语法树必须用能容纳所有 kind 的通用字段类比单字段的QuoteNodevs. 通用head/args字段的Expr。对只处理单一 kind 的代码这是劣势但对处理多种 kind 的通用代码一个通用但具体的布局反而可能更快。源码中这一设计体现为SyntaxHead(kind, flags)的组合JuliaSyntax/src/core/parse_stream.jl#L36-L57以及 JuliaSyntax/src/JuliaSyntax.jl 导出的head、is_trivia、is_prefix_call、is_infix_op_call、numeric_flags等一批基于标志位的谓词——“谓词极其高效”在这里是字面成立的。与 flisp 参考解析器的差异严格来说flisp 解析器并不完全是经典递归下降它经常回看并修改已经产出的输出树。JuliaSyntax 在可能的地方用 lookahead 取代这种模式因为在“解析器持续发出有严格源码顺序约束的节点流”这种工作方式下回改输出效果很差这类代码让人难以推理。但偶尔它确实能解决 Julia 代码无法用有限 lookahead 自顶向下消歧的真歧义比如括号内kw与的歧义。这些情况下作者选择容忍继续使用look_behind现名peek_behindJuliaSyntax/src/core/parse_stream.jl#L531-L561与reset_node!()JuliaSyntax/src/core/parse_stream.jl#L798-L802注释直白地写着 “This is a hack”这类“回改输出”的手段。代码结构移植时总体上避免了大型结构性改动几乎所有解析产生式production的函数名与 flisp 相同-换成_谓词加is_前缀。显著差异有两处parse-arglist与parse-paren-的一部分被合并为通用函数parse_brackets位于 JuliaSyntax/src/julia/parser.jl。它统一处理括号内,与;混用时 AST 发射的各种边角情况具体包括判断;是块语法分隔符还是关键字参数根据上下文判断是否发射parameter段根据上下文把键值对发射为kw或。parse-resword的进入方式被重排避免在parse-unary-prefix内部的parse-atom里解析保留字改为更早检测保留字并进入parse_resword。flisp 解析器的 bug文档列出了一批“看起来是 bug”的行为其中一些为兼容而被复制可能附带警告宏模块路径允许调用表达式带来奇怪的状态语义b() rand() 0.5 ? Base : Core b().info hi宏模块路径中位置错放如A.B.x被解析成怪异的坏 AST(macrocall (. A (quote (. B x))))理应被拒绝前缀运算符调用在(a;b,c)这类用逗号分隔关键字参数的情况下不工作产出的是元组const/global允许链式赋值但只有第一个绑定是 constconst a b 1这里a是 constb不是花括号内的ncat拼接语法产出奇怪的 AST{a ;; b}解析为(bracescat 2 a b)与{2 ; a ; b}相同按{a b}产出(bracescat (row a b))的类比它本应更接近(bracescat (nrow 2 a b))export a, \n $b被拒绝而export a, \n b正常解析try-catch-finally 中finally允许写在catch之前但总是最后执行“这大概是失误吧看起来非常糟糕”解析[x \n\n ]时 flisp 解析器会混乱而[x \n ]能正确解析为Expr(:vect)“也许在 1.7 修过了”f(x for x in in xs)重复的in竟然被接受且解析结果非常奇怪八进制转义序列饱和而不是报错\777得到\xff与Base.parse(::Type{Int}, ...)不一致以点开头且模块名是运算符的 import 路径如import .⋆被解析成点运算符(. .⋆)而按import .A的解析规则本应得到相对路径(. . ⋆)回看输出时忽略分组括号导致某些情况下结果怪异f(((((x1)))))被解析成带关键字x1的f调用但论起来它也许是赋值十六进制浮点字面量可以有尾部f如0x1p1f但毫无作用。flisp C 代码里这类情况会被当作 Float32 字面量曾有相关 PR 且属有意为之但 Julia 官方从未支持过这一点。该 bug 源于parse-number中(set! pred char-hex?)接受十六进制指数位——其中所有位都被判为非法唯独经isnumtok_base处理后尾随的f幸存索引处begin/end不被当作关键字。带类型的推导式起初与索引看起来相同但要等处理到fortoken 才能区分一旦处理过for把begin/end当关键字就是安全的。参考解析器只在for前有换行时才处理正确Any[foo(i) for i in x if begin true end ]这种写法可行而Any[foo(i) for i in x if begin true end ]则不行。JuliaSyntax 两种情况都正确处理。解析 / AST 的怪癖与毛病warts可疑但被允许的形式存在一些解析器很容易检测、但会留到降低阶段才拒绝的语法。为了构建 DSL这种“先允许”是合理且好的但有些形式即便对 DSL 也用处不大macro (x) end被允许但实际上没有匿名宏这回事abstract type A B end及其他子类型比较被允许但只有A : B有意义x where {S T}产出(where x (bracescat (row S T)))相当怪异[x for outer x in xs]能解析但此处的outer没有实际意义使用它是降低错误。kw与的不一致括号内解析keyval对时kw与的用法存在多处明显不一致点调用内外对元组关键字参数的解析不一致(a1,) # (tuple ( a 1)) f.(a1) # (tuple (kw a 1))调用中,与;混用会产出嵌套 parameter 的 AST解析结果怪异且很难用# (tuple (parameters (parameters e f) c d) a b) (a,b; c,d; e,f)长形式匿名函数的参数列表被解析为元组甚至块而非参数列表这一混乱似乎是在降低阶段被掩盖的。例如function (a;b) end中的(a;b)被解析为block这又进一步加剧了kw用法的不一致。其他怪癖带后缀运算符的解析不总是与不带后缀形式一致不清楚是设计还是失误[x y]得(hcat x ( y))而[x ₁y]得(hcat (call ₁ x y))global const x1被解析器归一化为(const (global ( x 1)))。对 AST 消费者有点用但反转源码顺序在转向无损耗解析器时相当别扭let绑定是否包在 block 里取决于特例# 特例不在 block 中 let x1 ; end # (let ( x 1) (block)) let x::1 ; end # (let (:: x 1) (block)) let x ; end # (let x (block)) # 在 block 中 let x1,y2 ; end # (let (block ( x 1) ( y 2) (block))) let x1 ; end # (let (block ( x 1)) (block))elseif的条件总在 block 里而if的条件不是。推测是 flisp 解析器需要插入行号节点所致if a xx elseif b yy end (if a (block xx) (elseif (block b) (block yy)))import 的点之间允许空格import . .A被允许与import ..A解析相同import A..产出(import (. A .))这基本是无意义的因为.不能是普通标识符raw 字符串的转义规则在字符串结尾附近的反斜杠上极其反直觉raw\\\\ 含四个反斜杠而raw\\\\只有两个。这是为让“所有字符串都可表示”的刻意特性能否改进尚不明确宏调用后的花括号中S{a b}非法但S{a,b}与S {a b}都能解析反过来S[a b]也能解析宏名与宏调用是对parse-atom/parse-call输出的后处理这导致一些惊人且存疑的构造竟然“能工作”(((((a))))) x得到(macrocall a x)这种荒诞结果中缀宏(x y) (macrocall x y)“好吧有点酷还有点奇怪的内在逻辑……但这是什么”括号还可以再嵌套(f(x)) (macrocall f x)宏模块路径允许开头如A.B.x而非A.B.x看起来是不必要的语法变体它使合法宏模块路径的解析更复杂并产生$.x y (macrocall ($ (quote x)) y)这类怪象——$先被当作宏名解析解析到.后才发现它其实是模块名而$在普通 Julia 代码里永远不可能是合法模块名毫无意义三重引号字符串可以当标识符var##被允许。考虑到它要套用复杂的重缩进deindentation规则不清楚这是不是必要的三重引号字符串重缩进在空白不匹配时行为怪异当内容只有空白时\\\\n \n \n \\\的结果是\n \n——中间一行空白没有被缩进而另外两行更长的却被缩进更自洽的做法应是 (a) 中间行完全去缩进或 (b) 所有行只去掉一个字符那才是公共前缀匿名函数参数解析不一致function (xs...) \n body end的参数列表解析为(... xs)而function (x) \n body end的参数列表解析为(tuple x)多维迭代器与扁平迭代器的区别微妙且可能过于宽松[(x,y) for x * in 1:10, y in 1:10]是多维迭代器[(x,y) for x * in 1:10 for y in 1:10]是扁平迭代器[(x,y) for x in 1:10, y in 1:10 if y x]也是扁平迭代器。最后这种情形最令人不安为什么不强制用第二种显式形式表示扁平连 pretty print 都不对julia :([(x,y) for x in 1:10, y in 1:10 if y x]) :([(x, y) for $(Expr(:filter, :(y x), :(x 1:10), :(y 1:10)))])字符字面量可以不转义直接写成而不必用\。与其他解析器/工具的对比与官方 Julia 编译器的关系官方 Julia 编译器前端就在 Julia 源码树中主要集中在少数文件解析器src/julia-parser.scm宏扩展src/ast.c 与 src/macroexpand.scm语法降低src/julia-syntax.scmflisp 运行时与 C 扩展src/flisp外加其他若干.scm/.c文件中的工具函数。参考前端存在两个问题说明重写的必要性不支持精确源码位置而现有数据结构裸 flisp 列表也难以直接扩展出位置信息修复它意味着几乎全部代码都要改它用 flisp 写成——一个美观、极简但晦涩的 Scheme 实现。学 Scheme 确实是理解 Julia 设计灵感的好途径但对 Julia 语言工具开发者是很大的门槛。除社区因素外内嵌 flisp 解释器与运行时自带独立的数据结构和 FFI既复杂又低效。flisp 没有用户级文档非 Scheme 背景者可参照 Racket 文档了解基础概念。与 JuliaParser.jl 的关系JuliaParser.jl 是 flisp 参考解析器的直接移植约在 Julia 0.5 时期被弃养。它不支持无损耗解析而补上该功能相当于完全重写。又因为它自 Julia-0.5 起已与参考解析器分叉作者认为不如直接从参考解析器重新出发。与 Tokenize.jl 的关系Tokenize.jl 是一个快速的 Julia 词法器。其代码被导入并用于 JuliaSyntax并做了一些重大修改见上文“词法分析”小节导入后的实现位于 JuliaSyntax/src/julia/tokenize.jl。与 CSTParser.jl 的关系CSTParser.jl 是一个大致上无损耗解析器目标与 JuliaParser 相近被 VSCode / LanguageServer / JuliaFormatter 生态广泛使用。它很有用但作者觉得其实现难以理解并想以一种全新尝试聚焦以下三点“生产就绪”好文档、测试、诊断与 flisp 解析器最大程度一致目标是把新解析器送进Core吸收 Julia 之外关于可组合解析与数据结构的新思想。特别是rust-analyzer的实现非常干净、文档完善是绝佳灵感来源树数据结构的可组合性树应该分层最底层是一个极轻量的绿色树类似 Roslyn 或 rust-analyzer相比之下 CSTParser 使用更重型的非分层结构。或者以及提供一个公共树 API配多个任务特化的具体实现。作者强调 JuliaSyntax 解析器的一个大优点解析代码与树数据结构完全分离为实验各种树表示形式留足了灵活性。同时作者希望 JuliaSyntax 接管宏扩展与其他降低步骤为核心语言与编辑器工具链提供同一套 API。与 tree-sitter-julia 的取舍用 tree-sitter 这类现代生产级解析器生成器是有趣的选项tree-sitter-julia 已有进展。但作者认为把真实语言边角情况与测试、“辅助代码”的工作量考虑进去后生成器文法的表达力只比手写解析器略高一点。另一方面手写解析器完全灵活且能与参考实现相互印证——JuliaSyntax 因此选择了手写路线。设计笔记原型、树设计与开放问题原型验证方法树数据结构设计颇具难度文档给出的分析框架是编译的符号部分前端对源文本做渐进的抽象与变换但过程中的错误要能回溯源码树必须是无损耗地表示源文本源文本的某些方面注释、大部分空白与解析无关有了表层语法的 AST 之后更多方面变得无关。好例子是2*(x y)里的括号以及2*x与2x中显式与隐式乘法号。存在多种分析analyses增强语法树的方式因用例而异且方法很多分析算法应能作用于任何树类型无视但不丢失它不认识的增强信息。这么多用例暗示“多个不同树类型 公共接口”可能优于“一个大而全的 AST”。作者决定通过原型若干关键工作流来验证语法变换挑一些宏来实现这是混合不同文件源树并保持精确源码位置的基本测试文档注明当时在test/syntax_interpolation.jl中完成格式化重新缩进一个文件测试 trivia 的处理重构一个重命名局部变量的 pass测试“编译管线更深层的信息如何挂到语法树上并用来修改源码”降低阶段的精确错误报告例如对[a, b] (c, d)做语法脱糖应报告“invalid assignment location[a, b]”并附精确源码位置或试一个降低更深层的例子如“macro definition not allowed inside a local scope”增量重解析给定一个字节范围替换重解析源文件。绿色树与 AST 的设计细节GreenNode要求结构上极简——为了效率与通用性不可变——为了效率与线程安全完整——为了保留解析器知识token 无关token agnostic——以支持任意源语言。最简方案是叶节点就是单个 token子节点按源码顺序。call的表示是 AST 与绿色树之间节点放置/迭代的难点中缀运算符 vs. 普通前缀函数调用。典型问题是a 1vs.(a, 1)更糟的是a 1 2vs.(a, 1, 2)。显然在 AST 的接口层需要抽象掉这种放置差异例如采用类似标准 Julia AST 的迭代顺序。设计新 AST 之所以棘手是因为与大多数语言不同现有Expr是每个宏扩展都在用的公开 API用户宏扩展插在源文本与降低之间且使用Expr会在很多方面丢失源码信息。文档列出几条可能的出路给Expr增加一些半隐藏字段指回Expr或其args来源的绿色树节点宏扩展期间沿用现有Expr然后在宏扩展后用启发式恢复源码信息——正确的卫生性hygiene或许能帮忙若新 AST 只对某种假设的“新式宏”开放opt-in也是可能的。修好卫生性应当与之配套。设计挑战字面量需要携带源码位置时如何让表达式操作保持合理一个可能的过渡方案是为少数需要的字面量类型提供包装SourceSymbol : AbstractSymbol SourceInt : Integer SourceString : AbstractString给符号附上源码位置或许能解决大部分卫生性问题。宏辅助函数使用符号字面量的问题仍在——总不能改变:x的语义一个思路是尝试在插值语法所在处捕获当前模块。例如:(y $x)在降低时展开为Core._expr(:call, :, :y, x)或许可以展开为类似Core._expr(:call, :, :y, _add_source_symbol(_module_we_are_lowering_into, x))错误恢复的进一步思考文档记录了若干“不太有条理”的恢复思路。不同类型的错误似乎包括不允许的语法如条件表达式缺少空格可以继续解析给节点打上错误标志后照常发出一个完整节点。某些情况下如中缀表达式尾部缺失发射一个零宽错误 token就能让上层产生式不必参与恢复就得到完整解析树当前上下文不允许的 token如parse_atom里的或中缀表达式内的闭合 token这里可以发出Kerror但无法继续深入解析树——必须弹出多个递归帧。“棘手”典型产生式结构如下function parse_foo(ps) mark position(ps) parse_bar(ps) # What if this fails? if peek(ps) Ksome-token bump(ps) parse_baz(ps) # What if this fails? emit(ps, mark, Kfoo) end end“missing end”问题更棘手因为中间语法都是合法的往往要到 EOF 才暴露问题function f() begin a 10 end # -- Indentation would be wrong if g() was an inner function of f. function g() end理想的恢复在这种情况下需要回溯弹回到正在解析f()的帧回溯解析事件直到找到缩进与父级嵌套不匹配的那个 function把 ParseStream 重置到调用g()之前的解析检查点发出错误并退出f()的解析重新开始解析想办法保证这一切不会导致无限递归 嵌套结构中缺逗号或缺右括号同样是难题。本地缩进有时能讲故事f(a, g(b, c # -- missing comma? d), e)f(a, g(b, c # -- missing closing ) ? d)但并不总是f(a, g(b, c # -- missing closing , ? d))当前体系里对诊断格外困难的问题还有字符串插值中破损的括号或双引号尤其是嵌套插值时。外部灵感Roslyn、rust-analyzer 与 RSLint设计文档的“Resources”部分记录了作者从工业界编译器项目中借鉴的设计C# Roslyn红绿树red-green trees的持久化与外观façade模型是绿色树术语的来源rust-analyzer与 JuliaSyntax 的思路最接近独立得出“绿色树布局 显式 trivia 节点”的结论。值得注意的是它其实有三棵树绿色树设计上与 JuliaSyntax 几乎完全相同包括 trivia 存储方式不过其团队当时仍在讨论改用 Roslyn 式 trivia 模型非类型化的红语法树类似但极简例如不尝试重排子节点类型化 AST 层每种表达式 head 一个类型其 AST 通过每次动态遍历子节点列表来查找子节点而不是依赖一个规范顺序或记住解析器已知的子节点位置。另外“解析器看不到空白节点空白在 TreeSink 层挂到树上”——这对 JuliaSyntax 有参考意义把空白挂到“有意义”token 上既麻烦又低效“实践中对 IDE 用途而言增量重解析其实没那么大意义从头解析已经足够快”作者还半开玩笑地问那为什么还实现了增量解析以及若干关于宏的评论——Rust 宏扩展与 Julia 差异很大看起来宏扩展可能与解析交织进行。 作者总结不确定 Julia 是否想要类型化 AST且必须正视Expr是既有公开接口这个事实——Expr2包装SyntaxNode是否可行RSLint基于 rust-analyzer 同一套解析基础设施与绿色树库的 JavaScript linter在大致共享这套架构下出错时回溯并重启解析器其实很简单——“事件流允许我们通过清空事件、把 token 源游标重置回某处来廉价地回溯解析器”其“错误恢复”章节讨论了多种恢复策略值得参考。诊断系统C 提案论文《P2429 - Concepts Error Messages for Humans》虽以 C 为中心但评审了 Elm、ReasonML、Flow、D、Rust 等编译器的错误报告质量Rust 侧则有rustc_errors::Diagnostic类型、诊断系统源码包括宏如何发出诊断、rustc_parse的diagnostics.rs可作参考。解析通识matklad 的《Modern parser generator》博文对手写解析器有大量实用建议鼓励把测试写成行内注释、Pratt 解析器用于运算符优先级、错误恢复讨论关于“解析 shell 风格字符串插值的状态词法器”oilshell 的一篇博文有相关笔记。有趣的研究性议题文档最后留下两个开放研究方向解析器恢复能否让解析器在遇到破损语法时学习快速且足够准确的恢复启发式而不是手写如何组织解析器使训练可行、模型注入又不侵入如果模型内嵌并与解析器协同工作能否让它足够紧凑使训练快速、模型本身极小格式化给定源码与语法树能否从语法树回归/学习一个缩进的生成模型源码格式化需要一堆“看起来好看”的启发式而机器学习系统恰好擅长启发式而且我们有海量训练数据——只需挑一些高质量、品味良好的手工格式化库即可。小结与源码导航JuliaSyntax 的设计可以概括为一条主线用与树结构解耦的ParseStream事件流做递归下降解析产出后序遍历的绿色树再按需用build_tree装配出无损耗的GreenNode、带源码位置的SyntaxNode或兼容用的Expr错误恢复通过补占位符与收拢Kerror节点保证输出永远是良构树。这一设计既继承 flisp 解析器的产生式结构以保证兼容性又在精确源码映射、版本兼容与可测试性上全面超越。想继续深入可以从这些仓库路径入手内容路径设计文档本文依据JuliaSyntax/docs/src/design.md模块入口与公共 APIJuliaSyntax/src/JuliaSyntax.jlParseStream、RawGreenNode、bump/emit/诊断JuliaSyntax/src/core/parse_stream.jl词法器改造自 TokenizeJuliaSyntax/src/julia/tokenize.jl递归下降解析器与parse_brackets等JuliaSyntax/src/julia/parser.jlparse!/parseall/parseatom/parsestmtJuliaSyntax/src/julia/parser_api.jlGreenNode与build_tree(GreenNode)JuliaSyntax/src/porcelain/green_node.jlSyntaxNode与build_tree(SyntaxNode)JuliaSyntax/src/porcelain/syntax_node.jlExpr转换目标JuliaSyntax/src/integration/expr.jl解析器行为测试含整包解析JuliaSyntax/testparser.jl、green_node.jl、syntax_node.jl、parse_packages.jl、fuzz_test.jl等旧 flisp 参考前端对照src/julia-parser.scm、src/julia-syntax.scm、src/macroexpand.scm、src/ast.c、src/flisp适用前提说明文中对当前代码行为的描述以本仓库JuliaSyntax/Project.toml 中标记为2.0.0-DEV兼容 Julia ≥ 1.0的实际代码为准设计文档部分表述反映的是设计阶段的方案例如树类型数量个别细节如SyntaxTree的引入已由后续代码演进扩展本文已按“从源码结构看”加以标注。【免费下载链接】juliaThe Julia Programming Language项目地址: https://gitcode.com/gh_mirrors/ju/julia创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
