编译原理

 

进程在内存中的大概分布情况
进程都需要占用一定内存，被占用的内存有些是事先静态分配和统一回收的，有些是按需动态分配和及时回收的。一般分为5种不同的内存数据段：

1.  代码段：用来存放可执行文件完整的操作指令（机器码）和只读数据，为了防止代码段被非法修改，代码段的特点是只读不写的。如果一个程序有多个运行实体，则这些实体共享同一个代码段。
2.  数据段：用来存放可执行文件中已经初始化了的全局变量，也就是在程序中静态分配的变量和全局变量。数据段在编译时分配。注意：数据段中的变量既占程序运行时的内存空间，也占程序文件的储存空间。    
3.  BSS段：用来存放可执行文件中未初始化的全局变量，在内存中全部置零。注意：BSS段中的变量只占用程序运行时的内存空间，而不占用程序文件的储存空间。
4.  堆（heap）：用来存放进程中被动态分配的内存段，大小不固定，动态扩张。当进程使用new或malloc申请变量内存时候，这些变量就会被分配到堆上，当使用delete或free释放内存时，堆上相应的内存会被释放。如果没有主动释放，操作系统会在程序结束后自动回收。
5.  栈（stack）： 用来存放程序临时创建的局部变量，也就是在函数体中定义的变量。此外还包括在函数调用时，函数的参数以及函数的返回值，这些内存是由系统自动分配和释放的。栈的特点是先进后出，向栈中添加数据（压栈），会将数据放置在栈顶，从栈中取出数据，会从栈顶部移出一个数据（弹栈）。所以栈在保存和恢复调用现场方面特别方便。    

 

堆和栈的区别
分配管理方式上：堆是动态分配，空间的分配和释放由程序员控制;栈由编译器自动管理。
产生碎片上：对堆来说，频繁的new/delete或者malloc/free势必会造成内存空间的不连续，造成大量的碎片，使程序效率降低。对栈而言，则不存在碎片问题，因为栈是先进后出的队列，永远不可能有一个内存块从栈中间弹出。
生长方向不同：堆是向着内存地址增加的方向增长的，从内存的低地址向高地址方向增长。栈的生长方向与之相反，是向着内存地址减小的方向增长，由内存的高地址向低地址方向增长。

 

进程间通信方式（IPC,Inter-Process Communication）
不同进程间的用户空间是相互独立的，一般不能相互访问。进程间通信是指在不同进程之间传播或交换信息，比较常见的进程间通信的场景是父子进程间的通信，共享数据，通知事件等。
1. 管道
也称为无名管道或匿名管道，使用pipe()创建。
管道上的数据只能在一个方向上流动，具有固定的读端和写端。
只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）。
管道可以看作是一种特殊的文件，但不属于任何文件系统，只存在于内存中。
2. FIFO
也称为命名管道，是一种文件类型。使用mkfifo创建。
可以在无关的进程之间交换数据，与无名管道不同。
FIFO有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。
3. 消息队列
消息队列是消息的链表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标识。
消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除。
消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。
消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。
4. 信号量
信号量是一个计数器，用于实现进程间的互斥与同步，而不是用于存储进程间通信数据，若要在进程间传递数据需要结合共享内存。
信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作（不可被中断的一个或一系列操作）。
一个进程对信号量成功执行来P操作，就得到了信号量，可以进入临界区，另外一个进程试图执行P操作时，会被挂起，直到拥有信号量的进程离开并执行V操作释放信号量。
5. 共享内存
共享内存（Shared Memory），指两个或多个进程共享一个给定的存储区。不同进程之间共享的内存通常安排为同一段物理内存。进程可以将同一段共享内存映射到它们自己的地址空间中，所有进程都可以访问共享内存中的地址。
共享内存是最快的一种进程间通信方式，因为进程是直接对内存进行存取。
因为多个进程可以同时操作，所以需要额外的同步控制，如互斥锁或信号量。
信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。

 

