有一段输入的离散信号{Zi}，假定这段信号长度为N（N=2^n）。

Q1：

通常，可以用Fourier Transform来进行频域分析。例如对于一段随机白噪，可以得出时域和频域的图像如下：

其中，上图为时域，横轴t，纵轴为Zt。下图为频域，横轴为1/f（即周期T），纵轴为|Fn|(波幅)。

如果有这样一种假说，一个信号，是由一个基频与若干高/低频谐波和噪声的混合，且基频、噪声和高/低频谐波的波幅存在着一定的分布率，例如指数分布，例如，假设基频波幅期望是t（0<t<1），而次一级的谐波/噪声波幅的期望为t^2，以此类推。且信号的波幅是随机的，其波幅概率曲线成正态分布。

问题：有没有一种办法，可以对频谱加以分析，判断出可能概率最大的基频频率，并给出这一判断的概率是多少。（要做假设检验用，例如90%）

 

Q2:

使用一个信号发生器，Zi = 1 + Sin( i * Pi / 20 )。并经过傅里叶分析，得出以下的时域和频域统计：

其中，上图为时域，横轴t，纵轴为Zt。下图为频域，横轴为1/f（即周期T），纵轴为|Fn|(波幅)。

问题：为什么在周期接近1的时候，会有一个波幅尖峰？

你看得懂C++不？那你可以靠边站了。听得懂人话不？那你也可以靠边站了。

此吐槽文，专门为没事干就想着怎么挑战编译器的牲口准备的。

在此之前，你必须要准备好听得懂人话的勇气和听不懂人话的基础。

 

1. 这个类要干些啥

在干一件事情之前，如果你早就预谋好了，那就是禽兽；如果你预谋都没有的，那就是禽兽不如。

所以在逆天之前，咱们得知道逆天之后，是如何作威作福的，这样才有Revolutionary的动力。

哥哥估计你应该是没写过软件渲染器。你们这群屁大孩子哪知道哥哥的苦啊。

老子他妈的为了兼容D3D的颜色，半夜爬起来黑灯瞎火的查手册，一看，我操，这么多颜色！

这世界咋不全他妈都是些颜色瞎子呢！

