编译原理

更新: 2021-06-30 20:19:57

课程主要参考：哈工大编译原理陈鄞
https://blog.csdn.net/Johan_Joe_King/article/details/79051993 https://blog.csdn.net/Johan_Joe_King/article/details/79058597?spm=1001.2014.3001.5501
关于展望符：https://www.cnblogs.com/xpwi/p/11070888.html
短语相关：
https://blog.csdn.net/qq_40147863/article/details/93236597
https://blog.csdn.net/starter_____/article/details/88601595
写实验：
手把手写C：https://lotabout.me/2016/write-a-C-interpreter-8/
语法分析：https://blog.csdn.net/qq_38247544/article/details/84582654
https://www.cnblogs.com/bluemo/p/13937473.html
目标代码生成：https://blog.csdn.net/qq_38247544/article/details/85076074
解释执行：https://blog.csdn.net/qq_38247544/article/details/85223084
晗哥网站:https://jcf94.com/2016/02/21/2016-02-21-pl0/

一、按照知识点/题型

1. 求First集、Follow集

求解规则

另一种表达
(1)对文法的开始符号 S，置‘#’于FOLOOW（S）中；
(2)若A→αBb 是一个规则，则把FIRST(b)-{ε}加到FOLLOW(B)中；
(3)若A→αB 是一个规则，或A→αBb 是一个规则，而 b=>ε，即ε∈FIRST(b),则把FOLLOW(A)加至FOLLOW(B)中。

原来的式子中虽然是αBβ, 但是β可能为ε的情况，式子会变为αB，这时运用第三条规则。

B站视频 10min学会对应的博客

2. 简答题/概念题

(1) 编译程序分哪几个主要部分？各部分的主要功能是什么？

词法分析器，又称扫描器，输入源程序，进行语法分析，输出单词符号。

语法分析器

语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出各类

语法单位，最终判断输入串是否构成语法上正确的「程序」。

语义分析与中间代码产生器

语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分

析，并把它们翻译成一定形式的中间代码。有的编译程序在识别语法单位后，会构造并输出一棵表示语

法结构的语法树，然后根据语法树进行语义分析和中间代码的产生。有的直接调用语义子程序，所以上

述三者可能是互相穿插的。

优化器

对中间代码进行优化处理

目标代码生成器

把中间代码翻译成目标程序

表格管理

在编译程序的工作过程中的一系列表格，用来登记源程序的各类信息和编译各阶段的进展状况。最重要

的是符号表，用来登记源程序中出现的每个名字以及名字的各种属性。

出错处理

出错处理程序：对出现在源程序中的错误进行处理，如果有错误应该设法发现错误，并且把有关错误信

息报告给用户。源程序中错误通常分为：语法错误和语义错误两大类。

(2) 描述LR语法分析算法。

(3) 解释语法制导翻译。

(4) L（G）={an bn︱n≥1}，试求上下文无关文法G。

(5) C语言活动记录的结构是怎样的？

从下往上：返回地址、动态链、静态链、形式单元、局部变量、内情变量、临时单元

SP TOP

(6) 语法分析有哪些方法，特点是什么

自上而下 LL(1)

自下而上 LR(0) SLR LR(1) LALR

(7) 属性文法是什么，L属性文法和S属性文法？

S属性文法：只有综合属性，适合自下而上，从自己或者儿子传过来，可以一遍过

L属性文法：综合属性 + 继承属性，适合自上而下，从自己或者父亲或者左边好兄弟传过来，可以一遍过

(8) 画出程序设计总框图

(10) 写三元式、四元式、间接三元式、后缀式

(11) 短语的概念，算符优先文法

短语定义：若 S 为文法 G 的开始符号，αβδ 是该文法的一个句型，即 S ⇒* αβδ，且有 A ⇒+ β，则称 β 是句型 αβδ 相对于非终结符 A 的短语。语法树：在语法树中表示所有分支结点对应子树，短语即子树叶子对应的符号。注：子树包括语法树本身，及句型本身也可以称为短语。直接短语定义：若 S ⇒* αβδ，且文法中包含产生式 A → β，则称 β 是句型 αβδ 相对于非终结符 A 的直接短语。语法树：在语法树中表示为该短语只有上下相邻父子两代

句柄 “可规约串”，句柄对应某个产生式的右部，是某个，但不是任意一个。作为一种规约对象，句柄表示最左直接短语。语法树：在语法树上，则表示为最左边的只包含相邻父子节点的短语（最左直接短语）

素短语定义：是指一个短语至少包含一个终结符，并且除它自身之外不再包含其他素短语

最左素短语定义：最左素短语就是句型最左边的素短语，是算符优先分析法的规约对象。语法树：通过语法树分析时，要注意先判断是否为素短语，再找相对最左端的素短语。