3.分開Lexical 與 Syntax的理由

• 簡單：兩者的工作內容不同，分開降低複雜度
• 效率：分開使Lexical 可優化
• 可移動性：Lexical 與IO及記憶體讀取有關，屬於platform dependent，而parser並無

4.lexical analyzer

• 讀入各種lexeme並賦予這些lexeme一個token ID。
• lexeme是拆分後的字詞
• 每次只讀入一個字元，利用一個 state machine\table去確認是否合法
• state table：人工建立表，建立lexeme集合，並比對表來確認合法與否
• state machine：定義規則，並遵循規則lexeme才合法
• 比如在C語言，變數首字不能為數字
• token是一個抽象概念的集合，比如識別字集合、加法符號集合

 5.Parsing

• 當成功拆分字串中的字為字詞，並將所有字詞歸類為對應的抽象概念後，便能開始分析字詞出現的順序與文法是否符合標準。Parsing便是分析文法的行為。
• 因往往無法馬上挑出正確的Paring tree，Parsing 的過程是相當緩慢的，一個沒優化的Parser通常要O (n^3)的時間。
• Recursive-Descent Parsing：使用遞迴，對於一個非終結字元，不斷窮舉可替換規則。
• 可分為Top Down 與 Bottom up的parsing
• Top Down ：由根至葉，將已定義的規則由上至下擴增(把左項擴增為右項)
• Bottom up ：由葉至根，用以定義的規則從下往上化簡(把右項化簡成左項)

• LL Parser ：Top Down 實做的Parser

對讀入的字串，從最左邊看到最右邊，並先挑選最左邊的非終結字元做代換。
不過，這樣會產生 Recursive的問題，如 A → A + B，因為A總是在最左側，導致A不斷的被替換，即是A不斷的呼叫自己。在實做上，可以透過修正語法來解決這個問題，比方將位於最左側與不位於最左側的非終結字元分開處理。

A → Aα1 | … | Aαm | β1 | β2 | … | βn 

↓

A → β1A’ | β2A’ | … | βnA’
A’ → α1A’ | α2A’ | … | αmA’ | ε

兩者可產生出相同的葉，因為原式最終在前的必定是 β1 | β2 | … | βn ，餘下α1 | … | αmA。
然而，因為A'存在ε (空字串)，可以避免無窮迴圈的問題。

再從效率上來看，假設代換規則後第一個字的集合為F，比方：

A → aB | bAb | Bb

B → cB | d

A可換為：aB | bAb | (cBb | db) ，得到第一個字的集合F：{a},{b},{c,d}，再比方：

A → aB | BAb
B → aB | b

A可換為：aB | (aAb | bAb) ，得到第一個字的集合F：{a},{a,b}

我們發現，第一個情形三個集合沒有任何交集(disjointness)，而第二個情形卻產生的交集a，從遍歷一棵樹的角度來看，我們應希望各個規則沒有交集，也就是第一種情形，這樣在尋找規則上更加明確，從而降低走錯路的機率。可透過Left factoring減少各個規則間的交集。

• LR Parser ：Bottom up 實做的Parser

對讀入的字串，從最左邊看到最右邊，每次從Leaf走回去時，優先挑選最右邊的節點。

計算機組織 - 電腦概述

摩爾定律

每隔18~24個月，積體電路上可容納的電晶體個數便會增加一倍。
 

電腦系統的種類

• 桌上型電腦(Desktop computers)：一般泛用的個人電腦。
• 伺服器型電腦(Server computers)：涉及網路，追求高效能、高容量及高穩定性。
• 嵌入式電腦(Embedded computers)：嵌入於其他系統(如手機、電視)中的電腦，追求耗電與效能之間的平衡。

程式的處理階層：

軟體層面(Software)：
應用程式(Application software)：為了達成特定需求(如遊戲、圖片\影片編輯......等等)，由高階語言編成的軟體。
系統軟體(System software) ：負責管理及協調硬體階層，包括了作業系統及編譯器等等。
硬體層面(Hardware)：
囊括了處理器、記憶體，以及IO控制器等等。

程式語言的階層：

高階語言(High level language)：
貼近人類語言，容易閱讀及編寫，透過編譯器或直譯器轉換為機器碼。
組合語言(Assembly language)：
屬於低階語言，指令多與處理器直接對應，以文字來描述機器的行為，透過組譯器轉換為機械碼。
機器碼(Machine code)：
由0和1構成的處理器的指令集，電腦可以直接識別。

電腦的元件：

不論是嵌入式、伺服器，或是桌上型電腦，都包含了這5個主要部分：

• 輸入與輸出元件
• 記憶元件
• 控制元件
• 資料路徑(Data path)

效能評估

Response Time and Throughput

•  Response Time(反應時間)

又稱為elapsed time，表示要完成一件工作，所需花費的時間。其中包括了CPU time、I/O、OS overhead及閒置時間。

•  Throughput(生產能力)：在一定時間內，所能完成的工作量。

CPU time

即CPU處理給定的工作所花費的時間，可再細分為User CPU time(處理器在處理這分工作所花的時間)與System CPU time(作業系統為了執行這份工作額外的準備時間)
CPU time 可以這麼定義：

CPU Time = CPU Clock Cycles * Clock Cycle Time

= CPU Clock Cycles / Clock Rate

Clock cycle稱為時脈週期，時脈(Clock)就像電腦中的一個計數器，每當時脈走了一格，便是完成了一個時脈周期，而走這一格所花費的時間，即是Clock Cycle Time，因此CPU Time即是總共走了幾個時脈周期乘上每走一個時脈周期所要花費的時間。

因此，若要改善CPU Time，我們能從減少clock cycle，或是增加Clock Rate著手。

CPI

CPI (Cycle per instruction) ，表示每執行一個指令(Instruction)，所要花費的時脈周期

Clock Cycles =  Sigma(CPI_i * Instruction Count_i ),i from 1 to n.

Average CPI  = Clock Cycles/Instruction count

指令的個數由編譯器、ISA(ISA instruction set architecture)、程式與演算法共同決定。

CPU Power

Power = Capacitive load * Voltage² * Frequency

設計要追求高響應(Frequency)而低功耗(Power)，便須下調前兩者的影響，然而在2004年後，降低電壓與冷卻的技術飽和而停滯，在功率挑戰中形同撞上了一面高牆(Power wall)，為了執續強化處理器的效能，技術便轉往多核心發展。


然而純粹增加核心數並不完全相關於效能改善，即是說「在單核心中要執行100s的工作，在五核心的電腦並不會只要執行20s」，實際上，它要花費 36 秒，這個數字是由阿姆達爾定律所推得(80/5 + 20 = 36)，阿姆達爾闡明了：即便無限的增加處理器的個數，仍然存在一個加速上限。

Graph - 圖

1.如何定義一張圖：
 
圖(Graph)是由點(Vertex)與邊(Edge)構成，以G = (V,E)表示。