前几天有个朋友做编译原理课程设计，其中一个题目要求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下载地址和其他一些参考资料：

b3aK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8X3N6F1N6i4N6A6L8U0x3J5i4K6u0W2M7$3!0#2M7X3y4W2k6X3!0J5k6$3g2Q4x3X3g2F1k6i4c8Q4x3V1k6H3j5h3y4C8j5h3N6W2M7#2)9J5c8X3u0A6M7$3!0F1i4K6u0W2K9s2c8E0
bison2.1官方下载

49dK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8X3c8G2j5%4y4Q4x3X3g2Z5N6h3W2Z5L8$3!0Q4x3X3g2U0L8$3#2Q4x3V1k6$3L8g2)9J5c8Y4c8#2N6q4)9#2k6Y4y4U0M7X3W2H3N6q4)9J5c8Y4c8#2N6q4)9#2k6Y4y4U0M7X3W2H3N6o6m8Q4x3X3g2Z5N6r3@1`.
实现一个脚本引擎

340K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6A6K9$3W2Q4x3X3g2Z5K9i4c8Q4x3X3g2W2k6s2g2Q4x3X3g2U0L8W2)9J5c8X3W2F1k6r3g2^5i4K6u0W2M7r3S2H3i4K6u0r3e0r3g2^5i4K6t1#2c8e0g2Q4x3U0f1&6x3W2)9J5y4e0S2o6P5h3q4U0j5#2)9J5y4f1f1#2i4K6t1#2b7U0N6Q4x3U0g2m8y4g2)9J5y4f1f1#2i4K6t1#2z5o6g2Q4x3U0g2n7y4#2)9J5y4f1f1@1i4K6t1#2b7V1u0Q4x3U0f1^5b7W2)9J5y4f1f1%4i4K6t1#2b7V1u0Q4x3U0f1^5c8l9`.`.
Lex和yacc工具介绍

ae4K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8X3u0D9L8$3N6Q4x3X3g2U0M7$3c8F1i4K6u0W2L8X3g2@1i4K6u0r3M7$3W2J5L8%4g2F1K9e0t1H3x3o6y4Q4x3V1k6S2M7X3y4Z5K9i4k6W2i4K6u0r3x3U0l9H3y4g2)9J5c8U0l9$3i4K6u0r3x3U0u0Q4x3V1j5@1x3o6l9$3y4K6u0Q4x3X3g2S2M7%4m8^5
20050620 GNU Bison 中文手册翻译完成

77aK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8X3u0D9L8$3N6Q4x3X3g2U0M7$3c8F1i4K6u0W2L8X3g2@1i4K6u0r3M7$3W2J5L8%4g2F1K9e0t1H3x3o6y4Q4x3V1k6S2M7X3y4Z5K9i4k6W2i4K6u0r3x3U0l9H3y4W2)9J5c8U0l9J5i4K6u0r3x3o6q4Q4x3V1j5#2z5e0l9$3y4U0q4Q4x3X3g2S2M7%4m8^5
20060121 GNU Bison 2.1中文手册翻译完成

049K9s2c8@1M7s2y4Q4x3@1q4Q4x3V1k6Q4x3V1k6%4N6%4M7$3i4K6u0W2M7$3!0X3N6s2N6S2M7X3g2Q4x3X3g2A6j5X3#2Q4x3X3g2U0L8$3#2Q4x3V1k6V1k6i4k6W2L8r3!0H3k6i4u0%4L8%4u0C8M7#2)9J5c8X3y4F1i4K6u0r3k6h3c8#2j5$3q4@1K9h3!0F1i4K6u0r3j5h3W2^5i4K6u0r3j5i4g2Q4x3X3c8D9k6i4S2&6j5h3y4U0i4K6u0r3K9h3&6V1k6i4S2Q4x3X3g2Z5N6r3#2D9
IBM developerWorks:使用 yacc 和 lex 编写文本分析器

741K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6h3W2T1L8g2)9J5k6h3y4G2L8g2)9J5c8X3c8W2N6X3g2D9L8%4m8W2M7Y4N6G2M7X3E0K6i4K6u0r3j5$3&6Q4x3V1k6D9K9h3&6#2P5q4)9J5c8Y4y4V1K9#2)9J5c8X3I4W2P5q4)9J5c8X3W2F1k6r3g2^5i4K6u0W2K9s2c8E0L8l9`.`.
IBM developerWorks:Yacc 与 Lex 快速入门

756K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6e0f1I4k6r3g2D9M7r3S2A6i4K6u0W2j5$3!0E0i4K6u0r3N6%4A6Q4x3V1j5^5i4K6u0W2K9s2c8E0L8l9`.`.
用YACC/LEX 设计计算机语言:BASIC

0b3K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4c8S2k6#2)9J5k6h3y4K6k6r3&6Q4x3X3g2F1k6i4c8Q4x3V1k6S2N6i4c8Z5L8%4u0Q4x3V1k6S2x3o6M7^5y4X3c8W2x3#2)9J5k6o6W2T1x3o6g2Q4x3X3b7@1x3K6N6S2i4K6u0V1z5o6b7^5j5g2)9J5k6o6q4T1x3o6j5I4x3e0V1I4y4U0j5%4y4#2)9J5c8Y4m8S2L8X3c8S2P5r3y4D9i4K6u0r3L8r3g2^5i4@1f1#2i4K6V1J5i4K6S2o6P5h3q4U0j5#2)9J5c8U0q4Q4x3X3g2Z5N6r3#2D9
Lex和Yacc从入门到精通(1)－－环境配置篇

