编译有必要学习一下。 分为两部分。前半部分看[Engineering a Compiler]这本书，了解编译器整体流程/基本概念，记录重点内容。

后半部分记录斯坦福的编译器课程，实际的CS143作业，写代码。 https://web.stanford.edu/class/cs143/

这个课程并不是完全从0写代码，而是在一套小框架上填入最重要的一部分代码，再借助flex/bison等工具完成整个编译器。 认真看看书/完成作业足够入个门。 后续的小目标是写一个C的编译器，中目标是从0写完整的编译器，大目标可以是做一个新的语言及其编译器，并跑在自己实现的cpu上。

课程有配套视频。前4个作业看看书/代码/文档可以硬来。最后的作业得详细看看视频。

其他资料: [Compilers Principles]等

编译器的工作就是把一种语言翻译成另一种语言。 编译器需要知晓输入语言的格式(语法)和上下文(含义)。同样需要知晓输出语言的相应规则。 最后需要一套方案，把输入语言map到输出语言。

典型的three-phase编译器架构。

前端处理输入语言，后端处理输出语言。 中间的数据称为intermediate representation(IR)，具体的内容和具体语言高度关联。 一般编译器都会在其中安排优化器，把原始IR在各种层面上进行优化。

编程语言和一般自然语言不同，它必须尽可能严谨、明确、简洁。

编译器一般把代码翻译成目标机器的代码。 也有的把代码翻译成另一种人类有好的语言。比如翻译成c语言。这种称为source-to-source translators。

有的形态称为interpreter，与compiler有很多相似之处。 大体的区别是compiler会生成低级代码，最终转成可执行文件之类。工作是事先完成的。 interpreter一般是online，运行时现读代码，一行行执行。不生成可执行文件。

just-in-time(JIT) compiler

编译器的基本原则

IR可以看作是另一个版本的输入程序。

对于two-phase compiler，前端需检查输入程序的格式，把代码map到IR。 后端把IR map到目标机器的指令集并做资源的整理。 后端不用考虑前端生成的IR有错。

编译器可以对IR做多遍(multiple passes)操作。

two-phase可以简化retargeting(为不同的处理器架构编译)。

在IR中间插入一个优化器，就变成了three-phase。优化器本质上是一个IR-to-IR的转换器。

考虑代码

下面看下编译的过程

首先必须明白代码的语法和语义。如果语法错，要报错。

scanner把输入文本转成一系列word，检查拼写。 parser检查syntax。把word装入语法模型(grammer)。 parser可不断调用scanner，得到后续的word。 parser可调用elaborator做一些其他计算，比如创建IR，检查类型一直，整理储存数据。

scanner和parser应用非常广泛。比如html、sql等的解析

检查语法就是比较程序的结构和这门语言的语法模型。

一套grammar定义一套word。在word和变量之上，规定一套规则，称为production。

例如一般英语句子的语法

sentence -> subject verb object endmark

那么对于Compilers are engineered systems. scanner要找到一个个word，并知道它的属性。

scanner最终可能生成这样的数据

下一步把这些word往grammar匹配。

parser就是要出这样的推演路径，从而保证语法正确。 语法正确并不代表有意义，比如Rocks are green vegetables.。

确认语法正确后，开始创建一系列IR等相关的后续数据。

编译器根据语言和功能，包含各种类型的IR。有的IR生成图结构，有的生成汇编代码。

例如

接下来一条一条处理IR生成的语句。可进行代码的优化。

优化一般包含分析和转换(analysis and transformation)。

分析包括Data-flow分析和Dependence分析。

根据分结果对代码进行转换。转换是一个大课题，可以出好多本书。

后端扫描IR，生成目标机器的代码。

整个工作称为code generation。

这三个问题都是困难问题。指令选择有大量的可选项，而指令调度和寄存器的安排都是NP-complete。

本书的低级语言用ILOC。

第一步把IR操作转成机器指令。见图1.4。用了四种ILOC指令。

指令选择阶段，编译器会假想硬件的寄存器是无限数量。

此阶段要考虑实际情况。

演示指令的顺序如何影响所需的指令周期。

一些工程角度的讨论

到此可以完成作业2。

以scanner输出的words作为输入，确定语法是否合法。

parsing是前端的第二阶段。

table-driven parsers direct-coded parsers hand-coded parsers

scanner是hand-coding更常用。 而parser更倾向于用工具生成。

