有一段輸入的離散信號{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~
你一定會說，啊，硬性綁定寄存器！太可怕了！如果表達式復雜了該怎么辦呢？呵呵。這些都是以后的問題了。以后的問題，就由以后的我們去解決好了。今日事，今日畢，時間不早，咱們還是洗洗睡了。

     摘要: 本文重點在于利用現有各式各樣的編譯器前端或后端技術和庫，以可控制和漸增的方式，將我們的編譯器從無到有，從小到大，從簡單到復雜，從低效到高效的實現出來。本文的寫作目標是，我們將編寫編譯器的任務，分解成多個迭代的階段，其中的大部分階段，你都能夠在理解它之后，在一個小時到一天不等的時間內達到預計的目標。  閱讀全文