进程5种通信（IPC）方式比较
管道：速度慢，容量有限，只有父子或兄弟进程能通讯
FIFO：任何进程间都能通讯，但速度慢
消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题
信号量：不能传递复杂消息，只能用来同步控制，相当于是一个信号灯
共享内存：能够很容易控制容量，速度快，但要保持同步，一般需借助于信号量或互斥锁，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全。

 

信号量与互斥锁区别
信号量用在多进程（或线程）多任务同步上的，拥有信号量的一个进程在执行动作的时候，别的进程必须等待。
互斥锁是用在多线程（多进程中不存在互斥锁）多任务互斥上的，拥有互斥锁的一个线程在访问某一资源时候，别的线程就无法访问。
信号量重点在执行顺序的流程控制上，而不一定是锁住某一个资源，而互斥锁重点在于霸占某一资源上，自己在使用，别人就不能使用。

 

Ctrl+C、Ctrl+Z、Ctrl+D
ctrl-c 发送信号给前台进程组中的所有进程，终止正在运行的程序。
ctrl-z 发送信号给前台进程组中的所有进程，把当前程序挂起，暂停执行。想继续执行的时候输入fg回车即可复活当前进程。
Ctrl+D ：发送一个 exit 的信号，退出当前的用户或者是客户端。

 

同一进程中的线程间哪些资源共享，哪些独有
共享的资源：
a. 堆  由于堆是在进程空间中开辟出来的，所以它是理所当然地被共享的；因此new出来的都是共享的
b. 全局变量 它是与具体某一函数无关的，所以也与特定线程无关；因此也是共享的
c. 静态变量 虽然对于局部变量来说，它在代码中是“放”在某一函数中的，但是其存放位置和全局变量一样，存于堆中开辟的.bss和.data段，是共享的
d. 文件等公用资源  这个是共享的，使用这些公共资源的线程必须同步。

独有的资源：
a. 线程ID 每个线程都有自己唯一的线程ID。
b. 寄存器组的值 由于线程间是并发运行的，每个线程有自己不同的运行线索，当从一个线程切换到另一个线程上时，必须将原有的线程的寄存器集合的状态保存，以便将来该线程在被重新切换到时能得以恢复。
c. 线程的栈 栈是保证线程独立运行所必须的。线程函数可以调用函数，而被调用函数中又是可以层层嵌套的，所以线程必须拥有自己的函数栈，使得函数调用可以正常执行，不受其他线程的影响。
d. 错误返回码 由于同一个进程中有很多个线程在同时运行，可能某个线程进行系统调用 后设置了errno值，而在该线程还没有处理这个错误，另外一个线程就在此时被调度器投入运行，这样错误值就有可能被修改。    所以，不同的线程应该拥有自己的错误返回码变量。
e. 线程的优先级 由于线程需要像进程那样能够被调度，那么就必须要有可供调度使用的参数，这个参数就是线程的优先级。

 

线程4种同步机制
临界区：临界区是一段独占对某些共享资源访问的代码，在任意时刻只允许一个线程对共享资源进行访问。通过对多线程的串行化来访问公共资源或一段代码。
互斥量：功能上跟临界区类似，采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。不过可用于不同进程间的线程同步。
事件: 通过通知操作的方式来保持线程的同步，还可以方便实现对多个线程的优先级比较的操作
信号量：信号量用于限制对临界资源的访问数量，允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目,保证了消费数量不会大于生产数量。
临界区（Critical Section）、互斥对象（Mutex）：主要用于互斥控制；都具有拥有权的控制方法，只有拥有该对象的线程才能执行任务，所以拥有，执行完任务后一定要释放该对象。
信号量（Semaphore）、事件对象（Event）：事件对象是以通知的方式进行控制，主要用于同步控制！

 

同步和互斥
同步：异步环境下的一组并发进程因制约关系而互相发送消息而进行互相合作、互相等待，使得各进程按一定的顺序执行的过程称为进程间的同步。
互斥：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行。也就是说，不允许两个以上的共享该资源的并发进程同时进入临界区。
互斥具有唯一性和排它性，但互斥并不限制任务的运行顺序，即任务是无序的。而同步的任务之间则有逻辑顺序关系。

 

