编译器介绍

发展历史

编译器和当今流行的NLP自然语言翻译有类似之处,都是将一种语言翻译成另一种语言,而不同之处在于,前者对象是机器,后者对象是人类。

我们想要让机器为我所用,那么必须模仿机器的思维,从机器的角度去看待问题。至于编程是一种控制机器的方式,代码是机器所能识别的语言。

可以将编译技术的不断进步总结为对现有代码语法的不断完善,使之更符合我们的人类思维。

最底层的语言应当为机器语言,由二进制0和1组成,但是在使用的过程中人们发现这种语言编写效率太低,于是为了方便程序代码的编写与调试,人们发明了与机器语言对应的汇编语言。

之后人们又觉得汇编指令用起来也相当繁琐,对新手入门很不友好,容易入门即放弃,因此将汇编封装成了高级语言如C等。

再然后,人们发现C语言在编程时需要做大量重复性工作,如数据结构的哈希等。于是数值计算语言PYTHON等又借助底层C加入了一些新的语法特性,如字典,列表等。

这种不断的完善降低了编程应用的门槛,但同时也带了新的问题,那就是新手在入门之后,会觉得无所适从,效率不高,写不出合适的代码。

因此,对编译原理的学习显得尤为重要。一方面可以实践之前的编程语言以及数据结构,另一方面对程序运行的内存分配有更深的理解,方便自己写出效率更高的代码,以及对复现的程序进行合理的调试。

此外,专家系统中运用得较为普遍的知识是产生式规则,因此编译原理学习对于ai中的专家系统的构建也有着重要的作用。

编译过程概述

在编译的过程中,代码实际上是一串字符,词法分析器将这些字符识别为一个个单词,以单词流的形式送给语法分析器。

再借助语法分析器识别相应语法,生成语法树,接着通过语义分析器检查语义。语义分析之后转化为中间代码,这就是编译器的前端。

中间代码很好地实现了前后端分离,可以约定相同的中间代码,那么中间代码之前可以定义不同的语言语法,之后则可以进行统一的优化分配。

当然其中的过程包含了一系列编译算法以及特定的数据结构,在本文介绍过程中,将尽量结合C语言编程实例进行描述分析。

由于笔者非计算机专业,仅凭兴趣和编程实践需求学习编译原理,因此本文只涉及编译原理的前端部分,即止于代码生成阶段。

直线式程序解释器

实现一个直线式程序解释器

为了方便入门,先介绍一个简单的例子,直线式程序解释器,这个例子参考虎书以及中科大相应课程。

功能虽然简单,却可以作为对环境、抽象语法、树数据结构的递归性以及无赋值语句的函数式风格程序设计的入门。

目标是将 2+3+4 转换为编译器实际要选取的操作,以printf语句打印到屏幕上。

需要解释的语言已经被解释为了抽象语法,同时为了不涉及语言的具体细节,用一个函数构造的方式实现抽象语法。

struct Exp_t *exp = Exp_Sum_new(Exp_Sum_new(Exp_Int_new(2),
Exp_Int_new(3)), Exp_Int_new(4));

可以看到,构造出来的抽象语法用如下数据结构存储,先运算2+3,最后+4:

enum Exp_Kind_t { EXP_INT, EXP_SUM };
struct Exp_t
{
	enum Exp_Kind_t kind;
};

struct Exp_Int
{
	enum Exp_Kind_t kind;
	int i;
};

typedef struct Exp_Sum
{
	enum Exp_Kind_t kind;
	struct Exp_t *left;
	struct Exp_t *right;
}Exp_Sum;

数字运算可以通过一个栈式计算机实现,为此先定义栈的相关操作:

struct Stack_t *Stack_Add_new()
{
	struct Stack_Add *p = (struct Stack_Add*)malloc(sizeof(*p));
	p->kind = STACK_ADD;
	return (struct Stack_t *)p;
}

struct Stack_t *Stack_Push_new(int i)
{
	struct Stack_Push *p = (struct Stack_Push*)malloc(sizeof(*p));
	p->kind = STACK_PUSH;
	p->i = i;
	return (struct Stack_t *)p;
}

接下来根据识别的SUM,INT对栈式计算机执行不同的操作ADD或PUSH,并以单链表形式存储:

// a compiler from Sum to Stack
struct List_t *all = 0;

void emit(struct Stack_t *instr)
{
	all = List_new(instr, all);//类似于栈的PUSH
}

void compile(struct Exp_t *exp)
{
	switch (exp->kind){
	case EXP_INT:{
					 struct Exp_Int *p = (struct Exp_Int *)exp;
					 emit(Stack_Push_new(p->i));
					 break;
	}
	case EXP_SUM:{
					 struct Exp_Sum *p = (struct Exp_Sum *)exp;
					 compile((struct Exp_t*)p->left);compile((struct Exp_t*)(p->right));
					 emit(Stack_Add_new());
					 break;
	}
	default:
		break;
	}
}

最后打印对栈相关操作ADD或PUSH的单链表,调试检验:

// "printer"
void List_reverse_print(struct List_t *list)
{
	while (list){
		switch (list->instr->kind){
		case STACK_ADD:
			printf("STACK ADD\n"); break;
		case STACK_PUSH:
			printf("STACK PUSH %d\n", ((struct Stack_Push *)(list->instr))->i); break;
		}
		list = list->next;
		
	}
}

程序最终运行结果如下:

Compile starting
the expression is:
2+3+4
STACK ADD
STACK PUSH 4
STACK ADD
STACK PUSH 3
STACK PUSH 2

Compile finished

可以看到的确是先运算2+3,最后结果再+4。

其中ADD操作应该既包含对栈中原有元素的POP出栈,也应当包含运算结果的PUSH进栈。

相关工具

相关工具

 Lex是由美国Bell实验室M.Lesk等人用C语言开发的一种词法分析器自动生成工具,它提供一种供开发者编写词法规则(正规式等)的语言(Lex语言)以及这种语言的翻译器(这种翻译器将Lex语言编写的规则翻译成为C语言程序)。

自动词法生成器flex和自动语法生成器bison,需要先转换成lex和yacc规范,然后自动生成.h文件和.cpp文件。

网盘链接: flex-bison 提取码:48p7

在windows平台下有一款对应的flex,bison软件——Win Flex-bison,支持vs开发。

下载官网:Win Flex-bison

lex规范

 [第一部分:定义段]
%{
[C语法的include和声明]
#include "tokens.h"
int charPos=1;
#define ADJ {charPos+=yyleng}
%}
[正则表达式的简写形式和状态说明]
digits    [1-9][0-9]*
 %%
 [第二部分:词法规则段]
[正则表达式和动作] yytext:匹配字符串   yyleng:字符串长度
\n   {ADJ;return ENT;}
if    {ADJ;return IF;}
([a-z]|_)[a-z0-9_]*    {ADJ;return ID;}
{digits}    {ADJ;return NUM;}
 %%
 [第三部分:辅助函数段]在词法规则段中用到的函数
int main(){
    return 0;
}

yacc规范

语法声明
%%
语法规则
exp:exp PLUS exp {执行的C代码}
%%
程序(原始的C代码)

词法分析

概述

程序在文本编辑器中实际上就是一个个字符串,用C语言读取的符号流为ASCII编码,而JAVA读取的符号流为UNICODE编码。

词法分析器用以将符号流转变为记号流,即一个个token单词的形式,比如如下的源代码将对应词法识别为相应的token单词。

2+3+4

对应识别为:

NUM(2)PLUS NUM(3) PLUS NUM(4)

发现有些记号比如NUM,数据有附加属性数值,在定义结构体的时候需要加入。

至于识别所用到的具体技术以及相关算法,可以利用原理手工构造,也可以借助一般性的描述语言比如正则表达式等借助工具FLEX自动生成。

可以规定程序结尾标志,如果读取文件的话可以定义结尾标志为EOF,当然也可以自定义一个结束字符比如”#”。

单词组成语句,即记号流最后会根据语法识别成相应语句,而在词法分析阶段,我们只需要将文本符号正确识别为文法所定义的单词即可。

而文法中规定的单词类型可以用枚举类型表示,继而组成单词结构体:

