编译原理

标签（空格分隔）： 编译原理

编译和解释

编译

整个程序全部翻译结束之后，程序才能开始运行；编译和运行是两个独立分开的阶段。

解释

不需要将分析和执行阶段分开，一边分析一边执行；更加适用于交互环境中

image.png

Java和早期语言的区别

image.png

Java处理环境既有编译程序，也有解释程序

0-3型文法

通过对产生式施加不同的限制，将文法分为四种类型

0型文法

image.png

1型文法（上下文有关文法）

image.png

另一种定义

image.png

2型文法（上下文无关文法）

image.png

3型文法（正规文法）

image.png

二义性文法

若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的

image.png

语言的二义性

这两个文法所产生的语言是相同的。跟文法的二义性不一样

语言先天二义性

如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。

有害规则，多余规则

有害规则

形如U→U的产生式。会引起文法的二义性

多余规则

指文法中任何句子的推导都不会用到的规则

• 文法中某些非终结符（除了开始符）不在任何规则的右部出现，该非终结符称为不可到达
• 文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止

规范推导，规范归约

推导

image.png

归约

最左归约为规范归约

算符优先文法归约

？？？

LL（1）文法

image.png

φ 为空集

LL（1）文法的判别

计算同一个非终结符Select集看看有没有交集，有就不是，没有就是

非LL（1）文法到LL（1）的等价变换

以下两种方法变换形式不止一种，且变换后不一定就为LL（1），多尝试几个变换形式

提取公因子

image.png

image.png

消除左递归

image.png

image.png

内存分配

存储区布局

image.png

代码数据分开存储，为什么？？？

数据区类型

• 静态存储分配
  静态数据区，编译时安排好数据存储空间，存储空间的分配在整个程序运行过程中有
  效（固定分配）
• 动态存储分配，编译时无法完全确定存储空间大小
  • 栈区，存储局部变量和过程参数
  • 堆区，自由申请和释放存储空间，典型语句：C语言 malloc、面向对象语言 new

典型程序

void func() {
    char *a;----------局部变量，栈
    a=(char *) malloc(100); ------在堆中分配100个字节
    ……
    free(a); ------在堆中释放100个字节
}

离开func()之后，释放栈的空间

过程调用参数传递方式

• 传值
• 传地址：数据地址
• 传过程（函数）参数：程序地址

栈式分配存储的实现

活动记录

一个过程的一次执行所需要的信息使用一个连续的存储区来管理，这个区（块）叫做一个活动记录

image.png

临时工作单元：计算时存放中间结果的临时空间
局部数据区：局部变量，空间大小固定。
控制信息：过程调用的链接以及返回地址等

image.png

四元式翻译

四元式（三地址码）

四元式形式 (op , arg1, arg2, result) 或 result:=arg1 op arg2

a:=t    ( := , t, --, a)
goto L    ( jump , --, --, L)

翻译

image.png

有常数的，要为常数创建一个临时变量

image.png

符号表

存放程序语言中出现的有关标识符的属性信息

F()
{         //第1层
   int a, b;
   {          //第2层
      float a, c;
      {         //第3层
         int b, d;
      }
   }
   {          //第2层
       int b, d;
   }
}

image.png

image.png

基本块优化

基本块

基本块：指程序中一个顺序执行的语句序列，只有一个入口语句和一个出口语句

DAG

有向无环图
一个基本块可以表达为一个DAG

例题

image.png

image.png

编译器后端

指令选择

CPU的指令集合具有冗余性，同一计算可用两个或多个不同的指令序列完成

寄存器分配

寄存器速度远远超过内存
尽量让变量的值或计算结果保留在寄存器中直到寄存器不够分配为止。
寄存器是紧缺资源
不再被引用的变量所占用的寄存器应尽早释放。提高寄存器的利用率。

指令调度

目标代码的指令顺序和中间代码的顺序未必一致，
指令执行顺序的调整称为指令调度
对具有流水线限制的体系结构，指令调度是必须的

分析题

正规式->NFA->DFA

正规式

正则表达式，表示正规集的工具

DFA

确定的有穷自动机

image.png

终态可以不为一，Z是终态集
初态唯一

NFA

不确定有穷自动机，初态不唯一，输入一个值，可能会有到多个状态

正规式->NFA

image.png

image.png

image.png

NFA->DFA

找出初态S，和其他空输入到达的状态
计算对于每个输入闭包，如果闭包集合出现新的，作为输入计算闭包
迭代直到没有新的闭包集合
换名，有原本的终态Z的闭包为终态

LL（1）

LL（1）文法

image.png

φ 为空集
就是说，同一个非终结符的产生式，它们的Select集不相交

LL（1）文法的判别

计算同一个非终结符Select集看看有没有交集，有就不是，没有就是

预测分析法

• 判断文法是否为LL（1）文法
  求SELECT集，看看有没有相交

• 构造预测分析表
  根据SELECT集填表，横坐标为输入，纵坐标为状态

  
  
  image.png

• 分析句子，写出分析过程
  

  image.png
  
  栈内容是反着写的，最右推导（规范推导）

算符优先分析法

算符文法

image.png

就是说没有两个非终结符连在一起

算符优先分析

只考虑算符（终结符）的优先关系

算法优先关系

image.png

画一棵树，高层的优先级低，低层优先高，方向由左到右

算符关系是不对称的

• X>Y 不一定有 Y<X
• X=Y 不一定有 Y=X
• 允许b>c、c>b同时存在，但是不允许b>c、b<c同时存在

算法优先文法

image.png

FIRSTVT(B)、LASTVT(B)

B产生式中的第一个非终结符、最后一个非终结符

过程

• 计算FIRSTVT(B)、LASTVT(B)
• 画算符优先关系表
  必须从左到右读
  有些算符是没关系，不能强加等于关系
  就算同一个算符，关系也不一定是相等
• 分析一个句子
  列表：栈内容、优先关系、当前输入、剩余串、动作（移进、归约、接受）
  当优先关系由<变成>的时候归约，归约成X，留在栈内容里，然后优先关系忽略X，比较它的上一个字符。
  当优先关系编程=接受该输入

LR（1）

过程

• 画出自动机
• 画分析表
• 分析句子（语义动作）
  Step 状态栈 符号栈 余留符号串 action goto
• 分析句子语义
  步骤、动作、状态栈、语义栈(值栈)、符号栈、余留输入串