Context-free grammars(CFGs)用来描述context-free语言。

有两种算法对其进行解析，top-down和bottom-up。 两者风格和实现都有很大不同，都很重要。 两者都有大量工具支持。

有一个正式的语法G，如果一串词语s符合语法G，就说G derives s。 parser尝试证明某个s符合语法G，这个就叫parsing。

Top-down语法分析 用预测下一个词，来匹配语法。 对于有限的语法，top-down准确且高效。 Recursive-descent属于top-down/hand-coded。 LL(1)属于top-down/table-driven。

Bottom-up语法分析 从底层往上走，从输入的具体词语开始，网上匹配语法。 LR(1)属于bottom-up/table-driven。

传统方法就是用CFG表示。它又有很多高效的变种。

例如一条规则 stmt -> if ( expr ) stmt else stmt

一条规则称为一个production。

其中的if/else/括号称为terminal。 expr/stmt这种带变量性质可以再展开的称为non-terminal。

从语法树的顶层开始往下分析，直到叶子与输入的词语完全匹配。

一个使top-down高效的特性。分析过程中，CFG的大部分子集是不用回溯的。

top-down是做一个leftmost的推理。

Left Recursion问题

Backtrack-Free Parsing

Left-Factoring

自底向上。

A->B表示一个规则。 (A->B, k)称为一个handle。k表示位置。

有action和goto两个表。

看懂图3.17/3.18/3.19和下面的伪代码就基本懂了LR(1)的逻辑。 这个例子语法是一个可嵌套的小括号list。比如()，()(), (())()()。

解析(())()的例子

问题是如何生成action和goto两个表。 这是一个繁重且极其细致的工作。手写一个个状态是不现实的。 下一节介绍生成LR(1) parse表的算法。

这里实际是在学parser generator的原理，和bison是一个层面，最后生成一个parser实体。 程序员大多时候只是用parser generator生成一个parse，然后解析某个语言，而不是经常去写parser generator。

LR是一个家族。一个LR(k) parser采用k个lookahead，往后看k个symbol。 矛盾的是，增加k并不能让parser识别更多语言。LR(1)能识别的语言跟LR(k>1)一样多。 LR(1)的语法甚至可以比LR(2)或LR(3)还多。

需要一种模型。称为canonical collection of sets of LR(1) items。 描述所有的状态和其转移。

学习两个例子。一个就是之前的括号解析，另一个是下一节的if-then-else。

一个LR(1) item用[A->B*Y, a]表示。 a是lookahead symbol。 A->B*Y意思就是语法里的BY归成A。 *指出匹配处于什么状态。有三种可能。

[A->*BY, a] 表示目前可能能匹配到A，如果lookahead是B，那么可以向A更近一步。 这个item叫做possibility。

[A->B*Y, a] 已经从上个状态匹配了B，向A更近了一步。 这个item叫做partially complete。

[A->BY*, a] parser已经找到了BY。这时如果lookahead是a，就能得到一个handle。 这个item叫做complete。

可以看出*左边是已经匹配到的数据(left context)。和之前流程中的当前栈上数据差不多？

图3.21是括号语法的LR(1) item集合。

到此可以完成作业3。甚至可以不用看具体的算法就能完成。

IR的总体介绍

编译器一般有几个pass。前面pass的数据传给后续的pass。 整个这其中的数据就叫intermediate representation。

可能只有一个IR，也可能有多个。编译器就是依赖这些IR来工作，并不会中途返回去查源代码。

编译器会生成各种辅助数据来提高效率或者优化等等，这些都属于IR。

在一个pass结构的编译器里，IR是一个程序的主要表示方法。

几乎所有的阶段都是在操作IR。所以IR的结构/性能等直接关系到整个编译器的效率。

总之IR是各种重要。

以三个维度来分类：组织结构/抽象层次/使用模式

Graphical IR 把信息转成图结构

Linear IR 重组伪指令

Hybrid IR 上面两种的结合

编译器需要选择某个IR对数据处理到什么深度。可以只是简单处理到一个树状表示，也可深到生成机器指令。

near-source level 更靠近源码

near-machine level 更靠近机器

Definitive IR 确定的IR。IR的主要形态。一般转到下一个pass时会有确定的IR。

Derivative IR 用来完成一些特殊的/临时性的任务。可作为确定IR的补充。 一般是在一个pass内生成。

命名很重要。