enum kind{IF,ID,NUM,...};
struct token{
    enum kind k;
    char *leneme;
};
正则表达式

正则表达式

为了对文法有一个标准的描述,可以借助正则表达式来对文法进行描述。

正则表达式有如下定义:

首先空串是正则表达式,任何字符集中的字符也是正则表达式。并且简单的正则表达式可以构成更复杂的。

选择    M|N={M,N}
连接    MN={mn|m属于M,n属于N}
闭包    M*={空串,M,MM,MMM,...}   "Kleen"

还可以引入更多语法糖来进一步封装以简化构造:

[c1-cn]==c1|c2|..|cn
e+==一个或多个e
e?==零个或多个e
"a*"==a*自身,不是a的Kleen闭包
e{i,j}==i到j个e的连接
.==除'\n\外的任意字符

正则表达式元字符

.除了换行符之外的任意字符
/n换行符
*0次或者多次匹配
+1次或者多次匹配
空格0次或者1次匹配
^行首
$行尾
a|ba或者b
(ab)+ab的1次或者多次匹配
“a+b”a+b
[]一类字符
自动机

确定有限状态自动机

引入有向图的概念,符号为边,从而构成一个个状态,类似于数电中的状态转移,由初态开始,终态结束。

前提需要这个状态数量是有限的,程序自动地读入字符,根据实际情况进行状态跳转,那么这个程序就被称为有限状态自动机FA。

规范的定义如下:

\(M=(\sum ,S,q0,F,\delta )\),其中元素分别代表字母表、状态集、初始状态、终结状态集、转移函数。

如果在任何一个状态,读入一个字符后转移的状态是确定的,那么称这个自动机为确定有限状态自动机DFA。

手工构造图转移算法

手工构造图转移算法

由于关键字和标识符可能会有交集部分,比如IF识别为关键字,而IF3应当被识别为标识符,这样就不满足DFA的定义。

处理的办法既可以利用回调函数实现对NFA的构造,也实现对关键字存储,即关键字表算法。

利用关键字表算法,将给定语言中所有的关键字放入表中,对所有标识符和关键字,先统一按标识符转移图识别,识别完成后再判断所识别的是否为关键字。

此处将采用关键字表算法实现对C语言中关键字IF,标识符以及无符号整型的识别,显示识别的类型,以及对应单词所在的位置(行,列)。

首先定义相关的数据结构:

#define TOKEN_MAX_LENGTH 10
enum kind {IF,NUM,ID};
//定义位置
typedef struct Position{
	int line;
	int column;
}Position;
//定义单词记号
typedef struct PreToken{
	char s[TOKEN_MAX_LENGTH];
	int length;
	Position p;
}PreToken;

typedef struct Token{
	int k;
	PreToken pre_t;
	bool error;
}Token;

typedef struct Token_list{
	Token t;
	Token_list* next;
}Token_list;

字符流被空格或回车分隔,因此我们需要将单词从字符流中提取出来,可以通过构造Tokenizer来实现。

Status Tokenizer(Token_list** t_lp, char* code){//按空格和回车符分割字符流,末尾加上\0
	int line = 1, column = 1;
	Token_list* p=NULL; int length = 0;
	while (*code != EOF){
		if (p){
			p->t.pre_t.s[length] = *code;
			if (*code == '\n' || *code == ' '){//分隔
				p->t.pre_t.s[length] = '\0';
				p->t.pre_t.p.column = column-length;
				p->t.pre_t.p.line = line;
				p->t.pre_t.length = length;
				//printf("%s\n", p->t.pre_t.s);
				Dfa(p);
				if (*code == '\n'){
					line += 1; column = 0;
				}
				while (*code == ' ' || *code == '\n'){
					code += 1; column += 1;
				}
				if (*code == EOF)
					return SUCCESS;
				p->next = (Token_list*)malloc(sizeof(Token_list));
				p = p->next;
				length = 0;
				p->t.pre_t.s[length] = *code;
			}//if
		}//if	
		else {
			p = (Token_list*)malloc(sizeof(Token_list));
			p->t.pre_t.s[length] = *code;

		}
		code += 1; column += 1; length += 1;
	}
	p->t.pre_t.s[length] = '\0';
	p->t.pre_t.p.column = column-length;
	p->t.pre_t.p.line = line;
	p->t.pre_t.length = length;
	//printf("%s\n", p->t.pre_t.s);
	Dfa(p);
	p->next = NULL;
	return SUCCESS;
}

需要注意的是我们以空格或回车进行分隔,因此要在最后继续提取一次单词,防止EOF之前的最后一个单词被遗漏。

C语言中标识符以字母或_开头,无符号整型以1-9开头,为了简便起见仅选取小写字母生成记号流。

a-z对应ascii值97-122,_对应ascii值95,0-9对应ascii值48-57。可用二维矩阵(跳转表)整理状态图如下:0状态代表初始,之后若转到状态0则出错。

 az_09
state0:开始2222011
state1:NUM0000111
state2:ID2222222

转换成代码形式:

