编译原理(H) 第一次习题课

作业 注意过程 作业共性的问题比较少，也没有人提问。下面只 讲一道难一点的题

最多只有一处相邻数字相同的所有数字串 思路： 首先考虑相邻数字都不相同的串 从两个数字开始，用归纳的方法扩展到十个数字 记相邻数字都不相同的串为S，则所求为SS 证明：SS满足要求，满足要求的串都可以表示为 SS

答案 no_1 = ‘0’ no_2 = no_1 | (‘1’ | no_1 ‘1’) (no_1 ‘1’)* no_1? no_3 = … … S = no_9 | (‘9’ | no_9 ‘9’) (no_9 ‘9’)* no_9? | ε ans = S S

某次作业 讨论：分析树与抽象语法树的区别

举例 x=1 y=2 3*(x+y) prog : ( stat )+ ; stat : expr | ID '=' expr NEWLINE | NEWLINE ; expr : multExpr (( '+' | '-' ) multExpr)* multExpr: atom ('*' atom)*; atom : INT | ID | '('! expr ')'!; x=1 y=2 3*(x+y) http://stackoverflow.co m/questions/5026517/ whats-the-difference- between-parse-tree- and-ast

分析树 x=1 y=2 3*(x+y) http://stackoverflow.co m/questions/5026517/ whats-the-difference- between-parse-tree- and-ast

AST x=1 y=2 3*(x+y) http://stackoverflow.co m/questions/5026517/ whats-the-difference- between-parse-tree- and-ast

MP1.1 部分同学没有去看提供的源代码。至少要对API 以及程序执行流程进行阅读 对COOL support code中的list的理解

list 是一个类似lisp表的，递归定义的单链表 结构：head, tail 接口：hd(), tl()

MP1.2 为什么不在这时候进行atoi？ 词法分析负责将字符流转换为token流，对常量进行转 换、判断是否越界，是后面语法、语义分析的内容

MP1.2 Ref bin的一个bug：字符串转义+EOF结尾 <STR>\" { ... } <STR><<EOF>> { ... } “\<<EOF>>”这样的序列会在STR中失配

MP1.2 Ref bin的另一个bug：多文件。正确处理： - 重置所有状态：注释层数等 - BEGIN(0)：防止无限输出 - YY_NEW_FILE宏

讨论：大家遇到的难以解决的bug以及如何解决

MP1.3 两次提交要求补充说明： 第一次提交要求可以识别正确的文法并产生AST。 注意AST结构与分析树结构、以及与cool文档的 syntax定义的区别。对正确样例的测试将以这次 提交为准，之后有修正会适当减分 第二次提交要求做错误处理与恢复。这部分不要 求与标程行为一致，但要求提供测试用例、文档 说明

MP1.3 一些指导 阅读ast-tree.h，了解你需要生成的AST node 编写文法。冲突的问题，可以借助命令 bison –report-file=FILE 打印分析表 let expression：二义的问题，

Clang和LLVM 在MP1.3两次提交之间、以及MP2中间，会有有 关clang和llvm的内容。 What is LLVM? A “collection of modular and reusable compiler and toolchain technologies” used to develop compiler front ends and back ends. 负责平台无关的中间代码到机器码的优化、代码生成

学习LLVM clang –S –emit-llvm：编译C到LLVM 阅读 http://llvm.org/releases/3.9.0/docs/LangRef.html 根据助教的指导，完成kaleidoscope实验

Clang源码阅读 阅读“Clang” CFE Internals Manual 从main函数读起 使用Doxygen生成文档 学习一些设计模式

理解visitor模式 分离遍历本身与遍历途中的操作 Visitor实现对每个节点的操作，另有遍历器负责 对数据结构进行遍历，要完成的操作由visitor指 定 使用该模式：继承visitor基类，实现对应节点的 访问方法，即可将其传给遍历器，由遍历器在合 适的时机调用

理解visitor模式 以SimpleStreamChecker类为例： class SimpleStreamChecker : public Checker<[…]> { public: checkPostCall(…) { … } checkPreCall(…) { … } checkDeadSymbols(…) { … } }

形式语言 字母表 形式语言 : 字符串集合 非终结符 开始符号 产生式 : 重写规则的集合 形式语法 每个语法定义一个语言 的子集

的分类 乔姆斯基谱系 Chomsky hierarchy Type-0 grammars (unrestricted grammars) Type-1 grammars (context-sensitive grammars) Type-2 grammars (context-free grammars)  Type-3 grammars (regular grammars) 

CFG 的子集 LR(0) grammars LR(0) 项目 直接利用栈中信息就能完成分析. 例子: LR(0) 从识别的角度定义的.

CFG 的子集 LR(0) grammars SLR grammars 利用 FOLLOW 集解决部分冲突 例子: 表达式 LR(0) 从识别的角度定义的. SLR(1)

