compiler.c

笔者自创的9个汇编终结符实现普通+,-,*,/,I/O的实用编译器(产生80486目标码)

/*	SLR(1)文法分析器,词限长.yacc冲突:先移入,依FOLLOW集,归约
	文rule(尾回车),原子词,首符大写,为非终结符,否则,为终结符
	规则,非终结/终结符,用isspace隔,相同邻左部,展成各右部R条
	左递归,定义char域的加减,符号大于或无条件转移,快I/O,注释
	冠ml615,初0数组,实莅标号L(hi标号数)

.model	small
.code
id_grp	db	ID_GRP_SZ值	dup(0)
L:

	尾
mov	ah,76
int	33
end	L

SLR EXE ;
SLR SLR EXE ;
EXE ADD
EXE IF
EXE GO
EXE GOAL
EXE GET
EXE PUT
EXE REM
ADD iD = iD + dEC
IF if JG then SLR
JG iD > iD
GO go _iD
GOAL _iD
GET + iD
PUT > iD
REM ! iD BY
BY iD BY
BY

右递归(耗栈)
SLR EXE ; R_nt
R_nt SLR
R_nt

	[文hi],单词,用isspace符隔

	iD(_iD)类,为(_)[a..z][0..9a..z]*,非if,go,then
	dEC类,为[+|-][0..9][0..9]*
    词器eat,读hi的类,返iD,_iD,dEC

	输入[0..9]/其他符,显[0..9]/asc模10
! copy make all ;
low = low + +47 ;
high = low + 11 ;
ten = ten + 10 ;
+ v ;
if v > low then
	if high > v then
! asc ;
		> v ;
		go _ok ; ; ;
_chk ;
if ten > v then
	go _v ; ;
v = v + -10 ;
go _chk ;
_v ;
v = v + 48 ;
> v ;
_ok ;

	[文tr],目标机某些非终结符替四元式为汇编码,大写符,EOF,隔替者
	_2,偏移2的立即数
	_:,偏移3的标号
	__1,偏移1,间接寻址id_grp
	__:,转到偏移3的标号
ADD
mov al,__1
add al,_2
mov __3,al
JG
mov al,__1
cmp al,__2
jle __:
GO
jmp __:
GOAL
_:
GET
xor ah,ah
int 16h
mov __3,al
PUT
mov al,__3
int 41

生a.asm
.model	small
.code
id_grp	db	4	dup(0)
L:

mov al,id_grp[0]
add al,47
mov id_grp[0],al

mov al,id_grp[0]
add al,11
mov id_grp[1],al

mov al,id_grp[2]
add al,10
mov id_grp[2],al

xor ah,ah
int 16h
mov id_grp[3],al

mov al,id_grp[3]
cmp al,id_grp[0]
jle _chk

mov al,id_grp[1]
cmp al,id_grp[3]
jle _chk

mov al,id_grp[3]
int 41
jmp _ok

_chk:

mov al,id_grp[2]
cmp al,id_grp[3]
jle L3

jmp _v

L3:
mov al,id_grp[3]
add al,-10
mov id_grp[3],al

jmp _chk

_v:

mov al,id_grp[3]
add al,48
mov id_grp[3],al

mov al,id_grp[3]
int 41

_ok:
mov	ah,76
int	33
end	L

冲测
移入-归约
E E - T
E T
T F
F ( E )
F i
T F - T
i - ( i - i )
归约-归约
G E = E
G f
E T
E E + T
T f
T T * f
f

测超前
S E = E
S f
E T
E E + T
T f
T T * f

约数基块测
+ x ;
+ y ;
_m ;
r = x + 5 ;
if r > r then
	go _ee ; ;
x = y + 0 ;
y = r + 0 ;
go _m ;
_ee ;
> y ;*/

#include <math.h>
#include <time.h>
#include <conio.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned char BYTE;
typedef unsigned short USHORT;
typedef unsigned __int64 ULONGLONG;

#define R_nt 1

#define	RULE_tot	19+R_nt	//规则数
#define	NT_GRP_SZ	11+R_nt	//非终结符SLR,EXE,ADD,IF,GO,GOAL,GET,PUT,REM,JG,BY数
#define	T_GRP_SZ	11	//终结符;,iD,=,+,dEC,if,then,>,go,_iD,!数
#define	ATOM_SZ_	4+1	//词,能占字节数;零

#define	ID_GRP_SZ	4	//标识符low,high,ten,v数
#define	TO_GRP_SZ	3+3	//标号_chk,_v,_ok数+必设内标if语句数
#define	G4_AF_SZ	17	//hi,非注释句数
#define	Nest_IF		2	//嵌套数

FILE *LP_F;

char atom[ATOM_SZ_];