int dfa[3][37] = {
	{ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
	{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
	{ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 },
};
Status Dfa(Token_list* p){//词法分析器
	int state = 0;
	//识别一个单词记号
	char *code = p->t.pre_t.s;
	//0;1-9;a-z;_,分为四类
	int length = 0;
	while (length <p->t.pre_t.length-1){
		int k = 0;
		if (*code == '0')
			k = 1;
		else if (*code >= '1'&&*code <= '9')
			k = 2;
		else if (*code >= 'a'&&*code <= 'z')
			k = 3;
		else if (*code == '_')
			k = 4;
		switch (k){
		case 1://27
			state = dfa[state][27]; break;
		case 2://49-28=11
			state = dfa[state][(int)(*code - '1')+28]; break;
		case 3://97-0=97
			state = dfa[state][(int)*code - 97]; break;
		case 4://26
			state = dfa[state][26]; break;
		}//switch
		length += 1; code += 1;
		if (state == 0){//识别出错
			p->t.error = true; break;
		}
	}//while

	if (state != 0 && length == p->t.pre_t.length-1){//成功识别一个单词后分类
		p->t.error = false;
		if (state == 1){
			p->t.k = NUM;
			printf("NUM(%s)  (%d,%d)\n", p->t.pre_t.s, p->t.pre_t.p.line, p->t.pre_t.p.column);
		}
		else if (state == 2){
			if (strcmp(p->t.pre_t.s, "if") == 0){//识别关键字IF
				p->t.k = IF;
				printf("IF  (%d,%d)\n", p->t.pre_t.p.line, p->t.pre_t.p.column);
			}
			else{
				p->t.k = ID;
				printf("ID(%s)  (%d,%d)\n", p->t.pre_t.s, p->t.pre_t.p.line, p->t.pre_t.p.column);
			}
			
		}
		
		

	}
	return SUCCESS;
}

由于此处仅有一个关键字IF可能与标识符有交叉,因此只要最后利用字符串函数简单判断一下即可。

在main函数中读取文件字符流,并规定用一个长度限制为1024的数组进行存储,接着对数组进行词法分析Tokenizer:

//打开文件
	FILE* fp = NULL;
	if (fopen_s(&fp, "code.txt", "r+") == 0){
		printf("开始读取符号流!\n");
		//规定代码字符串长度不超过1024
		char code[1024];
		int i = 0; char c;
		c = code[i] = fgetc(fp);
		i += 1;
		while (c != EOF){
			c=code[i] = fgetc(fp);
			i++;
		}
		code[i] = '\0';
		if (fclose(fp) == 0){
			printf("成功读取符号流!\n");
		}
		//词法分析
		Token_list** t_l = (Token_list**)malloc(sizeof(Token_list*));
		*t_l = NULL;
		printf("compile code:\n%s\n", code);
		printf("转换为记号流:\n");
		if(Tokenizer(t_l, code))
			printf("符号流被成功转换!\n");
	}

由控制台输出结果:

开始读取符号流!
成功读取符号流!
compile code:
ifx if iif       if  234
iff     if   
转换为记号流:
ID(ifx)  (1,1)
IF  (1,5)
ID(iif)  (1,8)
IF  (1,18)
NUM(234)  (1,22)
ID(iff)  (2,1)
IF  (2,9)
符号流被成功转换!

也可以引入栈这一数据结构将词法分析过程中状态过程记录下来,以应对有多个终态的情况。

实现DFA有多种方式,也可以借助字符串最长匹配算法,从终止状态开始维护一个栈,若不成功则返回上一个终止状态以实现rollback。

非确定有限自动机

NFA,读入一个字符后,存在状态的不确定性,但可以将其转化为DFA,然后构建DFA的词法分析器。

尽管DFA和NFA有不同的定义,在形式理论中可以证明它们是等价的;就是说,对于任何给定NFA,都可以构造一个等价的DFA。NFA实现过程复杂,所以一般需要将NFA转化为DFA。

词法转换算法

Thompson算法

RE(正则表达式)->NFA(非确定有限自动机),是基于对RE结构的归纳:对基本的RE直接构造,对复合的RE递归构造。

具体说来:空串或是单字符加连边,连接类似于串联,选择类似于并联,闭包构成回路。

子集构造算法

NFA(非确定有限自动机)->DFA(确定有限自动机),由图转移算法可以知道DFA方便编程实现。

子集构造法,根据接受的字符划分相应状态集合,即原状态集的子集作为新的状态。子集中若包含终止状态,则该子集也为终止状态。

具体实现时,闭包的计算涉及数据结构图中遍历算法。

Hopcroft算法

算法的核心是划分等价类,与最小化相关的概念:

多余状态:初态不能到达的状态;死状态:不能转移到终态的状态;统称为“无关状态”。

等价状态:从状态出发后对任意输入符号能够得到相同的状态;可区别状态:不等价

根据终态非终态首次分化,通过接受的字符依据可区别状态分化状态集至不能继续分化为止,然后合并等价状态(用同一个状态表示),删去无关状态,实现DFA的最小化。

由RE->NFA->DFA->最小化DFA,实际上也是一种小型编译器了,将正则语言转化为了图结构的语言进行表示。

自动生成词法分析器

借助flex自动生成词法分析器

flex就是采用上述词法转换算法实现一个正则表达式到最小化DFA的转换,它的使用十分方便,这里借助它对手工构造图转移算法做一个比较。

首先在lex文件中定义正则表达式:

[1-9][0-9]* {printf("%s",yytext);printf("(%d,%d)",line,column);column+=yyleng;}
[a-z_][a-z0-9_]*   {printf("%s",yytext);printf("(%d,%d)",line,column);column+=yyleng;}
"if"    {printf("%s",yytext);column+=yyleng;}
\n    {printf("\n");line++;column=1;}
" "    {column+=1;}

接着编写主函数,从同一个code文本中读取代码并输出到控制台结果:

int main(){
	FILE* fp = NULL;
	if (fopen_s(&fp, "code.txt", "r") == 0)
		yyin=fp;
	yylex();


	
	printf("success!\n");
	while(1);
	return 0;
}
code文本内容:
ifx if iif       if  234
iff     if
控制台显示信息:
ifx(1,1)if(1,5)iif(1,8)if(1,18)234(1,22)
iff(2,1)if(2,9)

可以看到和手动构造图转移算法实现结果一致。

语法分析

语法分析概述

语法分析接受词法分析输出的记号流,判断语法是否符合语言文法的规范,进而输出一棵语法树,作为语义分析阶段的输入。

若是语法出错,可以进行错误提示,进行定位以及输出诊断信息,接着重新词法分析、语法分析。

上下文无关文法

上下文无关文法CFG

上下文无关文法描述一种语言,文法有如下定义:

G=(T,N,P,S),其中元素分别代表终结符集合、非终结符集合、产生式规则集合X->beta、唯一的开始符号(非终结符)。

从开始符号S开始,将终结符用非终结符对应的产生式中的右部进行替换的过程称之为“推导”,同一个句子可以有多种不同的推导,最左推导扩展左边非终结符的推导,最右推导扩展右边非终结符的推导。

推导过程不断重复至不出现终结符为止,最终的串称为“句子”。

两种不同的推导可以有相同的语法分析树,但如果一个文法能够推导出不同的语法分析树,称该文法有二义性。一般可以可以将其转化为无二义性的文法,分析树的含义取决于树的后序遍历。

在乔姆斯基文法体系中,文法可以分为3型,即正则文法,2型即上下文无关文法,因此正则文法也可以看作是上下文无关文法的一种特例,Thompson算法也可也借助上下文无关文法实现。

上下文无关文法类似于词法分析中的正则表达式,作为一种声明式的规范,可以利用它来生成语法分析器。

自顶向下分析

自顶向下分析

从开始符号出发推出句子,称为自顶向下分析,对应于分析树自顶向下的构造顺序。

终结符需要和目标句子进行规则尝试性的匹配,在匹配过程中需要进行回溯,每匹配一个字符,目标句子中的游标后移一位,回溯时,目标句子中游标前移相应位数。

可以引入栈结构对元素逆序压栈实现回溯操作,借助循环和栈实现树结构的递归操作,若最后栈为空并且目标句子游标到结尾,则成功识别语言的语法。

但回溯给分析效率带来问题,而编译必须高效。因此需要线性时间算法避免回溯,引出了递归下降分析算法和LL(1)分析算法。

具体说来,自顶向下分析的问题在于对句子规则是进行尝试性的匹配,因此解决的思想是提前看符号实现选择性匹配以避免回溯。

但有时会出现提前符号冲突的情况,即选择性匹配的时候有多个选择如左递归等,这就需要一个系统的解决冲突的办法。

递归下降分析

递归下降分析也称“预测分析”,基本思想是对每个非终结符构造一个分析函数,用前看符号知道产生式规则的选择。

采用分治的思想,它具有如下的特点:分析高效(线性时间)、容易实现、错位定位和诊断信息准确。

语法分析器的实现

实现一个算术表达式的语法分析器

算术表达式的上下文无关文法定义如下:

E->E+T
 |E-T
 |T
T->T*F
 |T/F
 |F
F->num
 |(E)

对E、T、F分别构造分析处理函数,但是注意E和T存在冲突,经观察发现可以改写成类似T+T+…+T的形式,可以用循环解决冲突以及左递归的问题。

void parse_F()
{
	//printf("recognize F\n");
	char c = str[i];
	if (c >= '0'&&c<='9'){
		i++;
		return;
	}
	if (c == '('){
		i++;
		parse_E();
		c = str[i];
		if (c == ')'){
			i++;
			return;
		}
		error("\')\'", c);
		return;
	}
	error("\'0-9\' or \'(\'", c);
	return;
}


void parse_T()
{
	//printf("recognize T\n");
	parse_F();
	char c = str[i];
	while (c == '*'){
		i++;
		parse_F();
		c = str[i];
	}
	while (c == '/'){
		i++;
		parse_F();
		c = str[i];
	}
	return;
}

void parse_E()
{
	//printf("recognize E\n");
	parse_T();
	char c = str[i];
	while (c == '+'){
		i++;
		parse_T();
		c = str[i];
	}
	while (c == '-'){
		i++;
		parse_T();
		c = str[i];
	}
	return;
}

除此之外还可以构造错误提示函数进行控制台输出。

void error(char *want, char got)
{
	fprintf(stderr, "Compling this expression:\n%s\n", str);
	int j = i;
	while (j--)
		fprintf(stderr, " ");
	fprintf(stderr, "^\n");
	fprintf(stderr, "Syntax error at position: %d\n"
		"\texpecting: %s\n"
		"\tbut got  : %c\n",
		i, want, got);
	return;
}

正确识别时,控制台没有报错信息,但是一旦有错,则会准确定位错误并进行提示。

e = "(3+4*5))";
parse(e);

控制台显示:
Compling this expression:
(3+4*5))
       ^
Syntax error at position: 7
        expecting: '+' or '\0'
        but got  : )

LL(1)分析算法

从左向右读入程序,最左推导,采用(1)个前看符号,算法的基本思想是:表驱动的分析算法。

分析表类似于词法分析中的DFA,根据表中内容选择性进行推导,同时维护一个分析栈。在编写分析表时,需要借助FIRST集以及FOLLOW集。

FIRST集

FIRST(N),从非终结符N开始推导得出的句子开头的所有可能终结符集合,类似于子集构造法,直至不出现新的FIRST集为止。

