编译原理最终复习

时间：2022-03-24 16:26:47

编译原理最终复习

@(Campus_learning)

第一章 引论

  1. 编译与汇编的区别
    编译：高级语言翻译成机器语言或者汇编语言
    汇编：汇编语言到机器语言

  2. 一般一段高级语言需要经历以下四个阶段才能够使用：
    预处理器→编译器→汇编器→链接器

    预处理阶段：写好的高级语言的程序文本比如hello.c,预处理器根据#开头的命令，修改原始的程序，如#include

第二章 词法分析

  1. ”遍“ 和 ”阶段“ 的区别？
    答：编译的几个阶段往往通过一遍(pass)扫描来完成，通过是指读一个文件和写一个文件的过程。把几个阶段组成“一遍”，并且这些阶段的活动在遍中交错进行是经常发生的。
  2. 程序设计语言的五个基本语法单元？
    答：关键字、标识符、常量、运算符、界符
  3. 正规文法、右线性文法区别与联系？
    答：首先明确，右线性文法是特殊的正规文法，正规文法的产生式诸如：A→aB或A→a，a∈Vt*，当a长度为1的时候，就是右线性文法了
    几个好的练习题在：p17 例2.5 2.6
  4. 正规式如何来表示单词符号？
    这个表示方式与正规文法类似，大致的形式是：b(ab)*，与正规集对应则是：L(b(ab)*)={b，bab，babab…}
    几个比较好的练习题:p19 例2.12 2.13
  5. 正规文法和正规式的转换？
    比较好的练习题在: p20 例2.14（强调正规文法里面是没有表示运算意义的括号的）
  6. 正规文法、状态转换图、正规式的转换？
    （1）正规文法→状态转换图 p22 （2）正规式→状态转换图 p23
    比较好的例题：p24 例2.18 例2.19☆
  7. 有穷自动机(DFA)、非确定的有穷自动机(NFA)的概念
    具体的在p28、p29，注意的是，有穷自动机的表示方式有（1）DFA的状态转移矩阵(2)DFA状态转换图。
  8. 如何将NFA转换成DFA？
    这个不是很难，但必须掌握，主要就是闭包和状态子集，参考例2.24
  9. DFA的简化？
    这个是重点，必须掌握，难度也不大。主要分三步：（1）画出空的下三角关系图（2）首先将终态和非终态区分开（3）依次将各个状态对经过所有输入来判断得到的状态是否等价，重复多次 。 非常好的一个例题在 p32 例2.25
  10. 第二章比较好的习题
    p37 1,2（2）,4,5,12,14 明确几点:(1)DFA的状态转换图不能出现空字（2）文法表示不能出现运算意义的括号

