Share

绝句程序设计语言『词法定义』

😏中文编程也真是可怜。懂的人对它嗤之以鼻，一提到立刻说它是 肤浅、表面 的，偏偏是完全不懂和半懂不懂的人稍微有点或空无一物或半通不通的『实践经验』 不知道是不是和之前的『汉芯』一样，因为易语言的4kw坏了名声？呵呵呵……但不管怎么样易语言的确是广为诟病了。

绝句言者，编程之美。

绝句是一门面向对象+函数式程序设计语言，它基本是扩展自Kotlin，有类型推导、类型可空性、闭包(closure) 和高阶函数、扩展函数和属性、生产消费者型变性标记、值代理、面向对象混入(mixins) 等特性，此文档的描述目标是版本0.1。

构词分『软、常、苛』三种。

非角括名字被称为『白名』如 甲、蝴蝶、someVar，而非 『某甲』、『someVar』

其中，软构词可以作为名字、常构词不能作为白名，苛构词不能作为白名的起始部分

绝句文法层次：常量(literal)、言元(atom-expression)、言(expression)、句(statement)、段(block)， 体(body)、构(structure)、书(file)

绝句面向对象结构层次：类(interface)、物(class) 造于(constructor) 初(init)、例(object)、事(fun)、量(val) 取者(get)、变参(var) 置者(set)

关于函数式的 :: 语法：

fun <T> fx(f: (T, T) -> T, x: T): T = f(x, x)
fx(Int::plus, 1)

对 :: 来说 某我.(参1、参2、余)返 也可视为 (某我、参1、参2、余)返 实现。

关于「包」命名空间化定义引用：

一个文件只可定义一个包、包(名:复名)为 不强求在特定路径的文件中定义，只要复名匹配即可引用（但编译器器应该告警）。

包 某年.『三月』.『二日』 为 “应该在 某日/ 文件夹中，而其父文件夹是 某月/，又父文件夹是 某年/”
引 某事 “使用这种简写法来引用 某年.『三月』.『一日』 包中的构件”

若 引、引全、引记法 的目标名部分没有用「复名」，则表示引入此包上一阶（复名的最后一个「.」前）包里名为彼的事物，而使用 引(复命)的(名)、引全(复名)的(名) 类似 Java 1.5 的 import static。

绝句为所有文件默认引全 绝句.额联、绝句.区间、绝句.集合、绝句.读写、绝句.文本、绝句.标记。

构词(keywords)

普通构词一般为 常构词

我属(Self) 和 断止(Nothing) 都不能被 属别名 别名。

「你」是绝句的第二人称文法，除了外还有第一人称的「我」「亲」、第三人称「它」。

直接用法有两种：你(言)…… 作用域混合、你(言)a@(且|或) (中缀链) {a 中缀链} 如 你duangsuse，名字是"duangsuse"且年龄是18。、你duangsuse的年龄且存于年轻人且存于老年人

此外，对用户里的你…… 也是可用的，「若(你且/或)」「重复若(你且/或)」，当然「对…里的你……」皆可执行「作用域混合」，不过「对…里的你……」中引用可不带主语「你」

关于「你」第二人称文法的相关顾虑

不过「对…里的你……」中引用可不带主语「你」

这实际上就是给语言引入了一个不一致的特性，之前支持「若你」是为了一致、现在不想支持也是为了一致。 为了更类似于自然语言上应该是必须支持的（而且对于自然语言这样的表达有准确性），这种写法我预计也会比较常用，也不是很麻烦。

但就语言定义上来看，它是不太容易理解的，不是很清楚是否该加。#PL #jueju

对了，为什么不把这个 不过 「对…里的你……」 中引用可不带主语「你」 的特化处理给去掉呢？反正去掉也不会使得代码更难看啊！这样不就一致了吗？「你」就像是对表达式的一个标签，不存在作用域处理上一致性的问题。

……可那样 对…里的你 和 对…里的…… 还有什么区别啊？？？那就只能删掉这个用法了…… 唉

其实 对…里的你…… 也是有语言一致性的，因为「你」本身就代表作用域混合。

可是我们不能让

“……”
  若此人之曾杀人，杀(此人)。
  若你此人或之曾伤人或之曾盗窃，此人去抵(“此人的”罪)。

这种代码通过啊？！

这绝句越设计越像自然语言了，可这……真的没问题么；我感觉第二人称文法是个潘多拉盒子，支持了指不定会怎么样。

这么说吧，其实这个选择也就是绝句是走「倾向自然语言」还是「倾向更规范的编程语言」的区别，也就是设计的分岔路。