#define	ITEM_ATOMS_	6+1	//ADD iD = iD + dEC所占词数+DOT
#define	ITEM_SZ	(1+RULE_tot)*ITEM_ATOMS_//<S>

typedef struct{
char flg;
char loc;
}FLG_LOC;

struct{
FLG_LOC	dot_nt_t[ITEM_ATOMS_];
char dot_nt_t_cnt;
}item_grp[ITEM_SZ];

char item_grp_cnt=1;//用户

typedef	struct{
char t_grp[T_GRP_SZ];
char t_grp_cnt;
}FORE;

typedef struct{
char item[ITEM_SZ];
FORE fore[ITEM_SZ];//超前
char item_cnt;
struct{
FLG_LOC	by;
char to;
}out[ITEM_SZ];
char out_cnt;
FLG_LOC	reduce[NT_GRP_SZ];//项目号,产生式首nt_grp位
char reduce_cnt;
FLG_LOC	shift[T_GRP_SZ];//新态,移入的t_grp
char shift_cnt;
char lalr;//-1:父号
}ITEM_SET_GRP;

#define NOM	sizeof(ITEM_SET_GRP)*ITEM_SZ/sizeof(float)

#define Pnp		8*4
#define e8_th	(float)(1/2980.957987)
#define p4_32	1.8446744073709552e+019

union{
ITEM_SET_GRP item_set_grp[ITEM_SZ];
float f[NOM];
}U;

char item_set_grp_cnt=0;

char t_grp[2+T_GRP_SZ][ATOM_SZ_]={"#","@"};
char t_grp_cnt=2;//用户

struct{
char atom[ATOM_SZ_];
char first[T_GRP_SZ];
char first_cnt;
char follow[T_GRP_SZ];
char follow_cnt;
}nt_grp[1+NT_GRP_SZ]={"<S>"};

char nt_grp_cnt=1;//用户

char if_grp[Nest_IF];
char if_grp_cnt=0;

char ate,paw,rem;
char dew=0;
FLG_LOC stk[ITEM_SZ]={1,0};

#define	DOT	0x77
#define	NT	0x78
#define	T	0x79

struct{
char atom[ATOM_SZ_];
char val;
}id_grp[ID_GRP_SZ],to_grp[TO_GRP_SZ];

char id_grp_cnt=0;
char to_grp_cnt=0;

struct G4_AF{
char op;
char a0;
char a1;
char aim;
char _if;//to_grp位,-1初值
char entry;//基本块头
}g4_af[G4_AF_SZ];
char g4_af_cnt=0;

typedef union{
char *p;
float f;
size_t u;
BYTE B[4];
USHORT s[2];
}O4;

union{
O4 u[2];
double d;
ULONGLONG U;
}op;

O4 sh0,sh1;

void add(aim,sz,loc)char *aim,*sz,loc;{//升序添相异
	for(ate=0;ate!=*sz;aim++,ate++){
		if(*aim==loc){
			ate=0;
			return;
		}

		if(*aim>loc)
			break;
	}

	memmove(aim+1,aim,*sz-ate);
	*aim=loc;
	*sz+=1;
	ate=1;
}

void fore_add(parent,parent_item,first)char parent,parent_item,first;{
char loc0,loc1;
	if(first!=item_grp[parent_item].dot_nt_t_cnt)
		if(NT==item_grp[parent_item].dot_nt_t[first].flg){
			loc0=item_grp[parent_item].dot_nt_t[first].loc;
			op.u[0].p=0;

			for(loc1=0;loc1!=nt_grp[loc0].first_cnt;loc1++){//各first
				add(U.item_set_grp[item_set_grp_cnt].fore[sh0.u].t_grp,&U.item_set_grp[item_set_grp_cnt].fore[sh0.u].t_grp_cnt,nt_grp[loc0].first[loc1]);
				if(ate)
					op.u[0].p+=2;

				if(1==nt_grp[loc0].first[loc1])//单eps
					op.u[0].p++;
			}

			if(!((char)op.u[0].p & 1)){//未透
				ate=op.u[0].p>0;
				return;
			}
		}else
			if(item_grp[parent_item].dot_nt_t[first].loc){//非#
				add(U.item_set_grp[item_set_grp_cnt].fore[sh0.u].t_grp,&U.item_set_grp[item_set_grp_cnt].fore[sh0.u].t_grp_cnt,item_grp[parent_item].dot_nt_t[first].loc);
				return;
			}

	for(loc1=loc0=0;loc0!=U.item_set_grp[item_set_grp_cnt].fore[parent].t_grp_cnt;loc0++){
		add(U.item_set_grp[item_set_grp_cnt].fore[sh0.u].t_grp,&U.item_set_grp[item_set_grp_cnt].fore[sh0.u].t_grp_cnt,U.item_set_grp[item_set_grp_cnt].fore[parent].t_grp[loc0]);
		if(ate)
			loc1=1;
	}

	ate=loc1;
}