typedef enum DXGI_FORMAT
{
    DXGI_FORMAT_UNKNOWN = 0,
    DXGI_FORMAT_R32G32B32A32_TYPELESS = 1,
    DXGI_FORMAT_R32G32B32A32_FLOAT = 2,
    DXGI_FORMAT_R32G32B32A32_UINT = 3,
    DXGI_FORMAT_R32G32B32A32_SINT = 4,
    DXGI_FORMAT_R32G32B32_TYPELESS = 5,
    DXGI_FORMAT_R32G32B32_FLOAT = 6,
    DXGI_FORMAT_R32G32B32_UINT = 7,
    DXGI_FORMAT_R32G32B32_SINT = 8,
    DXGI_FORMAT_R16G16B16A16_TYPELESS = 9,
    DXGI_FORMAT_R16G16B16A16_FLOAT = 10,
    DXGI_FORMAT_R16G16B16A16_UNORM = 11,
    DXGI_FORMAT_R16G16B16A16_UINT = 12,
    DXGI_FORMAT_R16G16B16A16_SNORM = 13,
    DXGI_FORMAT_R16G16B16A16_SINT = 14,
    DXGI_FORMAT_R32G32_TYPELESS = 15,
    DXGI_FORMAT_R32G32_FLOAT = 16,
    DXGI_FORMAT_R32G32_UINT = 17,
    DXGI_FORMAT_R32G32_SINT = 18,
    DXGI_FORMAT_R32G8X24_TYPELESS = 19,
    DXGI_FORMAT_D32_FLOAT_S8X24_UINT = 20,
    DXGI_FORMAT_R32_FLOAT_X8X24_TYPELESS = 21,
    DXGI_FORMAT_X32_TYPELESS_G8X24_UINT = 22,
    DXGI_FORMAT_R10G10B10A2_TYPELESS = 23,
    DXGI_FORMAT_R10G10B10A2_UNORM = 24,
    DXGI_FORMAT_R10G10B10A2_UINT = 25,
    DXGI_FORMAT_R11G11B10_FLOAT = 26,
    DXGI_FORMAT_R8G8B8A8_TYPELESS = 27,
    DXGI_FORMAT_R8G8B8A8_UNORM = 28,
    DXGI_FORMAT_R8G8B8A8_UNORM_SRGB = 29,
    DXGI_FORMAT_R8G8B8A8_UINT = 30,
    DXGI_FORMAT_R8G8B8A8_SNORM = 31,
    DXGI_FORMAT_R8G8B8A8_SINT = 32,
    DXGI_FORMAT_R16G16_TYPELESS = 33,
    DXGI_FORMAT_R16G16_FLOAT = 34,
    DXGI_FORMAT_R16G16_UNORM = 35,
    DXGI_FORMAT_R16G16_UINT = 36,
    DXGI_FORMAT_R16G16_SNORM = 37,
    DXGI_FORMAT_R16G16_SINT = 38,
    DXGI_FORMAT_R32_TYPELESS = 39,
    DXGI_FORMAT_D32_FLOAT = 40,
    DXGI_FORMAT_R32_FLOAT = 41,
    DXGI_FORMAT_R32_UINT = 42,
    DXGI_FORMAT_R32_SINT = 43,
    DXGI_FORMAT_R24G8_TYPELESS = 44,
    DXGI_FORMAT_D24_UNORM_S8_UINT = 45,
    DXGI_FORMAT_R24_UNORM_X8_TYPELESS = 46,
    DXGI_FORMAT_X24_TYPELESS_G8_UINT = 47,
    DXGI_FORMAT_R8G8_TYPELESS = 48,
    DXGI_FORMAT_R8G8_UNORM = 49,
    DXGI_FORMAT_R8G8_UINT = 50,
    DXGI_FORMAT_R8G8_SNORM = 51,
    DXGI_FORMAT_R8G8_SINT = 52,
    DXGI_FORMAT_R16_TYPELESS = 53,
    DXGI_FORMAT_R16_FLOAT = 54,
    DXGI_FORMAT_D16_UNORM = 55,
    DXGI_FORMAT_R16_UNORM = 56,
    DXGI_FORMAT_R16_UINT = 57,
    DXGI_FORMAT_R16_SNORM = 58,
    DXGI_FORMAT_R16_SINT = 59,
    DXGI_FORMAT_R8_TYPELESS = 60,
    DXGI_FORMAT_R8_UNORM = 61,
    DXGI_FORMAT_R8_UINT = 62,
    DXGI_FORMAT_R8_SNORM = 63,
    DXGI_FORMAT_R8_SINT = 64,
    DXGI_FORMAT_A8_UNORM = 65,
    DXGI_FORMAT_R1_UNORM = 66,
    DXGI_FORMAT_R9G9B9E5_SHAREDEXP = 67,
    DXGI_FORMAT_R8G8_B8G8_UNORM = 68,
    DXGI_FORMAT_G8R8_G8B8_UNORM = 69,
    DXGI_FORMAT_BC1_TYPELESS = 70,
    DXGI_FORMAT_BC1_UNORM = 71,
    DXGI_FORMAT_BC1_UNORM_SRGB = 72,
    DXGI_FORMAT_BC2_TYPELESS = 73,
    DXGI_FORMAT_BC2_UNORM = 74,
    DXGI_FORMAT_BC2_UNORM_SRGB = 75,
    DXGI_FORMAT_BC3_TYPELESS = 76,
    DXGI_FORMAT_BC3_UNORM = 77,
    DXGI_FORMAT_BC3_UNORM_SRGB = 78,
    DXGI_FORMAT_BC4_TYPELESS = 79,
    DXGI_FORMAT_BC4_UNORM = 80,
    DXGI_FORMAT_BC4_SNORM = 81,
    DXGI_FORMAT_BC5_TYPELESS = 82,
    DXGI_FORMAT_BC5_UNORM = 83,
    DXGI_FORMAT_BC5_SNORM = 84,
    DXGI_FORMAT_B5G6R5_UNORM = 85,
    DXGI_FORMAT_B5G5R5A1_UNORM = 86,
    DXGI_FORMAT_B8G8R8A8_UNORM = 87,
    DXGI_FORMAT_B8G8R8X8_UNORM = 88,
    DXGI_FORMAT_R10G10B10_XR_BIAS_A2_UNORM = 89,
    DXGI_FORMAT_B8G8R8A8_TYPELESS = 90,
    DXGI_FORMAT_B8G8R8A8_UNORM_SRGB = 91,
    DXGI_FORMAT_B8G8R8X8_TYPELESS = 92,
    DXGI_FORMAT_B8G8R8X8_UNORM_SRGB = 93,
    DXGI_FORMAT_BC6H_TYPELESS = 94,
    DXGI_FORMAT_BC6H_UF16 = 95,
    DXGI_FORMAT_BC6H_SF16 = 96,
    DXGI_FORMAT_BC7_TYPELESS = 97,
    DXGI_FORMAT_BC7_UNORM = 98,
    DXGI_FORMAT_BC7_UNORM_SRGB = 99,
    DXGI_FORMAT_FORCE_UINT = 0xffffffffUL,
} DXGI_FORMAT, *LPDXGI_FORMAT;

除了BC?一组JB货，其他的我都要两两之间能够转化，擦，你丫他妈的还能够淡定？

然后我就在想啊，这他妈的都差不多，也就是转转类型啥的。

那能不能让编译器这个狗日的来替我当苦力，生成老子要的货呢？

然后老子就开始逆天了！老子要作威作福！

2. 怎么干

你问我，那我该问谁？记住了，某老说得对，你啥都不晓得做之前，就先把能做的事情做好。

第一件事情，先把祸害除掉。祸害？什么祸害？滚！别说老子认识你！

先把BC干掉。BC是啥？不知道？脑子都是bullshit呢你。

