BISON語法分析工具

1、自動語法分析工具Bison(2015-01-30 12:42:55)轉載標簽：雜談BISON用于語法分析器的自動生成，它可以很方便地生成一個所謂的抽象語法樹,樹的每一個子樹都代表了一個特定的語法成分，便于后期處理。這個工具可以在網上下載獲得?；c時間學習這個工具的用法，并用于SQL語言的分析，可以讓我們把精力專注在語法規(guī)則上，而不是具體的分析函數(shù)編寫上。對整個DBMS來說，使用自動化工具進行語言處理程序的自動生成，使得語言分析模塊成為最可靠最方便維護的模塊之一。BISON源文件的結構我們需要按照BISON的要求，書寫B(tài)ISON的源程序（gramma.y）。遵循它的規(guī)則是必須的，BISON會把它

2、的源文件翻譯為C文件。因此，BISON是編譯程序的翻譯器。BISON的源文件通常由八個部分組成：一自由定義部分:%這部分被BISON原封不動地復制到輸出的.C文件中。通常用于定義一些在規(guī)則程序中需要使用的一些常量，函數(shù)原形等。二語法棧的聯(lián)合(UNION)結構語法分析程序使用一個堆棧來存放規(guī)約到的各個語法成分，堆棧用一個數(shù)組表示，這個數(shù)組的每個元素需要能夠描述每一個語法成分，所以采用一個UNION：%unionUnion中的每一個項，都是一個語法規(guī)則的每一個非終結符；以整數(shù)四則表達式為例：exp : exp exp| exp - exp| exp * exp| exp / exp| ( exp

3、)| lt_integer；lt_integer: LT_INTEGER;這里有兩個語法規(guī)則，對應了兩個非終結符號: exp是表達式，lt_integer表示整數(shù)常量（LT_INTEGER表示詞法分析程序返回的一個確認為整數(shù)的單詞）。對應的，這個union可以書寫為：%par_exp_t*exp;intlt_integer;其中par_exp_t用來描述被識別出的exp的信息，int存放被識別出的整數(shù)的值。上面的例子很簡單，所以union只有兩個字段；在DM6的語法分析程序中，這個UNION大約有490個字段，也就是，大概有490個語法規(guī)則產生式。當然你也可以不采用這個UNION,那么每一個規(guī)

4、約出來的語法成分都是一個C指針,需要上層做類型轉換來解釋。三非終結符的類型聲明上面定義了分析棧的UNION類型,還需要把字段名與語法非終結符號對應起來：%type 非終結符號如上例，這部分應該寫為：%type exp%type lt_integer看上去似乎有點多余，每一行都是一個簡單的重復。但前面一個表示的是UNION中對應的字段名，后一個是語法符號；如果我們把UNION改為:%par_exp_t*eeee;intiiii;那么對應的類型聲明需要改為：%type exp%type lt_integer;這種不一致的寫法，事實上會造成混亂，所以應該采用上面一致的寫法。四：單詞（token）聲明

5、語法分析的輸入是連續(xù)的有確定意義的單詞。下面需要聲明分析程序支持的單詞：%token LT_INTEGER對于SQL語法，關鍵字如：SELECT, FROM, WHERE等，都可以定義為單詞:%token KW_SELECT, KW_FROM%token KW_WHERE五.確定運算符的優(yōu)先級%left - %left * /%left ( )%left表示是左結合的，表示先規(guī)約左邊的產生式，反應到表達式計算中：1 2 3別識別為：（1 2）3),而不是(1 (2 3)優(yōu)先級低的符號列在前面，高有限級的符號列在后面;同一行的表示優(yōu)先級相同。所以上面的書寫方式，符合“先乘除，后加減，括號最優(yōu)先”

6、的原則。除了%left以后，還有%right, %nonassoc等用來只是右結合，或者不結合等說明符號，可查看bison的詳細說明。六.聲明語法的開始符號%start exp這是告知bison,這是語法最終需要規(guī)約的非終結符號。七.語法規(guī)則定義這是語法分析程序的核心定義部分，用%開始,前面已經列出了關于表達式的語法規(guī)則：%exp : exp exp| exp - exp| exp * exp| exp / exp| ( exp )| lt_integerlt_integer: LT_INTEGER;八自由添加的C源代碼在語法規(guī)則定義部分的后面，可以用%開始，定義C的輔助代碼。這部分代碼將被原

7、封不動地復制到輸出的.C文件中。給語法規(guī)則配上規(guī)約動作規(guī)約動作是一段C代碼，它的作用是每當分析器識別出一個語法符號時，調用該代碼，完成一定的動作。通常，我們使用這段代碼，來建立當前語法節(jié)點與子節(jié)點勾連動作。規(guī)約動作應該緊接在語法規(guī)則的后面。如上例:exp : exp exp$ = new_node(PAR_EXP, 1);$-tag = 1;$-exp1 = $1;$-exp2 = $3;g_root = $;| ( exp )$ = $2;這里僅列出了其中的兩個子規(guī)則,其中A, B, C, D四個語句構成了第一個子規(guī)則的語句塊:A;為識別出的exp生成一個結構,用$指向它。$是一個bison

8、定義的特殊標記，其意義是當前語法棧的規(guī)約元素。如果沒有規(guī)約動作代碼，缺省情況下賦予$為NULL。new_node是一個需要自己編寫的函數(shù),用于生成各個子節(jié)點，PAR_EXP是一個事先定義的常量。顯然，對于不同的規(guī)則，需要定義不同的常量類型。象new_node這樣的函數(shù)，一般放在.y文件的最后一個部分。B:用來區(qū)分是哪個子規(guī)則規(guī)約的，這里用tag= 1來表示兩個子表達式運算C.保留第一個子表達式；$1表示這個產生式的第1個語法成分所在的語法棧中對應的值D.保留第二個子表達式；$3表示這個產生式的第3個語法成分所在的語法棧中對應的值；注意這里的也占一個位置，用$2，這里因為有tag=1，已經把相應的信息保存到$中，所以不需要管它。E:這是一個比較特別的語句，它把$賦給了一個全局量。因為exp是個開始符號，當分析結束時，這個g_root就是語法樹的根。F:因為加了括號的表達式與原表達式等價，所以直接把$2賦給$就可以了，不需要再生成par_exp節(jié)點。最終的函數(shù)yyparse()yyarse（）是bison生成的分析器的主函數(shù)。調用yyarse()，如果一切順利