parse树/ast/有向无环图(DAG)

见图4.2。

ast和parse树结构一样的。但是去掉了一些相对无关的节点。比如去掉了nonterminal，直接展开到terminal。

ast虽然精简，但仍然是终于源码的。

dag是对ast的一种压缩，去掉了ast中重复的部分。 一个节点可以有多个父节点。重复的部分得到复用。

主要使用原因：

线性IR用一串有序的指令表示程序。汇编指令是一个例子。 线性IR一般用来生成汇编代码。

背后的逻辑很简单。输入的源码就是线性的，输出的指令必然也可以是线性的。

one-address形式。

cs143的作业用stack machine code。

i B)得到value。

如果操作是reduce，value是赋给$$的值。 如果操作是shift，value就是lexeme值。

到此为止，只看到语法的local计算。每条规则的计算只用了自己范围内的数据。

而编译器中有很多计算需要用到其他部分的数据。

一个例子是语言中变量/函数/object等的类型/生命周期等信息。这些必须是全局的而不是local的。

编译器第一次碰到某个entity时，要确定它的各种属性。后续要随时随地能获取。

一个声明变量的例子。

声明变量的另一种写法，把int/float之类的匹配和list写到一起。省去了type的全局变量。

if then else的例子

现代编程语言可创建复杂的命名空间。很多语言支持词法的命名层级。 很多语言支持面向对象的命名层级。

当编译器碰到一个名字时，syntax-driven translation必须把这个名字map到一个entity(变量/函数等)。 name-to-entity binding。

命名空间可以有多个子空间或者scope。

Static binding Dynamic binding

原则:在程序的某一点p，一个名字n一定是关联到一个，与p在词法层面最近声明的一个n。

简单讲就是n会关联到当前scope，如果当前scope没有n，不断往上一级scope找。

最外层的scope通常包含全局名字。

symbol table

一个type是一系列属性的集合。同一type的实例拥有相同的属性。

有了命名空间和类型信息，可以做storage layout了。

三种storage class

automatic变量a的生命周期和它的声明scope一样。所以可以存在scope的local data area。

static变量s生命周期是从定义到最后一次使用。

生命周期为程序控制。比如动态分配内存。

程序运行过程中，会产生很多临时的值，并不会跟某个名字相关。 比如数学运算的一些中间值。

运行时如何使用memory。大多数系统中，程序运行在一个自己的虚拟地址空间。 操作系统会把虚拟地址映射到真实的地址。 编译器只需关注虚拟地址空间。

Code 存放可执行文件。运行时一般不变。

Static 存放static entity。包括全局变量、static变量。 大小可在link阶段获知。

Heap 可变的内存区域。动态分配的内存在这里。

Stack 其他各种数据。

heap和stack往中间对着涨，这样可以最大利用空间。

不同程序可能表面上用了同个地址，但是操作系统一定会把他们映射到不同的地址，保证不会出乱子。

主要讲函数调用相关

procedure是一般语言中的核心。这里单独用一章来讨论。

每个procedure有自己存储空间。一个程序基本上是以系列procedure的组合。 有了procedure就可以支持分部分编译，从而实现大型软件的开发。否则代码动一个字就要全部重编，是不能接受的。

调用函数时保存调用者的环境，初始化被调函数的环境。

Activation record AR是为函数的调用创建的一块数据。就是上面说的环境。 每次调用都生成一个。

编译器必须

AR数据

parameter area 参数

寄存器数据 储存在调用过程中需要保存的寄存器数据

返回值

返回地址

addressability 让被调者可以access到其他scope的数据

ARP 指向调用者的AR

local data area 其他本地数据

看到这里思考了一下，这些数据的维护逻辑在哪实现？ 是编译器中的某一部分代码？ 再看标题Runtime Support，难不就是常听到的运行时库么。

大概猜测总结一下，比如c程序。 一般用户层面是不关心runtime的，就写写逻辑完事。但是编译时几乎都会link对应的c运行时库。 这个运行时库的基本功能就是实现了上述的环境维护，让你能启动程序/花样调函数/分配数据等等。 其实它是一门语言的基础设施。可能是用高级语言比如c写，也可能用汇编写。 我猜它可能在生成机器指令的过程中检测你的代码行为，一旦你调函数或者其他操作，它就用runtime的预定流程对你的操作进行封装，生成维护调用环境的机器指令，最后整合成一份完整机器指令。 如果不带上runtime，你c代码根本跑不了。当然你也可以不用它的，自己写runtime！ 那么可能和写汇编的形式差不多了，可能是得在c代码里做各种汇编操作？有点像实现协程那种感觉，就是对调用过程做hack。本质也就是做一个runtime。

