编译原理入门之旅

背景： 为何学习编译原理

在过去的两年内，无论是我在工作还是业余的开发内容，都和图形渲染引擎的材质系统紧密相关。材质系统/框架本质上由这么几个部分组成：如何抽象着色逻辑，如何以最高的性能完成数据从应用程序到GPU的提交和更新，以及相关的资源管理。其中第一个部分，如何描述着色逻辑，对于大部分引擎而言就是shader构造的相关问题，这其中的相关问题我认为如果不在编译技术上投入精力进行学习和研究则会导致一些技术实现上的瓶颈。

可能一些人认为问题仅限于拼接shader字符串，的确，最基本的需求是可以通过拼接字符串，或者通过纯字符串操作得以解决。但以下高级需求很难做到：跨平台/功能降级，运行时优化，逻辑/依赖 的 提取/融合等，这些功能要求我们需要实现以真实程序的视角，而不是字符串的视角看待shader。

仓库地址位于：https://github.com/mikialex/rxsl。目前已经实现了从输入到一个线形IR的转化，其中分部实现了从原始输入经lexer得到tokenstream，再经 parser得到ast tree，再经过irgenerator 得到 ir的完整流程。

我的参考书籍就是编译原理龙书，此书我2015年便已购得，当然后续没有深入看下去，很多细节都只了解了大概，只能说对知识的框架有个粗略的认识。阅读此类较为晦涩的技术类书籍，特别是完全没有人指导和讲解的情况下，是富有挑战性的经历。很多时候某一页内容没有真正理解，后续都很难推进下去，而某些概念又写的颇为精妙和概括，的确遇到了一些困难。

对于阅读这种高深的技术书籍遇到的这种看不懂，又找不到人问的问题，经过我的实践，一般可以这么缓解：1 大量搜索其他网上的资料，交叉参考各自说法，或者去合适的社区提问 。2强行反复看，强行反复理解，很可能就能看懂。3 找现成代码研究和调试实现辅助理解。

一些认识和有趣之处

我想，这个世界上已经有太多文章教你怎么写parser了，所以我不想展开具体的技术细节，而是谈谈其中我认为有所认识，有所自我突破之处。

除了龙书，我还想推荐另一部偏理论的书：《有限自动机理论》，这本书让我了解到一些更本质的理论，比如：正则语言可以被一个简单的状态转化图的自动机识别，这就是正则表达式的实现。上下文无关语言可以被一个简单的状态转化图加一个状态的栈识别，这就是parser。

所谓自顶向下递归下降LL parser，由函数调用完成状态图的状态转化，由整个调用栈表达状态栈。所谓自底向上LR parser，则其实是根据文法显式的生成状态图转化，和状态栈的转化。

LR基本不能手写，需要parsergenerator生成，解析能力较强。LL手写很方便，而且非常直观，重要的是易于做错误恢复和调试，一般LL完全够用了，LR可以实现一遍了解了解细节。LR parser还是比较难以理解的，我在去年用ts写过一个简单的LR的parser generator来学习简单LR parser的细节，但我现在基本上又把细节都忘记了。

LL需要想一下的是文法的左递归消除。对于编程语言而言，左递归在文法中是常见的，消除左递归有一套完备的理论做法，即对文法做一系列等价的改写，其解法在形式上会引入一项新的非终结符号，而通过对这一新的终结符号进行解析可以使得分词器继续消费下去，避免陷入无限递归之中。

运算符优先级和结合性：对于编程语言中的二元运算符，语言设计上基本上都是通过优先级和结合性进行去歧义化，实践上来说，优先级表现哪个parser先进行调用上，优先级越低的parser越先在上层调用，使得对应的节点位于最后产生的语法树上层，反之亦然。而结合性则反映在最后树产生的形状。我们是自左向右读取输入的，所以左结合的parser编写起来较为自然，而右结合的parser，由于运算符左侧是optional的，我目前的做法就是简单的保存状态进行回溯。优先级和结合性有另一种灵活parser实现叫pratt parser：https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html，这种做法比较高级，写法也很优雅。

IR设计和生成方面目前还在学习阶段，在我的实现中，IR的指令集非常简陋，很多语法树的部分都还没有写完实现，这些需要后续推进。在IR生成方面，我遇到的当时比较难以理解的部分是生成纯goto的控制流/生成控制流图，其中尤其是逻辑运算符也会产生控制流的问题。实话说我真的把书上写的那几页用代码实现一边我才基本搞清了细节。

在这个问题上，本质就是生成正确的goto指令，即插入goto指令并goto到正确的位置，其中难点在于后者。在插入goto后，我们是不能确定goto位置的，而是需要等到我们真的开始为goto到的代码生成指令时才知道，也是这时才对之前未确定的goto指令进行回填（back patch）。代码的控制流可能会交汇，即多个goto指令的目标很可能是一个，所以在goto resolver的内部数据结构上，具有相同跳转目标的为解决goto是个list，生成器可以按需对list进行合并（merge），而回填也是基于list进行。对于任何一段代码/语法树上的结构，我们对其进行代码生成使总是要获得其首行指令位置以及其中未解决的goto，当然这两个都是optional的（不一定生成了指令，不一定有未解决的控制流），而如果有更外层的跳转，比如loop continue/break return，那么内部未解决的控制流会和这些保存在代码生成器上的未解决的goto进行合并，在loop/function结束时便可以正确进行回填。总之代码生成器在生成控制流代码时，基于上面的统一的return值，要做的无非是生成goto指令以及未确定的跳转目标，合并未确定的跳转目标，回填未确定的跳转目标。

但是，当考虑到布尔表达式隐含的逻辑控制流时，事实上意味着如果某个表达式是布尔值，那么遇到逻辑运算符时不仅要生成逻辑运算的指令，还要生成跳转的指令，而这意味着一个布尔值在运行时的true和false是两条不一样的控制流（goto目标），所以，为表达式生成上述的控制流跳转结果是，要额外抽象成枚举，即对于类型是布尔值的表达式，需要返回两条潜在的未解决控制流语句，以供后续代码生成进行正确的合并和回填。

后续我会继续将ast的其他ir部分补全，然后实现一个简单的VM来对IR进行执行和测试，然后会调整IR到一个真正的控制流图的结构，并进行SSA化，然后生成spirv代码，再后续会学习一下优化方面的内容。听起来越来越有趣了