对 N->a
FIRST(N) ∪= {a}
对 N->M
FIRST(N) ∪= FIRST(M)

冲突检测:
对N->β和N->γ,要求FIRST_S(β)∩ FIRST_S(γ) = {}
若存在冲突,则该文法不能用LL(1)分析表进行分析。

可以构建新的文法消除左递归改为右递归,或者提取左公因子改写文法以避免冲突。

FOLLOW集

当产生式中可以为空串时,不仅仅需要直到下一个终结符集合,还需要知道非终结符后面跟着的符号,而这些符号的集合称之为“FOLLOW集”。

NULLABLE集,当非终结符X可以推导出空串,则属于NULLABLE集。

FIRST集完整计算公式如下:

X->a
 .FIRST(X)∪= {a}
X->Y1 Y2 ... Yn
 .FIRST(X)∪= FIRST(Y1)
 .if Y1∈NULLABLE,FIRST(X)∪= FIRST(Y2)
 ...

LL(1)分析算法运行高效并且有现成的工具可用,但是能分析的文法类型受限,并且往往需要对文法进行改写。

自底向上分析

自底向上分析

与自顶向上不同,自底向上对句子进行规约操作即右侧替换成左侧,是推导的逆操作,直至最后完整识别出一个句子。

LR(k)分析算法

LL(k)分析技术的一个弱点是仅仅看到右部的前k个单词就必须预测选择哪一个产生式,另一种更有效的是LR(k)分析,能够将判断推迟到产生式的整个右部对应的输入单词之后。

LR算法就是一种自底向上分析算法,也称为“移进规约”算法,能够有效分析多种文法类型,并且也有许多的工具可用。其中移进是指压栈,规约是指栈顶上n个符号对应于左部的非终结符。

LR分析器通过DFA知道移进规约的时机,但非作用于输入(DA太弱而不适合CFG),而是作用于栈。二维矩阵实现为例,列为状态,行为动作(移进规约)以及转移。

可以引入点记号·以方便标记语法分析器读入的输入位置,加·号的产生式称为“项目”。

LR(0)分析算法

LR(0)不需要超前超看单词,直接根据分析栈的内容执行相应的操作,每一个操作要么是规约要么是移进,但是对于同一个状态可能产生移进-规约冲突。

这一类文法类似于自顶向下中的尝试性匹配,没有选择性,因此太弱而一般不使用,但是其构造的而分析表算法却是LR分析算法的开始。

SLR分析算法

SLR类文法是分析表不含冲突的文法,比LR(0)分析能力更强,对于LR(0)中的移进规约冲突,采取一种更合适的放置规约动作的方法,即只在FOLLOW集合指定的地方放置规约动作。

我们定义的FOLLLOW集合为紧跟非终结符的终结符,而非终结符对应于一个产生式已经可以规约,而不会继续移进,这样就减少了分析表中规约动作的数量。

LR(1)分析算法

LR(1)比SLR更加强大,因为它超前查看了一个单词,具有更好的选择性,这种方法在产生式的末尾有原点时即进行规约动作,此外仅进行换动作。

列为状态,行为符号,终结符和非终结符,分别对应移进或动作以及状态转换动作。

LALR分析算法

LR分析表有很多状态,因此可能存储空间过合并那种除超前查看符号集合外其余部分都相同的状态,得到一个较小的表,称之为LALR分析器。

实际中LALR表可能存在规约-规约冲突,而LR表中却没有冲突,但是影响较小,重要的在于存储空间小得多。

各类文法的层次图
抽象语法

抽象语法概述

在进行语法分析的时候,还必须完成一些语义动作,以便对分析的短语做一些有用的处理。

在递归下降的语法分析器中,语义行为是语法分析函数所返回的值或者时这些函数产生的副作用。以自底向上为例,语义动作在产生式“规约”时执行,即由右部的值计算左部的值。

在分析栈上维护一个三元组:<symbol,value,state>,分别标志终结符或非终结符,symbol的值,以及当前的分析状态。

在yacc文法中上通过编写一段C代码在括号中实现语法分析时执行相应的语义动作的。

E : E+ E  {$$=$1+$3;}
  | n     {$$=$1;}

编写由语义动作来实现的编译器很难阅读和维护,并且这种方法限制了编译器只能完全按照语法分析的顺序来处理程序。

分析树包含了句子推导的完整过程,但是也夹杂了很多不必要的信息,对于表达式而言只需要知道运算符和运算数,至于优先级、结合性等已经在语法分析部分处理掉了。

具体语法是语法分析器使用的语法,而抽象语法是用来表达语法结构的内部表示。为了有利于模块化,并使编译器内部流水线工作,可以借用一种数据结构即抽象语法树,作为语法和语义的接口,实现代码信息的传递。

也可也在yacc中借助语义动作生成抽象语法树:

E : E + E {$$ = Exp_Add_new($1,$3);}
  | E * E {$$ = Exp_Times_new($1,$3);}
  | n     {$$ = Exp_Int_new($1);}

程序一旦被转换成抽象语法树,源代码即被丢弃,后续阶段只处理抽象语法树,因此抽象语法树必须编码足够多的源代码信息,比如位置,以方便报错和检查。

抽象语法树的实现

抽象语法树的实现

在最开始的时候实现了一个直线式程序解释器,而接下来将对它做进一步完善,使其能够完整地读入代码并构造抽象语法树。

首先我们定义抽象语法树的结点结构:

enum Exp_Kind_t{
	EXP_INT,
	EXP_ADD,
	EXP_MINUS,
	EXP_TIMES,
	EXP_DIVIDE,
};

/*
E -> n
| E + E
| E * E
*/
 typedef struct EXP_t{
	enum Exp_Kind_t kind;
	
 }*Exp_t;

 // all operations on "Exp"
 void Exp_print(Exp_t exp);
 int Exp_numNodes(Exp_t exp);

 typedef struct EXP_Int{
	 enum Exp_Kind_t kind;
	 int n;
 }*Exp_Int;
Exp_t Exp_Int_new(int n);

 typedef struct EXP_Add{
	 enum Exp_Kind_t kind;
	 Exp_t left;
	 Exp_t right;
 }*Exp_Add;
 Exp_t Exp_Add_new(Exp_t left, Exp_t right);

 typedef struct EXP_Minus{
	 enum Exp_Kind_t kind;
	 Exp_t left;
	 Exp_t right;
 }*Exp_Minus;
 Exp_t Exp_Minus_new(Exp_t left, Exp_t right);

 typedef struct EXP_Times{
	 enum Exp_Kind_t kind;
	 Exp_t left;
	 Exp_t right;
 }*Exp_Times;
 Exp_t Exp_Times_new(Exp_t left, Exp_t right);

 typedef struct EXP_Divide{
	 enum Exp_Kind_t kind;
	 Exp_t left;
	 Exp_t right;
 }*Exp_Divide;
 Exp_t Exp_Divide_new(Exp_t left, Exp_t right);

并实现对表达式的相应操作:

Exp_t Exp_Int_new(int n)
{
	Exp_Int p = (Exp_Int)malloc(sizeof (*p));
	p->kind = EXP_INT;
	p->n = n;
	return (Exp_t)p;
}

Exp_t Exp_Add_new(Exp_t left, Exp_t right)
{
	Exp_Add p = (Exp_Add)malloc(sizeof (*p));
	p->kind = EXP_ADD;
	p->left = left;
	p->right = right;
	return (Exp_t)p;
}

Exp_t Exp_Minus_new(Exp_t left, Exp_t right)
{
	Exp_Minus p = (Exp_Minus)malloc(sizeof (*p));
	p->kind = EXP_MINUS;
	p->left = left;
	p->right = right;
	return (Exp_t)p;
}

Exp_t Exp_Times_new(Exp_t left, Exp_t right)
{
	Exp_Times p = (Exp_Times)malloc(sizeof (*p));
	p->kind = EXP_TIMES;
	p->left = left;
	p->right = right;
	return (Exp_t)p;
}

Exp_t Exp_Divide_new(Exp_t left, Exp_t right)
{
	Exp_Divide p = (Exp_Divide)malloc(sizeof (*p));
	p->kind = EXP_DIVIDE;
	p->left = left;
	p->right = right;
	return (Exp_t)p;
}

