c－－minusminus语言编译器的设计文档.txt

unix环境下实现的cmm语言编译器

C－－Minus Minus设计的目点：
 学习编译原理时就设想实现一个简单的编译器。这样能将编译原理上的知识进行实际的
运用加以更好的理解,同时为了更接近实际的编译器，最好能够产生实际的汇编代码。
在看了描述lcc的＜＜可变目标C编译器－设计与实现＞＞后，决定在lcc的基础上，去掉一些比较琐碎的细节，同时保留一些基本成分来设计一个C语言子集的编译器，这个C语言的子集给它取名C－－。
通过C－－编译器的设计主要有以下的目的：
 首先，C－－编译器是做为编译原理的一个实习作业而设计的。通过设计C－－编译器可
以使编译原理上的理论得到实际的运用，从而加深对理论理解和运用能力。
 第二，设计C－－编译器过程，本身就是对C语言语法和特性的的学习。同时C－－编译器本
身就是一个大型C语言项目，通过它可以提高从事大型C程序的设计和开发能力。
 C－－ 编译器最后生成的目标代码为nasm的汇编语言程序。现在还只能运行在linux环境，由于nasm本身是跨平台的，并且主体框架直接来源于lcc，所以将它移值于其它的系统，
特别是windows时所要做的工作不会很大。为了简化实现的难度对于代码优化，只采用了
常量合并、公共子表达式消除、等简单的优化技术。
C－－的语法：
  C－－的语法是根据＜＜可变目标C编译器－设计与实现＞＞英文名<<A Retargetable CCompliler Design and Implementation>>)一书中C语言语法经过裁剪得到的，它是C语言的一个字集。为了与＜＜编译原理及实践＞＞中附录定义的一个C－Minus相区别，所以取名C－－MinusMinus(不过并没有因为多了一个Minus符号，就意外着C－－比C－简单。相反C－－具有比C－更多的特性）。为了能使用最基本标准的C库函数，C－－类型包括了char,以及
指针类型。但由于不支持可变参数，因此对像printf函数的使用需要在不同的使用处进行不同的声明。
C－－的关键字：
	break char continue else if int return void while
	所有的关键字都是保留字，并且必须是小写。
C－－中的专用符号：
	+ - * / % < <= > >= == != = ! & 
C－－Minus Minus 的EBNF语法：
	1. translation-unit:
			external-declaration {external-declaration}
	2. external-declaration:
			function-definition
			declaration
	3. declaration:
			type-specifier init-declarator {,init-declarator};
			type-specifier;
	4. init-declarator:
			declarator
			declarator = initializer
	5. initializer:
			assignment-expression
			'{' initializer {, initializer}[,]'}'
	6.	type-specifier:
			void | char | int 
	7. declarator:
			pointer direct-declarator {suffix-declarator}
	8. direct-declarator:
			identifier
			'(' declarator ')'
	9. suffix-declarator:
			'[' [constant-expression] ']'
			'('	[parameter-list]')'
	10. pointer: {*}
	11. parameter-list:
			parameter {,parameter-list}
	12. parameter:
			type-specifier [declarator]
	13. function-definition:
			type-specifier declarator compound-statement
	14. compound-statement:
			'{' {declaration} {statement} '}'
	15. statement:
			[expression];
			if '(' expression ')' statement
			if '(' expression ')' statement else statement 
			while '(' expression ')' statement 
			break;
			continue;
			return [expression ];
			compound-statement
	16. expression:
			assignment-expression
			binary-expression 
	17. assignment-expression
			unary-expression assign-operator assignment-expression
	18. assign-operator:
			one of = 
	19. binary-expression:
			 unary-expression { binary-operator  unary-expression } 
	20. binary-operator:
			one of   == != < > <= >=  + - * / %
	21. unary-expression:
			postfix-expression
			unary-operator unary-expression
			'(' type-name ')' unary-expression
			sizeof unary-expression
			sizeof '(' type-name ')'
	22. unary-operator:
			one of & * + -  !
	23. postfix-expression:
			primary-expression {postfix-operator}
	24. postfix-operator:
			'['expression']' 
			'('	[assignment-expression {,assignment-expression}]')'
	25. primary-expression:
			identifer
			constant
			string-literal
			'(' expression ')'
	26. identifer:
		nondigit { nodigit | digit }
	27. nondigit:
		one of _
		a b c d e f g h i j k l m
		n o p q r s t u v w x y z
		A B C D E F G H I J K L M
		N O P Q R S T U V W X Y Z
	28. constant:
			integer-constant
			character-constant
	29. integer-constant:
			decimal-constant
	30. decimal-constant:
			digit {digit}
	31. digit:
			one of 0 1 2 3 4 5 6 7 8 9
	32. character-constant:
			'char'  | escape-sequence
	33. char:
		any character
	34. escape-sequence:
		one of \' \" \? \\ \a \b \f \n \r \t \v
	35. string-literal:
		"{char | escape-sequence}" 
	
对以上每条文法规则，给出了相关语义的简短解释
 	1. translation-unit:
            external-declaration {external-declaration}
    2. external-declaration:
            function-definition
            declaration
    3. declaration:
            type-specifier init-declarator {,init-declarator};
            type-specifier;	
程序由声明的列表或函数定义组成。声明可以是函数或变量声明，顺序是任意的。
声明由类型说明符(type-specifier)和初始化声明符列表(init-declarator)构成。
为了简化C-- 编译器的实现，己将C语言声明说明符中类型限定符和存储说明符去掉。
由于没有extern说明符，对于全局的标示符，是不能跨文件传递的。但是为了实现引用
标准C库中一些函数实现基本输入输出，对未定义的函数，将把它做为引用外部符号处理。
	4. init-declarator:
            declarator
            declarator = initializer
    5. initializer:
            assignment-expression
            '{' initializer {, initializer}[,]'}'
    6.  type-specifier:
            void | char | int
在声明中对一般变量的初始化使用在'='后跟一个赋值表达式，由于在C－－ 中没有结构和联合类型，只对数组的赋值才用花括号括起来的赋值列表。同样出于简化的目的类型说明符只保留C语言中最基本类型，其中空类型void只用于函数返回类型和函数参数类型，分别表
示函数没有返回值和没有参数。char,int 的使用与C语言中相似，用于说明变量类型。
    7. declarator:
            pointer direct-declarator {suffix-declarator}
    8. direct-declarator:
            identifier
            '(' declarator ')'
    9. suffix-declarator:
            '[' [constant-expression] ']'
            '(' [parameter-list]')'
    10. pointer: {*}
声明说明符(declarator)由前缀的指针说明符'*'、直接说明符、和可选的后缀说明符构成。C－－ 保留了C语言中的指针，包括指向字符、整数、空类型、以及函数的指针。后缀说明符用于声明数组和函数，其中数组下标也是从0开始。
	11. parameter-list:
            parameter {,parameter-list}
    12. parameter:
            type-specifier [declarator]
    13. function-definition:
            type-specifier declarator compound-statement
    14. compound-statement:
            '{' {declaration} {statement} '}'
函数的参数声明中可选的声明说明符(declarator)表示在用于函数声明时可以省略，函数的定义由返回类型指示符、标识符以及在圆括号内有用逗号分开的参数列表组成，后面跟了一个复合语句，是函数的代码。复合语句由声明与语句序列组成。
	15. statement:
            [expression];
            if '(' expression ')' statement
            if '(' expression ')' statement else statement
            while '(' expression ')' statement
            break;
            continue;
            return [expression ];
	 		compound-statement
C－－ 中语句由表达式、选择、循环、返回、复合语句以及用于跳出循环的break 和跳过当前循环继续下一次循环的continue组成。每一条语句都由分号结束，可以包括空语句。  if语句有通常的语义：表达式进行计算；非 0值引起第一条语句的执行； 0值引起第二条语句的执行，如果它存在的话。这个规则导致了典型的悬挂 else二义性，可以用一种标准的方法解决：else部分通常作为当前if的一个子结构立即分析(“最近嵌套”非二义性规则)。  while语句是 C－－中唯一的重复语句。它重复执行表达式，并且如果表达式的求值为非 0，则执行语句，当表达式的值为 0时结束。  返回语句可以返回一个值也可无值返回。函数没有说明为 void就必须返回一个值。函数声明为void就没有返回值。return引起控制返回调用者(如果它在main中，则程序结束)。

	16. expression:
            assignment-expression
            binary-expression
    17. assignment-expression
            unary-expression assign-operator assignment-expression
    18. assign-operator:
            one of = 
    19. binary-expression:
             unary-expression { binary-operator  unary-expression }
	20. binary-operator:
			one of   == != < > <= >=  + - * / %
C－－的表达式由赋值表达式和二元表达式构成，赋值有通常的存储语义：它的左边必须为左值(l-value),左值是可以由许多操作获得的地址。	找到变量的地址，然后由赋值符右边的子表达式进行求值，子表达式的值存储到给定的地址。这个值也作为整个表达式的值返回。赋值表达式是右结合的，C－－的二元表达式是左结合的，它不能做为左值出现。
	21. unary-expression:
			postfix-expression
			unary-operator unary-expression
			'(' type-name ')' unary-expression
			sizeof unary-expression
			sizeof '(' type-name ')'
	22. unary-operator:
			one of & * + -  !
C－－的一元表达式由后缀表达式、前缀操作符、类型转换符、以及sizeof操作符组成。&为取变量地址操作，*为间接引用操作，取地址中的值。为按位取反，！用于对逻辑表达式取反。sizeof 对类型或左值求类型大小，对类型时必须加上圆括号，当对数组进行sizeof运算得到是数组元素的个数。
	23. postfix-expression:
            primary-expression {postfix-operator}
    24. postfix-operator:
            '['expression']'
            '(' [assignment-expression {,assignment-expression}]')'
    25. primary-expression:
            identifer
            constant
            string-literal
            '(' expression ')'
C－－的基本表达式由标示符、常量表达式、字符串常量、以及有圆括号的表达式组成。
	26. identifer:
		nondigit { nodigit | digit }
	27. nondigit:
		one of _
		a b c d e f g h i j k l m
		n o p q r s t u v w x y z
		A B C D E F G H I J K L M
		N O P Q R S T U V W X Y Z
标示符由下划线或字母开头、后面可接数字或字母。
	28. constant:
			integer-constant
			character-constant
	29. integer-constant:
			decimal-constant
	30. decimal-constant:
			digit {digit}
	31. digit:
			one of 0 1 2 3 4 5 6 7 8 9
	32. character-constant:
			'char'  | 'escape-sequence'
	33. char:
		any character
	34. escape-sequence:
		one of \' \" \? \\ \a \b \f \n \r \t \v
常量表达式由整形常量和字符常量构成。整形常量只含十进制常数，字符常量由二个单引号括起来的一般字符和由单引号括起来的转义字符构成。C－－中的转义字符不包括C语言里的
转义数字序列。
	35. string-literal:
		"{char | escape-sequence}" 
字符串常量由双引号括起来的字符和转义序列构成。


详细设计：
C－－的编译器主要可以由前端和后端组成，前端负责词法分析、语法分析、以及语义分析。其中语义部分包括类型检查，抽象语法树建立，并进行常量合并，和削除公共子表达式。最后生成供后端使用的DAG(非循环有向图)结构。后端由DAG合理分配寄存器，并生成代码。
一、前端的设计
 前端的最终的目标是生成削除了公共子表达式的DAG(directed acycline graph)。
 前端主要由词法分析，语法分析，语义分析构成。前端主要的数据结构包括符号表、
 抽象语法树，DAG，以及将程序分成基本块的代码链表构成。
C－－编译器的前端部分主要是在lcc的前端的基础上进行小量的修改得到的，对它的分析
可以在看其源代码注释时，参照＜＜可变目标C编译器－设计与实现＞＞一书中对lcc的分析这里只对它进行简略的说明。这里按照从下而上的顺序，介绍各模块的实现。
 1、C－－的内存管理的设计
  C－－编译器采用与LCC相同的基于生命期的内存管理算法。它使用的是基于实存块(arena)的算法，该算法从某个实存块中分配内存单元，释放时一次释放整个实存块。这就避免了调用malloc时，每次都要记得去调用free释放空间，这样就减轻了内存管理的负担和内存错误的机会。C－－的内存管理模块在文件alloc.c中
  C－－编译器内存管理的接口：
	void *allocate(unsigned long n, unsigned a);
	void deallocate(unsigned a);
	void dispose(void);
	void *newarray(unsigned  m, unsigned n,  unsigned a);
  allocate函数在分配区a中分配n个字节的空间，并返回指向它的指针。如果分配失败则
  allocate在内部就已经做了处理，及退出这次编译过程。其中a作为实存块的编号可以取如下的值 enum {PERM=0, FUNC, STMT};
 deallocate函数释放编号为a的实存块。这时为a分配的空间并没有被释放，只是被放入了内部的空闲区。
dispose函数销毁整个分配区，释放所有的空间。
newarray在实存块中分配元素大小为m，长度为n的数组空间。
由于＜＜可变目标C编译器－设计与实现＞＞与＜＜C语言接口与实现＞＞中己详细的分析了它的实现，在这里就不再重复。
 2、 C－－字符串存储管理模块的设计
	为了高效的实现字符串的比较、查找等操作，该模块采用了哈希表。具体算法参见＜＜C语言接口与实现＞＞中的原子和＜＜可变目标C编译器－设计与实现>＞中字符串。C－－的字符串模块在cstring.c中。
 3、 C－－循环列表的设计：
	C－－循环列表的接口：
typedef struct list *List;
struct list {
	void *x;
	List link;
};
List append(void *x, List list);
int length(List list);
void *ltov(List *list, unsigned a);
void listmap(List list,
		void (*apply)(void *x,void *c1), void *c1);
append将元素x添加至链尾list。
length返回list的长度。
ltov将链表转换成一数组保存于a的存储区，并释放list。
listmap遍历列表list,并为其中每一个元素调用函数apply，在C－－中用于在调试时输出list中元素。列表模块的实现在文件list.c中。由于代码有较好的自述性和注释，这里就不详细说明了。

 4、符号表的设计
	C－－的符号表模块在sym.c中，对它的解释说明可参照＜＜可变目标C编译器－设计与实现＞＞的符号表。
 5、类型模块的设计与实现
   	C－－的基本类型包括char,int,void。另外还有指针、数组、函数构造类型。类型模块 主要实现了类型的构造、比较等功能。它的实现在type.c中。其中的函数大多与lcc的功能相同，对它们的说明请参照＜＜可变目标C编译器－设计与实现＞＞中的类型模块。这里主要需要解释一下eqtype函数的实现。