使用状态机（有穷自动机）实现 printf效能

使用状态机（有穷自动机）实现 printf功能
有穷自动机是编译原理讲的，在词法分析中使用比较广泛。因为它仅仅能分析正则规则的语言，因此使用起来比较简单。现在我们使用它来实现printf

printf 的原理是

输入：

一个格式串

不定个数的参数

在控制台上输出。

我们这里实现这个函数不在控制台输出，而是得到一个串，然后这个串可以任意的处理。

char* myprint(char* format,...)

从状态0开始（初始状态）

--->状态0

当遇到%，--->状态0--->状态1

这个时候处于接收后续的myprint的参数类型的状态

当接收到

...

我们就认为它对应的参数为字符串类型，整型...

那么这个时候我们做出对应的动作，strcat 或者从数字转化为字符串使用 itoa,然后追加到输出缓冲区后面

如果在状态 0 接收到非 % 那么直接追加到输出缓冲区

如果在状态 1 接收到非 (s d ...) 这些状态，那么直接将 % 追加到输出缓冲区

使用状态机（有穷自动机）实现 printf效能

我们使用C来实现。

#include <malloc.h>
#include <stdio.h>
#include <string.h>

//MACRO: REALLOC_IF_LESS
//desc:如果当前读取的长度 len>=alloc_len-1
//str - 当前输出串
//pos - 当前读取位置
//alloc_len 分配的长度
//detail:
//使用alloc_len = pos+16 没有什么根据，用处就是减少重新分配的次数
//变量 realloc_str 为重新分配空间的字符串

#define REALLOC_IF_LESS(str,pos,alloc_len) if(pos>=alloc_len-1) { \
	char*  realloc_str = malloc(alloc_len = pos+16);\
	memset(realloc_str,0,alloc_len);\
	strcpy(realloc_str,str);\
	free(str);\
	str = realloc_str;}

//FUNCTION:myprint
//input:
//	format - 格式串,类似 系统函数printf 现在接受 %s %d
//	...  不定长串
//output:
//	输出把%s %d 替换为指定参数后的最终串
//使用状态机的原理
//开始状态为 0  ,当接收到% 则进入1
//在状态1 的时候,接收到 s d ... 则接受，可以处理，然后状态转为0
//
char* myprint(char* format,...)
{
	int alloc_len = strlen(format)+1;
	char* o = malloc(alloc_len);
	
	int state = 0;
	int dest_pos=0;
	char* old_format = format;
	unsigned long ** addr = (unsigned long **) &format;
	addr+=1;
	memset(o,0,alloc_len);
	while(1)
	{
		char c = *format++;

		switch(state)
		{
		case 0:
			{
				//状态进入 1
				if(c == '%')
				{
					state = 1;
				}
				else //状态还是 0 ,把串原封不动的追加
				{
					REALLOC_IF_LESS(o,dest_pos,alloc_len);
					o[dest_pos++] = c;
				}
				break;
			}
		case 1:
			{
				//接收到 s ,则可以处理了
				if(c == 's')
				{//TODO:去掉%s然后计算参数长度
					dest_pos+=strlen((char*)*addr);
					REALLOC_IF_LESS(o,dest_pos,alloc_len);
					strcat(o,(char*)*addr);

					addr+=1;
					state = 0;
				}
				else if(c=='d') //接收到 d ,则可以处理了
				{
					char buf[16]={0};
					dest_pos+=strlen(itoa((int)*addr,buf,10));

					REALLOC_IF_LESS(o,dest_pos,alloc_len);
					strcat(o,buf);
					addr+=1;
					state = 0;
				}
				else //没有接收到可接受的字符,状态转为 0 
				{
					o[dest_pos++] = '%';
					state = 0;
				}
				break;
			}
		}
		if(c==0) break;
	}
	return o;
}
main()
{
	char* name="bkdrong";
	char* addr="北京";
	int number= 10520;
	char* x = myprint("myname=%s addr=%s number=%d\r\n",name,addr,number);
	printf("%s",x);
	free(x);
}

使用状态机（有穷自动机）实现 printf效能

相关推荐