不错，其实绝句完全可以不多作考量就立刻以我上面那个折衷法立刻准备加入正式设计的，可我觉得还是有点问题需要讲明白。 这个语法，它不像 尝试…成…… 那样，它是无可替代不能删除的，绝句里没有任何其他方法可以直接代替它作为表达式的位置，因为它一是在汉语言里属于对语言表达有极其特殊地位的构词而不应该在任何情况下作为名字的起始使用，二是它可以使得 a > 1 && a in xs 这种表达式更好描述，绝句里也有类似的并例（例如「」叫括号的中缀简记）。

就绝句未来而言，我觉得我的看法和 Matz 是一样的，不能把语言设计得太『简单』或过分数学、过分强调语言理论准确性，我不希望绝句成为『中文编程』领域的Scala（的确我也没那个水平），但是我觉得『自然』也是有限度的，不能没有章法。

第二人称文法其实本身就是一种会扰乱语言表达规范性的特性，支持它可以让语言对程序的描述更直白、更自然，有很大的积极作用，唯一的问题是——它是对作用域定义的扩充，利用它可以写出莫名其妙的程序，而绝句不可能检查这种情况，因为首先它们本该符合语法，其次这种检查是吹毛求疵的行为。

下面有相似的三个例子。

对此办公室里的你，
  若年龄不大30且头衔是总监，说(你的名字)。

这是正常情况，也就是我觉得有必要加入此语法的理由。——况且这的确是很常见的一种模式（当然 Kotlin 也可以用 E.() -> Unit 模拟，可为了一致性最好还是加上，而且那样就没有第二人称「作用域混合」了）

上面的『名字』『年龄』，很自然就能知道是指『存于办公室的某人』。（这里不提里面有很多行代码的情况，绝句里还能写很复杂很多行纯属编程方法有问题）

对里的你(办公室) { if (年龄<=30 && 头衔==总监) println(this.名字) /*注意这里就和第一人称的this混淆了，没法直接引用外层的this*/ }

Kotlin 的写法类似以上

对此办公室里的你，
  若甲君的名字[0..1]是名字，说("啊，${名字}你和${甲君}是一家的啊？")。 “开个玩笑”

这种情况，就没那么容易想出『名字』是指谁的名字了（甚至会与名字作为一类事物的情况发生混淆），或许说，对于以上代码可以调整「是」的语序修改，可我之前说过，严格的好语言不应该可以写出烂代码，那往往是设计思虑不够深刻导致的。

对零食区里的你，
  取色笔去取色(外封)令为，说("$它 $口感")。

这里就更明显了，我们引入了一个块，谁能一眼看出『口感』是指『存于零食区的某物』的口感？？？

……我觉得暂时还是支持吧。毕竟这个语法虽然让绝句不是那么『严格』了，在中文表达里它也是有价值的，而上面举出的问题程序其实本身以中文的视角看都是语素残缺、逻辑错误的，或许能够以中文的思路看绝句程序会有利于代码质量的提升。

我觉得，既然都无法确定的话…… 那还是用 plan C 好了，去掉 对……我 的特殊对待，这样虽然看起来有点弱智但不至于弄乱整门语言。 对应地，「你」的『文言式作用域混合』也就是『你(言)……』的情况…… 还是保留吧。

对此办公室里的你，
  若你的年龄不大30且你的头衔是总监，说(你的名字)。

事 严正执法(此人：人) 为 “用起来不自然但这只是例子”
  若此人之曾杀人，杀(此人)。
  若你此人或之曾伤人或之曾盗窃，你去抵(你的罪)。

这样看起来一致性就好多了，「你」后面跟的 都是「你的」「你去」。

中缀构词(infix keywords)

作为中缀的构词都是 苛构词

「不」是一种中缀简修饰，也是语言里唯一的中缀简修饰。

1不大2 代表 Kotlin 的 (1>2).not() 也即绝句的 非 (1大2)、(1大2)去取非()

运算符优先级

a+(b*c)，(*) lessThan (+) 降序优先结合

以下定义基本是从 Kotlin Grammar 处誊写，可能有少许变动

注意绝句里的访问也是一种运算符，但「：」语法，（后缀）label并不被认为是参与表达式链的东西，若是则它有最高的优先级。

下文 . 表示可能有一些空格。

绝句支持具名调用(named call)，但赋值不是表达式

绝句因为有『取置』抽象和「」中缀链不需要 +=、-= 这种简记赋值（x令置为「+a」、i令置为「它后」 即可）

但依然有 inc(后继)、dec(前驱) 算符，即便它没有特定的运算符语法支持