为了便于调试,我们需要对抽象语法树进行遍历:

void Exp_print(Exp_t exp)
{
	if (!exp) return;
	switch (exp->kind){
	case EXP_INT:{
					 Exp_Int p = (Exp_Int)exp;
					 printf("%d", p->n);
					 return;
	}
	case EXP_ADD:{
					 Exp_Add p = (Exp_Add)exp;
					 printf("(");
					 Exp_print(p->left);
					 printf(") + (");
					 Exp_print(p->right);
					 printf(")");
					 return;
	}
	case EXP_MINUS:{
					 Exp_Minus p = (Exp_Minus)exp;
					 printf("(");
					 Exp_print(p->left);
					 printf(")-(");
					 Exp_print(p->right);
					 printf(")");
					 return;
	}
	case EXP_TIMES:{
					   Exp_Times p = (Exp_Times)exp;
					   printf("(");
					   Exp_print(p->left);
					   printf(") * (");
					   Exp_print(p->right);
					   printf(")");
					   return;
	}
	case EXP_DIVIDE:{
					   Exp_Divide p = (Exp_Divide)exp;
					   printf("(");
					   Exp_print(p->left);
					   printf(") / (");
					   Exp_print(p->right);
					   printf(")");
					   return;
	}
	default:
		return;
	}
}

至于语法分析部分,我们借助bison实现语法分析以及添加相应的语义动作:

program: exp {tree = $1;}
;

exp: digit     {$$ = $1;}
| exp '+' exp  {$$ = Exp_Add_new ($1, $3);}
| exp '-' exp  {$$ = Exp_Minus_new ($1, $3);}
| exp '*' exp  {$$ = Exp_Times_new ($1, $3);}
| exp '/' exp  {$$ = Exp_Divide_new ($1, $3);}
| '(' exp ')'  {$$ = $2;} 
;

digit: '0'  {$$ = Exp_Int_new (0);}
| '1'       {$$ = Exp_Int_new (1);}
| '2'       {$$ = Exp_Int_new (2);}
| '3'       {$$ = Exp_Int_new (3);}
| '4'       {$$ = Exp_Int_new (4);}
| '5'       {$$ = Exp_Int_new (5);}
| '6'       {$$ = Exp_Int_new (6);}
| '7'       {$$ = Exp_Int_new (7);}
| '8'       {$$ = Exp_Int_new (8);}
| '9'       {$$ = Exp_Int_new (9);}
;

实际上我们所做的这些工作就是将最开始的程序解释器中的手动构造抽象语法树转变为输入符号串自动识别并构造抽象语法树。

//直线式程序解释器手动构造
struct Exp_t *exp = Exp_Sum_new(Exp_Sum_new(Exp_Int_new(2)
		, Exp_Int_new(3))
		, Exp_Int_new(4));
//自动识别并构造
yyparse();
	

程序台输出结果如下:

2+3+4
syntax error
((2) + (3)) + (4)
STACK ADD
STACK PUSH 4
STACK ADD
STACK PUSH 3
STACK PUSH 2

Compile finished

和最开始的实验结果一致,说明抽象语法树成功生成了。

语义分析

语义分析概述

语义分析阶段接受语法分析生成的抽象语法树,并遍历抽象语法树,将变量定义与使用关联起来,将抽象语法转换成更简单的中间代码的形式。

到语义分析结束就实现了一个编译器完整的前端部分,不同的目标语言可以用相同的中间代码表示,即对程序的翻译,以此实现多种语言间的编译。

语义分析之后,中间代码不存在语法或是语义上的错误,若是程序编译仍有错误,只可能是编译器本身的错误。因此需要对语义分析器进行合理的设计,进行语义的检查以及错误的提示,仍需要知道位置信息。

编译器的实现者必须对语言中的语义规定由全面的理解,换言之,学习语义分析能够进一步加深对我们所掌握的编程语言的理解,这也是我学习编译原理的目的所在。

符号表

符号表

语义分析阶段需要对符号表进行管理,而符号表的作用是将标识符映射到相应的类型、作用域、访问控制信息以及存储位置,使得变量定义与标识符相关联。

大型程序的标识符数量庞大,因此符号表的组织必须要能够进行搞笑的查找,可以借助散列表进行实现,并且考虑到作用域的局部屏蔽,应在头部插入。此外,若为了节约空间,也可选择红黑树等平衡树结构。

类型检查

类型检查

类型检查器类似于递归下降语法分析器,也可也用一个递归函数进行实现,和语法分析相比较,类型检查实际上是上下文相关分析,它负责检查程序(抽象语法树)的上下文相关的属性,依赖于具体的语言。

它需要对如下方面进行相应的检查:变量、下表和域的类型检查;变量、类型、函数声明的类型检查;

类型相等在实际语言中处理不同,可能比较名字相等,或是结构相等,前者可直接比较,而后者需要递归比较各个域。

目标代码生成

语义分析器还能够在遍历抽象语法树的同时生成中间代码或者是目标代码。可以生成目标机上相关的指令代码,然后直接作用于现有的物理机器,或是生成我们所规定的指令代码,然后在我们所写的虚拟机器“指令解释器”上面执行。

中科大的编译原理课程介绍了这两种相关的技术,实际上就是将抽象语法树进一步转化成机器所能读懂的指令,而转换的过程需要我们设计编译器时有清晰的了解并进行定义。

手动构造代码生成也以借助递归下降来实现,根据语句、产生式等分别构造转换函数,然后生成期望的指令。以贯穿本文的栈式计算机为例,语义分析器最终将程序翻译成栈式计算机的相关指令如load、store、add等。

语义分析器的实现

语义分析器的实现——类型检查

在语法分析阶段生成了一棵抽象语法树,语义分析阶段就是对这棵抽象语法树进行处理,相关重复构造不再赘述,只介绍关键的语义分析器的实现部分。

不同之处在于表达式多了标识符ID,布尔型变量以及逻辑上的与或操作。

 // id
typedef struct EXP_Id{
	enum Exp_Kind_t kind;
	char *id;
}*Exp_Id;
Exp_t Exp_Id_new(char *id);

// true
typedef struct EXP_True{
	enum Exp_Kind_t kind;
}*Exp_True;
Exp_t Exp_True_new();

// false
typedef struct EXP_False{
	enum Exp_Kind_t kind;
}*Exp_False;
Exp_t Exp_False_new();
// &&
 typedef struct EXP_And{
	 enum Exp_Kind_t kind;
	 Exp_t left;
	 Exp_t right;
 }*Exp_And;
 Exp_t Exp_And_new(Exp_t left, Exp_t right);

 // &&
 typedef struct EXP_Or{
	 enum Exp_Kind_t kind;
	 Exp_t left;
	 Exp_t right;
 }*Exp_Or;
 Exp_t Exp_Or_new(Exp_t left, Exp_t right);

接下来定义符号表,为了简便起见,用链表进行存储。

Type_t Table_lookup(char *id)
{
	List_t p = table;
	while (p){
		Dec_t d = (Dec_t)p->data;
		if (strcmp(d->id, id) == 0)
			return d->type;
		p = p->next;
	}
	return (Type_t)(-1);
}

void Table_insert(Dec_t dec)
{

	if (Table_lookup(dec->id) != -1){
		fprintf(stderr, "Error: the variable "
			"\"%s\" has been declared!\n", dec->id);
		return;
	}
	table = List_new(dec, table);
	return;
}

以及定义一些类型以便后续语义分析器的类型检查,程序由语句组成,语句有表达式组成,而表达式的值最后只有整型以及布尔型。

////////////////////////////
// type
typedef enum Type_Kind_t{
	TYPE_INT,
	TYPE_BOOL
} Type_t;
void Type_print(Type_t);

我们分别对声明、语句执行类型检查,需要进行查符号表操作。

// dec
void check_dec(Dec_t d)
{
	Table_insert(d);
}

void check_decs(List_t decs)
{
	while (decs){
		Dec_t d = (Dec_t)decs->data;
		check_dec(d);
		decs = decs->next;
	}
	return;
}

////////////////////////////////////////
// exp