所以简单说，这个runtime就是实现了高级语言的函数调用等等功能。 人们能用很简单的语句写逻辑并运行，费劲做出runtime是一个要付出的代价。 它本质是嵌在编译器的生成机器指令的流程中。然后可以把这部分抽出来，因为它较为通用。 把它抽出来做成单独的库，方便维护，方便针对跨平台做修改。

runtime可以包括更大的功能比如线程库之类。

区分操作系统和cpu架构。

再查查资料，整体大差不差。 https://en.wikipedia.org/wiki/Runtime_library https://en.wikipedia.org/wiki/Runtime_system

比如C++功能繁多，runtime自然比C之类复杂得多。

object record(OR)

链接是编译器/操作系统/目标机器三方达成的协议。

这一章开始讲指令生成。

对同一个代码，有较多的指令生成方式。有的快，有的耗内存少，有的耗寄存器少，有的耗电少。

代码形状直接影响后续的优化器等组件的工作。

比如c语言switch一个字符，有256个case。 最简单是生成256个比较指令，运行时如果输入是均匀分布，平均需要比较128次才能匹配到，n/2的速度。 如果编译器对256个字符做预处理，做成二叉搜索，那么就是log(n)的速度。 再如果做成一个数组的形式，直接按index就能得到结果。那么就是O(1)的速度。

x+y+z的例子。优化需要依赖上下文。

四则运算的例子。

Scalar变量。先确定是存在寄存器还是存在内存中。

寄存器中 直接可用。对于add r1, r2 => r1一般机器都能在一个周期完成。 寄存器的一个主要优化就是把常用的变量存到寄存器里。

内存中 有多种原因导致主要存在内存中。 可用(scope_level, offset)的形式存。

其他scope中的local变量 得用addressability机制去找。

Static and Global Variables 其地址用一个assembly-level的label表示。 isa会决定怎么取值。

作为参数的变量

heap中的变量

Aggregate objects就是类/类实例/struct/string/array之类数据。

struct 根据symbol table找

object member 找OR。再找内部member。

vector 根据起始地址和下标找

string

多维数组 根据排列方式计算

有的语言需要检查数据的范围。越界报错。

bool操作相关的汇编

if else/循环等等的汇编

string相关

函数调用相关

代码经过前端生成某种IR，后端把IR转成机器指令。

中间是优化器，把IR进行转换以生成更高质量的机器指令。

本书只讨论单线程。并行计算相关内容也同样重要但超纲。

一些历史

https://web.stanford.edu/class/cs143/

为cool语言写一个编译器。并不是从0写代码，是用一系列工具整合起来。 包括flex/bison/spim等等。

flex对代码进行scan，从代码中按规则识别出所有token(word)。 bison对token进行parse，组成语法树。 这里面的底层原理都是大课题。在这个课程里不细说。 编译器相关的实际工作内容可能更多集中在IR优化相关，而不是前端的scan/parse细节。

主要目的是掌握编译器的各部分基本原理，有能力自己搞一个新语言，并为其整合出一个编译器。

win11 virtualbox里ubuntu22.04

课程文件下载 https://courses.edx.org/asset-v1:StanfordOnline+SOE.YCSCS1+1T2020+type@[email protected]

包含课程初始代码，作业说明等。如果链接失效，可到github上找。

这个课程文件应该是2011年左右的，和cs143官方最新的文件有不同。我用的最新版本的flex，有的地方需要修改。

最新的文件貌似不公开，所以只能用老的文件。实际大同小异，可以相互参考。

语言基本用c++

用cool语言写一个小的栈模拟程序。

需要看他的语言手册和examples目录的代码。 没有数组。代码里起名也恶心，什么cdr，car，Cons。缩进是一塌糊涂。

但是到后续阶段懂了更多原理以后就习惯了，不那么恶心了。

主要看list.cl和sort_list.cl。

我的做法是模仿他的list写一个list和一个stack。 不知道怎么做空数据，list可以做一个永久的假数据当作尾巴。 写的比较松散，整了200行。

最后的结果为4。

作业2要做一个scanner。 最后的效果是把输入的cool代码打碎成一个个token。