类似 Kotlin 的 get/set/invoke，绝句的 取值、置值 实现了 a[i]、a[i] = x 的语义，绝句的 用 则实现了 f()

「」 可以被用来描述 「它后」、「它+1」、「此行加入它」 这样的中后缀链

修饰符(modifiers)

修饰符以 甲、乙的(构) 形式应用到文法结构， 作为修饰符的构词都是 常构词；【】扩住的记物实例是一种 普适 的修饰符

可见性、可覆盖性

抽象、待例物|事|量|变参

对 变量|事|参数 有区分

简修饰符(trivial modifiers)

简修饰符直接应用到目标构件，无须加「的」

泛型参数 生产消费位置(producer-consumer position) 和 型参实化(reified) 修饰 刻意没区分是『泛型型变』还是标准类型参数

属名 苛，用于定义变量。架构器参数列表中不可使用「变」修饰，以免与参数默认值混淆

控制流构词(control flow keywords)

控制流构词一般是 苛构词

控制流循环：

注意点：

绝句比 Kotlin 更不 倾向于表达式风格，因为记法和函数、『取置』抽象已经足够

常名(predeclared)

带作用域标记的常名「我」「亲」可带 [] 指明具体引用目标，「它」不可带

在「扩物」和「方法属」(Kotlin 的 T.() -> *) 以及「内物」「值例」(Kotlin 的 anonymous object) 上，「我」可能有多种引用目标，默认是最内层的「我」

类似 Kotlin，对多超类混入式继承名字冲突的情况也有办法，使用 亲<T>[位置] 或 亲[位置] 来指定使用某类版本、不同域里的「亲」的成员

常量(literal)

部分词法规则

谁知道呢，反正这不是最终版文档

绝句 0.1 的保留字

以下保留字都是常构词

一些废弃的历史设计

关于汉字数字开头的问题

觉得绝句不允许写 三月、三个人 这种名字很…… 不知道该怎么说？

或许 三十一、二 这种数字形式根本不该出现？

可是…… 我觉得 一行(a、b、c) 不如 行一(a、b、c) 明确啊，如果允许可能出乱子，为了一致最好还是不许的，汉字一般不把『五个人』当名词用的。

绝句里名字一般就是汉语里作为名词的东西，就许多『英文编程语言』来看，为了区分 也是不允许 1st、5items 这种命名的，即便那是为了区分数字形式方便人类阅读的原因。

可以不支持汉字数值，但我还是打算继续使用 元二、元三 这种名称而不是 二元、三元，就是为了用起来直白，如 回元二(a、b)、量提 (甲、乙) = 元二(x0、x1)，如果彻底改过来好像也没什么问题，但总感觉留着更好，不止因为这样看起来『文绉绉』一些。

常见类型(built-in types)

和 Kotlin 类似但更严格，绝句的『断止』被任何取值处使用时都需要显式写出其类型(甚至于非「量」「事回」处也要显式注明「作」)。0.1版可能不能包括类型系统相关特性。

对何<值者>其中 值者：值 皆有
扩物 取置<值者?> 为
  事 置空() 为
    我去置为(空)
  事 说值() 为
    说(取值())

forall T where T: Any theres
extension Modifible<T?> where
  fun makeNull() where
    this.set(null)
  fun printValue() where
    print(get())

泛数(泛化数值)

常见介词

方法名草记

入门教程设计

第一版

第二版

示例

私下的事 说作者(名：文) = 说("作者：$名")

事 『诵《江南》』() 为
  说作者("汉 无名氏")
  说("江南可采莲，莲叶何田田，鱼戏莲叶间。")
  量 位置 = 行一<文>("东"、"西"、"南"、"北")
  对位置里的方位，说("鱼戏莲叶${方位}")。

例 云一诗：应用程序 为
  实现的事 入口() 为
    说("诗云《江南》为")；『诵《江南》』()

“诗云《江南》为
作者：汉 无名氏
江南可采莲，莲叶何田田，鱼戏莲叶间。
鱼戏莲叶东
鱼戏莲叶西
鱼戏莲叶南
鱼戏莲叶北”

引记法 绝句.额联 「令为」

事 階乘(甲：数)：数 为
  若甲是一，回一。
  否则，
    量 乙 = 甲-1
    量 丙 = 阶乘(乙)
    量 丁 = 甲去乘(丙)；回丁
事 入口() 为
  阶乘(5)令为(::说)

断续的事 后继节点(e：节点) 为
  变节点 a 初e
  重复，回交(a)、a = a的下一项。当a不空。 “不空是一种后缀记法”
