编译数据的结构

① 编译原理的数据结构

编译原理一直是计算机学习的必修课.
当然，由编译器的阶段使用的算法与支持这些阶段的数据结构之间的交互是非常强大的。编译器的编写者尽可能有效实施这些方法且不引起复杂性。理想的情况是：与程序大小成线性比例的时间内编译器，换言之就是，在0 （ n ）时间内，n是程序大小的度量（通常是字符数）。本节将讲述一些主要的数据结构，它们是其操作部分阶段所需要的，并用来在阶段中交流信息。 临时文件（temporary file）：计算机过去一直未能在编译器时将整个程序保留在存储器中。这一问题已经通过使用临时文件来保存翻译时中间步骤的结果或通过“匆忙地”编译（也就是只保留源程序早期部分的足够信息用以处理翻译）解决了。存储器的限制现在也只是一个小问题了，现在可以将整个编译单元放在存储器之中，特别是在可以分别编译的语言中时。但是偶尔还是会发现需要在某些运行步骤中生成中间文件。其中典型的是代码生成时需要反填（backpatch）地址。例如，当翻译如下的条件语句时 if x = 0 then ... else ... 在知道else部分代码的位置之前必须由文本跳到else部分：
CMP X,0 JNE NEXT ;;
location of NEXT not yet known < code for then-part > NEXT : < code for else-part >
通常，必须为NEXT的值留出一个空格，一旦知道该值后就会将该空格填上，利用临时文件可以很容易地做到这一点。
如果想利用上面的编译原理开发一套属于自己的编程语言，或者想在一个产品中嵌入编程语言，可以参考zengl开源网开发的zengl编程语言，该编程语言为国人使用C语言开发，里面包含两个部分，一个是编译器，一个是解释执行中间代码的虚拟机。编译器包含了词法扫描，语法分析，中间代码输出等，虚拟机则类似JAVA一样解释执行中间代码。作者将所有的版本都公布出来，好让读者可以由浅入深的做研究，并且为了证明该编程语言的实用性，还结合SDL游戏开发库开发了一款图形界面和命令行界面的21点扑克小游戏 。
zengl编程语言目前适用平台为windows和linux (最开始在Linux下使用gcc开发，后来移植到windows平台)

② C语言代码组成 - BSS、Data、Stack、Heap、Code、Const

一段C语言经过编译连接后，成为一段可以运行的代码，可运行的代码可以分为以下四个部分组成：全局变量/静态变量区、堆、栈、代码区。其中全局变量/静态变量区又分为未初始化变量区和初始化变量区，代码区又分为代码和常量区。即汇总下来，代码可以分为6部分组成，包括：BSS区（未初始化的全局变量/静态变量区）、Data区（实始化的全局变量区）、Stack区（栈区）、heap区（堆区）、Code区（代码区）、const区（常量区）。

一、BSS区和Data区

C语言编程中定义的全局变量、静态局部变量，就是分配在全局变量/静态变量区域，但是为什么又要分为BSS区域和Data区域呢？其实我们在定义全局或者静态变量区，有时我会对它赋初始值，有的又不会赋初始化，比如我们定义的全局变量，初始化的赋值，是怎么样写到变量区域中的，我们定义的静态局部变量，在定义时初始化后，为什么后面函数被调用，又不会再初始化呢？这个局部静态变量是怎么样实始化的，什么时候初始化的？

如果分析编译后的汇编代码，就会发现在代码运行起来后，会有一段给变量赋值的指令，这一段代码，不是我们C代码对应的汇编，而是C编译器生成的汇编译代码，这段代码的作用就是给初始化了的静态变量和全局变量进行初始化。这也是为什么全局/静态变量区域，要分BSS和Data的原因。

二、Stack区