void item_set_add(left,parent,parent_item,first)char left,parent,parent_item,first;{//目前
	for(sh0.u=0;sh0.u!=(size_t)U.item_set_grp[item_set_grp_cnt].item_cnt;sh0.u++){//升
		if(U.item_set_grp[item_set_grp_cnt].item[sh0.u]==left){
			fore_add(parent,parent_item,first);
			return;
		}

		if(U.item_set_grp[item_set_grp_cnt].item[sh0.u]>left)
			break;
	}

	memmove(&U.item_set_grp[item_set_grp_cnt].item[sh0.u+1],\
	&U.item_set_grp[item_set_grp_cnt].item[sh0.u],\
	U.item_set_grp[item_set_grp_cnt].item_cnt-sh0.u);

	U.item_set_grp[item_set_grp_cnt].item[sh0.u]=left;//序
	fore_add(parent,parent_item,first);

	U.item_set_grp[item_set_grp_cnt].item_cnt++;
}

void closure(){//项目集的X->```a.Y```,让Y->.(b|Z)入项目集
char old,cnt,i_LOC,i_loc,nt,usr,fat;
	do
		for(old=U.item_set_grp[item_set_grp_cnt].item_cnt,fat=cnt=0;cnt!=U.item_set_grp[item_set_grp_cnt].item_cnt;cnt++)
			for(i_LOC=U.item_set_grp[item_set_grp_cnt].item[cnt],i_loc=1;i_loc!=item_grp[i_LOC].dot_nt_t_cnt;i_loc++)
				if(DOT==item_grp[i_LOC].dot_nt_t[i_loc].flg &&\
					i_loc!=item_grp[i_LOC].dot_nt_t_cnt-1 &&\
					NT==item_grp[i_LOC].dot_nt_t[i_loc+1].flg){

					nt=item_grp[i_LOC].dot_nt_t[i_loc+1].loc;

					for(usr=3;usr!=item_grp_cnt;usr++)//跳<S>
						if(item_grp[usr].dot_nt_t[0].loc==nt &&\
							DOT==item_grp[usr].dot_nt_t[1].flg){

							item_set_add(usr,cnt,i_LOC,i_loc+2);//加Y->.(b|Z)
							if(ate)
								fat=1;
						}

					break;//单
				}
	while(old<U.item_set_grp[item_set_grp_cnt].item_cnt||fat);
}

//#define LR1
void arrow(){
char a_loc=0,i_LOC,i_loc;
	for(;a_loc!=U.item_set_grp[paw].item_cnt;a_loc++)
		for(i_LOC=U.item_set_grp[paw].item[a_loc],i_loc=1;i_loc!=item_grp[i_LOC].dot_nt_t_cnt;i_loc++)//从DOT
			if(DOT==item_grp[i_LOC].dot_nt_t[i_loc].flg &&\
				i_loc!=item_grp[i_LOC].dot_nt_t_cnt-1 &&\
				!memcmp(&item_grp[i_LOC].dot_nt_t[i_loc+1],&stk[1],sizeof(FLG_LOC))){

				ate=U.item_set_grp[item_set_grp_cnt].item_cnt;
				U.item_set_grp[item_set_grp_cnt].item[ate]=i_LOC+1;//Y.

				memmove(U.item_set_grp[item_set_grp_cnt].fore[ate].t_grp,\
				U.item_set_grp[paw].fore[a_loc].t_grp,\
				U.item_set_grp[paw].fore[a_loc].t_grp_cnt);

				U.item_set_grp[item_set_grp_cnt].fore[ate].t_grp_cnt=\
				U.item_set_grp[paw].fore[a_loc].t_grp_cnt;

				U.item_set_grp[item_set_grp_cnt].item_cnt++;
				break;//单
			}

	if(U.item_set_grp[item_set_grp_cnt].item_cnt){
		closure();i_loc=-1;
		for(a_loc=0;a_loc!=item_set_grp_cnt;a_loc++)//历史
			if(U.item_set_grp[a_loc].item_cnt==\
				U.item_set_grp[item_set_grp_cnt].item_cnt &&\
				!memcmp(U.item_set_grp[a_loc].item,\
				U.item_set_grp[item_set_grp_cnt].item,\
				U.item_set_grp[a_loc].item_cnt)){//核同

#ifdef LR1
				for(sh0.u=0;sh0.u!=U.item_set_grp[a_loc].item_cnt;sh0.u++)
					if(U.item_set_grp[a_loc].fore[sh0.u].t_grp_cnt==\
						U.item_set_grp[item_set_grp_cnt].fore[sh0.u].t_grp_cnt &&\
						!memcmp(U.item_set_grp[a_loc].fore[sh0.u].t_grp,\
						U.item_set_grp[item_set_grp_cnt].fore[sh0.u].t_grp,\
						U.item_set_grp[a_loc].fore[sh0.u].t_grp_cnt))//超同
						break;

				if(sh0.u==U.item_set_grp[a_loc].item_cnt){
					i_loc=a_loc;
					continue;
				}
#endif
				break;
			}

		i_LOC=U.item_set_grp[paw].out_cnt;

		memmove(&U.item_set_grp[paw].out[i_LOC],&stk[1],sizeof(FLG_LOC));
		U.item_set_grp[paw].out[i_LOC].to=a_loc;

		U.item_set_grp[paw].out_cnt++;

		if(a_loc!=item_set_grp_cnt)
			U.item_set_grp[item_set_grp_cnt].item_cnt=0;
		else
			U.item_set_grp[item_set_grp_cnt++].lalr=i_loc;
	}
}