cool.flex是我们要完成的flex代码。 test.cl是一个输入例子，需要对这个文件做scan。这个文件可能包含错误，需要能识别。 最好的状态是对这个文件进行扩充，涵盖尽可能多的测试用例。 详见readme。

flex用来帮我们写scanner。我们编写语言的规则，和一些辅助逻辑。flex生成匹配算法，实现输入文件和语言规则的匹配。

flex文档 https://westes.github.io/flex/manual/

flex默认安装的版本为2.6.4，可能是2017年的版本，而文档版本为2.6.2。而且默认文档是分成多个页面的，有点烦。 如果不爽，自己编。

这样获得了最新的flex程序和文档。

flex例子

整个文件用两个%%分成三大部分。最终生成c代码。

第一部分的%{和%}之间可写c代码，进行一些初始化之类。

接着写名称的定义。比如DIGIT [0-9]，给后面的正则表达式起个名。

第一个%%之后是规则(pattern action)。例如

意思是一旦匹配到了{[0-9]}+，就执行后面的代码。

第二个%%之后是flex的启动逻辑。

具体细节看作业2说明和文档第6节。

直接进行编译make lexer 会报错因为这个课程代码用的是老版本flex。

先看下makefile，会编五个代码 lextest.cc utilities.cc stringtab.cc handle_flags.cc cool-lex.cc

http://cool-lex.cc 由flex cool.flex生成的代码，就是flex把cool.flex中我们写的规则嵌到它的逻辑中生成一个scanner。 其中有个默认的yylex()函数，用来scan出下一个token。 基本模式就是我们不断地调这个函数，直到把文件scan完毕。

http://lextest.cc 此文件包含main函数。文档中main是直接放在http://cool-lex.cc最后的。这里它分开写，再一起编。 在cool.flex中有定义#define yylex cool_yylex，所以换了个名字。在while循环里不断调用cool_yylex来做scan。

http://handle_flags.cc scan之前处理一些选项

http://utilities.cc 辅助函数，比如打印一些信息。

http://stringtab.cc string相关的小操作

yy_flex_debug这个在flex最新代码里，貌似变成了yyflexdebug。在这几个文件里替换成yyflexdebug。 cool.flex里加上%option noyywrap 可以编过了。

make dotest或lexer test.cl进行scan。 此时cool.flex里只定义了一个DARROW =>，而test.cl末尾加里没有=>，所以啥也没scan出来。 往test.cl末尾加个=>再运行，可以看到dump_cool_token()的打印#1 DARROW。 下面就要往cool.flex填cool语言的规则，进行scan。

课程要求看cool的手册第10节，和include目录中的cool-parse.h。

要打开%option yylineno，这样flex会自动维护yylineno。 然后把http://lextest.cc里的curr_lineno替成yylineno。 需要添加\n的匹配，否则不生效。 https://stackoverflow.com/questions/13317634/flex-yylineno-set-to-1

define为cool_yylval

存储见第5节。代码见stringtab.h/stringtab_functions.h等等。 数字要这样存

注释开始\(\* 注释结束\*\)

进入注释后，只有匹配注释结束或者EOF才能退出，其他的都不能去匹配。 需要有个状态机制，见flex手册第10节。 做一个comment状态，再做[^*]*这种匹配消耗注释中的数据。 再匹配结束字符，转到初始状态yybegin(INITIAL);。

见flex手册第10节的例子。

google可以搜到cs143的grading脚本。可直接运行perl pa2-grading.pl。 必须通过63个测试。

完成parser。用parser生成ast。

看课程文档、readme和makefile。 最终会生成一个parser程序。

实际编译的文件是

cool.y 填写语法规则。编译时对其调用bison，生成cool-parse.cc，cool-parse.h和cool.tab.h。 bison cool.y会使生成的cool-parse.cc里#include "cool.tab.h" -b参数能指定名字的替换，生成#define yyparse cool_yyparse这样的代码。 那么cool_yyparse函数就存在了，就是原始的yyparse。

cool-tree.aps 待分析 生成cool-tree.h和http://cool-tree.cc。

http://tokens-lex.cc 即flex生成的lexer。是课程自带的正确的lexer，所以只要考虑本次作业的parser。而不是联动之前我们自己做的lexer。 yylex()函数在parser仍然需要，见手册第4.3节等。 所以需要把flex生成的lexer代码拿过来一起编。