Block-Compression。压缩的格式，在咱的CPU系统里面，没啥JB用。以后顶多写个掏DIAO的工具，就能解决所有的需求了。

    DXGI_FORMAT_R32G32B32A32_TYPELESS = 1,
    DXGI_FORMAT_R32G32B32A32_FLOAT = 2,
    DXGI_FORMAT_R32G32B32A32_UINT = 3,
    DXGI_FORMAT_R32G32B32A32_SINT = 4,
    DXGI_FORMAT_R32G32B32_TYPELESS = 5,
    DXGI_FORMAT_R32G32B32_FLOAT = 6,
    DXGI_FORMAT_R32G32B32_UINT = 7,
    DXGI_FORMAT_R32G32B32_SINT = 8,
    DXGI_FORMAT_R16G16B16A16_TYPELESS = 9,
    DXGI_FORMAT_R16G16B16A16_FLOAT = 10,
    DXGI_FORMAT_R16G16B16A16_UNORM = 11,
    DXGI_FORMAT_R16G16B16A16_UINT = 12,
    DXGI_FORMAT_R16G16B16A16_SNORM = 13,
    DXGI_FORMAT_R16G16B16A16_SINT = 14,
    DXGI_FORMAT_R32G32_TYPELESS = 15,
    DXGI_FORMAT_R32G32_FLOAT = 16,
    DXGI_FORMAT_R32G32_UINT = 17,
    DXGI_FORMAT_R32G32_SINT = 18,
    DXGI_FORMAT_R32G8X24_TYPELESS = 19,
    DXGI_FORMAT_D32_FLOAT_S8X24_UINT = 20,
    DXGI_FORMAT_R32_FLOAT_X8X24_TYPELESS = 21,
    DXGI_FORMAT_X32_TYPELESS_G8X24_UINT = 22,
    DXGI_FORMAT_R10G10B10A2_TYPELESS = 23,
    DXGI_FORMAT_R10G10B10A2_UNORM = 24,
    DXGI_FORMAT_R10G10B10A2_UINT = 25,
    DXGI_FORMAT_R11G11B10_FLOAT = 26,
    DXGI_FORMAT_R8G8B8A8_TYPELESS = 27,
    DXGI_FORMAT_R8G8B8A8_UNORM = 28,
    DXGI_FORMAT_R8G8B8A8_UNORM_SRGB = 29,
    DXGI_FORMAT_R8G8B8A8_UINT = 30,
    DXGI_FORMAT_R8G8B8A8_SNORM = 31,
    DXGI_FORMAT_R8G8B8A8_SINT = 32,
    DXGI_FORMAT_R16G16_TYPELESS = 33,
    DXGI_FORMAT_R16G16_FLOAT = 34,
    DXGI_FORMAT_R16G16_UNORM = 35,
    DXGI_FORMAT_R16G16_UINT = 36,
    DXGI_FORMAT_R16G16_SNORM = 37,
    DXGI_FORMAT_R16G16_SINT = 38,
    DXGI_FORMAT_R32_TYPELESS = 39,
    DXGI_FORMAT_D32_FLOAT = 40,
    DXGI_FORMAT_R32_FLOAT = 41,
    DXGI_FORMAT_R32_UINT = 42,
    DXGI_FORMAT_R32_SINT = 43,
    DXGI_FORMAT_R24G8_TYPELESS = 44,
    DXGI_FORMAT_D24_UNORM_S8_UINT = 45,
    DXGI_FORMAT_R24_UNORM_X8_TYPELESS = 46,
    DXGI_FORMAT_X24_TYPELESS_G8_UINT = 47,
    DXGI_FORMAT_R8G8_TYPELESS = 48,
    DXGI_FORMAT_R8G8_UNORM = 49,
    DXGI_FORMAT_R8G8_UINT = 50,
    DXGI_FORMAT_R8G8_SNORM = 51,
    DXGI_FORMAT_R8G8_SINT = 52,
    DXGI_FORMAT_R16_TYPELESS = 53,
    DXGI_FORMAT_R16_FLOAT = 54,
    DXGI_FORMAT_D16_UNORM = 55,
    DXGI_FORMAT_R16_UNORM = 56,
    DXGI_FORMAT_R16_UINT = 57,
    DXGI_FORMAT_R16_SNORM = 58,
    DXGI_FORMAT_R16_SINT = 59,
    DXGI_FORMAT_R8_TYPELESS = 60,
    DXGI_FORMAT_R8_UNORM = 61,
    DXGI_FORMAT_R8_UINT = 62,
    DXGI_FORMAT_R8_SNORM = 63,
    DXGI_FORMAT_R8_SINT = 64,
    DXGI_FORMAT_A8_UNORM = 65,
    DXGI_FORMAT_R1_UNORM = 66,
    DXGI_FORMAT_R9G9B9E5_SHAREDEXP = 67,
    DXGI_FORMAT_R8G8_B8G8_UNORM = 68,
    DXGI_FORMAT_G8R8_G8B8_UNORM = 69,
    DXGI_FORMAT_B5G6R5_UNORM = 85,
    DXGI_FORMAT_B5G5R5A1_UNORM = 86,
    DXGI_FORMAT_B8G8R8A8_UNORM = 87,
    DXGI_FORMAT_B8G8R8X8_UNORM = 88,
    DXGI_FORMAT_R10G10B10_XR_BIAS_A2_UNORM = 89,
    DXGI_FORMAT_B8G8R8A8_TYPELESS = 90,
    DXGI_FORMAT_B8G8R8A8_UNORM_SRGB = 91,
    DXGI_FORMAT_B8G8R8X8_TYPELESS = 92,
    DXGI_FORMAT_B8G8R8X8_UNORM_SRGB = 93,