第三章 语法分析

  1. 四种类型文法具体是哪些，正则表达式的描述能力是怎样的？
    0型文法：描述一切 （短语文法）
    1型文法：能够描述 anbncn （上下文有关文法）
    2型文法：能够描述 anbn （上下文无关文法，用来描述语法规则）
    3型文法：能够描述 anbm （正规文法，用来描述单词）
    一个生动的例子就是配对的括号，对应的语法应该是： A→(A)|( )，这样一个语言是无法用正规文法描述的。
  2. 看下面几个语言到句型的转换
    {anbm|1<=m<=n<=2∗m}⇒S→aSb|aaSb|ab|aab
    {anbm|m>0,n>0}⇒S→aS|Sb
    {anbn|n>=1}⇒S→aSb|ab
    比较好的习题p41 例3.5
  3. 直接推导、间接推导，句型、句子、语言、上下文无关语言？
    直接推导：αAβ直接推导出αγβ当且仅当 A→γ,α,β∈(VT∪VN)∗
    间接推导： α1⇒α2⇒...⇒αn⇔α1⇒∗αn
    句型&句子：如果 S⇒∗α 认为α是语言S的一个句型，如果α仅含有终结符，那么认为α是一个句子
    语言：文法产生的全体句子是一个语言
    上下文无关语言：由上下文无关文法所产生的语言称为上下文无关语言。
  4. 产生式个数和产生式变元个数的计算
    p41 例3.6
  5. 语法分析树的几个要求？
    一般的要求都能记住，容易忽略的在于(5): 如果节点带有标记ε，则该节点是其父节点的唯一儿子节点
  6. 文法的二义性？
    E⇒(E)⇒(E+E)⇒(E∗E+E)⇒(i∗E+E)⇒(i∗i+E)⇒(i∗i+i)
    E⇒(E)⇒(E∗E)⇒(i∗E)⇒(i∗E+E)⇒(i∗i+E)⇒(i∗i+i)
    同样都是最左推导，但是使用的产生式的顺序却不同
  7. 文法的二义性、语言的二义性概念
    对于某个文法中，只要任意一个句子对应两棵不同语法分析树，那么该文法是二义性的
    如果产生该语言的文法全是二义性的，那么该语言是二义性的
  8. LL(1),
    LL(1)：自上而下、最左推导，本质是一种试探过程，一定是无二义的
  9. 左递归问题?
    分为直接左递归和间接左递归，关于直接左递归，消除公式为：
    出现： P→Pα | β⇔P⇒βS
                                     S⇒αS | ε
    间接左递归不考，但是如果做的话，就是消元的思想
  10. 回溯问题几个知识点
    • 可以对文法G的句子进行不带回溯的自上而下的语法分析的判据：文法G的终结符的所有候选式的首符号集两两相交为空，并均不含ε:
      FIRST(α1)∩...∩FIRST(αn)=∅
      FIRST(α1)∪...∪FIRST(αn)∉ε
  11. 关于LL(1)文法的判据(能够进行不带回溯的自上而下的语法分析)：对任何非终结符引导的产生式： A→α|β 对下面的条件成立：
    (1) FIRST(α)∩FIRST(β)=∅
    (2) 如果β⇒*ε ,FIRST(β)∩FOLLOW(A)=∅
    任何LL(1)文法都是无二义的，且不含左递归，但并不是所有的语言都可以用LL(1)文法来描述
  12. 计算FIRST集合和FOLLOW集合 p51、52⭐️
  13. 几个常见的分析表构造，虽然不考，但能理下学习思路：
    LR(0): 局限比较大，但却是建立一般LR分析表的基础，LR(0)项目的概念在14
    SLR(1): 这种分析方法是基于SLR(1)分析表的，主要用来讨论移进归约冲突但是需要积累它的判据：假定LR(0)项目集规范族中，含有n个归约项目，m个移进项目，如果对于一个终结符 α 能选择唯一一个产生式进行处理 p66，就是没有移进归约冲突。
    LR(1): 这种表适用大多数上下文无关文法，但分析表体积庞大。需要积累的判据是：
    LALR(1): 能力介于SLR(1)分析表和LR(1)分析表之间
    LR文法肯定是无二义性的
  14. 几个基础概念：句柄、活前缀、LR(0)项目、归约项目、移进项目、待约项目
    活前缀：句柄的前缀字符串
    LR(0)项目：对于产生式有部某个位置上标有原点的产生式称为该文法的一个LR(0)项目
    LR(1)项目：就是对LR(0)项目集中的每个元素做一步的展望
  15. 拓广文法：假定文法G以S为开始符号的文法，构造一个文法G‘，它包含了整个G，但引进了一个非终结符S’，并加进一个新产生式S‘→S，而这个S’是G‘的开始符号。
  16. LR(0)项目集规范族，并构造识别一个文法活前缀的DFA项目集。
  17. 寻找LR(1)项目集，并构造对应的规范项目族是重难点，比较好的练习p70 例3.36
  18. 短语、直接短语、句柄
    短语：
    直接短语：
    句柄：语法树中最左直接短语
    比较好的一个练习p79 习题3