C语言的编译过程
1. 预处理：读取C源程序，对其中的伪指令进行处理。预处理主要是要处理“#”，将#include包含的头文件插入到hell.c当中；将#define定义的宏进行替换，同时将代码中没用的注释部分删除，还要添加行号和文件标识，以便错误显示和调试。 生成 .i 文件。
2. 编译：将预处理完的文件进行一系列词法分析、语法分析、语义分析及优化后，产生相应的汇编代码文件。生成 .s 文件。
3. 汇编： 将编译完的汇编代码文件按照“汇编指令和机器指令的对照表”翻译成机器指令（机器指令是CPU能直接识别并执行的指令，它的表现形式是二进制编码。机器指令通常由操作码和操作数两部分组成，操作码指出该指令所要完成的操作，即指令的功能，操作数指出参与运算的对象，以及运算结果所存放的位置等）。生成 .o 文件。
4. 链接：通过链接器将一个个目标文件（或许还会有库文件）链接在一起生成一个完整的可执行程序。 生成 .exe 文件。
功能上的5个阶段是:词法分析、语法分析、语义分析和中间代码的产生、代码优化、目标代码生成

 

语法树
语法树是句子结构的图形表示，它代表了句子的推导过程，有利于理解句子语法结构的层次。
简单说，语法树就是按照某一规则（文法）进行推导时所形成的树（图形表示）。一棵语法树包括了一个句型的所有可能的推导过程。

 

文法
文法是描述语言的语法结构的形式规则（即语法规则），是定义由符号到一个有含义的句子的规则和协议。上下文无关文法就是文法的一种，指当前语法单位是上下文无关的，不用去关心在它上边或下边的语法单位。编译原理中的文法指的就是上下文无关文法。
对于一个文法，如果它的某些句子对应两棵不同的语法树，这个文法就属于“二义性文法”，应尽量避免，如在句子中设置优先级、添加隔离等，但是不存在判断句子是否具有二义性的方法。

 

词法分析
词法分析是编译的第一阶段。词法分析器的主要任务是读入源程序的输入字符，将它们组成词素，生成并输出一个词法单元序列，这个词法单元序列被输出到语法分析器进行语法分析。
另外，由于词法分析器在编译器中负责读取源程序，因此除了识别词素之外，它还会完成一些其他任务，比如过滤掉源程序中的注释和空白，添加行号和文件标识，以便错误显示和调试。总而言之，词法分析器的作用如下：
1. 读入源程序的输入字符，将它们组成词素，生成并输出一个词法单元序列；
2. 过滤掉源程序中的注释和空白；
3. 将编译器生成的错误消息与源程序的位置关联起来（添加行号和文件标识）。

 

语法分析
语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述。完成语法分析任务的程序称为语法分析器。
语法分析器会构造一棵语法分析树，并把它传递给编译器的其他部分进一步处理，在构建语法分析树的过程中，就验证了这个词素序列是否符合源语言的文法。
语法分析方法分为自上而下语法分析方法和自下而上语法分析方法。

 

语义分析
语义分析是编译过程的一个逻辑阶段. 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查, 进行类型审查。语义分析是审查源程序有无语义错误，为代码生成阶段收集类型信息。比如语义分析的一个工作是进行类型审查，审查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程序应报告错误。
编译程序最实质性的工作；第一次对源程序的语义作出解释，引起源程序质的变化。

 

代码优化
编译原理出于代码编译的模块化组装和提高目标代码运行效率、时间效率（减少运行时间）、空间效率（减少内存容量）的考虑，一般会在语义分析的阶段生成平台无关的中间代码，经过中间代码级的代码优化，而后作为输入进入代码生成阶段，产生最终运行机器平台上的目标代码，再经过一次目标代码级别的代码优化（一般和具体机器的硬件结构高度耦合，复杂且不通用）。编译原理中的代码优化主要针对的是中间代码级的代码优化。
常见的代码优化手段:
删除多余运算、循环中不变的代码提到循环外边、运算强度削弱（本质是把强度大的运算换算成强度小的运算，例如将乘法换成加法运算）、变换循环控制条件、合并已知量、删除无用赋值等。