Doraemonzzz

课程主页： https://www.edx.org/course/compilers 课程视频： https://www.bilibili.com/video/BV1NE411376V?p=20&t=6 这部分对PA5进行翻译。 编程作业V1. 简介在本作业中，您将实现一个代码生成器。成功完成后，您将拥有一个功能齐全的Cool编译器！ ​ 代码生成器使用PA3中构造的AST和PA4中执行的静态分析。你的代码生成器应该产生MIPS汇编代码，忠实地实现任何正确的Cool程序。代码生成中没有错误恢复——所有错误的Cool程序都已被编译器的前端阶段检测到。​​ 与静态分析任务一样，此任务具有相当大的设计决策空间。如果生成器生成的代码工作正常，则程序是正确的；如何实现这个目标取决于你自己。我们会建议一些我们认为会让你的生活更轻松的惯例，但你不必接受我们的建议。一如既往，在README文件中解释并证明您的设计决策。这个任务的代码量大约是前一个编程任务的两倍，尽管它们共享很多相同的基础结构。早点开始！​​ 获得一个正确的代码生成器的关键是透彻地了解Cool构造的预期行为以 ...

课程主页： https://www.edx.org/course/compilers 课程视频： https://www.bilibili.com/video/BV1NE411376V?p=20&t=6 这部分对PA4进行翻译。 编程作业 IV1. 简介在此作业中，您将实现Cool的静态语义分析。您将使用解析器构建的抽象语法树（AST）来检查程序是否符合Cool规范。您的静态语义组件应拒绝错误的程序； 对于正确的程序，它必须收集某些信息以供代码生成器使用。语义分析器的输出将是带注释的AST，供代码生成器使用。 ​ 与以前的作业相比，这次作业具有更大的设计决策空间。如果语义分析器根据规格检查程序，则它是正确的。这次作业没有标准的正确答案，但是可以检查出错误答案。我们认为许多标准做法会使此次作业更轻松，我们将尝试将这些方法传达给您。但是，您所做的主要是取决于您。无论您决定做什么，都应证明并解释您的解决方案。 ​ 您将需要参考《Cool参考手册》中定义的输入规则，标识符作用域规则和其他有关Cool的限制。您还需要为此阶段将方法和数据成员添加到AST类定义中。抽象语法树包 ...

在完成SICP 4.21时接触到Y运算符，感觉很巧妙，这里加以总结，大部分内容来自于第二份讲义，这里只做了翻译以及总结的工作。 参考资料： https://liujiacai.net/blog/2016/02/22/recursion-without-name/ https://mvanier.livejournal.com/2897.html 问题的引入问题来自于sicp习题4.21，基本问题是，如何不使用递归来定义递归函数？答案是，使用Y运算符。后续会一步步引入Y运算符，为了叙述方便，这里以阶乘函数为例： (define factorial (lambda (n) (if (= n 0) 1 (* n (factorial (- n 1)))))) 简单的想法为了消除递归定义，只要将函数内factorial替换即可： (define sort-of-factorial (lambda (n) (if (= n 0) 1 (* n (<???> (- n 1)))))) 那么???处应该也 ...

课程主页： https://www.edx.org/course/compilers 课程视频： https://www.bilibili.com/video/BV1NE411376V?p=20&t=6 备注： 图片均来自于课件。 这次回顾Java。 Java Java：COOL的升级版 同一时期出现 包含 数组 异常（Exceptions） 接口（Interfaces） 强制（Coercions） 线程 动态加载和初始化 总结 历史 Java出现在SUN公司 最初针对机顶盒设备 最初的开发花费了数年（91-94） 后来重新定位为互联网语言（94-95） 每种新语言都需要一个“杀手级应用” 竞争对手是TCL，Python 一些语言比较 Modula-3 类型 Eiffel，ObjectiveC，C ++ 面向对象，接口 Lisp Java的动态风格（许多功能） 对比COOL 从我们的角度来看，Java是COOL的增强版，增加了如下特性 异常（Exceptions） 接口（Interfaces） 线程 动态加载 其他一些次要的特性 Java ...