第四章 语义分析

  1. 编译中，语义处理的两个用处（1）审查每个语法成分的静态语义 （2）生成目标代码或中间代码
  2. 静态语义分析主要包括哪几个步骤（1）类型检查 （2）控制流检查 （3）一致性检查
  3. 语义是上下文有关的，因此语义的形式化描述十分困难，目前较为常见的是用语法制导定义或者语法制导翻译模式作为描述程序语言语义的工具，并采用语法制导翻译的方法完成对语法成分的翻译工作
  4. S属性定义：一个语法制导仅仅使用综合属性，则称这种语法制导定义为S-属性定义，或S属性文法
  5. L属性定义：对每个产生式 A→X1X2X3X4...Xn 的每条语义规则计算的属性要么是A的综合属性，要么 Xj,(1≤j<=n) ，而该属性仅依赖于 Xj 产生式左边的符号 X1,X2,X3,...,Xj−1 或A的继承属性

  6. 我一直纠结于怎么通过一个语义规则来判断语义是综合属性还是继承属性，根据课本p88 例4.7 认为大致应该是：

    产生式 语义规则 属性
    S→UVW W.h:=S.a h是继承
    U.c:=W.g c是继承
    S.b:= U.d-2 b是综合
    V.e:=S.b e是继承
    U→u U.d:=2*u.c d是综合
    V→v V.f:=2*v.e f是综合
    W→w W.g:=w.h+2 g是综合

  7. 抽象语法分析树和DAG p92

第六章 运行时的存储结构

  1. 程序运行时的存储区划分为：代码区、静态数据区、栈区和堆区
  2. 静态数据分配：由主程序和若干程序段组成，定义的名字一般独立、同一名字在不同的段之间不能相互引用、赋值，每个数据名所需的存储空间大小都是常量，整个程序所需的数据空间的总量在编译时完全确定
  3. 动态存储分配：主要分两种（1）栈式分配策略，将程序的数据空间存放在一个栈式的存储空间中，调用一个过程，它所需的空间就分配在栈顶，调用结束后就释放（2）

  4. 静态链的构建，这个是非常核心的一个部分，总结下来有三种情况：
    （1）N层调用N+1层：新的N+1层的动、静态链值相同，都是N层的SP
    （2）N层调用N-1层：新的N-1层的动态链是是N层的SP，但静态链是N-1层的直接外围过程
    （3）N层调用N层： 新的N层的动态链是旧的N层的SP，静态链与旧的N层相同
    编译原理最终复习

    1. display表的构建，这个也是很核心的，总结下来有三点：
      （1）到第N层程序的时候，需要在display写出0,1,2…N层的SP位置
      （2）每次需要在返回地址上面写出上一SP的display表位置
      编译原理最终复习

    2. 1

    3. 1

第七章 优化

  1. 优化所遵循的几个基本原则：等价原则、有效原则、经济原则
  2. 根据涉及范围，在代码上进行的优化可以分为局部优化、循环优化和全局优化
  3. 对于给定的程序，判定入口语句的三条判据：（1）程序的第一条语句（2）能由转移语句转移到的语句（3）紧跟在条件转移语句后面的语句
  4. 几种优化的技巧
    （1）删除公共子表达式 ：某个表达式已经计算过，并且值没有改变，后面有的时候，就没必要计算了
    （2）复写传播：如果新的赋值没有改变，就用原来的，比如 t6:=t2  x:=a[t6] 可以改写为 t6:=t2  x:=a[t2] 这个方法单独用不会加速，但可与后面的方法结合
    （3）删除无用代码：这个顾名思义吧
    （4）合并已知量和常数传播：把能在编译时计算出值的表达式用其相应的值来代替，并且尽可能用常数代替变量
    （5）临时变量换名、交换语句次序：这些在DAG中自然会使用
    （6）基于基本块的DAG优化，这个是核心
  5. 必经节点、必经节点集
  6. 关于循环的优化技巧
    （1）代码外提
    （2）循环展开(要对比展开是否能减少代码量)
    （3）强度削弱
    （4）删除归纳变量

