[TOC] 原文地址：[linux--Flex and Bison](https://blog.csdn.net/qq_38880380/article/details/99447017#121_flex_8) # 1 介紹 ## 1.1 概述 * Flex and bison就是lex and yacc的升級版。Lex 代表 Lexical Analyzar。Yacc 代表 Yet Another Compiler Compiler。 * Flex和bison是兩個用來生成程序的工具，它們生成的程序分別叫做詞法分析器和語法分析器。  * Flex生成的詞法分析器將輸入拆分成一個個記號（token），bison生成的語法分析器根據已有的規則，分析這些token的組合，是否符合語法規范。 ## 1.2 理解 ### 1.2.1 flex > flex用于分詞，它比較好理解 > flex的規則文件以.l為后綴名，生成的文件為lex.yy.c > 規則文件分為3個部分，每個部分之間用%%分割 * 聲明部分 聲明部分可以進行聲明和選項設置 另外，如果有被%{和%}包圍的部分，里面的內容會被完整地復制到 lex.yy.c 的開頭，通常會用來放置include、define的信息 例如： %{ #include %} * 規則部分 這部分主要描述規則，格式是： 正則表達式 {匹配到之后執行的C代碼} 例如： \[0-9\] {printf(“NUMBER %s\\n”,yytext);} 行首不可留白 * C代碼部分 這部分是C代碼，它們會被復制到 lex.yy.c的最末 通常用于一些未定義接口的定義，例如 int yywrap() { return 1; } ### 1.2.2 bison > bison的規則文件以.y為后綴，生成的文件為 xxx.tab.c和xxx.tab.h > 規則文件也分為3個部分 * 聲明部分和C代碼部分 和flex一樣，可以進行聲明和選項設置，C代碼則是拷貝到文件末 聲明部分同時也可以寫%{%} 在這之后，一般還要進行token設置 token用于標記語法解析中用到的基本語素，教程里稱之為“記號”，語法是： %token 記號 例如 %token NUMBER 一行可以聲明多個記號，例如 %token ADD SUB MUL DIV 記號大概就是每個語法樹的節點，比如一個變量、一個數字/字符串常量、一個運算符 這些記號將被用于規則部分 通常是：flex中匹配到某個詞，然后{return NUMBER;}返回一個記號，然后在bison的規則中查找應該進行的動作 * 規則部分 ## 1.3 應用 * 桌面計算器bc * 工具eqn和pic，用于數學方程式和復雜圖片的排版預處理器 * 用于特定應用設計的大量領域特定語言 * PCC，在許多unix系統中被使用的可移植的C編譯器 * flex自身 * SQL數據庫語言翻譯器 ## 1.4 編譯器的定義與需求 * 編譯器是將一種程序語言（源程序：source language）翻譯為另一種程序語言（目標程序：target language）的計算機程序。一般來說，源程序為高級語言，而目標語言則是匯編語言或機器碼。 * 早期的計算機程序員們用機器碼寫程序，編程十分耗時耗力，也非常容易出錯，很快程序員們發明了匯編語言，提高了編程的速度和準確度，但編寫起來還是不容易，且程序嚴格依賴于特定的機器，很難移植和重復利用。 * 上世紀50～60年代，第一批高級語言及編譯器被開發出來，程序的文法非常接近于數學公式以及自然語言，使得編寫、閱讀和維護程序的難度大為降低，程序編制的速度、規模和穩定性都有了質的飛躍。 * 可以說是編譯器的產生帶來了計算機行業的飛躍發展，所以開發編譯器是非常有必要的。 # 2 詞法分析與語法分析 ## 2.1 詞法分析 ### 2.1.1 基本概念 > 詞法分析也稱為 分詞 ，此階段編譯器從左向右掃描源文件，將其字符流分割成一個個的 詞 （ token 、 記號 ）。所謂 token ，就是源文件中不可再進一步分割的一串字符  一般來說程序語言中的 token 有：常數（整數、小數、字符、字符串等），操作符（算術操作符、比較操作符、邏輯操作符），分隔符（逗號、分號、括號等），保留字，標識符（變量名、函數名、類名等）等。如： * 3 和 255 是整數常數 token * “Fred” 和 “wilma” 是字符串 token * numTickets 和 queue 是標識符 token * while 是 T\_WHILE token 上述的 3 、 “Fred” 和 while 等稱為 token 的 字面值 。有些類別的 token 只有一個字面值，如保留字和分隔符類的 token，其他類別的 token 則有不同字面值，如整數常數 token 。下面是一些典型的 token 及其字面值： ~~~ TOKEN-TYPE TOKEN-VALUE ----------------------------------------------- T_IF if T_WHILE while T_ASSIGN = T_GREATTHAN > T_GREATEQUAL >= T_IDENTIFIER name / numTickets / ... T_INTEGERCONSTANT 100 / 1 / 12 / .... T_STRINGCONSTANT "This is a string" / "hello" / ... ~~~ 編譯器中的 token 中一般用一個 struct 來表示： ~~~ typedef enum { T_IF, T_WHILE, T_ADD, T_INTCONSTANT, T_STRINGCONSTANT, T_IDENTIFIER, ... } TokenType; typedef struct _Token { TokenType type; union { char *stringval; int *intval; double *doubleval; } value; } TokenRecord; ~~~ 詞法分析器每掃描到一個完整的 token 后，立即 新建一個 TokenRecord ，將此 token 的類型記錄在此結構的**type**域中，將其字面值記錄在**value**域中對應的子域內，并將此 TokenRecord 結構傳遞給下一階段的語法分析模塊使用，然后接著掃描下一個 token 。這樣從語法分析模塊的角度來看，源程序就變成了一個連續的 token stream 了。 ### 2.1.2 分詞方法 > 分詞掃描的方法有直接掃描法和正則表達式匹配掃描法 #### 2.1.2.1 直接掃描法 * 直接掃描法的思路非常簡單，每輪掃描，根據第一個字符判斷屬于哪種類型的 token 然后采取不同的策略掃描出一個完整的 token ，再接著進行下一輪掃描。 * 直接掃描法思路簡單，代碼量非常少。但缺點是速度慢，對標識符類型的 token 需要進行至少 2 次掃描，且需進行字符串查找和比較。而且不容易擴展，只適用于語法簡單的語言。目前一般的編譯器都是采用基于正則表達式匹配的分詞掃描法。 #### 2.1.2.2 正則表達式 正則表達式一般都采用一些簡寫的方式，最常見的有： * 特殊字符 以下 11 個字符： ~~~ * [ ] ^ $ . | ? * + ( ) ~~~ 被保留作特殊用途，如果想使用這些字符的字面值，需要在前面加反斜杠 “\\” 轉義。另外，一些不便書寫的字符可以通過在前面加 “\\” 轉義，如 \\n 和 \\t 分別表示換行符和制表符。 * 字符集 如： \[abferx\] ，用方括號括起來的字符，表示匹配這些字符中的其中一個，相當于 (a|b|f|e|r|x) 。方括號內的特殊字符不需要轉義（ \[ \] - ^ 除外），如 \[af({\] 表示 匹配 “a”, “f”, “{”, “(” 中的其中一個。方擴號內可以使用 “-“ 來定義一個范圍，且可以定義多個范圍，如 \[0-9\] 表示匹配單個數字， \[a-zA-Z\] 表示匹配單個字母。 * 取反字符集 如： \[^abc\] ，在方括號內的第一個字符為 ^ ，表示這是一個取反字符集，表示匹配一個不在方括號內部的字符。 * \*、?和+ \* 表示匹配前面的字符（或者由括號括起來的表達式、方括號括起來的字符集）0次或多次； ? 表示匹配前面的字符（或者由括號括起來的表達式、方括號括起來的字符集）0次或1次； \+ 表示匹配前面的字符（或者由括號括起來的表達式、方括號括起來的字符集）1次或多次。 * ”.” 通配符 . 表示匹配除換行符外的任意字符一次。 正則表達式可以用來表示源程序中的 token ，如： 整數 ： \[0-9\]+ 小數 ： \[0-9\]+.\[0-9\]\* 字符串 ： \\”\[^\\”\]*\\” 標識符 ： \[\_a-zA-Z\]\[\_a-zA-Z0-9\]* 關鍵字 if ： if ### 2.1.3 有限狀態自動機（FA） * 有限狀態自動機（finate automaton）是用來判斷字符串（句子）是否和正則表達式匹配的假想機器，它有一個字母表 Σ 、一個狀態集合 S ，一個轉換函數 T ，當它處于某個狀態時，若它讀入了一個字符（必須是字母表里的字符），則會根據當前狀態和讀入的字符自動轉換到另一個狀態，它有一個初始狀態，還有一些所謂的接受狀態。 * 它的工作過程是：首先自動機處于初始狀態，之后它開始讀入字符串，每讀入一個字符，它都根據當前狀態和讀入字符轉換到下一狀態，直到字符串結束，若此時自動機處于其接受狀態，則表示該字符串被此自動機接受。如下圖：  * 上圖中圓圈表示各種狀態，各箭頭及簽頭上的字符表示狀態的轉換表，自動機只有一個初始狀態，用一個不含字符的箭頭指向此狀態，可以認為此為自動機的入口，自動機可以有一個或多個接受狀態，用雙圓圈表示。上圖中的自動機的字母表為 {a, b}，初始狀態為 S1 ，當它讀入一個 a 后，就轉到狀態 S2 ，若讀入的是 b ，則轉到 S4，然后一個接一個字符的轉換其狀態，若字符結束時自動機處在其接受狀態，則表示此字符串被其接受。經過觀察可知，此圖中的自動機能接受的字符串為 “ab”, “abb”, “abbb”, … ，也就是說，**此自動機與正則表達式 ab+ 是等價的**。 * 簡單的有限狀態自動機可以通過 與、連接和重復 搭建出復雜的自動機。數學家們已經證明了：任何一個正則表達式都有一個等價的有限狀態自動機，任何一個有限狀態自動機也有一個等價的正則表達式。 * 可以看出有限狀態自動機的判斷速度是非常快的，它只要求對字符串掃描一遍就可以了，顯然比直接掃描法要快多了。 * 總而言之，正則表達式的匹配判斷可以通過構造有限狀態自動機來進行，以上僅介紹了構造有限狀態自動機的大體思路：先構造基本的自動機，再根據正則表達式的結構搭建出復雜的自動機。構造有限狀態自動機的具體算法十分復雜，這里不再深入介紹了，還是借用前人已經做好的工具吧，下面，將介紹如何使用 flex 來進行基于正則匹配的詞法分析。 ### 2.1.4 用 flex 做詞法分析 #### 2.1.4.1 介紹 flex 是一個快速詞法分析生成器，它可以將用戶用正則表達式寫的分詞匹配模式構造成一個有限狀態自動機（一個C函數），目前很多編譯器都采用它來生成詞法分析器。 #### 2.1.4.2 用法 * 安裝 flex ~~~ sudo apt-get install flex 或者下載相應版本的安裝文件安裝 ~~~ * 然后新建一個文本文件，輸入以下內容： ~~~ %% [0-9]+ printf("?"); # return 0; . ECHO; %% int main(int argc, char* argv[]) { yylex(); return 0; } int yywrap() { return 1; } ~~~ 將此文件另存為 hide-digits.l 。注意此文件中的 %% 必須在本行的最前面（即 %% 前面不能有任何空格）。 * 之后，在終端輸入： ~~~ flex hide-digits.l ~~~ * 此時目錄下多了一個 “lex.yy.c” 文件，把這個 C 文件編譯并運行一遍： ~~~ gcc -o hide-digits lex.yy.c ./hide-digits ~~~ * 然后在終端不停的敲入任意鍵并回車，可以發現，敲入的內容中，除數字外的字符都被原樣的輸出了，而每串數字字符都被替換成 ? 了。最后敲入 # 后程序退出了。如下： ~~~ eruiewdkfj eruiewdkfj 1245 ? fdsaf4578 fdsaf? ... # ~~~ * 當在命令行中運行 flex 時，第二個命令行參數（此處是 hide-digits.l ）是提供給 flex 的分詞模式文件， 此模式文件中主要是用戶用正則表達式寫的分詞匹配模式，用flex 會將這些正則表達式翻譯成 C 代碼格式的函數 yylex ，并輸出到 lex.yy.c 文件中，該函數可以看成一個有限狀態自動機。 * 當在命令行中運行 flex 時，第二個命令行參數（此處是 hide-digits.l ）是提供給 flex 的分詞模式文件， 此模式文件中主要是用戶用正則表達式寫的分詞匹配模式，用flex 會將這些正則表達式翻譯成 C 代碼格式的函數 yylex ，并輸出到 lex.yy.c 文件中，該函數可以看成一個有限狀態自動機。 * 下面再來詳細解釋一下 hide-digits.l 文件中的代碼，首先第一段是： ~~~ %% [0-9]+ printf("?"); # return 0; . ECHO; %% ~~~ * flex 模式文件中，用%% 和 %%做分割， 上面分割的內容被稱為 規則（rules），本文件中每一行都是一條規則，每條規則由 匹配模式（pattern） 和 事件（action） 組成， 模式在前面，用正則表達式表示，事件在后面，即 C 代碼。每當一個模式被匹配到時，后面的 C 代碼被執行。 * flex 會將本段內容翻譯成一個名為 yylex 的函數，該函數的作用就是掃描輸入文件（默認情況下為標準輸入），當掃描到一個完整的、最長的、可以和某條規則的正則表達式所匹配的字符串時，該函數會執行此規則后面的 C 代碼。如果這些 C 代碼中沒有 return 語句，則執行完這些 C 代碼后， yylex 函數會繼續運行，開始下一輪的掃描和匹配。 * 當有多條規則的模式被匹配到時， yylex 會選擇匹配長度最長的那條規則，如果有匹配長度相等的規則，則選擇排在最前面的規則。 ~~~ int main(int argc, char *argv[]) { yylex(); return 0; } int yywrap() { return 1; } ~~~ * 第二段中的 main 函數是程序的入口， flex 會將這些代碼原樣的復制到 lex.yy.c 文件的最后面。最后一行的 yywrap 函數， flex 要求有這么一個函數。 #### 2.1.4.3 示例 * word-spliter.l ~~~ %{ #define T_WORD 1 int numChars = 0, numWords = 0, numLines = 0; %} WORD ([^ \t\n\r\a]+) %% \n { numLines++; numChars++; } {WORD} { numWords++; numChars += yyleng; return T_WORD; } <<EOF>> { return 0; } . { numChars++; } %% int main() { int token_type; while (token_type = yylex()) { printf("WORD:\t%s\n", yytext); } printf("\nChars\tWords\tLines\n"); printf("%d\t%d\t%d\n", numChars, numWords, numLines); return 0; } int yywrap() { return 1; } ~~~ 本例中使用到了 flex 提供的兩個全局變量 yytext 和 yyleng，分別用來表示剛剛匹配到的字符串以及它的長度 * 編譯執行 ~~~ flex word-spliter.l gcc -o word-spliter lex.yy.c ./word-spliter < word-spliter.l 輸出： WORD: %{ WORD: #define ... WORD: } Chars Words Lines 470 70 27 ~~~ 可見此程序其實就是一個原始的分詞器，它將輸入文件分割成一個個的 WORD 再輸出到終端，同時統計輸入文件中的字符數、單詞數和行數。此處的 WORD 指一串連續的非空格字符。 * 擴展 （1） 列出所需的所有類型的 token； （2） 為每種類型的 token 分配一個唯一的編號，同時寫出此 token 的正則表達式； （3） 寫出每種 token 的 rule （相應的 pattern 和 action ）。 第 1 類為單字符運算符，一共 15 種： ~~~ + * - / % = , ; ! < > ( ) { } ~~~ 第 2 類為雙字符運算符和關鍵字，一共 16 種： ~~~ <=, >=, ==, !=, &&, || void, int, while, if, else, return, break, continue, print, readint ~~~ 第 3 類為整數常量、字符串常量和標識符（變量名和函數名），一共 3 種。 * 拓展后 ~~~ %{ #include "token.h" int cur_line_num = 1; void init_scanner(); void lex_error(char* msg, int line); %} /* Definitions, note: \042 is '"' */ INTEGER ([0-9]+) UNTERM_STRING (\042[^\042\n]*) STRING (\042[^\042\n]*\042) IDENTIFIER ([_a-zA-Z][_a-zA-Z0-9]*) OPERATOR ([+*-/%=,;!<>(){}]) SINGLE_COMMENT1 ("//"[^\n]*) SINGLE_COMMENT2 ("#"[^\n]*) %% [\n] { cur_line_num++; } [ \t\r\a]+ { /* ignore all spaces */ } {SINGLE_COMMENT1} { /* skip for single line comment */ } {SINGLE_COMMENT2} { /* skip for single line commnet */ } {OPERATOR} { return yytext[0]; } "<=" { return T_Le; } ">=" { return T_Ge; } "==" { return T_Eq; } "!=" { return T_Ne; } "&&" { return T_And; } "||" { return T_Or; } "void" { return T_Void; } "int" { return T_Int; } "while" { return T_While; } "if" { return T_If; } "else" { return T_Else; } "return" { return T_Return; } "break" { return T_Break; } "continue" { return T_Continue; } "print" { return T_Print; } "readint" { return T_ReadInt; } {INTEGER} { return T_IntConstant; } {STRING} { return T_StringConstant; } {IDENTIFIER} { return T_Identifier; } <<EOF>> { return 0; } {UNTERM_STRING} { lex_error("Unterminated string constant", cur_line_num); } . { lex_error("Unrecognized character", cur_line_num); } %% int main(int argc, char* argv[]) { int token; init_scanner(); while (token = yylex()) { print_token(token); puts(yytext); } return 0; } void init_scanner() { printf("%-20s%s\n", "TOKEN-TYPE", "TOKEN-VALUE"); printf("-------------------------------------------------\n"); } void lex_error(char* msg, int line) { printf("\nError at line %-3d: %s\n\n", line, msg); } int yywrap(void) { return 1; } ~~~ 上面這個文件中，需要注意的是，正則表達式中，用雙引號括起來的字符串就是原始字符串，里面的特殊字符是不需要轉義的，而雙引號本身必須轉義（必須用 \\” 或 \\042 ），這是 flex 中不同于常規的正則表達式的一個特性。 除單字符運算符外的 token 的編號則在下面這個 token.h 文件，該文件中同時提供了一個 print\_token 函數，可以根據 token 的編號打印其名稱。 ~~~ #ifndef TOKEN_H #define TOKEN_H typedef enum { T_Le = 256, T_Ge, T_Eq, T_Ne, T_And, T_Or, T_IntConstant, T_StringConstant, T_Identifier, T_Void, T_Int, T_While, T_If, T_Else, T_Return, T_Break, T_Continue, T_Print, T_ReadInt } TokenType; static void print_token(int token) { static char* token_strs[] = { "T_Le", "T_Ge", "T_Eq", "T_Ne", "T_And", "T_Or", "T_IntConstant", "T_StringConstant", "T_Identifier", "T_Void", "T_Int", "T_While", "T_If", "T_Else", "T_Return", "T_Break", "T_Continue", "T_Print", "T_ReadInt" }; if (token < 256) { printf("%-20c", token); } else { printf("%-20s", token_strs[token-256]); } } #endif ~~~ * makefile ~~~ out: scanner scanner: lex.yy.c token.h gcc -o $@ $< lex.yy.c: scanner.l flex $< ~~~  ## 2.2 語法分析 ### 2.2.1 上下文無關語法 > * 上下文無關文法可以采用遞歸的形式推導，比正則表達式的表達能力要強大的多。 > * 為什么要把這種語法稱為上下文本無關語法呢？這是由其產生式的固定形式 A -> u 所決定的，事實上，還有所謂的上下文有關語法，其產生式的形式為 v A w -> v u w ，也就是說只有 A 的上下文分別為 v 和 w 時，才能應用該產生式。上下文本無關語法其實是上下文有關語法中的一種特例，也就是 v 和 w 分別為空串時的特例。 ~~~ 終結符集合 T （terminal set） ： 一個有限集合，其元素稱為 終結符（terminal） 。 非終結符集合 N （non-terminal set) ： 一個有限集合，與 T 無公共元素，其元素稱為 非終結符（non-terminal） 。 符號集合 V （alphabet） ： T 和 N 的并集，其元素稱為 符號（symbol） 。因此終結符和非終結符都是符號。符號可用字母：A, B, C, X, Y, Z, a, b, c 等表示。 符號串（a string of symbols） ： 一串符號，如 X1 X2 ... Xn 。只有終結符的符號串稱為 句子（sentence）。 空串 （不含任何符號）也是一個符號串，用 ε 表示。符號串一般用小寫字母 u, v, w 表示。 產生式（production） ： 一個描述符號串如何轉換的規則。對于上下文本無關語法，其固定形式為： A -> u ，其中 A 為非終結符， u 為一個符號串。 產生式集合 P （production set） ： 一個由有限個產生式組成的集合。 展開（expand） ： 一個動作：將一個產生式 A -> u 應用到一個含有 A 的符號串 vAw 上，用 u 代替該符號串中的 A ，得到一個新的符號串 vuw 。 折疊（reduce） ： 一個動作：將一個產生式 A -> u 應用到一個含有 u 的符號串 vuw 上，用 A 代替該符號串中的 u ，得到一個新的符號串 vAw 。 起始符號 S （start symbol） ： N 中的一個特定的元素。 推導（derivate） ： 一個過程：從一個符號串 u 開始，應用一系列的產生式，展開到另一個的符號串 v。若 v 可以由 u 推導得到，則可寫成： u => v 。 上下文本無關語法 G （context-free grammar, CFG） ： 一個 4 元組： (T, N, P, S) ，其中 T 為終結符集合， N 為非終結符集合， P 為產生式集合， S 為起始符號。一個句子如果能從語法 G 的 S 推導得到，可以直接稱此句子由語法 G 推導得到，也可稱此句子符合這個語法，或者說此句子屬于 G 語言。 G 語言（ G language） 就是語法 G 推導出來的所有句子的集合，有時也用 G 代表這個集合。 解析（parse） ： 也稱為分析，是一個過程：給定一個句子 s 和語法 G ，判斷 s 是否屬于 G ，如果是，則找出從起始符號推導得到 s 的全過程。推導過程中的任何符號串（包括起始符號和最終的句子）都稱為 中間句子（working string） 。 ~~~ 一個上下文無關語法 G 就是由一個終結符集合 T ，一個非終結符集合 N （ N 和 T 不相交），一個產生式集合 P ，以及一個起始符號 S （S ∈ N）組成。由語法 G 推導（產生）出來的所有的句子的集合稱為 G 語言。因此一個語法可以代表一個句子集合，也就是一個語言。 終結符和非終結符統稱為符號，符號一般用字母 A, B, X, Y, a, b 表示，符號串一般用小寫字母 u, v 表示。產生式的形式為 A -> u ，其中 A 為非終結符， u 為一個符號串。 下面再來看一個例子： ~~~ S –> AB A –> aA | ε B –> b | bB ~~~ 這里面的第二行中的 ε 表示一個空句子，表示 A 可以用一個空句子來代替。 經過觀察可知，這個語法所能推導出的所有句子的集合為： ~~~ A : { ε, a, aa, aaa, ... } B : { b, bb, bbb, ... } S : { b, bb, bbb, ..., ab, abb, ..., aab, aabb, ... } ~~~ 因此 S 相當于正則表達式 a\*b+ 。 再來看一個稍微復雜的例子： ~~~ Expr -> Expr op Expr | (Expr) | number op -> + - * / ~~~ 其中的 number 是詞法分析得到的一個 token ，它在詞法分析中用正則表達式 \[0-9\]+ 表示。 經過觀察可知，此語法可以推導出所有的整數算術表達式： ~~~ Expr : { 123, 25 + 24, 78 - 34, 12 * ( 23 + 9 ), ... } ~~~ 可以看出，上下文無關文法可以采用遞歸的形式推導，比正則表達式的表達能力要強大的多。 ### 2.2.2 分析樹和抽象語法樹 > 語法分析不但要判斷給定的句子是否符合語法結構，而且還要分析出該句子符合哪些結構 以上面表達式語法為例，給定一個句子 12 + 53 ，經過觀察，發現此句子可以按以下方式被推導出來： ~~~ Expr ==> Expr + Expr ==> number + Expr ==> number + number ==> 12 + 53 ~~~ 以上推導過程可以用分析樹來表示：  再看一個稍微長的句子： 12 + ( 53 - 7 ) ，其分析樹如下：  可以去掉此分析樹中一些多余的節點，并進一步濃縮，得到抽象語法樹：  對于這種樹狀結構，可以采用遞歸的方式加以分析，從而生成目標代碼。 再看一個句子： 12 + 53 \* 7 ，這時候問題來了，我們發現它可以由兩種不同的方式推導出來：  這就是語法的歧義性，所謂**歧義**（ambiguity），就是指對于一個符合語法結構的句子，它可以由兩種不同的方式被推導出來。 消除歧義的方法之一是改寫語法，將有歧義的產生式改寫成無歧義的，這種改寫非常困難，而且改寫后的產生式往往和原產生式相差很大，可讀性非常差。另一種方法就是引入 優先級 ，不需要改寫語法，當推導過程中出現歧義的時候（也就是出現兩種不同的推導方式的時候），利用符號的優先級來選擇需要的推導方式 ### 2.2.3 分析方法簡介 分析可以采用 自頂向下分析 或 自底向上分析 兩種方法。 * 自頂向下分析 **自頂向下分析就是從起始符號開始，不斷的挑選出合適的產生式，將中間句子中的非終結符的展開，最終展開到給定的句子。** ~~~ S –> AB A –> aA | ε B –> b | bB ~~~   * 自底向上分析 **自底向上分析的順序和自頂向下分析的順序剛好相反，從給定的句子開始，不斷的挑選出合適的產生式，將中間句子中的子串折疊為非終結符，最終折疊到起始符號。** ~~~ S –> AB A –> Aa | ε B –> b | bB ~~~   ### 2.2.4 自頂向下分析 * **LL(1) 分析法**是一種自頂向下分析方法，它通過精心構造語法規則而使得每個推導步可以直接挑選出合適的產生式。 * LL(1) 分析法的優點 不需要回溯，構造方法較簡單，且分析速度非常快，每讀到第一個符號就可以預測出整個產生式來。 * LL(1) 分析法的缺點 **對語法的限制太強**，它要求同一個非終結符的不同產生式的首字符集合互不相交，能滿足此要求的語法相當少，而將一個不滿足此要求的語法改寫到滿足要求也相當不容易。因此， LL(1) 分析法目前已經應用的比較少了。 ### 2.2.5 自底向上分析 * 自底向上分析法的解析力量比自頂向下分析法要**強大**的多，和自頂向下分析法相比，它可以解析更為復雜、更為廣泛的語法。但自底向上分析法的構造過程也復雜的多， LL(1) 法程序的手寫難度不大，但自底向上分析法程序的手寫難度卻相當之大。幸運的是，目前有一些非常強大的分析器構造工具（如**bison**），可以將用戶定義的語法規則轉化成一個自底向上分析器，使得編寫語法分析器變得非常簡單。 * 典型的自底向上分析法有**LR 分析法**。 * LR(1) 的構造過程用代碼來實現這個構造流程還是很不容易的，不過已經有了非常優秀的工具可以利用了，那就是 bison。 ### 2.2.6 用 bison 做詞法分析 #### 2.2.6.1 介紹 bison 讀取用戶提供的語法的產生式，生成一個 C 語言格式的 LALR(1) 動作表，并將其包含進一個名為 yyparse 的 C 函數，這個函數的作用就是利用這個動作表來解析 token stream ，而這個 token stream 是由 flex 生成的詞法分析器掃描源程序得到。 #### 2.2.6.2 用法 * 安裝bison ~~~ sudo apt-get install bison 或者下載相應版本的安裝文件安裝 ~~~ * 安裝完成后，新建一個文本文件，輸入以下內容： ~~~ %{ #include "y.tab.h" %} %% [0-9]+ { yylval = atoi(yytext); return T_NUM; } [-/+*()\n] { return yytext[0]; } . { return 0; /* end when meet everything else */ } %% int yywrap(void) { return 1; } ~~~ 將此文件另存為 calc.l 。注意此文件中的 %% 、 %{ 、 %} 的前面不能有任何空格。 * 再新建一個文本文件，輸入以下內容： ~~~ %{ #include <stdio.h> void yyerror(const char* msg) {} %} %token T_NUM %left '+' '-' %left '*' '/' %% S : S E '\n' { printf("ans = %d\n", $2); } | /* empty */ { /* empty */ } ; E : E '+' E { $$ = $1 + $3; } | E '-' E { $$ = $1 - $3; } | E '*' E { $$ = $1 * $3; } | E '/' E { $$ = $1 / $3; } | T_NUM { $$ = $1; } | '(' E ')' { $$ = $2; } ; %% int main() { return yyparse(); } ~~~ 將此文件另存為 calc.y 。注意此文件中的 %% 、 %{ 、 %} 的前面也不能有任何空格。 * 將前面兩個文件都放在終端的當前目錄，再在終端輸入： ~~~ bison -vdty calc.y ~~~ 此時可以發現終端下多了三個文件： y.tab.h, y.tab.c, y.output 。 * 再在終端輸入： ~~~ flex calc.l ~~~ 此時終端下又多了一個文件： lex.yy.c 。 * 最后將 y.tab.c 和 lex.yy.c 一起編譯并運行一遍： ~~~ gcc -o calc y.tab.c lex.yy.c ./calc ~~~ * 然后在終端輸入算術表達式并回車： ~~~ 1+2+3 ans = 6 2*(2+7)+8 ans = 26 ~~~ 可以發現回車后，終端會自動輸出算術表達式的結果。這個程序就是一個簡單的支持加、減、乘、除以及括號的整數計算器。想象一下，如果用 C 語言手工編寫一個同樣功能的程序，那代碼量肯定很大吧。 #### 2.2.6.2 示例 * 詞法分析文件： scanner.l ~~~ %{ #define YYSTYPE char * #include "y.tab.h" int cur_line = 1; void yyerror(const char *msg); void unrecognized_char(char c); void unterminate_string(); #define _DUPTEXT {yylval = strdup(yytext);} %} /* note \042 is '"' */ WHITESPACE ([ \t\r\a]+) SINGLE_COMMENT1 ("//"[^\n]*) SINGLE_COMMENT2 ("#"[^\n]*) OPERATOR ([+*-/%=,;!<>(){}]) INTEGER ([0-9]+) IDENTIFIER ([_a-zA-Z][_a-zA-Z0-9]*) UNTERM_STRING (\042[^\042\n]*) STRING (\042[^\042\n]*\042) %% \n { cur_line++; } {WHITESPACE} { /* ignore every whitespace */ } {SINGLE_COMMENT1} { /* skip for single line comment */ } {SINGLE_COMMENT2} { /* skip for single line comment */ } {OPERATOR} { return yytext[0]; } "int" { return T_Int; } "void" { return T_Void; } "return" { return T_Return; } "print" { return T_Print; } "readint" { return T_ReadInt; } "while" { return T_While; } "if" { return T_If; } "else" { return T_Else; } "break" { return T_Break; } "continue" { return T_Continue; } "<=" { return T_Le; } ">=" { return T_Ge; } "==" { return T_Eq; } "!=" { return T_Ne; } "&&" { return T_And; } "||" { return T_Or; } {INTEGER} { _DUPTEXT return T_IntConstant; } {STRING} { _DUPTEXT return T_StringConstant; } {IDENTIFIER} { _DUPTEXT return T_Identifier; } {UNTERM_STRING} { unterminate_string(); } . { unrecognized_char(yytext[0]); } %% int yywrap(void) { return 1; } void unrecognized_char(char c) { char buf[32] = "Unrecognized character: ?"; buf[24] = c; yyerror(buf); } void unterminate_string() { yyerror("Unterminate string constant"); } void yyerror(const char *msg) { fprintf(stderr, "Error at line %d:\n\t%s\n", cur_line, msg); exit(-1); } ~~~ * 語法分析文件： parser.y ~~~ %{ #include <stdio.h> #include <stdlib.h> void yyerror(const char*); #define YYSTYPE char * int ii = 0, itop = -1, istack[100]; int ww = 0, wtop = -1, wstack[100]; #define _BEG_IF {istack[++itop] = ++ii;} #define _END_IF {itop--;} #define _i (istack[itop]) #define _BEG_WHILE {wstack[++wtop] = ++ww;} #define _END_WHILE {wtop--;} #define _w (wstack[wtop]) %} %token T_Int T_Void T_Return T_Print T_ReadInt T_While %token T_If T_Else T_Break T_Continue T_Le T_Ge T_Eq T_Ne %token T_And T_Or T_IntConstant T_StringConstant T_Identifier %left '=' %left T_Or %left T_And %left T_Eq T_Ne %left '<' '>' T_Le T_Ge %left '+' '-' %left '*' '/' '%' %left '!' %% Program: /* empty */ { /* empty */ } | Program FuncDecl { /* empty */ } ; FuncDecl: RetType FuncName '(' Args ')' '{' VarDecls Stmts '}' { printf("ENDFUNC\n\n"); } ; RetType: T_Int { /* empty */ } | T_Void { /* empty */ } ; FuncName: T_Identifier { printf("FUNC @%s:\n", $1); } ; Args: /* empty */ { /* empty */ } | _Args { printf("\n\n"); } ; _Args: T_Int T_Identifier { printf("\targ %s", $2); } | _Args ',' T_Int T_Identifier { printf(", %s", $4); } ; VarDecls: /* empty */ { /* empty */ } | VarDecls VarDecl ';' { printf("\n\n"); } ; VarDecl: T_Int T_Identifier { printf("\tvar %s", $2); } | VarDecl ',' T_Identifier { printf(", %s", $3); } ; Stmts: /* empty */ { /* empty */ } | Stmts Stmt { /* empty */ } ; Stmt: AssignStmt { /* empty */ } | PrintStmt { /* empty */ } | CallStmt { /* empty */ } | ReturnStmt { /* empty */ } | IfStmt { /* empty */ } | WhileStmt { /* empty */ } | BreakStmt { /* empty */ } | ContinueStmt { /* empty */ } ; AssignStmt: T_Identifier '=' Expr ';' { printf("\tpop %s\n\n", $1); } ; PrintStmt: T_Print '(' T_StringConstant PActuals ')' ';' { printf("\tprint %s\n\n", $3); } ; PActuals: /* empty */ { /* empty */ } | PActuals ',' Expr { /* empty */ } ; CallStmt: CallExpr ';' { printf("\tpop\n\n"); } ; CallExpr: T_Identifier '(' Actuals ')' { printf("\t$%s\n", $1); } ; Actuals: /* empty */ { /* empty */ } | Expr PActuals { /* empty */ } ; ReturnStmt: T_Return Expr ';' { printf("\tret ~\n\n"); } | T_Return ';' { printf("\tret\n\n"); } ; IfStmt: If TestExpr Then StmtsBlock EndThen EndIf { /* empty */ } | If TestExpr Then StmtsBlock EndThen Else StmtsBlock EndIf { /* empty */ } ; TestExpr: '(' Expr ')' { /* empty */ } ; StmtsBlock: '{' Stmts '}' { /* empty */ } ; If: T_If { _BEG_IF; printf("_begIf_%d:\n", _i); } ; Then: /* empty */ { printf("\tjz _elIf_%d\n", _i); } ; EndThen: /* empty */ { printf("\tjmp _endIf_%d\n_elIf_%d:\n", _i, _i); } ; Else: T_Else { /* empty */ } ; EndIf: /* empty */ { printf("_endIf_%d:\n\n", _i); _END_IF; } ; WhileStmt: While TestExpr Do StmtsBlock EndWhile { /* empty */ } ; While: T_While { _BEG_WHILE; printf("_begWhile_%d:\n", _w); } ; Do: /* empty */ { printf("\tjz _endWhile_%d\n", _w); } ; EndWhile: /* empty */ { printf("\tjmp _begWhile_%d\n_endWhile_%d:\n\n", _w, _w); _END_WHILE; } ; BreakStmt: T_Break ';' { printf("\tjmp _endWhile_%d\n", _w); } ; ContinueStmt: T_Continue ';' { printf("\tjmp _begWhile_%d\n", _w); } ; Expr: Expr '+' Expr { printf("\tadd\n"); } | Expr '-' Expr { printf("\tsub\n"); } | Expr '*' Expr { printf("\tmul\n"); } | Expr '/' Expr { printf("\tdiv\n"); } | Expr '%' Expr { printf("\tmod\n"); } | Expr '>' Expr { printf("\tcmpgt\n"); } | Expr '<' Expr { printf("\tcmplt\n"); } | Expr T_Ge Expr { printf("\tcmpge\n"); } | Expr T_Le Expr { printf("\tcmple\n"); } | Expr T_Eq Expr { printf("\tcmpeq\n"); } | Expr T_Ne Expr { printf("\tcmpne\n"); } | Expr T_Or Expr { printf("\tor\n"); } | Expr T_And Expr { printf("\tand\n"); } | '-' Expr %prec '!' { printf("\tneg\n"); } | '!' Expr { printf("\tnot\n"); } | T_IntConstant { printf("\tpush %s\n", $1); } | T_Identifier { printf("\tpush %s\n", $1); } | ReadInt { /* empty */ } | CallExpr { /* empty */ } | '(' Expr ')' { /* empty */ } ; ReadInt: T_ReadInt '(' T_StringConstant ')' { printf("\treadint %s\n", $3); } ; %% int main() { return yyparse(); } ~~~ * makefile 文件： makefile ~~~ OUT = tcc TESTFILE = test.c SCANNER = scanner.l PARSER = parser.y CC = gcc OBJ = lex.yy.o y.tab.o TESTOUT = $(basename $(TESTFILE)).asm OUTFILES = lex.yy.c y.tab.c y.tab.h y.output $(OUT) .PHONY: build test simulate clean build: $(OUT) test: $(TESTOUT) simulate: $(TESTOUT) python pysim.py $< -a clean: rm -f *.o $(OUTFILES) $(TESTOUT): $(TESTFILE) $(OUT) ./$(OUT) < $< > $@ $(OUT): $(OBJ) $(CC) -o $(OUT) $(OBJ) lex.yy.c: $(SCANNER) y.tab.c flex $< y.tab.c: $(PARSER) bison -vdty $< ~~~ * 測試文件： test.c ~~~ #include "for_gcc_build.hh" // only for gcc, TinyC will ignore it. int main() { int i; i = 0; while (i < 10) { i = i + 1; if (i == 3 || i == 5) { continue; } if (i == 8) { break; } print("%d! = %d", i, factor(i)); } return 0; } int factor(int n) { if (n < 2) { return 1; } return n * factor(n - 1); } ~~~ # 3 TinyC 編譯器要點 ## 3.1 編譯器的工作流程圖  ## 3.2 編譯器的工作流程 ### 3.2.1 詞法分析 編譯器掃描源文件的字符流，過濾掉字符流中的空格、注釋等，并將其分割為一個個的詞（或稱為記號、token，下文中都將稱為 token ） eg: ~~~ a = value + sum(5, 123); ~~~ 被拆分為11個 token ~~~ a 標識符 = 賦值運算符 value 標識符 + 加號 sum 標識符 ( 左括號 5 整數 , 逗號 123 整數 ) 右括號 ; 分號 ~~~ ### 3.2.2 語法分析 > 根據語法規則將這些記號構造出**語法樹** 詞法分析完成后，上面的字符流就被轉換為 token 流了 ~~~ ID<a> '=' ID<value> '+' ID<sum> '(' NUM<5> ',' NUM<123> ')' ';' ~~~ 上面的 ID 表示這一個標識符類型的 token ，其內容為 a。 接下來，根據語言的語法規則來解析這個 token 流。首先，這是一個語句。而TinyC 中只有四種語句：賦值語句，函數調用語句， if 語句和 while 語句。把這四種語句的語法結構和這個 token 流對比一下發現只有賦值語句的結構才能和它匹配：  于是將此語法結構應用到 token 流上，把源程序的等號兩邊的內容分別放在該語法結構樹的對應節點上，生成語法樹如下：  接下來，對這個語法樹上的 expresion 進行解析。TinyC中的表達式有很多種，包括：變量表達式、數字表達式、加法表達式、減法表達式等等。經過對比，發現只有加法表達式的結構才能匹配這個 ，于是將加法表達式的語法結構應用到此表達式上，生成：  然后，解析這個語法樹上的 和 ，經過對比，發現只有變量表達式和函數調用表達式的結構能匹配成功，應用后，得到：  這個語法樹中，有些節點是可以去掉的，如 assign expression 中的 ‘=’ 和 ‘;’ ，既然我們已經知道這是一個賦值表達式，那么這兩個節點是不必要的了，我們去掉這樣的節點，同時對語法樹進一步濃縮，可以得到最終的抽象語法樹  ### 3.2.3 語義分析 > 對語法樹的各個節點之間的關系進行檢查，檢查語義規則是否被違背，同時對語法樹進行必要的優化 語義分析階段，編譯器開始對語法樹進行一次或多次的遍歷，檢查程序的語義規則。主要包括聲明檢查和類型檢查，如上一個賦值語句中，就需要檢查： * 語句中的變量 a 和 value 、函數 sum 是否被聲明過 * sum 函數的參數數量和類型是否與其聲明的參數數量及類型匹配 * 加號運算的兩個操作數的類型是否匹配（sum 函數的返回值類型是否和變量 value 匹配） * 賦值運算符兩邊的操作數的類型是否匹配 語義檢查時，也會對語法樹進行一些優化，比如將只含常量的表達式先計算出來，如： ~~~ a = 1 + 2 * 9; 會被優化成： a = 19; ~~~ 語義分析完成后，源程序的結構解析完成，所有編譯期錯誤都已被排除，所有使用到的變量名和函數名都綁定到其聲明位置（地址）了，至此編譯器可以說是真正理解了源程序，可以開始進行代碼生成和代碼優化了。 ### 3.2.4 中間代碼生成 > 遍歷語法樹的節點，將各節點轉化為中間代碼，并按特定的順序拼裝起來 一般的編譯器并不直接生成目標代碼，而是先生成某種中間代碼，然后再生成目標代碼。生成中間代碼 * 一個是為了降低編譯器開發的難度，中間代碼既有部分高級語言特性、又有接近機器語言操作的中間代碼，將高級語言翻譯成中間代碼、將此中間代碼再翻譯成目標代碼的難度都比直接將高級語言翻譯成目標代碼的難度要低。 * 二是為了增加編譯器的模塊化、可移植性和可擴展性，一般來說，中間代碼既獨立于任何高級語言，也獨立于任何目標機器架構，這就為開發出適應性廣泛的編譯器提供了媒介。 * 三是為了代碼優化，一般來說，計算機直接生成的代碼比人手寫的匯編要龐大、重復很多，計算機科學家們對一些具有固定格式的中間代碼（最典型的是三地址中間碼）的進行大量的研究工作，提出了很多廣泛應用的、效率非常高的優化算法，可以對中間代碼進行優化，比直接對目標代碼進行優化的效果要好很多。 以上述語法樹為例說明中間代碼生成的方法 ~~~ 首先從根節點 assign_statement 開始： GEN_CODE( assign_statement<a = value + sum(5, 123);> ) 對于賦值語句，先將其右邊的表達式翻譯成 Pcode ，再在最后加一個 pop var_name 就可以了，如下： GEN_CODE( add_expression<value + sum(5, 123)> ) pop a 對于加法表達式，將兩個操作符翻譯成 Pcode ，再加上 add ，如下： GEN_CODE( var_expression<value> ) GEN_CODE( call_expression<sum(5, 123)> ) add pop a 對于變量表達式，直接翻譯成 push var_name ，對于函數調用表達式，將其參數翻譯成 Pcode ，再加上 $func_name，如下： push value GEN_CODE( arguments<5, 123> ) $sum add pop a 最后將各參數翻譯成 Pcode ，最終得到： push value push 5 push 123 $sum add pop a ~~~ 從以上過程可以看出，代碼生成的算法是一個遞歸的算法，遞歸的遍歷語法樹，將語法樹上的一些節點替換成中間代碼塊，再根據特定的規則和順序將這些中間代碼塊拼裝起來。 ### 3.2.5 中間代碼優化 在本階段，編譯器對中間代碼進行優化，嘗試生成體積最小、最快、最有效率的代碼。常見的優化方法有： * 去除永遠都不會被執行的代碼區 * 去掉未被使用到的變量 * 優化循環體，將每次循環中的運行結果不變的語句移到循環的最外面 * 算術表達式優化，將乘 1 和 加 0 等操作去掉，將乘 2 優化成左移 1 位等 ### 3.2.6 目標代碼生成 編譯器根據中間代碼和目標機器架構生成目標代碼，由于大部分中間代碼接近低級語言，這一步的難度較低。比如 Pcode 中，很多 Pcode 命令可以用一組 x86 指令代替，如： ~~~ ; ------------------------------------------------ ; Pcode push 3 ; x86 PUSH DWORD 3 ; ------------------------------------------------ ; Pcode push a ; x86 PUSH DWORD [EBP - 12] ; 假定a的地址為 EBP - 12 ; ------------------------------------------------ ; Pcode add ; x86 POP EAX ADD [ESP], EAX ~~~ ### 3.2.7 目標代碼優化 * 本階段，編譯器利用目標機器的提供的特性對目標代碼做進一步的優化，如利用 CPU 的流水線，利用 CPU 的多核等，生成最終的目標代碼。 ### 3.2.8 編譯過程的錯誤檢查 * 在詞法、語法和語義分析的過程中，都伴隨著錯誤檢查，詞法錯誤主要是字符錯誤（如非法字符、未結束的注釋、未結束的字符串等），語法錯誤主要是格式錯誤（如語句后未加分號、不匹配的括號等），最常發生的是語義錯誤（如變量名錯誤、表達式類型錯誤、函數參數不匹配等）。編譯器不僅檢查錯誤，還需要精確定位出錯誤發生的位置，協助編程人員修改。 * 錯誤檢查和代碼優化是編譯器中兩個很重要的步驟，也是最難實現的部分，前者定位出所有的編譯期錯誤所在，協助程序員寫出正確的程序，后者則保證生成高效的目標程序，這兩點是早期編譯器獲得廣泛接受的基石。 ### 3.2.9 編譯器的遍數 從詞法分析到語法分析生成語法樹一般只需要對源文件進行一遍掃描就可以了，生成語法樹后，語義檢查、代碼優化的過程中可能需要對語法樹進行反復的遍歷，5 、 6 遍，甚至 8 遍都是有可能的。但有些語言（如 C 語言）也可能 1 遍就編譯完成，其語義檢查和代碼生成可以在語法分析的同時同步進行，此時一般無任何代碼優化。