看懂没？有啥特点你这个猪脑子分析出来没？

总共只有以下的色彩通道：RGBADSX。

也只有一下的数据类型：UINT SINT FLOAT TYPELESS UNORM SNORM

当然还有几个比较操蛋的格式

DXGI_FORMAT_R9G9B9E5_SHAREDEXP = 67, 
DXGI_FORMAT_R10G10B10_XR_BIAS_A2_UNORM = 89, 
DXGI_FORMAT_B8G8R8A8_UNORM_SRGB = 91, 
DXGI_FORMAT_B8G8R8X8_UNORM_SRGB = 93,

下面要干的活，就是让编译器能够为不同的颜色转换，给爷苦力出好使的代码来。

RT。 同志们，要切题啊！ZOJ, PKU的题库都可以。。。要切题啊。。。血的教训。。。 今天一个Paper For Test，第一题是一个烂大街的背包。 DFS，递归什么的都好。。。结果硬生生的给我写的一团糟，还花了50min，我就是一大坨XXX啊。。。

三月九日，去了一家做SoC Graphics的硬件的公司面试。这家公司是一个朋友Destiny no Cyber介绍的，所以面试完了去和他一起吃饭（当然是别人花钱，嘎嘎），同行的还有另一个朋友Fake German。不过COBET、Mickey和Baby Valkyrie没去，同时因为时间关系，我也没能去朝拜一下Mr.Lalrone，这些让我觉得挺遗憾的。

------------------------我是YD的分割线--------------------------------------------

唔，言归正传，简单讨论一下面试的事情。由于他们Corp仍然在招人，所以我也就不好透露具体的面试题目，不过也都是写基本的问题。只要功底稍微好一点，回答上来应该问题不大。而且很不幸的我属于那种功底不怎好的人。晚上和Mr.Lalrone聊天的时候，还被耻笑了。我也小小总结了一下其他网上的面试题，就语言本体部分而言，大概就一下这么几个方面：
1. Macro
对于Macro只需要把握一点，Macro的机制是编译期的文本替换，而不是运行期的。这是它和函数最大的区别。因此要注意一下Block的使用（ 也就是{}和()一定要用 )。如果遇到对Macro行为的解释的题目，为了慎重起见，一定要先手工展开，再来进行别的方面的计算。
2. 指针/数组
没啥好说的，最常考的内容之一。主要是传值/传引用，sizeof，指针/数组在初始化上的区别。等等等。一个可能会出现的问题，是const的左绑定
3. 结构体/对象
在这一方面，常见的问题包括：内存对齐导致的sizeof和member layout问题，bit field的正确使用，继承关系下的基类和派生类成员的分布。
4. 类
类方面的问题主要包括以下若干方面：
访问控制：public，private，protected，friend。对于这些，要有相对深刻的理解。对于硬件公司，这方面关心的不多。但是如果是一个做Application的Corp，出于工程方面的考虑，这些问题就显得尤为重要。你必须理解，访问控制仅在编译期有含义。在编译期之外，不会生成任何额外的代码，来保证你的访问正确性。
构造函数：要理解什么时候编译器会生成缺省构造函数，以及缺省构造函数的行为。对于一些测试代码风格的题目，千万不要忘了对拷贝构造、赋值的特殊处理，以及对单值构造函数的explicit声明。部分情况下，可能要考虑到成员/基类的构造顺序的问题。这个顺序是：先基类，后子类。本类中，声明序。不是按照初始化函数的顺序，而是按照声明的顺序。如果记不清，那就请记得把初始化函数的顺序和成员声明的顺序一致起来。
析构函数：有两个地方是重中之重。第一，有虚函数的基类，一定要有一个虚析构函数。第二，不得抛出异常。
虚函数/非虚函数：这个主要可以参见书“Inside C++ Object Model”。虚函数的考点不外乎两点，底层实现和运行时行为。底层实现大部分的实现都是vptr - vtable的组合。关于调用顺序，自然不用赘述了，只要辨明了Object Slice和Reference（包括pointer）的区别，就没有任何问题了。
静态/非静态成员变量/成员函数：这里的考点比较多。他们在行为上的区别，存储上的区别，初始化的区别，访问的区别，指针的区别，（函数）调用协议的区别是最常见的考点。几乎每一个部分都有不少内容可以让考官爽你一把的。有两个相对容易陌生的操作符.*和.->万一考到了，一定需要注意。（多年没用过，我都忘得差不多了。不过好在我估计出面试题目的，也忘了差不多了。还是functor好。）对于函数而言，const和non-const函数的区别，this的具体含义和行为是很常见的考点。一个罕见的关键字mutable的运用，也可能作为考点出现。
5. 类型和声明系统
主要考点在const和volatile上。const前面已经说过了。对于有着并发需求的公司，面试之前的准备中，千万不能忘了volatile。volatile一般仅用于编译器的native type。他是C++这个多线程残废唯一还算靠点谱的并发一致性保证的拐杖。然后要特别注意，typedef里面的type modification的行为，可能不像你YY的那个样子。唯一靠谱的类型修饰，还是来自于STL和TR1的type traits。
6.函数
有关于函数方面的问题，能考的点非常多。相对底层的包括调用协议（参数传递方法，入栈顺序，堆栈平衡等），应用级别的，主要还是考你栈和堆的区别。在代码的Robust和Security的问题上，如果是做Kernel的公司，还要好一些。应用系统的，最常见的就是缓冲区溢出的问题。千万别在这个问题上犯傻了。对于效率而言，strlen，strcpy和memmove是几项最容易考的实现函数。还有就是关于static member和non static member的区别。这个不难，但是经常会考到。
7. 模板
大部分公司都不怎么用模板，因此考的可能性也不大。
8. 库
这个就没什么好说的了。CRT和STL是最常见的考点。要特别注意库在性能方面、安全性方面、线程安全方面、出错处理方面的Features。必要的时候还要了解其实现。