// Your job:
Type_t check_exp(Exp_t exp)
{
	if (!exp) 
		return (Type_t)(-1);
	Type_t t1, t2,t;
	switch (exp->kind){
	case EXP_INT:
		return TYPE_INT;
	case EXP_ID:
		t=Table_lookup(((Exp_Id)exp)->id);
		if (int(t)==-1)
			printf("id not found\n");
		else
			return t;
	case EXP_TRUE:
		return TYPE_BOOL;
	case EXP_FALSE:
		return TYPE_BOOL;
	case EXP_ADD:
		t1 = check_exp(((Exp_And)exp)->left);
		t2 = check_exp(((Exp_And)exp)->right);
		if (t1 != TYPE_INT || t2 != TYPE_INT)
			printf("type mismatch\n");
		else return TYPE_INT;
	case EXP_MINUS:
		t1 = check_exp(((Exp_Minus)exp)->left);
		t2 = check_exp(((Exp_Minus)exp)->right);
		if (t1 != TYPE_INT || t2 != TYPE_INT)
			printf("type mismatch\n");
		else return TYPE_INT;
	case EXP_TIMES:
		t1 = check_exp(((Exp_Times)exp)->left);
		t2 = check_exp(((Exp_Times)exp)->right);
		if (t1 != TYPE_INT || t2 != TYPE_INT)
			printf("type mismatch\n");
		else return TYPE_INT;
	case EXP_DIVIDE:
		t1 = check_exp(((Exp_Divide)exp)->left);
		t2 = check_exp(((Exp_Divide)exp)->right);
		if (t1 != TYPE_INT || t2 != TYPE_INT)
			printf("type mismatch\n");
		else return TYPE_INT;
	case EXP_AND:
		t1 = check_exp(((Exp_And)exp)->left);
		t2 = check_exp(((Exp_And)exp)->right);
		if (t1 != TYPE_BOOL || t2 != TYPE_BOOL)
			printf("type mismatch\n");
		else return TYPE_BOOL;
	case EXP_OR:
		t1 = check_exp(((Exp_Or)exp)->left);
		t2 = check_exp(((Exp_Or)exp)->right);
		if (t1 != TYPE_BOOL || t2 != TYPE_BOOL)
			printf("type mismatch\n");
		else return TYPE_BOOL;
	}
}

////////////////////////////////////////
// stm

// Your job:
void check_stm(Stm_t stm)
{
	Type_t t1, t2, t;
	if (!stm) 
		return;
	switch (stm->kind){
	case STM_ASSIGN:
		t1 = Table_lookup(((Stm_Assign)stm)->id);
		t2 = check_exp(((Stm_Assign)stm)->exp);
		if (t1 != t2)
			printf("type mismatch\n");
		else
			return ;
	case STM_PRINTI:
		t = check_exp(((Stm_Printi)stm)->exp);
		if (t!= TYPE_INT)
			printf("type mismatch\n");
		else
			return;
	case STM_PRINTB:
		t = check_exp(((Stm_Printb)stm)->exp);
		if (t != TYPE_BOOL)
			printf("type mismatch\n");
		else
			return;
	default:
		return;
	}

}

void check_stms(List_t stms)
{
	while (stms){
		Stm_t s = (Stm_t)stms->data;
		check_stm(s);
		stms = stms->next;
	}
	return;
	
}


void Semant_check(Prog_t prog)
{
	if (!prog) return;
	// create table
	check_decs(prog->decs);
	// check stm
	check_stms(prog->stms);
	return;
}

最后编写主函数依次调用语法分析器生成抽象语法树,调用语义分析器,若有错误输出相关信息。

printf("lex and parse starting...\n");
	
yyparse();
printf("lex and parse finished\n");

printf("print the AST starting...\n");
Prog_print(tree);
printf("print the AST finished\n");

printf("semantic analysis starting...\n");
Semant_check(tree);
printf("semantic analysis finished\n");

控制台输出信息为:

lex and parse starting...
{  int a;  bool a;  printb (b);  a = a + 3333;  b = b && true;  printi(a);}
lex and parse finished
print the AST starting...
{
  int a;
  bool a;

  printb(b);
  a = (a) + (3333);
  b = (b) && (true);
  printi(a);
}
print the AST finished
semantic analysis starting...
Error: the variable "a" has been declared!
id not found
id not found
type mismatch
type mismatch
type mismatch
semantic analysis finished

的确,我们代码中未声明标识符b以及赋值语句类型检查出错,之后改bool a为bool b,控制台输出信息如下:

lex and parse starting...
{  int a;  bool b;  printb (b);  a = a + 3333;  b = b && true;  printi(a);}
lex and parse finished
print the AST starting...
{
  int a;
  bool b;

  printb(b);
  a = (a) + (3333);
  b = (b) && (true);
  printi(a);
}
print the AST finished
semantic analysis starting...
semantic analysis finished

可见代码正确,语义分析器正确分析代码并未报错。

语义分析器的实现——代码生成

将类型检查与代码生成分步进行是为了更好地了解每一个模块的作用,使得代码的框架更加清晰,此处将在类型检查之后生成目标代码,以栈式计算机为例。

首先定义栈式计算机的指令,并实现相应的构造函数。

/////////////////////////////////////
// instructions
enum Stack_Instr_Kind_t{
	STACK_INSTR_PUSH,
	STACK_INSTR_LOAD,
	STACK_INSTR_STORE,
	STACK_INSTR_ADD,
	STACK_INSTR_MINUS,
	STACK_INSTR_TIMES,
	STACK_INSTR_DIV,
	STACK_INSTR_AND,
	STACK_INSTR_OR,
	STACK_INSTR_PRINTI,
	STACK_INSTR_PRINTB
};

typedef struct STACK_Instr_t{
	enum Stack_Instr_Kind_t kind;
}*Stack_Instr_t;;
void Stack_Instr_print(Stack_Instr_t);

// push n
typedef struct STACK_Instr_Push{
	enum Stack_Instr_Kind_t kind;
	int n;
}*Stack_Instr_Push;;
Stack_Instr_t Stack_Instr_Push_new(int n);

// load x
typedef struct STACK_Instr_Load{
	enum Stack_Instr_Kind_t kind;
	char *x;
}*Stack_Instr_Load;;
Stack_Instr_t Stack_Instr_Load_new(char *);

// store x
typedef struct STACK_Instr_Store{
	enum Stack_Instr_Kind_t kind;
	char *x;
}*Stack_Instr_Store;;
Stack_Instr_t Stack_Instr_Store_new(char *);

// add
typedef struct STACK_Instr_Add{
	enum Stack_Instr_Kind_t kind;
}*Stack_Instr_Add;;
Stack_Instr_t Stack_Instr_Add_new();

// minus
typedef struct STACK_Instr_Minus{
	enum Stack_Instr_Kind_t kind;
}*Stack_Instr_Minus;;
Stack_Instr_t Stack_Instr_Minus_new();

// times
typedef struct STACK_Instr_Times{
	enum Stack_Instr_Kind_t kind;
}*Stack_Instr_Times;;
Stack_Instr_t Stack_Instr_Times_new();

// divide
typedef struct STACK_Instr_Divide{
	enum Stack_Instr_Kind_t kind;
}*Stack_Instr_Divide;;
Stack_Instr_t Stack_Instr_Divide_new();

// and
typedef struct STACK_Instr_And{
	enum Stack_Instr_Kind_t kind;
}*Stack_Instr_And;;
Stack_Instr_t Stack_Instr_And_new();

// or
typedef struct STACK_Instr_Or{
	enum Stack_Instr_Kind_t kind;
}*Stack_Instr_Or;;
Stack_Instr_t Stack_Instr_Or_new();

// printi
typedef struct STACK_Instr_Printi{
	enum Stack_Instr_Kind_t kind;
}*Stack_Instr_Printi;;
Stack_Instr_t Stack_Instr_Printi_new();

// printb
typedef struct STACK_Instr_Printb{
	enum Stack_Instr_Kind_t kind;
}*Stack_Instr_Printb;;
Stack_Instr_t Stack_Instr_Printb_new();