栈是一种先进后出的数据结构，这种数据结构正好完美的匹配函数调用时的模型过程，比如函数f(a)在运行过程中调用函数f(b)，f(a）在运行过程中的变量就是分配在栈中，通过在调用f(b)前，会将代码中用到的R0~Rn寄存器的值保存到栈中，同时将函数的传入参数写入到栈中，然后进入f(b)函数，函数f(b)的变量b分配在栈中，当函数运行完毕后，释放变量b，将栈中存放的f（a）函数的运行的R0~Rn寄存器值恢复到寄存器中，同时f(b)的返回结果存入到栈中，这样f（a）继续运行。当一个函数运行完毕后，它在栈中分配的临时变量会全部释放。

对于中断也是一样的，中断发生时，也是一个函数打断了另一个函数的运行，这种现场的保存（即寄存器的值）,都是通过栈来完成的。所以栈的作用有：

三、Heap区

全局变量分配的内存在代码整个运行周期内都是有效的，而在栈区分配的内存在函数调用完成后，就会释放。这两种内存模型都是由编译器决定它的使用，代码是无法控制的。那有没有内存是由用户控制的，要用时，就自由分配，不用时，就自行释放？答案是肯定的，这部分内存就是堆。

用户需要使用的动态内存，就是通过malloc函数，调用分配的，在没有释放前，可一直由代码使用。当这部分内存不再需要使用时，可以通过free函数进行释放，将它归还到堆中。从这中可以看出，堆的内存，是按需分配的。这就是赋予了代码很大的自由度，但这也是会带来负作用的，比如：内存碎片化导致的malloc失败；忘记释放内存导致的内存泄露，而这些往往是致命的失误。

四、Code区

代码区就是编译后机器指令，这些指令决定了功能的执行。我们编译的代码一般是下载进flash中，但是运行，却有两种方式：在RAM中运行和在ROM中运行。 在RAM中运行，即是boot启动后，将flash中的代码复制到RAM中，然后PC指针在指到RAM中的代码中开始运行。 有时在调试时，我们可以直接将代码下载进RAM中运行进行调试，这样加快调试速度。便是大部分的情况我们的代码是从flash中开始运行的。

五、常量区

代码中的常量，一部分是作为立即数，在代码区中，但是像定义的字符串、给某数组赋值的一串数值，这些常量，就存在常量区，我们常用const来定义一个常量，即该变量不能再必变。这部分的变量，编译器一般将它定义的flash中。

六、各个区域大小的是如何决定的：

code区和const区：是由代码的大小和代码中常量的多少来决定的。

bss区和data区：这是由代码中定义的全局变量和局部变量的多少来决定的。

stack区：这个可以由使用都自行定义大小，但使用都要根据自已代码的情况，评估出一个合理的值，再定义其大小，如果定义的太小，很容易爆栈，导至代码异常，但是如果定义的太大，就容易浪费内存。

heap区：RAM剩下的部分，编译器就会作为堆区使用。

七、嵌入式代码一般启动过程

以STM32为例，通过分析其汇编启支代码，大致可以分为以下几个步骤：

如果大家想看编译扣，代码文件的组成，可以查看统后生的map文件，里面有详细的数据，包括各个函数的分配内存，BSS，Data，Stack，Heap，Text的分配情况。

如果相要了解详细的代码启动过程，可看它的启动汇编文件。

③ 编译程序包括哪几个主要组成部分

数据结构 分析和综合时所用的主要数据结构，包括符号表、常数表和中间语言程序。符号表由源程序中所用的标识符连同它们的属性组成，其中属性包括种类（如变量、数组、结构、函数、过程等）、类型（如整型、实型、字符串、复型、标号等），以及目标程序所需的其他信息。常数表由源程序中用的常数组成，其中包括常数的机内表示，以及分配给它们的目标程序地址。中间语言程序是将源程序翻译为目标程序前引入的一种中间形式的程序，其表示形式的选择取决于编译程序以后如何使用和加工它。常用的中间语言形式有波兰表示、三元组、四元组以及间接三元组等。

分析部分 源程序的分析是经过词法分析、语法分析和语义分析三个步骤实现的。词法分析由词法分析程序（又称为扫描程序）完成，其任务是识别单词（即标识符、常数、保留字，以及各种运算符、标点符号等）、造符号表和常数表，以及将源程序换码为编译程序易于分析和加工的内部形式。语法分析程序是编译程序的核心部分，其主要任务是根据语言的语法规则，检查源程序是否合乎语法。如不合乎语法，则输出语法出错信息；如合乎语法，则分解源程序的语法结构，构造中间语言形式的内部程序。语法分析的目的是掌握单词是怎样组成语句的，以及语句又是如何组成程序的。语义分析程序是进一步检查合法程序结构的语义正确性，其目的是保证标识符和常数的正确使用，把必要的信息收集和保存到符号表或中间语言程序中，并进行相应的语义处理。

综合部分 综合阶段必须根据符号表和中间语言程序产生出目标程序，其主要工作包括代码优化、存储分配和代码生成。代码优化是通过重排和改变程序中的某些操作，以产生更加有效的目标程序。存储分配的任务是为程序和数据分配运行时的存储单元。代码生成的主要任务是产生与中间语言程序符等价的目标程序，顺序加工中间语言程序，并利用符号表和常数表中的信息生成一系列的汇编语言或机器语言指令。

结构编译过程分为分析和综合两个部分，并进一步划分为词法分析、语法分析、 语义分析、 代码优化、存储分配和代码生成等六个相继的逻辑步骤。这六个步骤只表示编译程序各部分之间的逻辑联系，而不是时间关系。编译过程既可以按照这六个逻辑步骤顺序地执行，也可以按照平行互锁方式去执行。在确定编译程序的具体结构时，常常分若干遍实现。对于源程序或中间语言程序，从头到尾扫视一次并实现所规定的工作称作一遍。每一遍可以完成一个或相连几个逻辑步骤的工作。例如，可以把词法分析作为第一遍；语法分析和语义分析作为第二遍；代码优化和存储分配作为第三遍；代码生成作为第四遍。反之，为了适应较小的存储空间或提高目标程序质量，也可以把一个逻辑步骤的工作分为几遍去执行。例如，代码优化可划分为代码优化准备工作和实际代码优化两遍进行。

一个编译程序是否分遍,以及如何分遍,根据具体情况而定。其判别标准可以是存储容量的大小、源语言的繁简、解题范围的宽窄，以及设计、编制人员的多少等。分遍的好处是各遍功能独立单纯、相互联系简单、逻辑结构清晰、优化准备工作充分。缺点是各遍之中不可避免地要有些重复的部分，而且遍和遍之间要有交接工作，因之增加了编译程序的长度和编译时间。

一遍编译程序是一种极端情况，整个编译程序同时驻留在内存,彼此之间采用调用转接方式连接在一起(图2)。当语法分析程序需要新符号时，它就调用词法分析程序；当它识别出某一语法结构时，它就调用语义分析程序。语义分析程序对识别出的结构进行语义检查，并调用“存储分配”和“代码生成”程序生成相应的目标语言指令。

随着程序设计语言在形式化、结构化、直观化和智能化等方面的发展，作为实现相应语言功能的编译程序，也正向自动程序设计的目标发展，以便提供理想的程序设计工具。

参考书目

陈火旺、钱家骅、孙永强编：《编译原理》，国防工业出版社，北京，1980

④ 我想了解c语言中内存分配问题方面的知识

C语言程序编译的内存分配：
1.栈区（stack） --编译器自动分配释放，主要存放函数的参数值，局部变量值等；
2.堆区（heap） --由程序员分配释放；
3.全局区或静态区 --存放全局变量和静态变量；程序结束时由系统释放，分为全局初始化区和全局未初始化区；
4.字符常量区 --常量字符串放与此，程序结束时由系统释放；
5.程序代码区--存放函数体的二进制代码
例： //main.c
int a=0; //全局初始化区
char *p1; //全局未初始化区
void main()
{
int b; //栈
char s[]="bb"; //栈
char *p2; //栈
char *p3="123"; //其中，“123\0”常量区，p3在栈区
static int c=0; //全局区
p1=(char*)malloc(10); //10个字节区域在堆区
strcpy(p1,"123"); //"123\0"在常量区，编译器 可能 会优化为和p3的指向同一块区域
｝
一个C程序占用的内存可分为以下几类：
(一) 栈
这是由编译器自动分配和释放的区域。主要存储函数的参数，函数的局部变量等。当一个函数开始执行时，该函数所需的实参，局部变量就推入栈中，该函数执行完毕后，之前进入栈中的参数和变量等也都出栈被释放掉。它的运行方式类似于数据结构中的栈。
(二) 堆
这是由程序员控制分配和释放的区域，在C里，用malloc()函数分配的空间就存在于堆上。在堆上分配的空间不像栈一样在某个函数执行完毕就自动释放，而是一直存在于整个程序的运行期间。当然，如果你不手动释放(free()函数)这些空间，在程序运行结束后系统也会将之自动释放。对于小程序来说可能感觉不到影响的存在，但对于大程序，例如一个大型游戏，就会遇到内存不够用的问题了
(三) 全局区
C里的全局变量和静态变量存储在全局区。它们有点像堆上的空间，也是持续存在于程序的整个运行期间，但不同的是，他们是由编译器自己控制分配和释放的。
(四) 文字常量区
例如char *c = “123456”；则”123456”为文字常量，存放于文字常量区。也由编译器控制分配和释放。
(五) 程序代码区
存放函数体的二进制代码。
2． 例子(一)
int a = 0; //全局区
void main()
{
int b; //栈
char s[] = "abc"; //s在栈,"abc"在文字常量区
char *p1,*p2; //栈
char *p3 = "123456"; //"123456"在常量区，p3在栈上
static int c =0; //全局区
p1 = (char *)malloc(10); //p1在栈，分配的10字节在堆
p2 = (char *)malloc(20); //p2在栈，分配的20字节在堆
strcpy(p1, "123456"); //"123456"放在常量区
//编译器可能将它与p3所指向的"123456"优化成一个地方。
}
3． 例子(二)
//返回char型指针
char *f()
{
//s数组存放于栈上
char s[4] = {'1','2','3','0'};
return s; //返回s数组的地址，但程序运行完s数组就被释放了
}
void main()
{
char *s;
s = f();
printf ("%s", s); //打印出来乱码。因为s所指向地址已经没有数据
}
还有就是函数调用时会在栈上有一系列的保留现场及传递参数的操作。
栈的空间大小有限定，vc的缺省是2M。栈不够用的情况一般是程序中分配了大量数组和递归函数层次太深。有一点必须知道，当一个函数调用完返回后它会释放该函数中所有的栈空间。栈是由编译器自动管理的，不用你操心。
堆是动态分配内存的，并且你可以分配使用很大的内存。但是用不好会产生内存泄漏。并且频繁地malloc和free会产生内存碎片（有点类似磁盘碎片），因为C分配动态内存时是寻找匹配的内存的。而用栈则不会产生碎片，在栈上存取数据比通过指针在堆上存取数据快些。一般大家说的堆栈和栈是一样的，就是栈(stack)，而说堆时才是堆heap.栈是先入后出的，一般是由高地址向低地址生长。
堆(heap)和栈(stack)是C/C++编程不可避免会碰到的两个基本概念。首先，这两个概念都可以在讲数据结构的书中找到，他们都是基本的数据结构，虽然栈更为简单一些。在具体的C/C++编程框架中，这两个概念并不是并行的。对底层机器代码的研究可以揭示，栈是机器系统提供的数据结构，而堆则是C/C++函数库提供的。具体地说，现代计算机(串行执行机制)，都直接在代码底层支持栈的数据结构。这体现在，有专门的寄存器指向栈所在的地址，有专门的机器指令完成数据入栈出栈的操作。种机制的特点是效率高，支持的数据有限，一般是整数，指针，浮点数等系统直接支持的数据类型，并不直接支持其他的数据结构。因为栈的这种特点，对栈的使用在程序中是非常频繁的。对子程序的调用就是直接利用栈完成的。机器的call指令里隐含了把返回地址推入栈，然后跳转至子程序地址的操作，而子程序中的ret指令则隐含从堆栈中弹出返回地址并跳转之的操作。C/C++中的自动变量是直接利栈的例子，这也就是为什么当函数返回时，该函数的自动变量自动失效的原因。
和栈不同，堆的数据结构并不是由系统(无论是机器系统还是操作系统)支持的，而是由函数库提供的。基本的malloc/realloc/free函数维护了一套内部的堆数据结构。当程序使用这些函数去获得新的内存空间时，这套函数首先试图从内部堆中寻找可用的内存空间，如果没有可以使用的内存空间，则试图利用系统调用来动态增加程序数据段的内存大小，新分配得到的空间首先被组织进内部堆中去，然后再以适当的形式返回给调用者。当程序释放分配的内存空间时，这片内存空间被返回内部堆结构中，可能会被适当的处理(比如和其他空闲空间合并成更大的空闲空间)，以更适合下一次内存分配申请。这套复杂的分配机制实际上相当于一个内存分配的缓冲池(Cache)，使用这套机制有如下若干原因：
1. 系统调用可能不支持任意大小的内存分配。有些系统的系统调用只支持固定大小及其倍数的内存请求(按页分配)；这样的话对于大量的小内存分类来说会造成浪费。
2. 系统调用申请内存可能是代价昂贵的。系统调用可能涉及用户态和核心态的转换。
3. 没有管理的内存分配在大量复杂内存的分配释放操作下很容易造成内存碎片
堆和栈的对比
从以上知识可知，栈是系统提供的功能，特点是快速高效，缺点是有限制，数据不灵活；而堆是函数库提供的功能，特点是灵活方便，数据适应面广泛，但是效率有一定降低。栈是系统数据结构，对于进程/线程是唯一的；堆是函数库内部数据结构，不一定唯一。不同堆分配的内存无法互相操作。栈空间分静态分配和动态分配两种。静态分配是编译器完成的，比如自动变量(auto)的分配。动态分配由alloca函数完成。栈的动态分配无需释放(是自动的)，也就没有释放函数。为可移植的程序起见，栈的动态分配操作是不被鼓励的！堆空间的分配总是动态的，虽然程序结束时所有的数据空间都会被释放回系统，但是精确的申请内存/释放内存匹配是良好程序的基本要素。

⑤ 编译程序有哪些主要构成成分它们各自的主要功能是什么

编译过程分为分析和综合两个部分，并进一步划分为词法分析、语法分析、语义分析、代码优化、存储分配和代码生成等六个相继的逻辑步骤。这六个步骤只表示编译程序各部分之间的逻辑联系，而不是时间关系。

编译过程既可以按照这六个逻辑步骤顺序地执行，也可以按照平行互锁方式去执行。在确定编译程序的具体结构时，常常分若干遍实现。对于源程序或中间语言程序，从头到尾扫视一次并实现所规定的工作称作一遍。每一遍可以完成一个或相连几个逻辑步骤的工作。

例如，可以把词法分析作为第一遍；语法分析和语义分析作为第二遍；代码优化和存储分配作为第三遍；代码生成作为第四遍。

反之，为了适应较小的存储空间或提高目标程序质量，也可以把一个逻辑步骤的工作分为几遍去执行。例如，代码优化可划分为代码优化准备工作和实际代码优化两遍进行。

(5)编译数据的结构扩展阅读

从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。执行词法分析的程序称为词法分析程序或扫描器。

源程序中的单词符号经扫描器分析，一般产生二元式：单词种别；单词自身的值。单词种别通常用整数编码，如果一个种别只含一个单词符号，那么对这个单词符号，种别编码就完全代表它自身的值了。若一个种别含有许多个单词符号，那么，对于它的每个单词符号，除了给出种别编码以外，还应给出自身的值。

词法分析器一般来说有两种方法构造：手工构造和自动生成。手工构造可使用状态图进行工作，自动生成使用确定的有限自动机来实现。

编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程序是最终的一个语法单位。编译程序的语法规则可用上下文无关文法来刻画。

⑥ 定义语法树和符号表的数据结构

为了维持静态作用域的程序里各个名字的轨迹，编译器需要依靠一种称为符号表的数据结构。从最基本的层次上看，符号表就是一个字典：它把名字映射到编译器已知的有关信息。这里最基本的操作是把一个新映射关系（名字对象约束）放入表里，以及（非破坏性的）用一个给定名字去提取映射下的信息，以后我们把

这两个操作分别称为insert和lookup。大部分语言里的静态作用域规则还提出了另外的复杂性，它们要求在程序里的不同部分有不同的引用环境。为了处理作用域规则，我们可能希望简单增加一个remove操作。由于编译器在语义分析阶段要从头到尾扫描代码，这样它就可以在某个作用域开始时插入新约束，在作用域最后撤销它们。但是，存在一些因素使这种直接做法并不实际。

¨ 在许多有着嵌套作用域的语言里，内层声明的效果可以遮蔽外层声明，这就意味着符号表必须有能力为一个给定名字保存任意数目的映射。lookup操作必须返回最内层的映射，到作用域结束时还必须使外层映射重新变成可见的。

¨ 类Algol语言里的记录（结构）具有某种作用域性质，但却又不享有作用域那样的良好嵌套结构。当语义分析器看到一个记录声明时，它就必须记下各个记录域的名字（它们也是递归的，因为记录可以嵌套）。在这种声明结束时，各个域的名字又必须变成不可见的。然而，在此之后，一旦这一记录类型的某个变量出现在程序的正文里（例如在my_rec.field_name），在引用中位于圆点之后的部分，这些域名又必须立即重新变成可见的。在Pascal和另一些有with语句的语言里，记录域的名字还应该在多个语句的上下文里变成可见的。

¨ 某些时候一些名字有可能在它们被声明之前使用，即使在类Algol语言里情况也如此。举例说，Algol 60和Algol 68都允许标号的向前引用。Pascal避免了这种情况，它要求标号必须在作用域开始处声明，但还是允许指针声明的向前引用：

type