http://parser-phase.cc main入口。调用cool_yyparse()。cool_yyparse在cool-parse.cc中定义。

http://dumptype.cc 辅助功能。遍历并打印ast。

http://handle_flags.cc 处理一些选项

https://www.gnu.org/software/bison/manual/bison.html

内容非常多，得耐心看。

输入语言必须是context-free grammar(CFG)。 CFG有很多继承者。bison对于LR(1)优化最好。 LR(1)的parser具有确定性(deterministic)。 意思是下一条匹配的语法规则一定是由之前的输入和剩余的输入唯一决定的。 也就是说给定同样的数据状态，让parser去跑，永远会匹配出同样的结果。 一个CFG是允许有歧义/模棱两可的，一个输入可能存在多种匹配。 而无歧义的语法又可能是不确定的(nondeterministic)。

bison把terminal称为token。nonterminal称为grouping。 简单来说terminal就是不可分的一个语法单元，比如c语言的变量名/关键字/操作符等。 nonterminal就是可再分的，比如一个表达式(expression)，比如x * x。 那么对于nonterminal，必须为其定规则，如何拆分为更小的单元。 比如一个statement。可以拆分为一个return加一个expression加一个分号。 整个输入，到最后一定是向上匹配到一个根nonterminal。形成一个完整的程序。

详见文档第3节。

按习惯nonterminal写成小写字母单词。terminal写为大写字母单词。 关键字terminal是把关键直接转成大写，比如FOR。

stmt: RETURN expr ';' ;这里最后的;是bison的规则结尾。里面的';'是匹配代码里的分号。

详见文档第3.4节。

对于语法来说x+4和x+66666是一样的。它只关心分类。 语义值(semantic value)需要记录其他信息，比如它的值和名字。

nonterminal也可以按需赋予语义。

详见文档第3.4.6节。 和flex一个意思，每当匹配到一个规则，进行预定的操作。

bison的LR(1)parser，在有些状态下无法给出结果。

例如

现在要匹配word 可以走word->maybeword>sequence。 也可以走word->%empty word->sequence word->sequence。 也可以走word->%empty word->maybeword word->sequence word->sequence。 都可以匹配到sequence。

Bison优先选择先出现的规则来解决这种冲突。但我们不能依赖于此。 这种冲突一般必须手动消除。否则有隐患。

当lookahead token读到else时，此时之前的输入能匹配第一个规则，但同时也有希望匹配第二个规则。 形成冲突。

例如对于 if x then if y then win; else lose;

如果选择先匹配，结果为 if x then (if y then win;) else lose;

如果选择继续读，结果为 if x then (if y then win; else lose;)

根据目前普遍的约定，bison默认会选择继续读输入，除非有其他优先级规定。 这样的效果就是把else优先匹配到最近的if上。

对于一些无法符合LR(1)的语法，%glr-parser选项可以生成一个Generalized LR (GLR) parser。 这种parser遇到冲突时直接"分裂"成两个parser，把两种可能都执行。后续还可能继续分裂。最后是一种分支形状。 一条分支只有两种结果。要么走不下去了，解析出错，直接杀掉。要么成功并和其他分支合并。

GLR具体内容较多，貌似也用不到。略过。

可获取语法单位的行号。

讲了一些基本流程/约定。

Reverse Polish Notation计算器语法

%define api.value.type {double} 定义语义值的类型。

%token NUM terminal(除了单字符的)都要用%token定义。

%empty意思是空

input: input xxxx 这种称为左递归。如果右边的input放在最后，称为右递归。文档有说只允许用左递归，右递归存在隐患。

{}里是匹配到规则时执行的c代码

$$是语义值

$x是展开的第x项。

必须要提供yylex() lexer的yylex()的返回值是一个数，即作业2中我们写的return (STR_CONST);之类。 bison中共用STR_CONST等等这一套枚举量。

必须要提供一个yyerror()来报错。

Infix Notation计算器

%left和%right指定左关联右关联

越晚定义优先级越大。所以^优先级最大。

%precedence NEG定义一个优先级标签，占个位。后续的%prec NEG赋予这个优先级。

其他例子自行学习。

make parser编译直接能成功。因为它用的tokens-lex.cc是老版本的flex生成的，所以不用像之前做lexer时做一些修改代码。 如果要把lexer替换成我们的，就需要修改了。 不过有很多warning。

