ardentsia-cgs/kparser 源：https://github.com/ardentsia-cgs/kparser # kparser CI（https://github.com/ardentsia-cgs/kparser/actions/workflows/ci.yml） codecov（https://codecov.io/github/ardentsia-cgs/kparser） 许可证：Apache 2.0 一个针对 K 编程语言的小型、可读的解析器。单个 C 文件，包括注释约 570 行。它是一份教学参考——其任务是让 K 的语法清晰易读。这里没有求值器。解析器从 REPL 读取 K 源代码，并以 lisp 风格的嵌套列表形式打印出生成的 AST。一旦你能看到 2+3 变成 (+;2;3)，1 -2 3 是一个向量而 1-2 是减法，以及 lambda、副词和索引都复用相同的形式，那么 K 的其他部分就不再神秘了。

快速开始

make
./kparser

你会得到一个双空格提示符，每行输入对应一行 AST。Ctrl-D 退出。make test 运行一个黄金测试套件（tests/run.sh + tests/cases.tsv），涵盖扫描器、解析器和打印机的每条路径。

2+3
(+;2;3)
a:b:42
(:;`a;(:;`b;42))
1 -2 3
1 -2 3
+/1 2 3 4
((`/;+);1 2 3 4)
{x+y}
(`{;(+;`x;`y))
f[1;2]
(`f;1;2)

语法

K 拥有所有编程语言中最紧凑的语法之一。取自：

E : E ; e | e         // 分号分隔的表达式
e : nve | te | empty  // 二元、并置或空
t : n | v             // 项是名词或动词
v : tA | V            // 动词基，或带有副词的项
n : t[E] | (E) | {E} | N  // 名词基，或带有索引的项
A : ' | / | \ | ': | /: | \:
V : : + - * % ! & | < > = ~ , ^ # _ $ ? @ .（可选地 + ':'）
N : | (s) | (s)

这五条产生式就是全部结构化语法。所有 K 程序都通过它们解析。

读取 AST

每个解析后的表达式变成一个嵌套列表，其中头部（head）是对剩余部分进行运算的元素。解析器生成的五种形式：

叶子值来自 K 的类型系统。此解析器中有五种类型：

这就是整个类型表面。浮点数、字符串、十六进制——任何会扩展类型系统的东西——都故意不在范围内。

一个值得注意的细微点：x（名称）和 `x（字面符号）都是 sym 类型，但 x 是原子，而 `x 是单元素向量。打印形式中的前导 , 是用于区分它们的“enlist”标记。K 的类型代码（原子为负，向量为正）也在做同样的工作。

这种 lisp 风格的形式不仅仅是看起来整洁。因为它是前缀形式且完全括号化，K 所做的每一个分组决策——从右到左的顺序、哪个动词是单目、参数列表在哪里结束——都变得明确，无需推断优先级。2*3+4 对有优先级习惯的人来说读起来有歧义；而 (*;2;(+;3;4)) 则不可能被误读。实际上，它就像是 K 简洁的表层与 Lisp 风格 S 表达式之间的罗塞塔石碑——后者经过几十年的发展已变得无处不在——这也是为什么将解析树交给一个推理 K 表达式含义的工具是有用的原因之一。但它是一种阅读辅助工具，而且是一种狭隘的辅助：最适合查看单个片段是如何分组的。深度嵌套的树本身需要仔细阅读——这种形式在浅层片段中发挥作用，但随着嵌套加深，其价值会逐渐消失。

代码布局

该文件从上到下连续阅读：

1. 分配辅助函数（die、xmalloc 等）——包装标准分配器，带有 OOM 中止，因此解析器无需在每个函数中传递错误返回。
2. K 结构体——运行时值类型，原子和向量存储的带标签联合体。t 是类型代码，r 是引用计数，G0[] 是用于向量数据的灵活数组尾部。
3. 构造函数（ki、ks、ktn、klist）——创建各种 K 值。
4. 引用计数（inc_ref、dec_ref）——每个 K 对象创建时 r=0（一个隐式所有者）。dec_ref 在 r=0 时释放，并递归进入容器类型。
5. 动词表——根据它们在 VERB_CHARS 中的位置索引的基本动词。函数指针数组是存根；求值器会填充它们。
6. 打印机（print_k）——以上述 lisp 风格形式输出 AST。
7. 扫描器（scan）——单次正向传递，构建带有 K 对象的词法单元。
8. 解析器（parse_E、parse_e、parse_term、parse_base）——每个非平凡产生式对应一个函数。如果你想理解 K 的语法，这部分是必读的；每个函数清晰地映射到一条产生式规则。
9. REPL（main）——fgets 循环。

设计笔记

一些费心思考的决策，如果你想知道原因的话。

负数与减法

- 是有歧义的：它可以是二元减号（a-b），也可以是字面上的符号（-1）。规则如下：

如果前一个有意义的词法单元是动词、副词、左括号（(/[/{）、; 或输入开头，那么后跟数字的前导 - 就是符号。否则它就是动词。

因此 a-1 是减法，a:-1 是将 -1 赋值给 a，而 1 -2 3 是一个三元素向量。扫描器跟踪一个 noun_pos 标志，以单次传递确定每个 - 的含义——无需回溯。

两阶段：扫描器直接构建 K 对象

初版中，扫描器发出“带有解析载荷的词法单元”，解析器再将其转换为 K 值。这意味着每个名称被复制两次（strdup），每个整数向量被分配两次，每个符号被复制两次。现在，扫描器直接构建 K 对象并存储在词法单元上；解析器只需取出它们（并将槽位置为 NULL，以便统一清理）。分配流量减半。

动词默认为二元，在 AST 构建时降级

裸 + 解析为二元动词（类型 KV2，代码 102）。当动词处于一元位置时，parse_e 中的 te-with-verb-head 情况会构建一个新的单目动词（KV1，代码 101）——因此 +1 变成 (+:;1)。不修改 K 节点；降级形式是一个新节点。

通过项的角色（而非词法单元）选择 nve vs te

e : nve | te 归结为一个问题：在名词之后，下一个项是否是动词？单个词法单元无法回答这个问题，因为项的角色不取决于其首字符——{x+y} 是名词，但 {x+y}' 是动词；f 是名词，但 f' 是动词。因此 parse_e 解析下一个项，并根据其角色（R_NOUN/R_VERB）进行分支，而不是预读下一个词法单元。这保持了预测性和线性：当没有项时，parse_term 不消耗任何东西，因此单项前瞻是免费的且从不回溯。其回报是副词派生的动词可以在中缀位置工作——1 2 f' 3 4 解析为 nve 形式 ((`';`f);1 2;3 4)，而不是并置。

投影和组合是涌现的，而不是语法上的

K 程序员视为不同特性的两件事——投影（固定函数的部分参数）和组合（链式函数）——没有自己的产生式。它们由其他所有内容使用的相同 t[E] 和 te/nve 形式自然产生，因为语法与元数无关：它构建应用树和并置树，从不询问动词需要多少个参数。一棵树是应用、投影还是组合，这是求值时的解读，一旦你知道动词的价数就能确定——这正是动词表存在但在解析器中保持为空的原因。

投影是缺少参数的应用。K 用其通用空值 :: 标记空位——值得注意的是，并没有单独的“缺失”类型：通用空值（单目冒号，KV1 索引 0）就是空位。参数位置的空 e（e : empty 规则）变成 ::：

2+        -> (+;2;::)          二元 + 的右参数省略
f[1;;3]   -> (`f;1;::;3)     中间参数省略
f[;2]     -> (`f;::;2)       左参数省略
f[]       -> (`f;::)          f[] 即 f[::]

注意 :: 与 () 不同：() 是空列表（名词），而 :: 是填充省略槽位的通用空值——因此解析器将它们区分开（空位替换仅在 t[E] 参数列表和 nve 空操作数情况下发生；空 (E) 保留为 ()）。求值器会统计非 :: 槽位数量，与动词的价数比较；太少意味着“返回一个等待剩余参数的函数”——即投影。没有新的节点，没有新的类型，只是在普通的应用树中填充了通用空值。

组合是并置（te），其中项和表达式都是函数，而不是函数与名词：

|+        -> (|:;+)          反序在上，加号在下
*|+       -> (*:;(|:;+))     右关联的动词序列

这与 f x 应用的 (t;e) 形式相同——唯一的区别是 e 解析为名词（应用）还是动词（组合），这同样需要价数来确定。te 分支的降级中有一个细微之处：裸动词头降级为单目（+* → (+:;*)），而括号括起来的则不会（(+)(*) → (+;*)，因为 (E) 产生名词类型的项）。解析器承诺采用应用解读；真正的 K 运行时会根据元数重新审视这一点。

要点是整个语法的核心：K 的表层很小，因为投影和组合不是新的语法。它们就是五条产生式在意识到价数的求值器下的已有含义。解析器的工作是得到正确的形状，然后停止。

Lambda 标记使用符号 `{

对 {x+y} 的包裹列表是 (`{; (+;`x;`y))。使用符号（而不是发明新类型）保持了类型表面的精简。真正的 K 运行会用实际的闭包值替换这个标记；对于解析输出，符号就足够了。

Lambda 具有固定的形状 —— (`{; body)，其中 body 是单个表达式。多语句主体就是该表达式为一个序列（下一点）：{a;b} 是 (`{; (`;; `a; `b))。这比将语句直接展开在 `{ 下更整洁，并且意味着无论主体是一个表达式还是多个，求值器都统一读取主体。

语句序列是符号 `;，区别于列表

; 扮演三个角色，由容器区分。在 (E) 内，它构建列表字面量（每个元素都保留）；在 t[E] 内，它分隔参数；在顶层或 {} 主体内，它对语句进行排序——求值每个，返回最后一个。前两者已经有头部（括号列表没有头部，应用有函数），但裸语句序列没有头部，因此无法与列表区分：

1;2;3   (`;;1;2;3)   // 序列：全部执行，值为最后一个
(1;2;3) (1;2;3)        // 列表字面量：三个元素

因此，两个或更多语句的序列被包裹在符号 `; 下（单个语句折叠为其自身，就像 (E) 只有一个元素时一样）。`; 只能是这个标记 —— ; 词法分析为分隔符词法单元，绝不是名称 —— 因此，就像 `{ 一样，作为头部是没有歧义的。转换发生在单个辅助函数 seq_of 中，应用于两个序列上下文（run 中的顶层程序和 lambda 主体）；列表和参数上下文保持不变。

无区域的引用计数

每次解析，对于典型输入，大约分配 190 个 K 节点。dec_ref 在每个 REPL 行结束时遍历 AST，这是正确且足够快的。区域分配器可以减少分配时间，但解析器并非受分配限制 —— 添加求值器时才是考虑区域分配的正确时机。

括号匹配是调用栈，而非计数器

解析器不保持括号深度计数器。在递归下降中，调用栈就是计数器 —— 每个嵌套层级对应一个 parse_E —— 因此唯一需要的规则是每个层级遇到它期望的终止符：括号层级遇到其右括号（)/}/]），最外层遇到输入结束。一个单行的 expect 辅助函数强制执行右括号；run 在顶层解析后断言 T_EOF。缺失右括号或多余的右括号都是硬性 die，与解析器其他部分一样快速失败：

1+(
kparser: expected ')'
1+)
kparser: unexpected token

这与故意填充空位无关：f[]、f[;2] 和 2+ 是平衡的，因此它们的省略槽位仍变成 ::。只有真正不平衡的输入才会出错。（更丰富的消息会指明出问题位置，使用下面“源位置错误”中列出的 start/len 机制。）

缺失的内容

大致按添加每项所需工作量的顺序排列：

• 浮点字面量（1.5、1e10）和浮点向量——对 scan_int 和 K 类型集的小扩展。
• 字符串字面量（"hello"）——转义处理，新的 K 类型。
• 十六进制字节向量（0xff）——单独的扫描器分支，新的 K 类型。
• 源位置错误——词法单元已经携带 start/len，因此这只是个管道问题。
• 求值器。动词函数表已经定义大小并命名，但为空。

下一步：ksql（第 2 步）

KSQL.md 是一个后续内容，它为这个解析器扩展了 K 的 SQL 方言——select / exec / update / delete ... by ... from ... where ...。令人惊讶的是开销很小：查询实际上是第四个名词基（n : t[E] | (E) | {E} | N | q），它脱糖为你已经拥有的应用形式 (`verb; t; c; b; a)。别名（qty:sum amt）根本不需要新的语法——它们就是现有的 : 赋值。第 2 步的代码位于 ksqlparser.c（kparser.c 加一个约 120 行的 ksql 层）；使用 make ksqlparser 构建，使用 make test2 测试。

下一步：SQL（第 3 步）

SQL.md 更进一步，展示了标准 SQL——或者说是它的一个小型查询子集（SELECT/UPDATE/DELETE，不含 DDL/DCL/TCL）——可以针对相同的 AST。SELECT * FROM t 解析为与 ksql 中 select from t 完全相同的树 —— (`select;`t;();();()) —— 因为 *（“所有列”）脱糖为 ksql 的空短语列表。关系核心（SELECT/FROM/WHERE/GROUP BY）一对一映射到 (verb; t; c; b; a)，而 SQL 的关系后子句（DISTINCT/ORDER BY/LIMIT）将查询包装为普通的 K 动词——SELECT a FROM t ORDER BY x LIMIT 10 就是普通 K 的 10 # `x asc select a from t。两种语言通过运行时的模式（--sql/--ksql，或在 REPL 中 \sql/\ksql）选择；SQL 需要而 K 没有的是运算符优先级，因此它有一个小型的优先级爬升表达式解析器。第 3 步的代码位于 sqlparser.c（ksqlparser.c 加一个 SQL 层和模式切换）；使用 make sqlparser 构建，使用 make test3 测试。

附录：ksimple 的语法

KSIMPLE.md 走向另一个方向：它从 Arthur Whitney 的 ksimple（https://github.com/kparc/ksimple）中提取隐式语法，这是一个约 100 行的学习用解释器，没有解析器——词法分析、解析和求值融合成一个递归函数，作用于单字节词法单元的磁带。它归结为五条产生式，并且只保留了使 K 成为 K 的两个想法（无优先级的从右到左；从左上下文确定元数），同时放弃了所有结构（(E)、{E}、t[E]、;）。

为什么手工编写？

对于五条产生式，解析器生成器主要是开销——但这是简单的答案。更有趣的原因是，K 的词法分析器才是难点所在。语法本身很小且统一；词法分析在三个地方依赖上下文，而大多数解析工具都假设这三个地方不存在。（值得注意的是，生产级编译器——clang、rustc、GCC 的 C 前端——出于类似原因都采用手工编写的递归下降：与周围的语义机制相比，语法相对较小，而