练习题

  1. LR分析法：自左向右，自底向上
  2. 一个句型的句柄一定是文法某产生式的右部 (√)
  3. 在中间代码优化中循环上的优化有循环展开、不变表达式外提和削减运算强度。
  4. 对于数据空间的存贮分配，FORTRAN采用静态贮存分配策略
  5. 在 SLR(1)分析法的名称中，S的含义是简单的(√)
  6. 继承属性是 从上而下传递信息。 综合属性自下而上传递信息。 终结符号只有综合属性 非终结符号既有综合属性也可有继承属性
  7. 符号表至少包括名字栏、信息栏
  8. 对于允许嵌套的过程定义，一个过程可以直接引用包围它的任一外层过程所定义的变量所表示的标量或数组。
  9. 程序语言的语言处理程序是一种应用软件。(×)
    软件系统可分成系统软件和应用软件。前者又分为操作系统和程序语言处理系统。程序语言处理系统是系统软件而不是应用软件
  10. 软件系统可分成系统软件和应用软件。前者又分为操作系统和程序语言处理系统。程序语言处理系统是系统软件而不是应用软件。
  11. 一个 LL(l)文法一定是无二义的。 (√)
  12. 逆波兰法表示的表达式亦称后缀式 。 (√ )
  13. 如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 (√ ) 最左推导 和 最右推导 是不影响语法树结构的
  14. 编译程序是对高级语言程序的解释执行。(× ) 编译程序是,是把用高级语言编写的面向过程的源程序翻译成目标程序的语言处理程序
  15. 语法分析时必须先消除文法中的左递归 。 (×) 这个好理解，自右推导就可以了
  16. LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 (√)
  17. 如果r和s是正规式，那么有 L(r|s)=L(r)∪L(s) 和 L(r∗s)=L(r)L(s) 及 L(r∗)=(L(r))∗
  18. 确定的自动机以及不确定的自动机都能正确地识别正规集。(√)
  19. 规范归约和规范推导是互逆的两个过程。 (√)
  20. LR分析技术无法适用二义文法。 (× )
  21. 编译程序是一种翻译程序
  22. 在自底向上的语法分析方法中，分析的关键是寻找句柄
  23. 若文法 G 定义的语言是无限集，则文法必然是递归的
  24. 解释程序和编译程序是两类程序语言处理程序
  25. 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组产生式
  26. 与编译系统相比，解释系统比较简单 , 可移植性好 , 执行速度慢：编译程序、解释程序、汇编程序是3种语言处理程序。其区别主要为：
    汇编程序（为低级服务）是将汇编语言书写的源程序翻译成由机器指令和其他信息组成的目标程序。
    解释程序（为高级服务）直接执行源程序或源程序的内部形式，一般是读一句源程序，翻译一句，执行一句，不产生目标代码，如BASIC解释程序。
    编译程序（为高级服务）是将高级语言书写的源程序翻译成与之等价的低级语言的目标程序。
    编译程序与解释程序最大的区别之一在于前者生成目标代码，而后者不生成；此外，前者产生的目标代码的执行速度比解释程序的执行速度要快；后者人机交互好，适于初学者使用。用COBOL、FORTRAN等语言编写的程序考虑到执行速度一般都是编译执行。 解释:程序运行时，取一条指令，将其换化为机器指令， 再执行这条机器指令。 编译：程序运行时之前，将程序的把有代码编译为机器代码，再运行这个程序。
  27. 词法分析器的输出结果是单词的种别编码和自身值
  28. 四元式之间的联系是通过临时变量实现的
  29. 编译程序绝大多数时间花在表格管理上
  30. 采用自上而下分析，必须消除回溯
  31. 间接三元式表示法的优点为采用间接码表，便于优化处理
  32. 在目标代码生成阶段，符号表用地址分配
  33. 词法分析的主要功能是识别单词
  34. 若某程序允许标识付先使用后说明，则其编译程序就必须多遍扫描
标签：

相关文章