用正确的lexer做scan并传给parser ../../bin/lexer good.cl | ./parser 报错。然后就要开始完善cool.y。

可以用正确的parser看看是什么样子。 ../../bin/lexer good.cl | ../../bin/parser

看cool.y

%union 待分析。 定义可作为结果的类型。会把代码复制到cool.tab.h。

对%union中定义的类型，可以用%type给nonterminal指定类型。 %type program

%token可以定义token的类型(%union中定义)和语义值。 比如%token BOOL_CONST 277

然后可以写具体的语法。

makefile里bison加参数--graph可以生成gv文件。是你parser的图示。 非常庞大的图。如文档所说，用来debug的话价值不大，因为过于繁琐。初学可以看看。

下载Graphviz程序 .\Graphviz\bin\dot.exe -Tsvg .\cool.gv > ./out.svg 目前能生成但是打开报错。

https://dreampuf.github.io/GraphvizOnline/ 可在线生成。

let先初始化一堆变量，再in一个expr，执行这个expr。 这个语法中间是一个list，但是cool-tree.cc中的创建函数只能单个创建。有点不正常。 看example/lam.cl中用了list的语法，初始化多个变量，而且用课程自带的parser能编过，说明他确实是实现了的。

看看自带的parser的输出，是一个树状结构。 dumptype.cc会打印各种类型，但dump_type我看了一圈全是打印_no_type，也没看出来什么名堂。

接续看打印结构和let_class::dump_with_types()的逻辑。 可以发现他是在每个let类里只放一个初始化，然后把其他的初始化放在这一个let的body里。

那么极大概率，需要把let的list的语法做成嵌套的结构。有几个初始化就要套几层，就要创建几个let。

然后let在cool语言中又可以嵌套。最简单的想法搞个栈。每次碰到let就往里压，每次结束一个let就释放。 这样嵌套的let不会相互干扰。 我是先匹配一个let，进栈。再从in expr往前匹配，这样可以先创建最底层的let，每组let只存一个最新的实例即可，代码比较简洁。 如果从前往后，可能要折腾数组。

https://en.wikipedia.org/wiki/Operator_associativity https://www.gnu.org/software/bison/manual/bison.html#Precedence

比如当一个类中的某个函数有错，需要Error Recovery，继续往下检查其他函数。 对于class列表/expr列表等都需要。

https://www.gnu.org/software/bison/manual/bison.html#Error-Recovery

基本原理就是在一个列表形式的匹配中加error的匹配。 类似这样

正常情况是不断把新的feature加到list中。现在如果某个feature报错，会产生一个error，也可以加到list中。 这样就不会造成整个feature_list失败，而是能继续查后续的feature。

google可以搜到cs143的grading脚本。可能需要改脚本，见下面作业4中的说明。 可能还要把lexer的链接复制过来。

list的顺序问题可导致通不过测试。比如类的feature list，写法不同导致顺序颠倒。 比如把feature list改成左递归，一下子通过了很多测试。

'~'是neg not是comp

通过70条测试。

经过parse后，得到了ast。需要在这个ast上进行semantic的检查。包括type/scope等各种cool手册中的规定。 并做一些补全。

用课程自带的程序运行看看效果 ../../bin/lexer ./bad.cl | ../../bin/parser | ../../bin/semant ../../bin/lexer ./good.cl | ../../bin/parser | ../../bin/semant

首先bad和good的基本词法都是对的。 但对比空白程序，正确的程序会改正一些no_type，会检测各种语义的细节。

看makefile。

文件:

http://semant-phase.cc main入口。ast_root是Program类型，在.y的最终program规则中赋值。 ast_root的semant()在http://semant.cc中实现。

http://ast-lex.cc 课程自带的正确的lexer代码。

http://ast-parse.cc 课程自带的正确的parser代码。

http://semant.cc 主要要改这个代码。

cool-tree.h 包含各种语法的定义。重要。

cool-tree.handcode.h 需要给有些语法组件添加函数，在这添加。

看懂semant的整个输出，看懂http://dumptype.cc，就懂了怎么遍历ast。

把id/int/string分别存在三个list里，各自不允许有重复。可进行查找等操作。 其实就是个hash表之类的东西，把所有出现的名字记录一下而已。

见symtab.h，http://symtab_example.cc和list.h。 基本是一个二维的结构，然后做一些添加查找。scope做成栈的效果。 它代码较为恶心，添加scope的逻辑配合它那个list，给我看呆了。而且只有new没有delete。 自己重写把。

