編譯 | bluemin
編輯丨陳彩娴
1
抽象
計算思維以設計問題的抽象模型為中心，應用計算步驟和高效算法解決問題——這一概念不僅服務于計算機科學（CS），而且逐漸滲透到科學和日常生活中。
「抽象」（Abstraction）是計算思維的核心，也是本文的主題。「抽象」一直是計算機科學的重要概念，在向廣大閱聽人教授計算機知識時，對計算思維的強調更是突顯了抽象的重要性。
在計算機科學中，抽象并不局限于實體現實，是以我們發現有用的抽象無處不在，例如「量子力學」。它有一種衍生的計算抽象，叫「量子電路」，從實體概念開始，催化出用于模拟的程式設計語言，以及利用其獨特功能的理論算法，有望在大型機器上實作。
計算機科學中的「抽象」往往包含以下内容：
資料模型包含一種或多種類型的資料以及資料之間可能存在的關系。例如，無向圖可以描述為由節點和邊組成，每條邊連接配接兩個節點。
某些程式設計語言不進行資料操作。這可能是一種傳統的程式設計語言，也可能隻進行一些特定的操作。這種語言總是有一個正式的語義——關于程式如何影響資料的規範。
是以，每個抽象模型都允許我們設計算法，以特定的方式操作資料。
我們的目标是設計「優質」、具有多項優勢的抽象模型。在設計解決方案時，抽象的難易程度是一項重要名額。例如，我們将在 3.1 節讨論關系模型如何導緻資料庫使用頻率的激增。生成的算法還有其他性能名額，例如串行或并行機器上的運作時間。同樣，我們傾向易于實作的抽象。最後，一些抽象提供了一種簡單的方法來衡量算法的效率（因為對于傳統程式設計語言，我們可以估計程式運作時間的上界），而其他抽象則要求我們即使是近似讨論算法的效率，也要先在較低層級進行實作。
1.1 編譯
有些抽象的層次太高，無法提供有意義的性能名額。是以，進階抽象的操作可能需要在較低的層級上實作。
實際上，在逐漸接近機器本身的層次上，可能存在多個抽象層次。如圖1所示，進階抽象（抽象1）的操作可以由較低級别的抽象（抽象2）實作，而較低級别的抽象又可以由更低級别的抽象（圖中未顯示）實作。有一些有趣的抽象層次将我們從進階程式帶到機器指令、實體硬體、邏輯門、半導體，最後到電子。不過，我們隻關注更高的層次。
圖1. 抽象層和算法層
使用抽象1的操作的算法被編譯為較低級别的抽象2中的算法。在本文中，我們使用的是普遍意義上的術語編譯器，不僅僅是《龍書》中重點介紹的程式設計語言的正常編譯器，還會使用将一個抽象的程式轉換為另一個程式的算法，這大概屬于較低級别的抽象。是以，在某些情況下，編譯過程很簡單，較進階别的每個操作都被較低級别的一個或多個特定操作所取代。在其他情況下，尤其是從傳統語言（比如C語言）到機器級語言編譯時，翻譯算法非常複雜。還有其他的一些情況，例如當進階抽象使用強大的代數運算（如線性代數或關系代數）時，優化是至關重要的，因為原始編譯通常會導緻算法比通過優化編譯生成的算法多花費幾個數量級的時間。
這可能是因為抽象2與機器層次太接近，是以具備有意義的性能名額。如果是這樣，抽象1可以繼承這些名額，為抽象1中編寫的算法提供優質概念。但是進階抽象通常可以在幾個不同的低級抽象中實作。每個低級抽象都可能提供一個完全不同的運作時間或其他度量的概念，是以在高層次上必然包含不同的算法優度概念。
1.2抽象的分類法
我們至少可以确定四種不同類型的抽象，可以根據它們的預期目标進行劃分。在構成本文主體的讨論中，我們将給出相應的例子并探讨它們的互相作用。
1.2.1. 基本抽象
與所有抽象一樣，基本抽象由資料模型和操作組成。這些抽象通常被認為是在面向對象程式設計語言中實作的抽象資料類型。但是基本抽象沒有操作的具體實作，也沒有表示資料的特定資料結構。人們也可以将這些抽象比作 Java 中的接口，但與接口不同的是，這些抽象對它們的操作具有預期的含義，而不僅僅表示操作的名稱。
研究基本抽象實際上有兩個截然不同的目的。在某些情況下，它們代表了值得單獨研究的常見操作，并且有多種實作方法。例如，我們在 1.4 節讨論字典（一個包含插入、删除和查找操作的集合）。這種類型的其他示例包括堆棧、隊列、優先級隊列，以及許多其他抽象。
其他抽象非常廣泛，可以支援應用程式的大型元件。常見的例子包括各種各樣的樹和圖，例如有向圖、無向圖、有标簽圖和無标簽圖。
這些抽象具有廣泛的操作集，可以通過各種方式組合。但是，這些操作本身并不是圖靈完備的。相反，它們被假定嵌入在圖靈完備的語言中，并建構了使用該模型的算法。例如，在圖抽象中，我們可能有一個操作，例如「查找相鄰節點」。在這個抽象之外，我們可以假設有一種程式設計語言允許在所有相鄰節點上進行疊代。這個操作的實作和圖本身的表示都沒有具體說明，是以我們沒有運作時間的具體概念。我們可以将這些抽象與面向對象程式設計語言中的典型類及其方法進行類比。差別在于類的方法在底層程式設計語言中有特定的實作。同樣，我們可以将諸如程式設計語言庫或 TeX 包之類的東西視為這種類型的抽象。
1.2.2 抽象實作
這些表示實作的方法，可能是一個或多個基本抽象的實作。這些語言本身并不是圖靈完備語言，通常可以被編譯成幾種不同的機器模型，例如，串行或并行機器，或者采用主記憶體或輔助記憶體的模型。每一個機器模型都提供了運作時間的概念，可以将其轉換為抽象實作的運作時間，然後轉換為支援的基本抽象的運作時間。
這一類型還包括自動機，如确定性或非确定性有限自動機（見第2.1.1和2.1.3節）和移位歸約解析器（見第2.2.1節）。
1.2.3 聲明性抽象
抽象最重要的用途之一是培養一種程式設計風格，隻需說明想做什麼，而不是如何去做。是以，我們發現許多不同的抽象，包括一個資料模型和一種比傳統語言更進階的程式設計語言；這些語言通常是某種代數。例如正規表達式（将在第2.1節中讨論）和關系代數（将在第3節中提到）。上下文無關文法（第2.2節）盡管不是嚴格意義上的代數，也是這類抽象的另一個例子。
這些抽象的特點是它們的編譯需要高度優化。對于傳統語言，好的優化可以使其在機器上的運作時間加快兩倍，而對于這些抽象，好實作和壞實作的運作時間之間可能存在數量級差異。另一個特點是聲明性抽象的程式設計語言不是圖靈完備的。任何圖靈完備語言的不可判定性屬性都将排除優化器的存在。優化器可以有效地、全面地處理程式想要做的事情，而無需被告知如何做。
1.2.4 計算抽象
與抽象實作相比，這些抽象接近于實體實作的機器。也就是說，沒有人會僅僅為了形成一個抽象實作而建構一台機器，但通常會實作計算抽象或易于轉換的東西。是以計算抽象提供了有意義的性能名額，即使它們不是100%準确。
你可能熟悉許多計算抽象，因為它們包括所有通用程式設計語言以及機器指令集。這種類型的其他抽象更具理論性，例如随機存取存儲器（RAM）模型或并行随機存取存儲器（PRAM）模型。在這裡，我們将在 1.7 節讨論一個強調二級存儲作用的傳統機器模型。我們還将讨論并行計算的抽象：3.5 節中的批量同步和 3.6 節中的映射規約模型（MapReduce）。
雖然許多計算抽象與傳統計算機有關，但也有一些例外。圖靈機就是其中之一，還有一些甚至不是圖靈完備的，但在計算機科學中發揮着重要作用。例如，在克勞德·香農的碩士論文之後，布爾電路和布爾代數是計算科學最早使用的抽象概念之一，而量子電路抽象則是最新的概念。
1.3 對抽象空間的探索
為了解抽象鍊的本質及其關系，接下來看一個基本抽象的常見示例：字典。
字典是抽象的一個常見示例，它具有許多替代實作，并說明了随着進階抽象被編譯為低級抽象而暴露出的一些問題。字典的資料模型包括以下内容：
一個全集 U。
全集 U 的子集 S，初始化時，S為空。
字典的「程式設計語言」由以下三種操作的直順序列組成：
插入(x)：如果U的元素x不在集合S中，則将其插入集合S中，即 S: = S ∪ 。
删除(x)：從集合S中去除元素x，S:= S – 。
查找(x)：如果元素x在集合S中傳回真，否則為假。
例如，字典可用于描述編譯器中符号表的行為。U将是程式設計語言的可能辨別符集。當編譯器掃描程式時，S将是一組辨別符，在程式中的每個點上都有定義好的含義。然而對于符号表，需要将資料附加到每個辨別符上，例如它定義的資料類型和出現的嵌套塊的級别（以便我們可以區分具有相同名稱的辨別符）。當編譯器找到一個聲明時，它會将聲明的辨別符插入集合S。當它到達程式或函數的末尾時，它會删除與該程式塊關聯的辨別符。在程式中使用辨別符時，編譯器會查找該辨別符并檢索其類型和其他必要資訊。
請注意，字典的程式設計語言相當簡單，不具備圖靈機的功能，也沒有真正的算法設計概念，因為「程式」隻是反映其他程序正在做什麼。同樣，也沒有真正的運作時間概念，因為不清楚每個操作需要多長時間。我們可以将每個操作定義為占用機關時間，但由于我們無法控制「程式」的長度，是以這個運作時間也沒有意義。
1.4 字典的實作
字典可以使用許多不同的抽象方法來實作。連結清單應該是大家非常熟悉的抽象實作，其資料模型包括以下内容：
單元格包含值（某個全集U的成員）和指向另一個單元格的連結（可能為空）。
标頭，簡單命名為指向單元格的連結（可能為空）。
假設讀者熟悉可以執行的典型操作，例如建立單元格或标頭、從清單中插入和删除單元格以及傳回包含在指定單元格中的資料。可以通過建立集合 S 中所有元素的連結清單來實作字典。将三個字典操作編譯為清單操作很簡單。
如果假設連結清單是在計算機的 RAM 模型中實作的，那麼我們就有了一個現實的運作時間概念。我們可以為清單單元格上的每個基本操作配置設定一個時間機關，因為在 RAM 上，每個操作都需要恒定的時間。這一觀察結果讓我們将運作時間的RAM概念提升到運作時間的連結清單概念，然後提升到字典級别。但這不是個好消息，平均而言，我們必須至少走到清單的一半，通常一直到最後，才能實作任何字典操作。是以，單個字典操作的運作時間與當時集合 S 的大小成正比。
另一種易于了解的實作字典的抽象類的方法是使用搜尋樹。當三個字典操作的算法保持樹平衡時，例如AVL 樹或紅黑樹，每個操作的運作時間與操作時集合 S 的大小是對數關系。但是通常首選的實作字典的抽象是哈希表。
1.5 哈希抽象
哈希的資料模型包括以下内容：
全集 U。
哈希桶數 B，從 0 到 B-1 編号。
從 U 到 的哈希函數 h。每個哈希桶 b 是全集 U 的元素 x 的子集，使得 h(x)=b。
通常的操作是計算h(x)，其中x是U的一個成員，并在編号為 h(x) 的哈希桶中插入、删除或查找 x。例如，哈希表的插入操作将表示為 h-insert (x, b)，其中 b = h(x)。哈希程式包括交替計算一些 h(x)，然後對 x 和哈希桶 h(x) 執行三個操作中的某一個。
将字典程式編譯成哈希程式很簡單。例如，字典操作insert (x) 被翻譯成b: = h (x); h-insert (x, b)。
哈希與機器的距離有些遠，我們無法直接使用它來确定運作時間。存在的問題是，哈希法相當獨特，因為最壞情況下的性能，即集合中的所有元素都在同一個哈希桶中，比我們對所有可能的哈希函數進行平均時的平均情況要差得多。為簡單起見，應該正确地假設，在平均情況下幾乎所有的哈希桶都包含接近平均數的元素，即S/B。但即使同意隻讨論平均情況，仍然不知道對一個元素和哈希桶的每個操作需要多長時間。
本質上，每個哈希桶本身就是一個小型字典，是以我們必須決定如何實作它的操作。如果 S 的大小保持在 B 的數量級，我們可以使用哈希桶的連結清單實作，并期望每個操作在 RAM 或真實機器上平均花費 O(1) 時間。但是，如果 S 比 B 大得多，則表示哈希桶的清單的平均長度為 O (S/B)。這仍然比每個操作的時間複雜度為O (S) 要好。然而，當 S 太大而無法放入主存時，RAM 模型不再适用，我們就需要考慮另一種計算抽象。
1.6 二級存儲抽象
作為 RAM 計算抽象的替代方案，在 O(1) 時間内可以通路任何資料片段，我們可以在多個級别引入通路局部性。我們将隻讨論一個具有基于磁盤的輔助記憶體的抽象，其中大資料塊（比如64KB）作為一個整體在磁盤和主存之間移動，且必須在主存中讀取或寫入資料。與在主存中對資料本身進行的典型操作的成本相比，在主存和輔助記憶體之間移動資料塊的成本高昂。是以，在這種新模型中，将運作時間簡單地視為磁盤I/O的數量是合理的，即一個資料塊從輔助記憶體移動到主存的次數，反之亦然。
在底層機器的二級存儲模型中，實作哈希表的最佳方法與使用 RAM 模型的首選方法有些不同。特别是，每個哈希桶将由一個或多個完整的磁盤塊組成。為了利用局部性，希望典型的哈希桶由盡可能少的磁盤塊組成，但希望盡可能使這些磁盤塊充滿。是以，假設主存能夠容納全集中的M個元素，而磁盤塊能夠容納P個這樣的元素。然後希望哈希桶的數量 B 為 B = M/P，那麼就可以在主存中為每個哈希桶儲存一個磁盤塊，并且該磁盤塊可能會近乎充滿。
随着集合S的大小增加，我們使用磁盤塊的連結清單來表示每個哈希桶，隻有第一個哈希桶在主存中。最壞的情況下，這三個字典操作需要檢查單個哈希桶中的所有磁盤塊。是以，平均而言，預計每個操作的磁盤I/O數為O(S/BP），因為S的元素将在B個哈希桶中大緻平均配置設定，将單個哈希桶的元素每隔P個劃分成一組，放入一個磁盤塊中。由于B=M/P，每個操作的運作時間為O（S/M）。
2
編譯器的抽象
現代編譯器将翻譯過程細化為多個階段，每個階段将源程式的一種表示形式轉換為另一種語義等價的表示形式，通常處于較低的抽象級别。編譯器中的階段通常包括詞法分析、句法分析、語義分析、中間代碼生成、代碼優化和目标代碼生成。所有階段共享的符号表用于收集和提供有關源程式中各種結構的資訊。前四個階段通常稱為編譯器的前端，後兩個階段稱為後端。
編譯器實作的進展涉及許多重要的抽象。我們将具體讨論三種這樣的抽象：正規表達式、上下文無關文法和流圖。前兩個是帶有有趣優化故事的聲明性抽象。第三個雖然不是聲明性的，但也帶來了有趣的實作挑戰。
2.1 正規表達式和句法分析
句法分析是編譯器的第一個階段，它将源程式讀取為一個字元序列，并将其映射為一個稱為标記的符号序列，然後傳遞到下一個階段，即文法分析器。
例2.1 如果源程式包含語句：華氏溫度=攝氏度*1.8+32，句法分析器可以将該語句映射為七個标記的序列：。這裡id是任何程式變量或辨別符的标記，運算符=、*、和+本身就是标記，這兩個常量分别被轉換為标記real和int。
編譯器構造方面的一大進步是建立了句法分析的生成器，一個像Lex這樣的程式，将标記的描述作為輸入，生成一個程式，将源程式分解為标記，并傳回與源程式對應的标記序列。使Lex得以應用的抽象是正規表達式。像Lex這樣使用正規表達式抽象的系統使用了許多有用的速記，使編寫正規表達式更為簡單，但不會更改可以在此抽象中定義的字元串集。
例2.2 在某些程式設計語言中，作為合法辨別符的字元串集可以定義如下：
letter = [a-zA-Z]
digit = [0-9]
id = letter (letter+digit)*
在這個簡寫法中，像a-z這樣的表達式表示 a 到 z 之間帶有ASCII 碼的單字元串的并集。是以字母的正規表達式在最初的三個運算符集合中：
a+b+...+z+A+B+...+Z
類似地定義數字，然後将标記的字元串集定義為字母後跟0個或多個字母和/或數字串組成的字元串。
2.1.1 Lex程式産生之前：書目檢索
從理論研究中可以很好地了解，正規表達式抽象可以編譯成幾種抽象實作之一，例如确定性或非确定性有限自動機（NFA和DFA）。然而，當需要解決實際問題時，仍有一些技術有待突破。
貝爾實驗室在首次嘗試自動搜尋相關文獻時采取了一個有趣的步驟：他們在錄音帶上儲存了整個貝爾實驗室圖書館的标題，并且開發了軟體來擷取關鍵字清單、找到包含這些關鍵字的文檔。然而，當給定一長串關鍵字時，搜尋速度很慢，因為它每搜尋一個關鍵字就會周遊一次錄音帶。
Aho-Corasick算法對此做了改進，與單獨搜尋每個關鍵字不同，關鍵字清單被視為包含任何關鍵字出現的所有字元串集的正規表達式，即：
請注意，點是「任何字元」的擴充名。該表達式被轉換為确定性有限自動機。無論涉及多少關鍵字，都可以在錄音帶上進行一次傳遞。每個标題由有限自動機檢查一次，以檢視是否在其中找到了任何關鍵字。
2.1.2 句法分析的生成器設計
本質上，Lex之類的句法分析的生成器與第2.1.1節展現的思想異曲同工。為每個标記編寫正規表達式，然後對這些表達式應用聯合運算符。該表達式被轉換為确定性有限自動機，讀取字元，直到找到與标記比對的字元串字首，然後删除從輸入中讀取的字元，将該标記添加到輸出流中，并重複該過程。
還有一些額外的考慮，因為與關鍵字不同，标記之間可能存在一些複雜的互動。例如，雖然看起來像一個辨別符，但它實際上是一個用于程式中控制流的關鍵字。是以，當看到這個字元序列時，詞法分析器必須傳回标記，并非。在 Lex 中，正規表達式在其輸入檔案中列出的順序打破了諸如此類的歧義，是以所要做的就是在辨別符之前列出關鍵字，確定關鍵字被正确區分，而不是被當作辨別符。另一個問題是某些标記可以是另一個标記的字首。如果輸入的下一個字元是 =，我們不希望将
2.1.3 DFA的惰性評估
還有一種可以使用正規表達式抽象來提高算法的運作時間的優化方法——惰性評估。
你可能熟悉将正規表達式轉換為确定性有限自動機的标準方法。正規表達式首先通過 McNaughton-Yamada 的算法轉換為非确定性有限自動機。這種轉換很簡單，如果正規表達式的長度為 n，則生成最多具有 2n 個狀态的 NFA。将NFA轉換為DFA時，開始困難重重，這需要Rabin-Scott子集構造。在最壞的情況下，這種構造可以将具有2n個狀态的NFA轉換為具有個狀态的DFA，這實際上是不通的。在實踐中，最壞的情況發生的機率很小。
然而，在正規表達式的其他應用中，可能并且确實會出現接近最壞情況的情形。grep 是最早的 UNIX 指令之一，代表「擷取正規表達式并列印」。該指令将接受一個字元串并确定它是否具有給定正規表達式語言的子字元串。最簡單的實作是将正規表達式轉換為 NFA，然後再轉換為 DFA，讓 DFA 讀取字元串。當DFA較大時，将NFA轉換為DFA比掃描字元串要耗費更多的時間。
但是，當正規表達式僅用于一次掃描字元串時，有更有效的方法來實作指令，例如 grep。Ken Thompson 的第一篇研究論文表明，與其将小型 NFA 轉換為大型 DFA，不如直接模拟 NFA 更有效。也就是說，讀取字元串的 NFA 通常在讀取每個字元後處于一組狀态中。是以，隻需在每個字元之後跟蹤這些 NFA 狀态，并在讀取下一個字元時，從前一組狀态建構該字元可到達的狀态集。
通過 NFA 到 DFA 的惰性轉換可以實作更高的效率。也就是說，每次讀取一個字元的輸入字元串，然後将到目前為止所讀取的字首實際産生的 NFA 狀态集制成表格。這些 NFA 狀态集對應于 DFA 狀态，是以我們隻建構處理此特定輸入字元串所需的 DFA 轉換表部分。如果給定正規表達式的 DFA 不太大，完成處理字元串之前将建構大部分或全部的DFA，會獲得直接使用 DFA 的好處，而不是在字元串的每個字元後構造NFA狀态集。但是如果DFA比字元串大，大部分的DFA永遠不會被構造，是以我們會充分利用這兩種情況。這項改進是在名為 egrep 的 grep 版本中實作的。
圖2. 表達式 a + b * c 的文法樹
2.2 上下文無關文法和文法分析
編譯器的第二個階段，文法分析器或「解析器」将詞法分析器生成的标記序列映射為樹狀表示，進而明确标記序列中的文法結構。一種典型的表示是文法樹，其中每個内部節點代表某個結構，該節點的子節點代表該結構的元件。
例2.3 文法分析器可以将标記序列 a+b*c 映射成如圖2所示的文法樹。這裡，E代表一個表達式。操作數a、b和c本身就是表達式。但b*c也是一個表達式，由運算符标記*和兩個表達式b和c組成。在根部，我們看到另一個表達式，這個表達式使用運算符+和兩個操作數表達式a和b*c。
遵守有關運算符優先級的許多約定很重要。通常，乘法優先于加法，這就是為什麼文法樹在加a之前将b乘以c，而不是先将a和b相加。
給定程式設計語言所需的文法樹結構通常由聲明性抽象定義，即上下文無關文法（context free grammar，CFG），希望讀者熟悉此概念。CFG 是稱為産生式規則的集合，提供了從其他句法類别和終端（句法分析器生成的标記）構造各種文法類别（如表達式或語句）的方法。例如，如果 E 表示該語言的良構表達式的文法類别，那麼我們可能會找到如下規則：，這意味着一種構造表達式的方法是在兩個較小的表達式之間放置一個加号。
2.2.1 LR(k)文法分析
在20世紀60年代，有一系列關于如何從CFG構造高效文法分析器的提議。人們認識到，對于通用程式設計語言，隻要文法具有某些屬性，就可以對程式進行一次從左到右的掃描，而無需回溯，并根據該語言的文法建構文法樹。
有些決定很棘手。例如，在處理表達式a+b*c時，僅讀取a+b後，必須決定是否将表達式a和b與加号組合成更大的表達式。如果向前看一個标記并看到*，就會知道把a和b結合起來是不正确的，但必須繼續前進，最終把b和c結合起來。隻有在此基礎上，把a和表達式b*c結合起來才是正确的。
這種文法分析方式稱為「移位-歸約解析」。在掃描輸入時，每一步都需決定是通過将下一個輸入标記推入堆棧來移動它還是對堆棧頂部的符号進行歸約。歸約時，歸約的符号必須在CFG的右側。這些符号出棧後被替換到同一産生式的左側。此外，為産生式左側的符号建立文法樹節點。它的子節點是剛剛出棧的符号對應的樹根。如果一個标記出棧，它的樹隻是一個節點，但如果一個文法類别出棧，那麼它的樹就是之前為堆棧上的符号構造的樹。
Don Knuth提出了LR(k)文法分析，适用于最普遍的文法類别，對輸入進行單次從左到右掃描，使用移位-歸約範式并檢視輸入前面的最多k個符号後可以正确解析。這項工作似乎解決了文法分析器應該如何構造的問題。然而，并非每個CFG，甚至每個典型程式設計語言的CFG，都滿足成為任何 k 的 LR(k) 文法所必需的條件。雖然普通程式設計語言似乎确實有LR(1)文法，即僅使用輸入上的一個先行符号就可以進行移位-歸約分析的文法，但這些文法的設計相當複雜，通常比直覺需要的文法類别多出一個數量級。
2.2.2 Yacc文法分析的生成器
是以，在 Knuth 的論文之後，有幾次嘗試尋找使用 LR(1) 解析的方法，但要使其适用于更簡單的 CFG。我們受到普林斯頓大學的一位研究所學生 Al Korenjak 的啟發，他的論文是關于壓縮 LR(1) 解析器的方法。我們茅塞頓開，對于通用語言，可以從一個非LR(1)的文法開始，仍然為該文法建構一個從左向右的移位-歸約解析器。當文法不是LR(1)形式時，在某些情況下，我們也可以使用兩種不同的産生式進行歸約和移位或隻進行歸約。但是我們可以通過考慮運算符的優先級并在輸入中向前看一個标記來解決實際情況中的歧義。
例2.4 考慮例2.3中所提及的情況。在處理輸入a+b*c的a+b之後，堆棧的頂部将有E+E，其中a和b之前都被簡化為表達式。存在産生式 E E + E，可以将 E + E 歸約成一個 E，并用标簽 E 和子式 E、+ 和 E 建構解析樹的一個節點。但是 * 優先級高于+， 我們看到 * 作為下一個輸入符号，這說明将 * 移到堆棧上是正确的。稍後，我們也移動 c 并将 c 歸約為表達式 E。此時堆棧頂部有 E + E * E。我們正确地将前三個符号歸約成 E，留下 E + E。現在，将這些符号歸約成 E 是正确的，因為沒有任何内容輸入（或者還有其他不屬于表達式部分的輸入，例如結束語句的分号）。通過這種方式，我們将生成如圖 2 所示的文法樹。
我們在貝爾實驗室的同僚 Steve ohnson 采納了這個想法并實作了一個名為 Yacc的文法分析的生成器。為了幫助解決移位和歸約操作之間的歧義，或者兩個不同産生式的歸約之間的歧義，Yacc 根據産生式出現的順序進行判斷。在兩個産生式都可以歸約的情況下，無論哪個産生式首先出現都是首選的。為了解決移位和歸約之間的沖突，假設在 Yacc 輸入檔案中首先出現的運算符優先。
Yacc很快成為了編譯器實作的重要工具，編譯器不僅指傳統程式設計語言的編譯器，而且包含許多用途更有限的“小衆語言”的編譯器。與 Lex 一起，Yacc 提供了一種試驗新語言句法結構設計的簡單方法。這兩種工具貫穿學術界整個學期的編譯器課程，學生在課程中設計并實作一種新的領域特定程式設計語言。
3
大規模資料抽象
我們需要幾種新的抽象來考慮最大的可用資料集和可用于操作它們的算法。第1.6節的二級存儲模型很重要，但也存在其他表示各種形式的并行和分布式計算的抽象。我們将在這裡概述最相關的抽象。
3.1 資料的關系模型
首先，Codd 的關系模型已被證明是處理大規模資料的核心。簡而言之，資料被組織為表或關系的集合，其中兩個示例如圖 3 所示。左側是一個名為 Cities 的關系，它有兩列：City 和 State。關系的模式是它的名稱和列名清單，在本例中為 Cities (City, State)。關系本身是表格中一組行資料或元組。例如，(Toronto, Ontario)是關系 Cities 的其中一行記錄。第二種關系稱為States，它有名為 State、Country 和 Pop（該州的人口，以百萬計）的列。
圖3. 兩種關系：Cities (City, State) and States (State, Country, Pop)。
為關系模型選擇程式設計語言是一件趣事。Codd 可以将關系模型視為嵌入在通用語言中的基本抽象，如樹或圖。關系語言的操作是簡單的導航步驟，例如「在給定的行和列中查找值」或「給定一行，查找下一行」。事實上，早期的資料庫抽象，例如網絡和層次模型，正是采用這種方法。但Codd的觀點是一種聲明性的抽象，随着程式設計語言的發展，這種選擇一直在跟進，有助于使關系模型成為資料庫管理的主要方法。
在最初的表述中，關系模型的程式設計語言被認為是非遞歸的一階邏輯，或者等價于五種代數運算的集合，即并集、差集、選擇、投影和連接配接，稱為關系代數。最後三種運算可能比較生疏，定義如下：
選擇：在關系R的列名上采用條件C，并傳回滿足條件C的R行。例如，如果将條件「Country=India」應用于圖3中的關系狀态，會得到一個新的關系，它的列名為State、Country和Pop，但隻包含第二行和第六行狀态。
投影：為一個關系擷取一組列名，并生成一個具有相同行集的新關系，但隻包含擷取的列。
連接配接：接受兩個關系和一個涉及兩個關系的列名的條件 C，并通過以下方式生成一個新關系：1）考慮到每一對行，每個關系中的某兩行；2）如果這兩行中的值滿足條件 C，則将兩行合并後添加到結果關系中。
3.2 SQL抽象
關系模型提出後不久，程式設計語言SQL的開發就向前邁出了一大步。在最初的表述中，SQL仍然不是圖靈完備語言。然而，它确實支援比原始關系模型更多的功能。底層資料模型支援集合和包，同一行可以出現多次，還可以根據一列或多列的值對關系中的行進行排序。除了前面描述的關系代數操作符之外，SQL還支援分組和聚合，允許程式員根據一個或多個屬性中的值對關系的行進行分組，然後對每組中一列或多列的值進行聚合，例如求和或求平均值。
例 3.2 考慮圖 3 中的關系 States。我們可以按 Country 列的值對行進行分組，然後對每個國家/地區的各州人口求和。結果表如圖 4 所示。
圖 4. 按Country分組并對 Pop 求和。
随着SQL的發展，更多的功能被納入标準，包括編寫遞歸程式的能力，以及在通用程式設計語言中調用代碼的能力。是以，原則上，SQL現在是圖靈完備的。但絕大多數SQL程式都沒有使用使其圖靈完備的特性，是以在實踐中，仍然有可能以一種利用許多優化機會的方式編譯SQL，而這種優化就是我們所說的聲明性抽象。
3.3 SQL編譯
用 SQL 編寫的程式通常被編譯成低級語言，例如 C語言。C 代碼大量使用庫函數，例如執行選擇或連接配接等操作。SQL編譯的早期階段（詞法分析和句法分析等）與任何通用語言的編譯階段相似。SQL與規範的不同之處在于代碼優化階段（通常稱為查詢優化）。回想一下，諸如 C 這類語言的優化必須滿足在各處儲存機器指令，是以将速度提高兩倍是一個較好的優化結果。但是SQL和關系模型的操作通常比機器指令強大得多。例如，文法樹的一個操作符可以連接配接兩個巨大的關系。
是以，與C程式或其同類程式相比，SQL程式由相對較少的步驟組成，但如果按原樣實作，這些步驟可能會花費大量時間。是以，SQL 的編譯器通常會幾乎窮盡搜尋等效的文法樹，進而減少幾個數量級的執行時間。即使花費與SQL程式大小成指數關系的時間來優化一個隻執行一次的程式也是有意義的，因為這個程式通常會在較大的關系上執行。
3.4 分布式計算抽象
多年來，人們已經認識到單處理器的能力正在達到極限。為了處理越來越大的資料集，有必要開發使用多台獨立機器的算法。許多引發我們思考的分布式計算算法的抽象已經實作，并且正在被重點使用。
總的來說，這些抽象有一些共同的特點：
它們的資料模型是傳統程式設計語言的模型，但資料分布在許多不同的任務中，我們稱之為「計算節點」。實際上，多個任務可能在同一個處理器上執行，但将這些任務視為處理器本身便于分析問題。
程式也用正常語言編寫，但同一程式可以在各個節點上同時運作。
有一種裝置可供節點與其他節點通信。這種通信分階段進行，并與計算階段交替進行。
這類抽象有幾個不同的性能名額值得關注。顯而易見的一點是并行執行所有節點上涉及的程式所需的挂鐘時間。但有時，瓶頸在于節點之間通信所需的時間，尤其當需要在節點之間共享大量資料時。第三個運作時間問題是算法的輪數（一個計算階段後接一個通信階段）。
3.5 批量同步抽象
Valiant 的批量同步模型是一種流行的抽象，我們不再詳細讨論。該模型最近在 Google 的 Pregel 系統的計算叢集環境中得到普及，并已經擁有了許多類似的實作。
在批量同步模型中，計算節點可以被視為完整圖的