dfdK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8X3u0D9L8$3N6Q4x3X3g2U0M7$3c8F1i4K6u0W2L8X3g2@1i4K6u0r3k6r3q4%4L8X3c8#2i4K6u0r3j5i4u0U0K9r3W2$3k6g2)9J5c8U0t1H3x3o6k6Q4x3V1j5H3y4q4)9J5c8U0p5K6i4K6u0r3y4U0j5J5x3U0j5H3i4K6u0W2j5i4y4H3P5l9`.`.
递归下降纯解释器编写的困惑 (关于纯解释中的分支，循环)

46dK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6h3y4#2j5X3I4G2k6#2)9J5k6h3y4F1i4K6u0r3N6g2)9J5c8U0p5K6x3K6V1J5i4K6u0r3M7$3S2G2N6$3q4J5N6q4)9#2k6U0t1H3x3K6M7H3y4#2)9J5k6h3S2@1L8h3I4Q4x3U0x3I4x3#2)9J5k6g2)9J5y4e0t1H3b7$3q4$3k6h3q4@1M7#2)9J5y4e0t1H3j5h3&6V1i4K6t1#2x3U0m8n7N6h3N6K6
Lex-词法分析器生成器(M.E.Lesk,E.Schmidt著,中文翻译

3e1K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6h3W2T1L8g2)9J5k6h3y4G2L8g2)9J5c8X3c8W2N6X3g2D9L8%4m8W2M7Y4N6G2M7X3E0K6i4K6u0r3j5$3&6Q4x3V1k6D9K9h3&6#2P5q4)9J5c8X3N6S2L8h3g2Q4x3V1k6K6k6r3I4Q4x3V1k6H3K9i4u0S2N6r3g2K6i4K6u0V1y4q4)9J5c8X3W2F1k6r3g2^5i4K6u0W2K9s2c8E0L8l9`.`.
SDL 用法，第 4 部分: lex 和 yacc
构建用于脚本和 GUI 设计的语法分析器

979K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6i4y4#2M7r3y4G2k6r3g2Q4x3X3g2U0L8$3#2Q4x3V1k6m8M7Y4c8A6j5$3I4W2i4K6u0r3M7X3g2S2k6r3y4G2N6i4u0K6k6g2)9J5c8X3u0A6j5h3&6U0K9r3g2F1k6%4N6W2L8X3c8S2L8X3N6Q4x3V1k6I4K9i4c8S2P5i4g2&6j5h3&6Q4x3V1k6%4k6h3W2X3L8r3g2^5N6r3W2Y4L8$3&6Y4k6s2g2G2M7$3S2#2M7Y4g2Z5N6h3q4F1j5$3S2G2L8X3N6y4N6h3I4@1K9i4m8D9k6h3W2F1M7s2g2@1j5Y4g2X3k6X3g2J5M7#2)9J5k6i4y4Z5N6r3#2D9
为flex提供多输入缓冲！Multiple input buffers

使用 Flex 和 Bison 更好地进行错误处理
4efK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6h3W2T1L8g2)9J5k6h3y4G2L8g2)9J5c8X3c8W2N6X3g2D9L8%4m8W2M7Y4N6G2M7X3E0K6i4K6u0r3j5$3&6Q4x3V1k6D9K9h3&6#2P5q4)9J5c8X3I4Q4x3X3c8X3L8r3g2^5j5X3W2K6L8$3&6Q4x3X3g2Z5N6r3#2D9

73aK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6h3N6F1N6g2)9J5k6h3!0J5k6#2)9J5c8Y4y4G2k6Y4c8%4j5i4u0W2i4K6u0r3k6X3I4W2P5q4)9J5c8X3#2S2L8Y4g2S2L8q4)9J5c8X3S2@1L8h3I4Q4y4h3k6E0L8$3&6G2i4K6u0r3k6X3I4W2P5q4)9J5k6h3S2@1L8h3H3`.
flex munual *** english
d3cK9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6h3I4A6L8Y4g2^5k6X3!0J5N6h3#2Q4x3X3g2F1k6i4c8Q4x3V1k6X3L8%4u0#2L8g2)9J5c8X3k6A6L8r3g2K6i4K6u0r3y4o6j5#2x3K6V1^5i4K6u0V1P5X3S2Q4y4h3k6o6e0W2)9#2k6X3k6D9k6i4S2Q4x3X3g2@1P5s2b7`.
flex 手册

646K9s2c8@1M7q4)9K6b7g2)9J5c8W2)9J5c8Y4N6%4N6#2)9J5k6h3u0D9L8$3N6U0L8W2)9J5k6h3y4G2L8g2)9J5c8W2g2K6k6i4t1I4x3#2)9J5c8Y4S2B7L8%4W2%4j5h3N6Q4x3V1k6A6L8X3c8W2P5q4)9J5k6h3S2@1L8h3I4Q4x3@1k6@1M7q4)9K6c8p5I4W2P5q4)9J5y4e0t1H3i4K6t1$3i4K6t1#2x3U0m8k6j5h3y4U0
正则表达式使用详解 [转]
从lex&yacc说到编译器 [转]
Yacc - 一个生成 LALR(1) 文法分析器的程序 [转]
编译器（解释器）编写指南-编写编译器（解释器）的工具-LEX [转]

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课