/////////////////////////////////////
// prog
typedef struct STACK_Prog_t{
	List_t ids;  // List_t<char *>
	List_t instrs;   // List_t<Stm_t>
}*Stack_Prog_t;;
Stack_Prog_t Stack_Prog_new(List_t, List_t);
void Stack_Prog_print(Stack_Prog_t);
/////////////////////////////////////
// instructions

void Stack_Instr_print(Stack_Instr_t s)
{
	switch (s->kind){
	case STACK_INSTR_PUSH:{
							  Stack_Instr_Push p = (Stack_Instr_Push)s;
							  printf("push %d", p->n);
							  break;
	}
	case STACK_INSTR_LOAD:{
							  Stack_Instr_Load p = (Stack_Instr_Load)s;
							  printf("load %s", p->x);
							  break;
	}
	case STACK_INSTR_STORE:{
							   Stack_Instr_Store p = (Stack_Instr_Store)s;
							   printf("store %s", p->x);
							   break;
	}
	case STACK_INSTR_ADD:{
							 printf("add");
							 break;
	}
	case STACK_INSTR_MINUS:{
							 printf("minus");
							 break;
	}
	case STACK_INSTR_TIMES:{
							   printf("times\n");
							   break;
	}
	case STACK_INSTR_DIV:{
							 printf("div");
							 break;
	}
	case STACK_INSTR_AND:{
							   printf("and");
							   break;
	}
	case STACK_INSTR_OR:{
							 printf("or");
							 break;
	}
	case STACK_INSTR_PRINTI:{
								printf("printi");
								break;
	}
	case STACK_INSTR_PRINTB:{
								printf("printb");
								break;
	}
	default:
		break;
	}
}

// push 
Stack_Instr_t Stack_Instr_Push_new(int n)
{
	Stack_Instr_Push p = (Stack_Instr_Push)malloc(sizeof(*p));
	p->kind = STACK_INSTR_PUSH;
	p->n = n;
	return (Stack_Instr_t)p;
}

// load x
Stack_Instr_t Stack_Instr_Load_new(char *x)
{
	Stack_Instr_Load p = (Stack_Instr_Load)malloc(sizeof(*p));
	p->kind = STACK_INSTR_LOAD;
	p->x = x;
	return (Stack_Instr_t)p;
}

// store x
Stack_Instr_t Stack_Instr_Store_new(char *x)
{
	Stack_Instr_Store p = (Stack_Instr_Store)malloc(sizeof(*p));
	p->kind = STACK_INSTR_STORE;
	p->x = x;
	return (Stack_Instr_t)p;
}

// add
Stack_Instr_t Stack_Instr_Add_new()
{
	Stack_Instr_Add p = (Stack_Instr_Add)malloc(sizeof(*p));
	p->kind = STACK_INSTR_ADD;
	return (Stack_Instr_t)p;
}

// Minus
Stack_Instr_t Stack_Instr_Minus_new()
{
	Stack_Instr_Minus p = (Stack_Instr_Minus)malloc(sizeof(*p));
	p->kind = STACK_INSTR_MINUS;
	return (Stack_Instr_t)p;
}

// times
Stack_Instr_t Stack_Instr_Times_new()
{
	Stack_Instr_Times p = (Stack_Instr_Times)malloc(sizeof(*p));
	p->kind = STACK_INSTR_TIMES;
	return (Stack_Instr_t)p;
}

// divide
Stack_Instr_t Stack_Instr_Divide_new()
{
	Stack_Instr_Divide p = (Stack_Instr_Divide)malloc(sizeof(*p));
	p->kind = STACK_INSTR_DIV;
	return (Stack_Instr_t)p;
}

// and
Stack_Instr_t Stack_Instr_And_new()
{
	Stack_Instr_And p = (Stack_Instr_And)malloc(sizeof(*p));
	p->kind = STACK_INSTR_AND;
	return (Stack_Instr_t)p;
}

// or
Stack_Instr_t Stack_Instr_Or_new()
{
	Stack_Instr_Or p = (Stack_Instr_Or)malloc(sizeof(*p));
	p->kind = STACK_INSTR_OR;
	return (Stack_Instr_t)p;
}


// printi
Stack_Instr_t Stack_Instr_Printi_new()
{
	Stack_Instr_Printi p = (Stack_Instr_Printi)malloc(sizeof(*p));
	p->kind = STACK_INSTR_PRINTI;
	return (Stack_Instr_t)p;
}

// printb
Stack_Instr_t Stack_Instr_Printb_new()
{
	Stack_Instr_Printb p = (Stack_Instr_Printb)malloc(sizeof(*p));
	p->kind = STACK_INSTR_PRINTB;
	return (Stack_Instr_t)p;
}

///////////////////////////////////////
// prog
Stack_Prog_t Stack_Prog_new(List_t ids, List_t instrs)
{
	Stack_Prog_t p = (Stack_Prog_t)malloc(sizeof (*p));
	p->ids = ids;
	p->instrs = instrs;
	return p;
}

void Stack_Prog_print(Stack_Prog_t prog)
{
	List_t ids = prog->ids;
	printf("{\n");
	while (ids){
		char *id = (char *)ids->data;
		printf("  .int %s\n", id);
		ids = ids->next;
	}

	printf("\n");

	List_t instrs = prog->instrs;
	while (instrs){
		Stack_Instr_t s = (Stack_Instr_t)instrs->data;
		printf("  ");
		Stack_Instr_print(s);
		printf("\n");
		instrs = instrs->next;
	}
	printf("}\n");
	return;
}

接着类似于类型检查的递归下降,进一步封装栈的上层操作,如生成程序、语句、表达式等。

////////////////////////////////
// decs
List_t gen_decs(List_t decs)
{
	List_t ids = 0;
	while (decs){
		Dec_t d = (Dec_t)(decs->data);
		ids = List_new(d->id, ids);
		decs = decs->next;
	}
	return ids;
}

////////////////////////////////////////
// exp
void gen_exp(Exp_t exp)
{
	switch (exp->kind){
	case EXP_INT:{
					 Exp_Int p = (Exp_Int)exp;
					 emit(Stack_Instr_Push_new(p->n));
					 return;
	}
	case EXP_TRUE:{
					  emit(Stack_Instr_Push_new(1));
					  return;
	}
	case EXP_FALSE:{
					   emit(Stack_Instr_Push_new(0));
					   return;
	}
	case EXP_ID:{
					Exp_Id p = (Exp_Id)exp;
					emit(Stack_Instr_Load_new(p->id));
					return;
	}
	case EXP_ADD:{
					 Exp_Add p = (Exp_Add)exp;
					 gen_exp(p->left);
					 gen_exp(p->right);
					 emit(Stack_Instr_Add_new());
					 return;
	}
	case EXP_MINUS:{
					 Exp_Minus p = (Exp_Minus)exp;
					 gen_exp(p->left);
					 gen_exp(p->right);
					 emit(Stack_Instr_Minus_new());
					 return;
	}
	case EXP_TIMES:{
					  Exp_Times p = (Exp_Times)exp;
					  gen_exp(p->left);
					  gen_exp(p->right);
					  emit(Stack_Instr_Times_new());
					  return;
	}
	case EXP_DIVIDE:{
					  Exp_Divide p = (Exp_Divide)exp;
					  gen_exp(p->left);
					  gen_exp(p->right);
					  emit(Stack_Instr_Divide_new());
					  return;
	}
	case EXP_AND:{
					 Exp_And p = (Exp_And)exp;
					 gen_exp(p->left);
					 gen_exp(p->right);
					 emit(Stack_Instr_And_new());
					 return;
	}
	case EXP_OR:{
					Exp_Or p = (Exp_Or)exp;
					gen_exp(p->left);
					gen_exp(p->right);
					emit(Stack_Instr_Or_new());
					return;
	}
	default:
		return;
	}
}

////////////////////////////////////////
// stms
void gen_stm(Stm_t s)
{
	switch (s->kind){
	case STM_ASSIGN:{
						Stm_Assign p = (Stm_Assign)s;
						gen_exp(p->exp);
						emit(Stack_Instr_Store_new(p->id));
						break;
	}
	case STM_PRINTI:{
						Stm_Printi p = (Stm_Printi)s;
						gen_exp(p->exp);
						emit(Stack_Instr_Printi_new());
						break;
	}
	case STM_PRINTB:{
						Stm_Printb p = (Stm_Printb)s;
						gen_exp(p->exp);
						emit(Stack_Instr_Printb_new());
						break;
	}
	default:
		break;
	}
}