对何<项>皆有 扩物 可迭<项> 为
  断续的事 取前(取：命题<项>) 为
    对我里的，
      若取(它)，回交(它)。否则，停下。

事 启用代码过滤(id：元素名) 为
  量 基div = 文档去取(id)
  量 码div = 文档去取("$id-code")
  “当然也是记法，内联物+记法+扩物”
  码div的HTML代码 = "<button>显示 ${id} 的代码</button>"
  “当然绝句可以有更简洁而且检查更多的DSL”
  码div的子素[0]的点击监听 = 函数，码div的HTML代码 = 滤出代码(基div)映为(::HTML代码)以("<br>")拼合。

事 滤出代码(e：元素) 为
  量 全后继 = 后继节点(e)
  量 此部分 = 全后继去取前(::部分未完)“的”
  量 受用项目 = 此部分去滤出，接受类列表(它的类列表)。“的”
    “此部分去滤出(::接受类列表) 也可以”
  回受用项目
其中，
  事 部分未完(e：元素) = e的类列表?去试存("literate-end") 空则否
  事 接受类列表(classes：元素) = "language-kotlin"存于classes

“杀人者死，伤人及盗抵罪。”
引记法 绝句.符号 「之」

事 严明执法(此人：人) 为
  若此人之曾杀人，杀(此人)。
  若你此人或之曾伤人或之曾盗窃，你去抵(你的罪)。

一些辅助的设计草稿

Bool Num Char Str Ary Object Function Error

封装、抽象、继承、多态(子类型多态、参数化多态、特殊多态(函数重载、类型转换多态))

形式化文法

介于为定义文法，引入某种泛向的 形式化语言(formal Language) 和 一堆知识点 会让人难以理解，下面约定一种相对简单的形式化文法描述方法：

以下内容涉及 (1+2)+3 中缀链(infix chain) 和表达式组织的相关知识

总共有六类项目，它们名字的首字母简写为：”s b r u u o”，其中 “u u” = “until(~) unless(!)”

此外还有结合性规则，默认左结合、大者先结合：optional,repeat>unless>or>until>sequential；以及括号 (a) 实际用于手动 组织(group) 表达式

规则颠倒了 or 和 until 的顺序，如 a|b ~t 便实际指代 (a|b) ~t 而非 a| (b~t)

左结合指于 (a+b) 的中缀链 1+2+3 实际表示 (1+2)+3、右结合 1+(2+3)，注意：计算机在计算中缀时通常只能按两个一组、顺序计算

如 Kotlin 的 (T) -> (T1) -> R 为右结合实则表示 (T) -> ((T1) -> R)、category.item.child 为左结合实则表示 (category.item).child

优先级，优先级和结合性用于表示『结合序』，偶尔也可用『左/右』优先级区分并为表示『结合序』，Lua 程序设计语言官方实现即按此法进行

其中，a、b、c 作为「项」的一般名字、t 可以理解为 terminate (终止) 的缩写，但和是否为『Terminator(终结符)』无关

文法实例

以上是对基于所谓『项』的 序列 的 模式(pattern) 的一种高阶抽象，需要实际定义 a 等项具体表示什么才能工作，这里：

我们可以给模式命名，这样也能产生递归（如以括号括住一个表达式的结果，本身也是一种表达式）

『数位』[0-9]
『你好世界』你好世界
『十进制』
  (数位!0 {数位}?)
 |数位

此外，由于绝句的 「为」文法、『逗号表示法』、「记法」 要求解析器带有特定上下文（如当前逗号块的缩进深度、当前文件引用的记法）工作，无法直接用一般的形式化语言描述，下面的定义要依赖 『……』、『为……』 来描述基于『逗号表示法』和『为』的语言结构，与 『言元』 相对的 『言』、『中缀链』 由于中缀符等的不定也无法完整在此定义

一般而言，利用 递归下降法(recursive descent) 在输入的字符流上，自顶(起始规则)向下地读取解析即可。

一堆知识点 如 LL(k)、词法分析|标记化|分词(tokenize)、词条、终结符(terminator)和非终结符(non terminal)、左递归、预读、自底向上、基于栈的解析器、中缀运算符优先级

许多 是指大小可为零的；些许 是指大小不可为零的

解析器实现 Kotlin Literate

概括：此部分我们将实现一个 JSON 解析器、一个加减乘除计算器，以及一个基于 Lambda 演算的简易解释器。

import java.io.InputStream
import java.io.InputStreamReader

import java.nio.charset.Charset
import java.nio.charset.StandardCharsets.UTF_8