————————我是更YD的分割线————————

对于语言方面的考核点，我也就小小的总结一下，希望对大家有所帮助。当然，还有一个方面的问题就是领域相关的，比方说，你做UI，或者做Graphics，或者做Network，都会有各自的问题。这与面试官个人的性格、知识面、deep程度，公司职位对能力的需求都有莫大的关系。因此，这些方面的知识还是多多益善。

 

后来还见了他们的中国区BOSS（荣幸的很，嘿嘿），当时答应了要替他们公司问一下招聘的人的，所以我也在这里发一下招聘信息：

图芯芯片技术公司(Vivante Corp)招聘启事 - HW职位

ASIC Design Engineer（上海）
Responsibilities:
The candidate will be responsible for logic design and implementation in low power graphic and multi-media chip/core.
Micro-architecture definition, RTL design, verification, silicon bring-up, etc.
Qualifications:

• MSEE or above, with 2 years experience
• Proficiency in logic design, simulation, synthesis and test
• Proficiency in Verilog and its simulation environment.
• Experience in graphic, video, and multi-media chip design a big plus.
• Familiar with all aspects of the frontend ASIC design flow including RTL design, verification, synthesis, and timing analysis, DFT, etc.
• Good written and spoken English
• Good communication skills and able to work both independently and in a team

Design Verification Engineer（上海）
Responsibilities:
The candidate will be responsible for building up verification environment and completing verification of design and algorithm at both chip and unit levels.The candidate is also responsible for developing verification plan to verify design functionality.
Minimum requirements:

• MSEE or above, minimum 3 years direct experience in verifying complex SoC chips
• Experience with Verilog logic design language.
• Experience with high-level verification languages such as System Verilog, Vera, System C or Specman e language a plus
• Experience with UNIX/Linux simulation tools such as NC-Verilog or VCS.
• Experience with C and C++ and script language like PERL/SED, etc.
• Self-motivated and good team player.
• Strong problem solving and analytical skills
• Good written and spoken English
• Good communication skills and able to work both independently and in a team

.
About Vivante
Vivante Corporation is a promising, privately held fabless semiconductor company in the design, development,and marketing of graphic and multimedia ICs and related software for the fast growing handheld wireless device market.The company is foundered by successful industry veterans and is well funded.
Our mission is to provide the mass market with the capability of accessing rich graphics and multimedia content anywhere and anytime on their wireless handheld devices. Combining our low power architecture and design with our dynamic power management, our 3D graphics chips will give consumers the same immersive experience they have found on their PC and game consoles but with power consumption level orders of magnitude smaller. All day interactive computing will be tethered no more!
We believe and invest in our people, we promote a culture of creativity, and we created an environment where talents are recognized and teamwork and collaboration is valued and rewarded.

ps，他们也招SW职位的人，主要是User-Model Driver和Application的。有意向，也可以投简历。

Corp URL： http://www.vivantecorp.com/

语义：从分析树到语法树（一）

在1-7章里，我们已经建立了一个编译器所需要的绝大部分环节：词法分析、语法分析、代码生成、代码执行。前两个阶段，将会生成分析树（Parse Tree）后两个阶段，则是用语法树生成的。我们多希望语法分析后的分析树，直接就能用作语法树啊！

从结构上看，分析树和语法树几乎是如出一辙的。只可惜，如果我们再仔细的观察会发现，从分析树到语法树有一条深深的鸿沟。是的，你猜得没错，这条鸿沟，就是语义。只要有了语义，我们就可以将我们的分析树，变成可以产生代码的语法树。

本质上讲，语法树（Syntax Tree）是含有语义的。仍然用A+B这个表达式的语法树来举例子。在这里，A和B都是一个Int32的常量，例如我们这里A是5，B是10。这个语法树里面A节点，它具有以下的语义：

• A是一个常量。
• A是一个整型值。
• A是5。

这些语义信息在语法树里面都具备，而在语法分析之后的分析树里面，只有“5”这样一个字符串。所以实际上，从分析树到语法树的建立，还需要经历一个附加语义的过程。

