前几天有个朋友做编译原理课程设计，其中一个题目要求4天内编写一个编译器
当时觉得不可能，但考虑了下是否可能简化结构，做个简单的出来，后来就写了这个东西
这个程序编译过程已经简化，不需要语法树，甚至不需要汇编器，用了3000多行代码
如果语法更简单点，大概确实可以4天内写出来，但无法优化
编译的方法是，在yacc分析文法时生成代码，yacc分析表达式时内部有一个分析栈，文法单元入栈顺序和执行顺序是一样的
比如，2+3*4，这个式子234依次入栈，然后3*4规约，再和2规约，这正是这个式子执行时的顺序
因此可以边分析文法别生成代码，代码使用“双栈”结构，一个用于运算表达式，另一个就是存放局部变量，正常用途
实际上就在一个栈中就可以实现，因为一个函数局部变量的大小是可以确定的
所以，EBP作为栈的基址用于索引，而ESP指向栈顶，用于运算表达式，栈区布局如下
operand operand .... var(-8) var(-4) ebp(+0) ret(+4) arg(+8) arg(+0c) arg(+10)
这样对于一个运算，比如加法，其功能是明确的，就是取栈顶的两个数相加
所以，可以用固定的代码模版来实现，避免分配寄存器和汇编的麻烦
比如处理a+b*c这个表达式，abc三个变量依次入栈，栈顶两个数相乘结果入栈，然后栈顶两个数相加结果入栈
原理就是这样，比一个解释器复杂不了多少，剩下的基本是体力活
C语法有点麻烦，要处理各种类型变量，如果基本类型就是VARIANT，运算都放DLL库里，肯定还要简单许多
我写这个东西，实现了三种基本类型char int float，支持结构体，多维数组，指针，API，if while for switch
函数指针单独处理，有两类stdproc,cproc，分别是STDCALL CDECL调用方式
但函数调用不检查类型，一方面是我想不出一个幽雅简洁的方法处理自动类型转化，
另一面如果检查类型，调用API就要先声明，比较麻烦
测试代码：
#import "user32.dll"
#import "kernel32.dll"
int ss[200000];
int main()
{
char msg[100];
int t1,t2,n1,n2,n3,fg;
t1=GetTickCount();
n1=12;fg=1;
ss[0]=2; ss[1]=3; ss[2]=5; ss[3]=7; ss[4]=11; n3=4;
while (n1<=2000000)
{
for (n2=0;n2<=n3;n2++)
{
if (n1<ss[n2]*ss[n2]) break;
if (n1 % ss[n2]==0) {fg=0;break;}
else fg=1;
}
if (fg==1) {n3++;ss[n3]=n1;fg=0;}
n1++;
}
t2=GetTickCount();
((cproc)wsprintfA)(msg,"time=%d\r\n",t2-t1);
MessageBoxA(0,msg,"Dynasty",0);
int i;
for(i=0;i<10;i++)
{
((cproc)wsprintfA)(msg,"%d\r\n",ss[i]);
MessageBoxA(0,msg,"Dynasty",0);
}
}
用kflnig的计算素数代码改的，API默认为stdcall，wsprintfA要转化成cproc调用，计算的结果，比VC慢了2.5倍
另一个例子，是生成窗口的hello world
#import "user32.dll"
#import "kernel32.dll"
#import "gdi32.dll"
struct POINT
{
int x;
int y;
};
struct MSG
{
int hwnd;
int message;
int wParam;
int lParam;
int time;
POINT pt;
};
struct WNDCLASSEXA
{
int cbSize;
int style;
stdproc lpfnWndProc;
int cbClsExtra;
int cbWndExtra;
int hInstance;
int hIcon;
int hCursor;
int hbrBackground;
char*lpszMenuName;
char*lpszClassName;
int hIconSm;
};
struct RECT
{
int left;
int top;
int right;
int bottom;
};
struct PAINTSTRUCT
{
int hdc;
int fErase;
RECT rcPaint;
int fRestore;
int fIncUpdate;
char rgbReserved[32];
};
int WndProc(int hWnd,int message,int wParam,int lParam);
int MyRegisterClass(int hInstance)
{
WNDCLASSEXA wcex;
wcex.cbSize=48;
wcex.style=3;//CS_HREDRAW|CS_VREDRAW;
wcex.lpfnWndProc=WndProc;
wcex.cbClsExtra=0;
wcex.cbWndExtra=0;
wcex.hInstance=hInstance;
wcex.hIcon=0;
wcex.hCursor=LoadCursorA(0,32512);//IDC_ARROW
wcex.hbrBackground=6;//(HBRUSH)(COLOR_WINDOW+1);
wcex.lpszMenuName=(char*)0;
wcex.lpszClassName="Class_Name_Dynasty_HelloWorld";
wcex.hIconSm=0;
return RegisterClassExA(&wcex);
}
int hInst;
int InitInstance(int hInstance,int nCmdShow)
{
int hWnd;
hInst=hInstance;
hWnd=CreateWindowExA(0,
"Class_Name_Dynasty_HelloWorld",
"HelloWorld",
0xCF0000,//WS_OVERLAPPEDWINDOW,
0x80000000,//CW_USEDEFAULT,
0,
0x80000000,//CW_USEDEFAULT,
0,0,0,hInstance,0);
if(!hWnd)return 0;
ShowWindow(hWnd,nCmdShow);
UpdateWindow(hWnd);
return 1;
}
int WinMain(int hInstance,int hPrevInstance,char*lpCmdLine,int nCmdShow)
{
MSG msg;
MyRegisterClass(hInstance);
if(!InitInstance(hInstance,nCmdShow))return 0;
while(GetMessageA(&msg,0,0,0))
{
TranslateMessage(&msg);
DispatchMessageA(&msg);
}
return msg.wParam;
}
int main()
{
return ExitProcess(WinMain(GetModuleHandleA(0),0,GetCommandLineA(),1));//SW_SHOWNORMAL
}
int LOWORD(int dword)
{
int h1,h2,h3,h4;
h4=*((char*)&dword+0);
h3=*((char*)&dword+1);
h2=*((char*)&dword+2);
h1=*((char*)&dword+3);
return h3*0xFF+h4;
}
int HIWORD(int dword)
{
int h1,h2,h3,h4;
h4=*((char*)&dword+0);
h3=*((char*)&dword+1);
h2=*((char*)&dword+2);
h1=*((char*)&dword+3);
return h1*0xFF+h2;
}
int WndProc(int hWnd,int message,int wParam,int lParam)
{
int wmId,wmEvent;
PAINTSTRUCT ps;
int hdc;
switch(message)
{
case 0x0111://WM_COMMAND
wmId=LOWORD(wParam);
wmEvent=HIWORD(wParam);
switch(wmId)
{
case 105://IDM_EXIT:
DestroyWindow(hWnd);
break;
default:
return DefWindowProcA(hWnd,message,wParam,lParam);
}
break;
case 0x000F://WM_PAINT
hdc=BeginPaint(hWnd,&ps);
RECT rt;
GetClientRect(hWnd,&rt);
rt.top=rt.top+30;
DrawTextA(hdc,"Hello World",11,&rt,1);//DT_CENTER
rt.top=rt.top+30;
DrawTextA(hdc,"build by DynastyCompiler",24,&rt,1);//DT_CENTER
EndPaint(hWnd, &ps);
break;
case 0x0002://WM_DESTROY
PostQuitMessage(0);
break;
default:
return DefWindowProcA(hWnd,message,wParam,lParam);
}
return 0;
}
这种结构写出来的东西，用于编译的话，代码太烂，估计没多少价值
不过，这个可以用来实现高速脚本，不生成PE，直接编译在内存中运行
虽然比VC慢，但毕竟是编译级别的速度，解释执行据说最好的优化也要慢10倍
另外，也许可以用来做壳，改进下，生成LIB，就可以和VC联合编译
在编译器级别“编织”代码，可以编出的花纹就肯定漂亮得多，只是这样估计要生成语法树
原代码可以直接编译，但如果要修改yacc.y需要bison2.1，其他版本也行，但必须是支持%glr-parser之后的版本
下载bison后要在VC6 Project Settings里设置yacc.y的custom build中调用bison的路径才能编译
bison2.1下载地址和其他一些参考资料：
http://gnuwin32.sourceforge.net/packages/bison.htm
bison2.1官方下载
http://docs.huihoo.com/vm/tut_script/tut_script0.htm
实现一个脚本引擎
http://wiki.hit.edu.cn/index.php/Lex%E5%92%8Cyacc%E5%B7%A5%E5%85%B7%E4%BB%8B%E7%BB%8D
Lex和yacc工具介绍
http://blog.csdn.net/sirouni2003/archive/2005/06/22/400672.aspx
20050620 GNU Bison 中文手册翻译完成
http://blog.csdn.net/sirouni2003/archive/2006/02/01/590661.aspx
20060121 GNU Bison 2.1中文手册翻译完成
https://www6.software.ibm.com/developerworks/cn/education/aix/au-lexyacc/index.html
IBM developerWorks:使用 yacc 和 lex 编写文本分析器
http://www.ibm.com/developerworks/cn/linux/sdk/lex/index.html
IBM developerWorks:Yacc 与 Lex 快速入门
http://www.51delphi.com/wz/8.html
用YACC/LEX 设计计算机语言:BASIC
http://tag.csdn.net/author/a0786de3-9b05-437a-848a-1b0611916677/pandaxcl/lex和yacc/1.html
Lex和Yacc从入门到精通(1)－－环境配置篇
http://blog.csdn.net/dawndu/archive/2006/04/13/662260.aspx
递归下降纯解释器编写的困惑 (关于纯解释中的分支，循环)
http://www.cublog.cn/u/13392/showart_203707.html#13.%20Caveats%20and%20Bugs
Lex-词法分析器生成器(M.E.Lesk,E.Schmidt著,中文翻译
http://www.ibm.com/developerworks/cn/linux/game/sdl/pirates-4/index.html
SDL 用法，第 4 部分: lex 和 yacc
构建用于脚本和 GUI 设计的语法分析器
http://www.supcode.com/Article/readcourse/bianchengwendang/qitayuyan/weiflextigongduoshuruhuanchongMultipleinputbuffers.shtml
为flex提供多输入缓冲！Multiple input buffers
使用 Flex 和 Bison 更好地进行错误处理
http://www.ibm.com/developerworks/cn/linux/l-flexbison.html
http://www.gnu.org/software/flex/manual/html_mono/flex.html
flex munual *** english
http://www.linuxforum.net/forum/files/465398-zh_CN_flex.txt
flex 手册
http://www.blogcn.com/User13/xjoywag/index.html?tp=Lex%20&%20Yacc
正则表达式使用详解 [转]
从lex&yacc说到编译器 [转]
Yacc - 一个生成 LALR(1) 文法分析器的程序 [转]
编译器（解释器）编写指南-编写编译器（解释器）的工具-LEX [转]
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
上传的附件：