下面我们将具体定义一个基于 kotlin.String 和 java.io.InputStreamReader（以支持类似『浏览器控制台』式 REPL）抽象出的解析器输入封装，解析器使用『递归下降』方式工作。

因为实现比较简单，这里我们不讨论关于 SourceLocation 行号的问题。

未提及的也包括 RangeMap 这种辅助工具类的实现，关于中缀链扫描、自定义中缀记法扫描的『线索树(trie aka. dict tree)』实现以及中文数字读取稍后提及，传统（类似 Python）的布局文法实现也会在稍后阐述。

/** Something with [SourceLocator] tag */
interface SourceLocated { val sourceLocation: SourceLocator }
/** Identifier [file]:[line]:[column] #[position] */
interface SourceLocator { val file: String; val line: Cnt; val column: Cnt
  val position: Cnt }

data class SourceLocation(override val file: String, override var line: Cnt,
  override var column: Cnt, override var position: Cnt): SourceLocator

因为我们的解析器需要能够可嵌套地标记(mark)/回溯(reset)字符流，而且要同时支持可以索引随机访问的 Slice 以及『一遍过』式的 Iterator 流两种输入 (Slice 如数组、列表、字符串)，所以必须有一种手段针对 Iterator 实现对 mark 数据的保存，我们将把对应的算法和所需的存储空间分配写在 BaseInput 类里（因为它不带对 SourceLocated 的支持也不需要给解析器充当 ErrorHandler，比较简单原始，所以叫此名）

为了尽量泛化我们的序列模式匹配库（使它不止可用于字符流，例如可被用于在 Array<out String> 上执行解析），就先把 Reader 抽象为 Iterator<Char> 了（这里不用 unboxed 的 CharIterator，此框架是泛型的）

class ReadIterator(private val reader: InputStreamReader): Iterator<Char> {
  constructor(input: InputStream, charset: Charset = UTF_8): this(InputStreamReader(input, charset))
  override fun hasNext(): Boolean = reader.ready()
  override fun next(): Char = reader.read().toChar()
}

下面由于文章篇幅原因，不会赘述基于 BufferStack 的 BaseInput mark/reset 如何工作，作者花了许多时间重写类似的架构，要想一步登天地理解为何要这么写，着实不敢强求。

此外，还可以利用 kotlin.Lazy<T>、by lazy {} delegates 甚至 List<T?> 和空判断手动实现对 BufferStack 本身/它的Buffers 的惰性求值（应当这么做，出于解析框架架构内存效率的问题）但这里不多说了，不做对结果亦无影响。

// 引入一些数据抽象
typealias Cnt = Int
typealias Idx = Int
interface Sized { val size: Cnt }
inline val Sized.isEmpty get() = size == 0

class Stack<E>(private val storage: MutableList<E>): Sized {
  constructor(): this(mutableListOf())
  override val size: Cnt get() = storage.size
  fun push(item: E) { storage.add(item) }
  fun pop(): E = storage.removeAtEnd()
  val top: E get() = storage[storage.lastIndex]
  fun clear() { storage.clear() }
}
internal fun <T> MutableList<T>.removeAtEnd() = removeAt(lastIndex)

首先，我们要为两种输入（基于保存『流指针』的Slice式和保存『数据缓存』的Iterator式）兼容 MarkReset，不妨把两种数据状态存储出来：

interface MarkReset { fun mark() fun reset() fun unmark() }

/** 基于保存状态 [T] 栈形式的可回溯 */
abstract class StackMarkReset<T>(): MarkReset {
  private val stack: Stack<T> = Stack()
  protected abstract var saved: T
  override fun mark() { stack.push(saved) }
  override fun reset() { saved = stack.pop() }
  override fun unmark() { stack.pop() }
}
/** 基于保存缓存 [layer] 栈形式的可回溯，抽象 [newLayer] 和 [consumeLayer] */
abstract class BufferStackMarkReset<BUF>(): MarkReset {
  private val bufferStack: Stack<BUF> = Stack()
  protected val layer: BUF? get()
    = if (bufferStack.isEmpty) null else bufferStack.top
  protected abstract fun newLayer(): BUF
  protected abstract fun consumeLayer(layer: BUF)
  override fun mark() { bufferStack.push(newLayer()) }
  override fun reset() { bufferStack.pop().let(::consumeLayer) }
  override fun unmark() { bufferStack.pop() }
}

我们希望兼容 Array<T>、List<E>、String 作为输入，可它们的 get、set、size/length 根本不统一，这可以通过定义一个统一的规范实现：