在一个常见的编译流程里，语义分析可以分为两个部分。其中一部分会跟随在词法和语法分析中，用于解析一些最基本的语义。例如输入的是不是关键字啦，是不是字面量啦，是不是运算符啦一类的信息，这些语义信息还可能用来指导后一阶段的语法分析。

还有一个部分就是例如类型推导、符号设置、函数签名分析一类的语义分析。这些分析的结果通常并不影响语法树的结构，而放在语法分析阶段又会增加分析的复杂度。这一类的语义分析，通常是在语法树建立好之后，再来对语法树进行进一步的分析，将语法树上的语义信息补完。

在SASL里，我们将语法树的建立分成三个步骤。

第一步，在词法分析和语法分析的同时，进行简单的语义解析。包括字面值、操作符、关键字的提取等。这些一方面是语义，一方面也是为了语法分析服务的。

第二步，我们将语法分析得出来的分析树，转换成我们需要的语法树的形式。我们的语法树上，拥有一些属性。通过这些属性可以给语法树节点上附加产生代码所必须的语义。

第三步，遍历语法树，填充语义，执行一些准备工作。

这样，我们就建立了一颗可以被代码生成工具所识别的语法树。

接下来，我们将运用Spirit.Lex和Spirit.Qi来完成我们前两步的工作。

第三部分，我们暂时还不需要，等需要的时候，咱们再来扩充。

Exodus：语法分析（一）

在一个魔法世界里，你是一个会魔法的法师。我的意思是，作为一个法师，你什么都会了，也什么都有了，施法材料，法袍，魔杖，法术书。甚至你连成功后的庆祝动作都想好了。你以为你会“魔法”了。只可惜，这里还缺少了一样东西，那就是，魔法的口诀。

而在这里，我们什么都有了。用来分析的Token，语法树到OP CODE的翻译，虚拟机，什么都有了。但是我们还是缺一样口诀，那就是，如何从Token到语法树的口诀。

在我们进行词法分析的时候，遵从的是Spirit这本颇有难度的《圣经》。不过，我们只浏览了如《使徒行传》般流畅而松散的Spirit.Lex。在这里，我们依然沿用Spirit，这是我们编译器前端的原旨。不过现在，我们要讲解的是环环相扣、荡气回肠的《Exodus》——Spirit.Qi。

嘛，这段神叨叨的引子，只是为了强调语法分析的地位而已。在继续阅读本章之前，需要你看的明白BNF。有关于BNF方面的信息，你可以在任何一本讲述编译原理的书籍上找到。

仍然是以一个简单的A+B为例。由于我们已经有了词法“literal_int”和“literal_add”，因此A+B这样一个表达式，用BNF来表示，就是：

Expr ::= literal_int literal_add literal_int

在Spirit.Qi里，语法的表达也类似于BNF的形式。只要你设计出语言的BNF，就很容易的翻译成Spirit.Qi支持的语法定义。我们这里，就可以写成：

template <typename IteratorT>

struct binary_expression: qi::grammar<IteratorT>{

    template <typename TokenDefT> binary_expression(const TokenDefT& tok): binary_expression::base_type(start)

    {

        start = (  literal_int >> literal_op >> literal_int );

        literal_int = tok.littok_int;

        literal_op = tok.optok_add;

    }

    qi::rule<IteratorT> literal_op, literal_int, start;

};

在Spirit.Qi中，一个Rule就等于EBNF的一个非终结符。一个Grammar相当于一组Rule的集合，并且可以拥有一个或者多个的起始Rule作为入口。本质上我们可以把Grammar看成一个Rule（准确的说，是Parser，若要了解相关概念，请参阅Spirit的自定义Parser部分）。等号用于连接非终结符（Rule）及其推导式；使用“>>”（输入流/右位移运算符）连接语法要素之间的连接符号。更多的符号请参阅Spirit.Qi文档。

至于为什么不将Rule合并到一起，而提供一个Grammar的中间层，主要有两方面的考虑，一个是提供了一个抽象层，例如我们可以把Statement和Expression分开来写，使得层次上更加清晰；还有一个方面在于节省编译时间。因为Spirit使用了大量的源编程技术，如果把所有的Rule合并到一起编译，会占用大量的编译时间。在使用了Grammar之后，可以运用C++编译器在一个编译过程里对相同的模板特化只进行一次的Tricks，大大节省了编译时间。

在上一章里，咱们最后还留了一个问题，就是空白符号的处理方法。这里，我们将于空白符号一起，来走一下Spirit的语法和词法分析的流程。

首先，我们建立好词法，将源代码字符流组织成更加容易被语法分析识别的Token流。

template <typename BaseLexerT> struct sasl_tokens : public boost::spirit::lex::lexer< BaseLexerT > {     sasl_tokens(){         this->self.add_pattern("SPACE", "[ \\t\\v\\f]+");           littok_int = "[0-9]+";         optok_add = "[\\+]");         whitetok_space = "{SPACE}";                 this->self = littok_int | optok_add;         this->self("SKIPPED") = whitetok_space;     }     boost::spirit::lex::token_def<>         littok_int, optok_add, whitetok_space; };