void gen_stms(List_t stms)
{
	while (stms){
		gen_stm((Stm_t)(stms->data));
		stms = stms->next;
	}
	return;
}

/////////////////////////////////////////
// prog
Stack_Prog_t Gen_stack(Prog_t prog)
{
	List_t ids = gen_decs(prog->decs);
	instrs = 0;
	gen_stms(prog->stms);
	return Stack_Prog_new(List_rev(ids)
		, List_rev(instrs));
}

之后遍历栈操作,生成对应的x86汇编代码并存储到temp.txt中。

//////////////////////////////////////////
// decs
static void genx86_ids(List_t ids)
{
	fprintf(fp,"\t.data\n",
		"int_format:\n",
		"\t.string \"%%d\\n\"\n",
		"trues:\n",
		"\t.string \"true\\n\"\n",
		"falses:\n",
		"\t.string \"false\\n\"\n");
	while (ids){
		char *id = (char *)ids->data;
		fprintf(fp, "%s:\n\t.int 0\n", id);
		ids = ids->next;
	}
	return;
}

///////////////////////////////////////////
// instrs
static void genx86_instr(Stack_Instr_t s)
{
	switch (s->kind){
	case STACK_INSTR_PUSH:{
							  Stack_Instr_Push p = (Stack_Instr_Push)s;
							  fprintf(fp, "\tpushl\t$%d", p->n);
							  break;
	}
	case STACK_INSTR_LOAD:{
							  Stack_Instr_Load p = (Stack_Instr_Load)s;
							  fprintf(fp, "\tmovl\t%s, %%eax", p->x);
							  break;
	}
	case STACK_INSTR_STORE:{
							   Stack_Instr_Store p = (Stack_Instr_Store)s;
							   fprintf(fp, "store %s", p->x);
							   break;
	}
	case STACK_INSTR_ADD:{
							 fprintf(fp, "add");
							 break;
	}
	case STACK_INSTR_MINUS:{
							 fprintf(fp, "sub");
							 break;
	}
	case STACK_INSTR_TIMES:{
							   fprintf(fp, "times");
							   break;
	}
	case STACK_INSTR_DIV:{
							 fprintf(fp, "div");
							 break;
	}
	case STACK_INSTR_PRINTI:{
								fprintf(fp, "\tcall\tprinti\n"
									"\taddl\t$4, %%esp");
								break;
	}
	case STACK_INSTR_PRINTB:{
								fprintf(fp, "\tcall\tprintb\n"
									"\taddl\t$4, %%esp");
								break;
	}
	default:
		break;
	}
}

void genx86_instrs(List_t l)
{
	fprintf(fp, "\n\n\t.text\n"
		"\t.globl main\n"
		"main:\n"
		"\tpushl\t%%ebp\n"
		"\tmovl\t%%esp, %%ebp\n");

	while (l){
		genx86_instr((Stack_Instr_t)(l->data));
		fprintf(fp, "\n");
		l = l->next;
	}
	fprintf(fp, "\tleave\n"
		"\tret\n");
	fprintf(fp, "\t.globl printi\n"
		"printi:\n"
		"\tpush\t%%ebp\n"
		"\tmovl\t%%esp, %%ebp\n"
		"\tpushl\t8(%%ebp)\n"
		"\tpushl\t$int_format\n"
		"\tcall\tprintf\n"
		"\tleave\n"
		"\tret\n"
		"\t.globl printb\n"
		"printb:\n"
		"\tpush\t%%ebp\n"
		"\tmovl\t%%esp, %%ebp\n"
		"\txorl\t%%eax, %%eax\n"
		"\tcmpl\t8(%%ebp), %%eax\n"
		"\tje\t.L_f\n"
		"\tpushl\t$trues\n"
		"\tjmp\t.L_e\n"
		".L_f:\n"
		"\tpushl\t$falses\n"
		".L_e:\n"
		"\tcall\tputs\n"
		"\tleave\n"
		"\tret\n");
	return;
}

///////////////////////////////////////////
// prog
void Stack2x86_print(Stack_Prog_t p)
{
	fopen_s(&fp,"temp.txt", "w+");
	if (fp == 0){
		printf("error in open file\n");
		return;
	}

	genx86_ids(p->ids);
	genx86_instrs(p->instrs);

	fclose(fp);
	fp = 0;
	return;
}

最后定义主函数main并观察实验结果:

int main(int argc, char **argv)
{
	printf("lex and parse starting...\n");
	yyparse();
	printf("lex and parse finished\n");

	printf("print the AST starting...\n");
	Prog_print(tree);
	printf("print the AST finished\n");

	printf("semantic analysis starting...\n");
	Semant_check(tree);
	printf("semantic analysis finished\n");

	printf("stack machine code generation starting...\n");
	Stack_Prog_t stack = Gen_stack(tree);
	printf("stack machine code generation finished\n");

	printf("stack machine code output starting...\n");
	Stack_Prog_print(stack);
	printf("stack machine code output finished\n");

	printf("x86 code generation starting...\n");
	Stack2x86_print(stack);
	printf("x86 code generation finished (writing to file \"temp.txt\")\n");
	//system("cat temp.s");

	while (1);//暂停屏幕
	return 0;
}
test输入代码:
{
  int a;
  bool b;

  printi (88);
  printb(true);
}
控制台输出:
lex and parse starting...
{  int a;  bool b;  printi (88);  printb(true);}
lex and parse finished
print the AST starting...
{
  int a;
  bool b;

  printi(88);
  printb(true);
}
print the AST finished
semantic analysis starting...
semantic analysis finished
stack machine code generation starting...
stack machine code generation finished
stack machine code output starting...
{
  .int a
  .int b

  push 88
  printi
  push 1
  printb
}
stack machine code output finished
x86 code generation starting...
x86 code generation finished (writing to file "temp.txt")
temp.txt内容:
	.data
a:
	.int 0
b:
	.int 0


	.text
	.globl main
main:
	pushl	%ebp
	movl	%esp, %ebp
	pushl	$88
	call	printi
	addl	$4, %esp
	pushl	$1
	call	printb
	addl	$4, %esp
	leave
	ret
	.globl printi
printi:
	push	%ebp
	movl	%esp, %ebp
	pushl	8(%ebp)
	pushl	$int_format
	call	printf
	leave
	ret
	.globl printb
printb:
	push	%ebp
	movl	%esp, %ebp
	xorl	%eax, %eax
	cmpl	8(%ebp), %eax
	je	.L_f
	pushl	$trues
	jmp	.L_e
.L_f:
	pushl	$falses
.L_e:
	call	puts
	leave
	ret

可以看到成功转换成了x86汇编代码,至此语义分析器部分结束。

总结与展望

在学习编译原理的过程中会遇到很多抽象的概念如自动机、闭包等,但是只要根据具体的实例仔细分析,就不难掌握他们的由来以及相互之间的关联。而这也是我作为一个非科班学生学习编译原理的心得所在。

比如语法分析为例,人们自然想到的是递归下降即LL(0),但是它存在一些弊端,所以逐个引出了之后的语法分析技术,也就是说计算机作为一门逻辑性很强的学科,而知识点与知识点之间的逻辑关系更是如此,而非凭空产生的。

虽然很多时候需要技巧帮助,但是技巧也是逻辑知识积累到一定程度上的体现。正如编译原理这门课程的诞生一样,为了使机器理解我们,而机器不是凭空产生,正是我们所制造的。

我学习编译原理的目的在文中多次提及,是为了明白程序运行的机理,同时通过实践巩固所学的编程语言以及数据结构,学以致用。

但同时在学习的过程中我发现编译原理不仅仅用于编译器的编写,还可以在其他领域,比如NLP再比如智能控制的专家系统中有所应用。

完整工程项目托管在github,而至此,编译原理的学习也告一段落了,至于更深入的理论以后有机会再去学习吧。

——黑帅

2020.7.10

By gzj7108

人生只有一条路,就是勇往直前。

发表评论

邮箱地址不会被公开。 必填项已用*标注