/** 一个统一的 Array-Like objects 接口定义 */
interface Slice<out T>: Sized {
  operator fun get(index: Idx): T
}
fun <T> slice(ary: Array<T>): Slice<T> = object: Slice<T> {
  override val size: Cnt get() = ary.size
  override fun get(index: Idx) = ary[index]
}
fun <E> slice(list: List<E>): Slice<E> = object: Slice<E> {
  override val size: Cnt get() = list.size
  override fun get(index: Idx) = list[index]
}
fun slice(chars: CharSequence): Slice<Char> = object: Slice<Char> {
  override val size: Cnt get() = chars.length
  override fun get(index: Idx) = chars[index]
}

考虑一下解析 1|2|3 的过程，如果输入 "1"，next() 一遍成功还好说，可如果不成功该怎么办？数据流也回不去了啊？

这种情况在组合解析器里是频繁发生的，所以许多 C-style 的递归下降解析器都弄了个 lastChar 而非一直 getchar() 移动数据视图，但那样太难看——闲得没事为什么要一直用 lastChar 然后成功了去 nextChar()？getchar() 的语义不是更准确？

于是现在一般都用（其实也就是我用过几次）peek/consume 消费模型，不过因为 Kotlin 有 Iterator 我们就用原名吧。 为了方便代入之前的知识先这么理解，理论上有一些出入。

Feed 和 Iterator 最大的区别就是多一个可以不改变流位置的方法 peek，而不是每个子解析器为了测试匹配，即便匹配失败也要改变输入流。

interface Feed<out T>: Iterator<T> { val peek: T }

class StreamEnd: NoSuchElementException("no more")

class IterateFeeder<T>(private val input: Iterator<T>): Feed<T> {
  private var lastItem = input.next() //init
  private var tailConsumed = false //note that "next" represents "consume" now
  override fun hasNext() = input.hasNext() || !tailConsumed
  override val peek: T get() = lastItem
  override fun next(): T
    =  if (input.hasNext()) input.next()
  else if (!tailConsumed) lastItem.also { tailConsumed = true }
  else throw StreamEnd()
}

考虑我们开始『预取』了 input 里的一项，为了使可 peek 版本的数据对 yield(peek); next() 依然完整，在 input 迭完后仍然要多 next 一个尚存于 lastItem 里的数据。

class SliceFeeder<out T>(private val input: Slice<T>): StackMarkReset<Idx>(), Feed<T> {
  override var saved: Idx = 0
  override fun hasNext() = saved != input.size
  override val peek: T get() = input[saved]
  override fun next() = try { input[saved++] }
    catch (_: IndexOutOfBoundsException) { throw StreamEnd() }
}

一般而言在单个使用 xs[i++] 的时候不会存在意图模糊的问题，但切不可滥用
这里没有检查 next 是否被过多调用，如果打算利用异常系统，就应该统一两者抛出的异常类型

接下来定义我们的 BaseInput 要接受两种 Feed 而且还得兼容 MarkReset，试试利用 as? 测试，如果接受到的 Feed 已经实现了此接口，就不必再帮它『实现』一个更泛泛的版本了。这样类似 java.io.InputStream#markSupported 但利用语言内部特性，比之更优雅

其实，实际工程完全可以仅对 T=Char 实现 BaseInput，这样就可以利用 StringBuilder 类更高效地工作了，不过这里仅为示范，不画蛇添足了

typealias Buf<T> = MutableList<T>
open class BaseInput<T>(private val feed: Feed<T>): BufferStackMarkReset<Buf<T>>(), Feed<T> {
  private val resetting: Buf<T>?
    = if (feed !is MarkReset) mutableListOf() else null
  override fun hasNext() = feed.hasNext() || hasReset
  override val peek: T get() = feed.peek
  override fun next()
    = (if (hasReset) resetting!!.removeAtEnd()
     else feed.next())
    .also { layer?.add(it) }

  override fun newLayer(): Buf<T> = mutableListOf()
  override fun consumeLayer(layer: Buf<T>)
    { resetting?.addAll(layer.reversed()) }
  override fun mark() = feedMr?.mark() ?: super.mark()
  override fun reset() = feedMr?.reset() ?: super.reset()
  override fun unmark() = feedMr?.mark() ?: super.unmark()

  private val hasReset: Boolean get() = resetting?.isNotEmpty() ?: false
  private val feedMr: MarkReset? = feed as? MarkReset
}

这个实现在 reset() 到尚有 mark 层存在时 next() 依然工作正常，至于为什么要 reversed() 和 removeAtEnd() 是为了方便把 [1,2,3] [4,5,6] 拼接回 6,5,4,3,2,1 而无须令 MutableList<T> 去 insertAt(0, _)，可能没有用但我良心不会过不去……