void dot(char n){
memmove(&item_grp[item_grp_cnt],&item_grp[item_grp_cnt-1],sizeof(item_grp[0]));
memmove(&item_grp[item_grp_cnt].dot_nt_t[n-1],&item_grp[item_grp_cnt].dot_nt_t[n],sizeof(FLG_LOC));
item_grp[item_grp_cnt++].dot_nt_t[n].flg=DOT;
}

char eat(char r){
	while(1){
		if(-1==(ate=fgetc(LP_F)))
			return 0;

		if('\n'!=ate)
			break;

		if(!paw&&r)//规则行
			return 0;
	}

	ungetc(ate,LP_F);
	fscanf(LP_F,"%s",atom);

	ate=T;
	if(isupper(atom[0]))
		ate=NT;
	else
		if(paw){//hi
			if('!'==atom[0])
				rem=1;
			else
			if(islower(atom[0])){
				for(r=0;r!=t_grp_cnt;r++)//内字
					if(!strcmp(t_grp[r],atom))
						return -1;

				for(r=0;r!=id_grp_cnt;r++)
					if(!strcmp(id_grp[r].atom,atom))
						break;

				if(r==id_grp_cnt&&!rem)//位,初值0
					strcpy(id_grp[id_grp_cnt++].atom,atom);

				strcpy(atom,"iD");
			}else{
				if('_'==atom[0]){//标号
					for(r=0;r!=to_grp_cnt;r++)
						if(!strcmp(to_grp[r].atom,atom))
							break;

					if(r==to_grp_cnt){//位
						strcpy(to_grp[to_grp_cnt].atom,atom);
						to_grp[to_grp_cnt++].val=-1;//初值-1
					}

					strcpy(atom,"_iD");
				}else{
					r=(char)strtol(atom,&op.u[0].p,10);
					if(atom!=op.u[0].p)//成
						strcpy(atom,"dEC");
				}
			}
		}
	return r;
}

void rule(){
	for(;;){
		eat(rem=item_grp[item_grp_cnt].dot_nt_t_cnt);
		switch(ate){
			case NT:
				for(ate=1;ate!=nt_grp_cnt;ate++)//用户
					if(!strcmp(nt_grp[ate].atom,atom))
						break;

				if(ate==nt_grp_cnt)
					strcpy(nt_grp[nt_grp_cnt++].atom,atom);

				item_grp[item_grp_cnt].dot_nt_t[rem].flg=NT;
				item_grp[item_grp_cnt].dot_nt_t[rem].loc=ate;

				if(!rem){
					item_grp[item_grp_cnt].dot_nt_t[1].flg=DOT;
					item_grp[item_grp_cnt].dot_nt_t_cnt=2;
				}else
					item_grp[item_grp_cnt].dot_nt_t_cnt++;

				break;

			case T:
				for(ate=2;ate!=t_grp_cnt;ate++)//用户
					if(!strcmp(t_grp[ate],atom))
						break;

				if(ate==t_grp_cnt)
					strcpy(t_grp[t_grp_cnt++],atom);

				item_grp[item_grp_cnt].dot_nt_t[rem].flg=T;
				item_grp[item_grp_cnt].dot_nt_t[rem].loc=ate;
				item_grp[item_grp_cnt].dot_nt_t_cnt++;

				break;

			case -1:
				return;

			case '\n':
				rem=item_grp[item_grp_cnt++].dot_nt_t_cnt;
				for(ate=2;ate!=rem;ate++)
					dot(ate);
		}
	}
}

void cp_1st(hd,nt)char hd,nt;{
	paw=nt_grp[hd].first_cnt;
	for(sh1.u=0;sh1.u!=(size_t)nt_grp[nt].first_cnt;sh1.u++)
		if(nt_grp[nt].first[sh1.u]!=1)//非eps
			add(nt_grp[hd].first,&nt_grp[hd].first_cnt,nt_grp[nt].first[sh1.u]);
	ate=nt_grp[hd].first_cnt>paw;
}