每个symbol的名字和类型都可以采用Symbol类，一起放进symbol table。

从ast_root也就是program_class开始遍历ast。对于不同的语句都要实现一个check_symbol之类的函数，在里面根据语法操作symbol table。

我是到这个作业才找的测试脚本，前面的作业没测试。 到此可以把前面的测试也跑一下，改正茫茫多的错误。 最后的目标是把lexer和parser都换成自己的，仍能跑通所有测试。

google可以搜到cs143的grading脚本。可能需要改改才能跑。 在作业目录运行脚本perl pa4-grading.pl -v，生成grading文件夹并自动运行case，但输出都是找不到命令。 跟踪它的perl逻辑，最终会调其中的mysemant。 它是csh脚本，而我的环境是bash，所以出错。 改为bash格式，再运行加参数-r不再次解压，否则文件又会被它覆盖。 perl pa4-grading.pl -v -r可以得到评分了。

报错要按照它的格式来。

类默认继承自Object。继承中attr不能重复定义，method可重写，参数必须一样。 类的定义顺序可以随意，可以先使用某个类型，后续再定义。 这样可能造成循环继承，不允许出现循环继承。可以最先单独检查是否存在循环继承。 子类里不能改父类函数的参数。

课程代码的install_basic_classes()是生成内置的基本类。 ClassTable的构造函数里传入了program的class列表，即ast中的所有class。 那么可以在构造函数中检查类相关的错误。

直接调函数时，调用者实际为self。

SELF_TYPE可用于定义基类函数中返回自己，这样派生类new之后可以直接赋给派生类的变量，不用严格匹配类型。 代码按需要把dispatch返回的SELF_TYPE转成new出来的类型。见basic.test。

有很多地方需要转SELF_TYPE。

lowest common ancestor经典的最近公共父节点问题。 可简单暴力算。也可研究lca系列算法。

有的语句如case/if有多个返回分支，需要定一个static type。 把多个分支的LCA作为static type，并检查上下文。

遍历时可判断重复定义/名字在scope中不存在/类型不匹配等错误。 检查函数的返回类型。 要根据symbol table，用set_type()补全一些数据的类型。见输出中的no_type。 见测试。非常多的例子。

共74条测试。 它的loop永远会返回Object而不是body的类型。没搞懂。 因为这个原因有2个测试过不了。

最后http://semant.cc整了1700行代码。

看完课程视频的后半部分，看到书本第八章可以开始最后一个作业。

make cgen得到我们需要的cgen。 像之前的作业一样，从lexer/parser/semant一直输入到cgen。

用bash的话需要改造一下mycoolc脚本。

./mycoolc example.cl -o wtf.s -c 编译生成.s汇编。-c参数可控制cgen_debug打log。

../../bin/spim ./wtf.s mips模拟器运行生成的汇编。

http://cgen.cc 主要要修改的代码。 我是把之前重写的symbol table拿过来改造一下。然后不用它的list，改为std::list。指针改为std::shared_ptr。顺便熟悉了它的node逻辑。

http://cgen-phase.cc main函数。调用ast_root->cgen()。

这个文档很好，快速扫盲。 建议通读一遍。 https://web.stanford.edu/class/cs143/materials/SPIM_Manual.pdf

参考 https://www.cs.csub.edu/~eddie/cmps2240/doc/britton-mips-text.pdf

cgen生成汇编代码，assembler把汇编代码转成object文件。最后linker把所有obj转成可执行文件。 object文件的格式

header 文件各部分的大小和位置

text routine的机器指令。可能因为unresolved reference而无法执行。

data 一些二进制数据。可能因为unresolved reference而不可用。

relocation info 依赖于绝对地址的一些指令和数据

symbol table 外部的label和unresolved reference

debugging info 描述此程序的编译信息，以便debugger找到相应信息并正常工作。

单个obj本质上是可执行的？但如果有依赖外部就有问题。 linker把所有obj link起来，解决相互的依赖问题，生成可执行文件。

操作系统运行程序时先做loading。

https://en.wikipedia.org/wiki/Call_stack https://courses.cs.washington.edu/courses/cse410/09sp/examples/MIPSCallingConventionsSummary.pdf https://web.archive.org/web/20130111161107/http://pages.cs.wisc.edu/~cs354-2/beyond354/conventions.html