REPL Read-Eval-Print-Loop，可以理解为立即执行代码的编程交互，一般用于试用既成代码

解析器 一般为输入是某种『数据流』的程序，它试着从流中提取给定结构，如把 1: 2 提取为 (pair 1 2)

解释器 对语言抽象结构进行实际计算的东西，这个抽象结构一般是语法树如 (add 1 (add 1 9))

编译器 从『源语言』到『目标语言』的翻译器，源和目标可以是同抽象层次的语言，语言中包括低层次的机器语言、汇编式语言和高级语言

unboxed 在传「值」时，Java 提供 by-reference 和 by-value 的形式，如 int 和 “boxed” java.lang.Integer，后者可能需要 GC 自动管理，这是底层存储分配上的问题，使用上分不出区别

GC Garbage Collector，自动内存管理器，现代编程语言一般需要一些并不「轻量(lightweight)」的『聚合量(product value)』（如 String 是一大堆字符的排列、List<E> 更是）而它们无法直接在不同的函数里以和 int、long 这种「标量(scalar)」相同 by-copy 复制方式新建和传递，一般的方法是『按引用传』，也就是先把目标聚合量「分配」在 存储器 提供的空间里，然后传递目标的地址(address)，这也涉及数据对象可变性的问题，如 C 里传出 int 对 caller(调用者) 肯定不是可变的（你复制了另外一份交出），但 C String: char * 指针 对 callee(被调者) 就是可改动的了；GC 允许你把底层的存储视为对象，在需要的时候可以分配新对象、在某对象不能再被引用时（比如，从最后一个引用它的列表中被移除）自动回收它占用的内存，简单的 GC 算法如 Rc（引用计数）和 MarkSweep（标记-清除）等

分配 这里指对存储器空间的分配，好比就餐时座位分配一样，在某人吃完之前不能空出来另作他用，其中某人可以理解为计算尚存依赖的有用数据。

存储器 如裸计算机暴露出的内存或机器寄存器(register)，一般可以按存储编号（地址）随机访问，可用于存数值等

指针 指针是 C 相较很老很老的非结构化编程方式一个很有用的提升了，它是编译器和编程语言对底层存储器「相对安全」的封装，但仍有溢出等问题

实现组合复用部分

下面我们将依照上文对『形式化文法』的描述，实现六个结构的函数式抽象模板，以 高阶函数 面向对象子类 的形式

这六个模板分别是 sequential, branch, repeat, until, unless, optional

它们代表 顺序、分支、重复、重复直到、否定前提、可选 的模式

interface Parser<T, out R> {
  fun read(s: BaseInput<T>): R?
}
inline val notParsed: Nothing? get() = null

我们之前也用过 typealias Parser<T, R> = (BaseInput<T>) -> R? 的版本，可那样存在一些问题，如扩展函数较为混淆。

但在这之前还有一个问题，就是对于要解析多项的 sequentail, repeat, until，它们的结果该如何表达？

一般来说肯定第一个想到用 List<R> 来表达，可那样的话，如解析 251 这样的数字我们可以 acc*10 + digi 实现，保存它们的字符形式就显得多此一举。

于是我们引入一个 Reducer<T, R> 来表示对这类解析器结果的计算方式：

interface Reducer<in T, out R> {
  fun accept(item: T)
  fun finish(): R
}

介于我们开始的设计目的就是抽提 List<R> 的『解析返值构建模式』，肯定能够想到 Reducer 是要包含某种数据状态的（比如 List 实例）

于是，我们还认为有 新建 带状态的 Reducer 的架构器式函数，起名为 Reduce

typealias Producer<R> = () -> R
typealias Reduce<T, R> = Producer<Reducer<T, R>>

此外，为了标准化用法以及使用方便，我们添加两个子类：

/** Build [R] with temporatory [A], [self], [onAccept], [finish] */
abstract class EffectReducer<T, A, R>: Reducer<T, R> {
  final override fun accept(item: T) { self.onAccept(item) }
  abstract val self: A
  abstract val onAccept: A.(T) -> Any?
}
open class MonoidReducer<T>(mzero: T, private val mplus: Join<T>): Reducer<T, T> {
  private var base = mzero
  override fun accept(item: T) { base = base.mplus(item) }
  override fun finish() = base
}

typealias Join<T> = T.(T) -> T
private fun <E> MutableList<E>.add1(item: E) { add(item) } // 待会使用

在使用时，便可类似这样定义：