这里，我们将词法分为两组，对语法分析有效的Tokens组和无效的空白组，空白组用”Skipped”作为状态以示区别。这里我们需要说明一下，Spirit.LEX的词法分析的“状态”与词法分析工具“Lex/Flex”中的状态概念是相同的。

在Lex类的词法分析工具里，有一个专门的状态。一般而言，这些状态都用字符串表示。Lex的默认是“INITIAL”，Spirit.Lex的默认状态是空（如果我没记错的话）。在指定词法的时候，可以告诉词法分析器，此文法在什么状态下，这条词法才发挥作用。词法分析器的状态可以由外部程序自由指定。

我们将表示空白的词法都放在Skipped状态下后，我们就可以对每个单词，用Skipped状态去匹配。如果发现是在Skipped状态下匹配成功的单词，在进入语法分析前就可以先丢弃，进而实现过滤空白符的目的。

考虑表达式“55_+38”（‘_’代表空格），在分析成Token流之后，会变成以下的形式：

State	INITIAL	SKIPPED	INITIAL	INITIAL
Token	Literal_int	Literal_ws	Literal_op	Literal_int
Literal	55	_	+	38

然后撰写我们的Grammar。由于我们需要指定Skipper来跳过我们不需要的Token，因此我们的Grammar在模板参数里，也要加入这个Skipper的类型参数。

template <typename IteratorT, typename LexerT> struct binary_expression: qi::grammar<IteratorT, qi::in_state_skipper<LexerT> > {     template <typename TokenDefT> binary_expression(const TokenDefT& tok):     binary_expression::base_type(start)     {         start = (  literal_int >> literal_op >> literal_int );         literal_int = tok.littok_int;         literal_op = tok.optok_add;     } boost::spirit::qi::in_state_skipper<LexerT> skipper_type;     qi::rule<IteratorT, skipper_type> literal_op, literal_int, start; };

并在咱们的驱动代码里面，这样写：

typedef sasl_tokenizer::iterator_type sasl_token_iterator; typedef sasl_tokenizer::lexer_def sasl_skipper;   sasl_tokenizer sasl_tok; binary_expression<sasl_token_iterator, sasl_skipper> g( sasl_tok );   lex::tokenize_and_phrase_parse( first, last, sasl_tok, g, qi::in_state("SKIPPED")[sasl_tok.self] );

喏，看到了指定skipper的代码了不？这就提示parser，遇到了skipped状态解析出来的token，就自己吃了吧，不要拿去匹配了。这样就达到了过滤掉空白符的目的。

不过呢，尽管我们parse通过了，但是仍然没有提取出我们想要的信息来。到目前为止，我们还没能让parser构造出咱们之前手工构建并传递给Code Generator的语法树来。这仍然是横亘在出埃及的我们面前的红海。

下一次，我们将仍然相信Spirit这本Bible，相信它给我们的一章叫 “Semantic Action”的启示录。它将告诉我们，如何把Parser分析出的结果转化为我们要的语法树，以引领我们走向流OP CODE之地。

God bless programmers and p2p sites except gfw’s developers and Cisco. Amen

起源：词法分析

不管你学什么样的外语，大约都是从词汇开始。词，是一个语言里最小的语义单元。编译器阅读你的语言，也是如此。所以第一件事情，就是要把整个文法打散成一个一个的单词。在这里，我们把这些单词叫token。

怎么进行词法分析，此处就不再赘述，这是一个上下文无关文法的匹配问题。如果需要理解词法分析的原理，或者手工编写词法分析工具，可以参考陈梓翰提供的两篇极好的教程。在SASL里，我们不再发明轮子，而选用已有的词法分析工具。

可选的词法分析工具很多，例如出名的Lex及其改进Flex，ANTLR等。对于C++而言，这些方法多属于产生式的方法，就是用一段不太靠谱的代码去生成另外一些更不靠谱的代码。更重要的是，这些代码的编译、调试都不方便。所以最终我们还是选择了一个在用C++实现、并且可以直接在C++里书写词法和语法的分析器产生工具，它就是Spirit。

Spirit V1.8和V2.1都是Boost库里的一个部分。需要注意的是，Spirit的V1和V2是完全不兼容的两个库。在这里，我们选择了V2作为我们的词法和语法分析工具。Spirit V2总共分为3个部分，负责语法分析的Qi，格式化打印的Karma，和词法分析器Lex。此外，Spirit还有一个类似于boost.mpl和boost.lambda的库phoenix，这个库也常被用于词法和语法分析中。详细的使用指南和参考，可以参见Spirit的文档。

由于Spirit.Lex大量运用了Template Meta-Programming和编译器推导，因此编译时很容易出错，而且错误信息难于定位；同时Spirit.Lex的指南也写得非常简单，它所演示的特性，不足以用来实现一个完整的编译器。因此，这里我们也将给出另外一个快速指南，以展示那些我们在撰写编译器时所用到的技术和特性。