课程主页： https://www.edx.org/course/compilers 课程视频： https://www.bilibili.com/video/BV1NE411376V?p=20&t=6 备注： 图片均来自于课件。 这次回顾垃圾回收。 自动内存管理 在现代编程中，存储管理仍然是一个难题 C和C++程序有很多存储错误 忘记释放未使用的内存 取消引用悬空指针（dereferencing a dangling pointer） 意外覆盖部分数据结构 等等… 很难找到存储错误 但错误可能会导致明显的影响。 历史 这是一个老问题： 自1950年代开始对LISP进行研究。 有众所周知的全自动内存管理技术； 随着Java的流行而成为主流。 内存管理动机 创建对象时，将自动分配未使用的空间。 在Cool中，新的对象由new创建。 一段时间后，不再有未使用的空间。 一些空间将被不再使用的对象占据。 此空间可以释放以供以后重用。 我们如何知道某个对象将“不再使用”？ 观察：程序只能使用可以找到的对象： let x : A <- new A i ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 参考资料： https://cs170.org/assets/pdf/dis12-sol.pdf https://www.cse.iitk.ac.in/users/rmittal/prev_course/f14/notes/lec24.pdf http://theory.stanford.edu/~trevisan/cs261/lecture07.pdf https://cs170.org/assets/pdf/hw11-sol.pdf 这次回顾HW11。 2. 2-SAT and Variants(a)注意到$x \vee y$等价于 (\neg x \Rightarrow y)\and (\neg y \Rightarrow x)所以构造图，图中节点为$x,\neg x$，对于$x\vee y$，增加有向边 \begin{aligned} ( ...

这次回顾第四章第二部分习题。 学习资料： https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/index.htm https://github.com/DeathKing/Learning-SICP https://mitpress.mit.edu/sites/default/files/sicp/index.html https://www.bilibili.com/video/BV1Xx41117tr?from=search&seid=14983483066585274454 参考资料： https://sicp.readthedocs.io/en/latest http://community.schemewiki.org/?SICP-Solutions http://community.schemewiki.org/?sicp https://l ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 参考资料： https://blogs.asarkar.com/assets/docs/algorithms-curated/Maximum%20Independent%20Set%20Problem%20-%20Chekuri.pdf https://cs170.org/assets/pdf/dis10-sol.pdf 这次回顾HW14。 3. Entanglement(a) \begin{aligned} \alpha_0 \beta_0 &=\frac 1 {\sqrt 2}\\ \alpha_0 \beta_1 &=0\\ \alpha_1 \beta_0 &=0\\ \alpha_1 \beta_1 &=\frac 1 {\sqrt 2}\\ \end{aligned}等式$1,4$说明$\alpha_i,\beta_j$都不为$0$，这 ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 参考资料： https://blogs.asarkar.com/assets/docs/algorithms-curated/Maximum%20Independent%20Set%20Problem%20-%20Chekuri.pdf 这次回顾HW13。 2. Universal Hashing备注： 个人感觉这里有个前提条件，就是$a_1,a_2$是从$[m]$中均匀选择的。 (a)假设$(x_1,x_2)\neq (y_1, y_2)$，并且 a_1x_1 + a_2 x_2 \equiv a_1y_1 +a_2 y_2 \bmod m不失一般性，假设$x_2\neq y_2$，那么 a_1(x_1 -y_1 )\equiv a_2(x_2 - y_2) \bmod m由于$m$是质数，并且$x_2 -y_2\neq 0$，所以 a_2 ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 这次回顾Section 12。 1. 2-Universal Hashing(a) \begin{aligned} \mathrm{Pr}_{h\in \mathcal H}[h(x)=h(y)] &=\sum_{i=0}^{m-1} \mathrm{Pr}_{h\in \mathcal H}[(h(x),h(y))=(i, i)]\\ &=\sum_{i=0}^{m-1} \frac{1}{m^2}\\ &=\frac 1 m \end{aligned}(b)(i)参考了习题解答。 考虑下表： $x$ $y$ $z$ $h_1$ $0$ $0$ $1$ $h_2$ $1$ $0$ $1$ 假设$x,y,z$选择$h_1,h_2$的概率为$\frac 1 2$，那么显然该函数族为Universal Hashing。 另一 ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 参考资料： https://blogs.asarkar.com/assets/docs/algorithms-curated/Maximum%20Independent%20Set%20Problem%20-%20Chekuri.pdf 这次回顾HW12。 2. Independent Set Approximation参考资料： https://blogs.asarkar.com/assets/docs/algorithms-curated/Maximum%20Independent%20Set%20Problem%20-%20Chekuri.pdf 给出如下算法： $S\leftarrow \varnothing$: while $G\neq \varnothing$: 令$v$为$G$中度最小的节点 $S\leftarrow S\cup \{ ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 这次回顾Section 11。 1. Local Search for Max Cut(a)因为每步操作会让cut的大小至少增加$1$，而cut的最大值为$|E|$，所以最多循环$|E|$次。 (b)对于$v\in V$，记 \begin{aligned} d_{in}(v)&= \sharp \{ u| (u,v) \in E,u,v\in S或u,v \in T\}\\ d_{out}(v)&= \sharp \{ u| (u,v) \in E,u\in S, v\in T或u\in T,v \in S\} \end{aligned}那么Max Cut为 c=\frac{1}{2}\sum_{v} d_{out}(v)注意到对于任意$v$，都有 d_{out}(v) \ge d_{in}(v)以及 \sum_{v} d_{out}(v ...