CFG 的子集 LR(0) grammars SLR grammars LR(1) grammars 引入 LR(1)项目, 比 FOLLOW 考虑更细致 LR(0) 从识别的角度定义的. SLR(1) LR(1)

CFG 的子集 LR(0) grammars SLR grammars LALR(1) grammars LR(1) grammars 同心 LR(1)项目, 合并后, 可能有 LR(1) 没有的冲突 例 LR(1) grammars 例3.34, P86 LR(0) http://people.cs.vt.edu/~ryder/515/f05/homework/hw1ans.pdf SLR(1) LALR(1) LR(1)

CFG 的子集 LR(0) grammars SLR grammars LALR(1) grammars LR(1) grammars LL(1) grammars 和上面的不在一个维度上 LR(0) 从识别的角度定义的. SLR(1) LALR(1) LL(1) LR(1)

CFG 的子集 LR(0) grammars SLR grammars LALR(1) grammars LR(1) grammars LL(1) grammars 和上面的不在一个维度上 LR(0) http://people.cs.vt.edu/~ryder/515/f05/homework/hw1ans.pdf SLR(1) LALR(1) LL(1) LR(1)

CFG 的子集 LR(0) grammars SLR grammars LALR(1) grammars LR(1) grammars LL(1) grammars 书 P88, 例3.36 CFG 非二义 CFG LR(0) SLR(1) LALR(1) LL(1) LR(1)

CFG 的子集 二义的 CFG (语言) CFG 无二义 CFG LR(0) SLR(1) LALR(1) LL(1) LR(1) 为什么是两个 CFG 相交? Anbncndn 是什么语言? SLR(1) LALR(1) LL(1) LR(1)

CFG 的子集 二义的 CFG (语言) CFG 无二义 CFG LR(0) SLR(1) LALR(1) LL(1) LR(1) 为什么是两个 CFG 相交? Anbncndn 是什么语言? SLR(1) LALR(1) LL(1) LR(1)

K 变大, 会变强吗? http://www.cs.cornell.edu/Courses/cs412/2006sp/lectures/lec09.pdf https://www.wikiwand.com/en/LR_parser https://www.wikiwand.com/en/LALR_parser http://www.antlr2.org/article/needlook.html 理论上 LR(1) = LR( k), 实际不方便报错

K 变大, 会变强吗? http://www.cs.cornell.edu/Courses/cs412/2006sp/lectures/lec09.pdf https://www.wikiwand.com/en/LR_parser https://www.wikiwand.com/en/LALR_parser http://www.antlr2.org/article/needlook.html 理论上 LR(1) = LR( k), 实际不方便报错

K 变大, 会变强吗? http://www.cs.cornell.edu/Courses/cs412/2006sp/lectures/lec09.pdf https://www.wikiwand.com/en/LR_parser https://www.wikiwand.com/en/LALR_parser http://www.antlr2.org/article/needlook.html 理论上 LR(1) = LR( k), 实际不方便报错

K 变大, 会变强吗? LL(k+1) , not LL(k) LL(k+1) , not LL(k) http://www.cs.cornell.edu/Courses/cs412/2006sp/lectures/lec09.pdf https://www.wikiwand.com/en/LR_parser https://www.wikiwand.com/en/LALR_parser http://www.antlr2.org/article/needlook.html 理论上 LR(1) = LR( k), 实际不方便报错 LL(k+1) , not LL(k)

最左/最右推导与二义 一个分析树有很多种推导顺序 分析树的结构 语义 一个句子对应多个分析树 二义的语法 语义 : 顺序, 块

最左/最右推导与二义 一个分析树有很多种推导顺序 分析树的结构 语义 一个句子对应多个分析树 二义的语法 分析树的结构 语义 一个句子对应多个分析树 二义的语法 没有二义的语法最左最右产生 的分析树相同? 语义 : 顺序, 块

LR 分析 定义 句型 右句型 句柄 活前缀

LR 分析 定义 分析中出现了两个句柄, 文法是二义的吗? 句型 : 推导到一半的字符串(也可能推到底了) 右句型 : 最右推导得到的句型 句柄 : 句型中和一个产生式右部匹配的子串, 并且, 把 它规约成改产生式左部的非终结符代表了最右推导过 程的逆过程的一步. 活前缀 : 右句型的前缀,该前缀不超过该右句型的最右 句柄的右端 分析中出现了两个句柄, 文法是二义的吗?

LR 分析 分析中出现冲突, 文法是二义的吗?

LR 分析 分析中出现冲突, 文法是二义的吗? 二义文法一定会在分析中出现冲突吗?

现代编程语言的前端 绝大多数是手写的递归下降分析器 GCC 早期使用 yacc : LALR 更好的错误提示 对于上下文相关的语言特性, CFG 无能为力 (下一个实验) GCC 早期使用 yacc : LALR Ocaml , Haskell 使用类似 yacc 工具: LALR https://www.quora.com/What-are-the-parsing-techniques-used-by-modern-compilers