class AsList<T>: EffectReducer<T, MutableList<T>, List<T>>() {
  override val self: MutableList<T> = mutableListOf()
  override val onAccept = MutableList<T>::add1
  override fun finish() = self as List<T>
}

object DecShift: MonoidReducer<Int>(0, { this*10 + it })

//val _nil: Reduce<Int, List<Int>> = ::AsList

因为我们抽提出了 seq, repeat, until 解析器的返回类型，原 T、R 两个符号就不够用了（大解析器本身的返回类型需要起新名字）

我们把子解析器输入叫 IN，而 T、R 则分别代表子解析器输出和大的返回类型。

class Seq<IN, T, R>(private val reduce: Reduce<T, R>,
    private vararg val sub: Parser<IN, T>): Parser<IN, R> {
  override fun read(s: BaseInput<IN>): R? {
    val reducer = reduce()
    for (item in sub) {
      item.read(s)?.let(reducer::accept)
        ?: return notParsed
    }
    return reducer.finish()
  }
}

这里，我们就能够使用之前对于 MarkReset 的定义了

class Or<IN, T>(private vararg val sub: Parser<IN, T>): Parser<IN, T> {
  override fun read(s: BaseInput<IN>): T? {
    for (item in sub) {
      s.mark();
      val parse = item.read(s)
      if (parse == notParsed)
           { s.reset() }
      else { s.unmark(); return parse }
    }
    return notParsed
  }
}

class Repeat<IN, T, R>(private val reduce: Reduce<T, R>,
    private val item: Parser<IN, T>): Parser<IN, R> {
  override fun read(s: BaseInput<IN>): R? {
    val reducer = reduce()
    var parse: T? = item.read(s) ?: return notParsed
    do { reducer.accept(parse!!); parse = item.read(s) }
      while (parse != notParsed)
    return reducer.finish()
  }
}

关于中缀链的解析

中缀链解析本质上有点类似对列表排序的过程，不过输入是不可随机访问的词条流，能做的hack相对更少一些

类似排序问题，有许多人设计过许多种方法，利用栈、双栈、多层函数调用/等待嵌套，来解决这个『如何从 1+2*3+0 到 1+(2*3)+0』的问题，但对初学者来说 太复杂，这里不赘述。

a ⦁ b ⦁ (c) (c has no next operator, terminates this chain)

↑____↑ 比较这两个算符的优先级，看是 (a ⦁ b) ⦁ c 还是 a ⦁ (b ⦁ c)；后者意味本层递归要等待 b⦁c 的结果并在完成时在前面加 a⦁

给你 scanAtom()、scanInfix()，请完成扫描中缀链的算法

按照一般的方法，就是比较某算符与【它后面表达式的算符（如果没有就表示解析完了）】、若某算符胜则『结合』了 a⦁b，然后递归下去扫描余项

为了实现 (a⦁b) 先结合后还能被 ⦁c 使用，以及第二个本来是『预取』的 ⦁ 算符的优先级信息能作为下一次优先级比较的「左边」也即 “a” 参与下一个 “a<b” 的比较，我们认为参数必须包含两项：

fun infixChain(base: Atom, op_left: Op? = null): Atom {
  val op1 = op_left ?: scanInfix() ?: return base  //'+' in 1+(2*3)... | atom "1"
  val rhs1 = scanAtom() //'2'
  val op2 = scanInfix() ?: return op1.join(base, rhs1) //(a⦁b) "terminated"
  return when { // lessThan b => win; default ("="): left assoc
    op1 <= op2 -> infixChain1(op1.join(base, rhs1), op2) //(a ⦁ b) ⦁ ...
    op1  > op2 -> op1.join(base, infixChain1(rhs1, op2)) //a ⦁ (b ⦁ ...)
    else -> impossible()
  }
}

具体实现的做的杂事有点多（比如包括了判断是中缀链还是单项的逻辑，以及上面也提到的对预取infix的保留性传递），但它的简洁性仍然可以令人接受

太复杂 记得我 有一次 用基于 kotlin.collection.MutableList<E> 的栈而不是系统栈写了一次传统方式的中缀优先级解析器，代码行数足足是递归下降的 3倍，还额外定义了两个栈的辅助类，跑分结果还不理想

编译器参数

对绝大部分程序设计语言来说，第一个版本的编译器会比较简单以方便发现问题、快速采取行动，而且在第一版实现之前，无法直接以还未实现的编译器实现『自举』编译器

jueju 参数 源文件

其中，参数可为

以及

自举 这里指某种编译器完成对『以自己的源语言描述的，自身的代码』的翻译，前提条件是得先有『第一个』这个编译器存在

This site is open source. Improve this page.