这里我们仍然以A+B这样一个简单的表达式为例，其中A和B都是一个字面值的整数，A+B之间没有其他空格填充。这样我们就可以把这个“句子”拆分成A，+，B三个token。例如“33+65”就可以被拆分成“33”，“+”，“65”三个token。对于这样一个表达式，我们只需要下面两个正则就可以完成词法分析：

literal_int = “[0-9]+”; literal_add=”\+”;

由于C++里面“\”是转义符，因此实际上literal_add实际上应该写成“\\+”。然后我们需要用Spirit来实现。

Spirit中，首先定义一个tokens列表：

template <typename BaseLexerT>

struct sasl_tokens : public boost::spirit::lex::lexer< BaseLexerT > {

    sasl_tokens(){

        littok_int = "[0-9]+";

        optok_add = "[\\+]";

 

        this->self =

            littok_int

            | optok_add;

    }

    boost::spirit::lex::token_def<> littok_int, optok_add;

};

 

然后，我们利用这个token列表生成一个词法分析器sasl_tokenizer：

 

typedef boost::spirit::lex::lexertl::lexer<> sasl_lexer_base; typedef sasl_tokens<sasl_lexer_base> sasl_tokenizer;

 

最后来执行一下我们的tokenizer。在执行之前，我们写一个callback函数，这个函数在每分析出一个词之后，都会被调用一下，我们用它来判断我们分出的词正确与否：

struct token_printer{

    template <typename TokenT> bool operator()( const TokenT& tok ){

        cout << "token: " << tok.value() << endl;

        return true;

    }

};

最后执行一下词法分析：

boost::spirit::lex::tokenize(first, last, sasl_tok, token_printer());

first，last是输入字符串的迭代器。如果输入为“55+65”，那么屏幕上就会依次打印出“55”，“+”，“65”的三行。

不过，如果你在“55+65”之间敲入一个空格，例如“55+_65”(‘_’代表空格)这样的，那么词法分析就会失败。因为“_”这个字符，没有合适的词可以匹配。即便是匹配了，空白这个Token也没办法用在语法树之中，最终也会导致语法分析失败。而在程序语言里，支持空白符号的过滤掉是必不可少的。所以，下一次，我们就要将语法，顺便过滤掉空白符，让我们可以自由写出美观的语句。

知道咱们的虚拟机能够执行OP CODE之后，下一步就要考虑，怎么从语法树里面生成咱们需要的OP CODE了。简单来讲，语法树就是将程序的逻辑按照树状组织并保存在内存中的一种形式。有关于更详细的信息，搜“Syntax Tree”，到处都是解释。

一时不明白也没关系，我们来看一个直观的例子。考虑a+b这样一个基本形式的表达式。这个表达式既可以按照我们所写的这样，分为a，+，b三个部分串行表示，也可以表示成下图的样子


可能一个表达式你还看不出来树形的优势。要是表达式级联起来，就显示出这种表示的威力了：

 
这样一个语法树，可以不借助任何别的手段，保存了表达式的优先级关系。这里的语法树表示的就是(A+B)*C的表达式。同时，在语法树上求值也很方便，后根遍历语法树就可以了。即先算出左右节点的值，再根据当前节点符号求出当前节点值。

王阳明说，知行合一。知道了语法树是什么东西，我们就要开始考虑怎么用了。“怎么用”这个问题可以分成两个部分，第一，语法树怎么实现。第二，语法树怎么生成op code。啊，先不要把语法树想象的这么复杂。在这里，我们的运算符只有加号，一个加号也只能带两个int的值节点，而不能递归的带上一个符号节点。也就是说，这棵树只可能有一种形式而已。

首先来解决语法树怎么实现的问题。在这个问题上，我们只需要把握一点，语法树是一个天然的composite模式。我们用一个UML来看看这个只有加法算符的语法树定义：
唔，很简洁，不是么。Node_type是一个syntax_node_types类型的枚举，这个枚举告诉以后的代码生成器这个抽象的node究竟是个什么类型，然后代码生成器再还原它原本的类型并生成适当的代码。op是一个operators类型的枚举，表示一个二元运算的操作符。对于本例，只有operators::add可用。
在有了基本实现之后，再考虑一下其它需求，例如语法树节点类型之间的可能存在的循环依赖问题，语法树的深浅拷贝问题，等等，最终SASL的语法树节点接口是这样的：


道理复杂，不过实际上，并没有那么复杂吧？
下面来解决第二个问题：怎么用表达式树产生代码？我不多解释，直接上代码，相信你一定会看明白的：



然后我们将生成语法树，生成code，运行code的代码补上，运行，OK~
你一定会说，啊，硬性绑定寄存器！太可怕了！如果表达式复杂了该怎么办呢？呵呵。这些都是以后的问题了。以后的问题，就由以后的我们去解决好了。今日事，今日毕，时间不早，咱们还是洗洗睡了。

     摘要: 本文重点在于利用现有各式各样的编译器前端或后端技术和库，以可控制和渐增的方式，将我们的编译器从无到有，从小到大，从简单到复杂，从低效到高效的实现出来。本文的写作目标是，我们将编写编译器的任务，分解成多个迭代的阶段，其中的大部分阶段，你都能够在理解它之后，在一个小时到一天不等的时间内达到预计的目标。  阅读全文