Doraemonzzz

课程主页： https://www.edx.org/course/compilers 课程视频： https://www.bilibili.com/video/BV1NE411376V?p=20&t=6 备注： 图片均来自于课件。 这部分回顾Cool的类型检查。 静态类型 vs 动态类型 静态类型系统（在编译时刻）检测常见错误。 但是某些正确的程序不被静态类型系统允许 所以有些人主张动态类型检查。 其他人想要更具表达力的静态类型检查。 更具表达力的类型系统往往更复杂。 对象的动态类型是创建它的“new C”表达式中使用的类C。 动态类型是运行时概念。 即使非静态类型的语言也具有动态类型的概念。 表达式的静态类型捕获该表达式可能具有的所有动态类型。 静态类型是编译时概念。 稳定性定理： 对于所有表达式$\mathrm{E}$ \text{dynamic_type(E) = static_type(E)}在所有执行中，$\mathrm{E}$求值为编译器推断的类型的值。 Cool类型系统的稳定性定理： \forall \mathrm E, \text{ ...

课程主页： https://www.edx.org/course/compilers 课程视频： https://www.bilibili.com/video/BV1NE411376V?p=20&t=6 备注： 图片均来自于课件。 这部分回顾语义分析和类型检查。 语义分析导论编译器的前端部分如下： 词法分析 检测输入中的非法token。 解析 检测输入中格式错误的解析树。 语义分析 “前端”的最后阶段。 作用捕获所有剩余的错误。 之所以需要语义分析，主要有以下两点原因： 解析无法捕获某些错误。 某些语言的构造不是上下文无关的。 语义分析的要求取决于语言，coolc的语义分析检查： 所有标识符都已声明。 类型。 继承关系。 类只定义一次。 类中的方法只定义一次。 保留的标识符没有被滥用。 作用域（scope）作用域将标识符声明与用途匹配： 这是大多数语言中重要的静态分析步骤，也包括COOL。 例子 例1 \text { let y:} \text { String } \leftarrow \text{"abc" in y} +3这里$\tex ...

前一篇博客%E7%8E%AF%E5%A2%83%E9%85%8D%E7%BD%AE/)中介绍了如何在windows环境下配置chez scheme开发环境，但是这个版本的scheme在做3.5节习题时会碰到不少问题，这里介绍如何利用wsl2 + vscode配置mit scheme环境。 参考资料： wsl+ubuntu: https://www.zhihu.com/question/389774000 https://www.jianshu.com/p/6b02948b3d37 https://www.jianshu.com/p/3e627ff45ccb https://docs.microsoft.com/zh-cn/windows/wsl/install-win10#manual-installation-steps https://www.howtoinstall.me/ubuntu/18-04/mit-scheme/ https://jingyan.baidu.com/article/e5c39bf5e89c3039d660336a.html https://github.c ...

这次更新第3章剩余习题。 参考资料： http://csapp.cs.cmu.edu/3e/waside/waside-embedded-asm.pdf https://github.com/DreamAndDead/CSAPP-3e-Solutions https://dreamanddead.github.io/CSAPP-3e-Solutions/ https://cs.nyu.edu/wies/teaching/cso-fa19/class13_machine.pdf Chapter 33.68C代码： typedef struct { int x[A][B]; /* Unknovn constants A and B */ long y; } str1; typedef struct { char array[B]; int t; short s[A]; long u; } str2; void setVal(str1 *p, str2 *q) { long v1 ...

书籍介绍： https://book.douban.com/subject/21323941/ github仓库： https://github.com/Doraemonzzz/Concrete-Mathematics 这次回顾第三章，整值函数。 第3章 整值函数热身题1注意到 \begin{aligned} 2^m &\le 2^m + l < 2^{m} + 2^m\\ m &\le \log_2(2^m + l)

这次更新第3章习题。 参考资料： https://dreamanddead.github.io/CSAPP-3e-Solutions/chapter3/ https://cs.nyu.edu/wies/teaching/cso-fa19/class13_machine.pdf Chapter 3难题:3.59 3.58汇编代码： decode2: subq %rdx, %rsi # y = y - z imulq %rsi, %rdi # x = x * y movq %rsi, %rax # tmp = y salq $63, %rax # tmp = tmp << 63 sarq $63, %rax # tmp = tmp >> 63 xorq %rdi, %rax # tmp = tmp ^ x ret 对于移位操作，如果tmp为偶数，那么 (tmp << 63) >> 63 = 0...0 否则， (tmp ...

这次回顾第三章第五部分习题。 学习资料： 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 3.43(p21 ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 参考资料： https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture15.pdf https://piazza.com/class_profile/get_resource/honxzoabz711ew/hvep5i3vb292gs 这次回顾HW5。 2. Horn Formulas参考资料： https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture15.pdf set all variables to false $W=\{v|(\Rightarrow v)\in \text{formulas} \}$ while $W\neq \varnothing$: $\forall v\i ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 这次回顾Section 5。 1.Horn Formula Practice(a) 迭代轮数 $x$ $y$ $z$ $w$ 0 f f f f 1 t t f f 2 t t f t 3 产生矛盾 (b) 迭代轮数 $x$ $y$ $z$ $w$ 0 f f f f 1 f f t t 2. Huffiman Proofs1假设$i$是出现次数最多的字符，那么其出现比例$p_i > \frac{2}{5}$，在最后一轮之前，每轮至少有个两个字符$j,k$（合并后的字符视为一个字符）出现频率比$i$小，这是因为如果该结论不成立，那么 p_i + p_j+p_k > 1这就与定义矛盾，因此在最后一轮之前都不会合并$i$，从而$i$在最后一轮合并，由此可得存在长度为$1$的编码。 对 ...

这次回顾第三章第四部分习题。 学习资料： 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 3.33(p20 ...

课程主页： https://cs170.org/ https://inst.eecs.berkeley.edu/~cs170/fa18/ 课程视频： https://www.bilibili.com/video/BV1wK411g7ck 这次回顾Section 4。 1. Minimum Spanning Trees (short answer)(a)初始化$X= E’$，对$(u, v)\in E’$，令 $\mathrm{union}(u,v)$ 剩余部分不变。 (b)对每条边加上权重$d$，使得每条边的权重都为正数，然后计算MST，注意MST包括的边数恒定，所以新旧MST的权重对应关系为 w\leftrightarrow w + |V| d由此可得变换后的MST和原始的MST一一对应。 (c)构造新图$G’$，令$w(u,v)=-w(u,v)$，然后计算$G’$的MST即可。 2. Picking a Favorite MST对于Kruskal算法，每轮迭代中选择属于$F$的边；对于Prim算法，只有当$(v,z)\in F$时才更新cost。 3. MST Varian ...

这次回顾第三章第三部分习题。 学习资料： 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 3.24(p18 ...