BISON語(yǔ)法分析工具參考模板

1、自動(dòng)語(yǔ)法分析工具Bison (2015-01-30 12:42:55)轉(zhuǎn)載標(biāo)簽： 雜談    BISON用于語(yǔ)法分析器的自動(dòng)生成，它可以很方便地生成一個(gè)所謂的抽象語(yǔ)法樹(shù), 樹(shù)的每一個(gè)子樹(shù)都代表了一個(gè)特定的語(yǔ)法成分，便于后期處理。這個(gè)工具可以在網(wǎng)上下載獲得?；c(diǎn)時(shí)間學(xué)習(xí)這個(gè)工具的用法，并用于SQL語(yǔ)言的分析，可以讓我們把精力專(zhuān)注在語(yǔ)法規(guī)則上，而不是具體的分析函數(shù)編寫(xiě)上。對(duì)整個(gè)DBMS來(lái)說(shuō)，使用自動(dòng)化工具進(jìn)行語(yǔ)言處理程序的自動(dòng)生成，使得語(yǔ)言分析模塊成為最可靠最方便維護(hù)的模塊之一。BISON源文件的結(jié)構(gòu)  &#

2、160;  我們需要按照BISON的要求，書(shū)寫(xiě)B(tài)ISON的源程序（gramma.y）。遵循它的規(guī)則是必須的，BISON會(huì)把它的源文件翻譯為C文件。因此，BISON是編譯程序的翻譯器。BISON的源文件通常由八個(gè)部分組成：一    自由定義部分:1 / 9%這部分被BISON原封不動(dòng)地復(fù)制到輸出的.C文件中。通常用于定義一些在規(guī)則程序中需要使用的一些常量，函數(shù)原形等。 二語(yǔ)法棧的聯(lián)合(UNION)結(jié)構(gòu)語(yǔ)法分析程序使用一個(gè)堆棧來(lái)存放規(guī)約到的各個(gè)語(yǔ)法成分，堆棧用一個(gè)數(shù)組表示，這個(gè)數(shù)組的每個(gè)元素需要能夠描述每一個(gè)語(yǔ)法成分，所以采用一

3、個(gè)UNION：%union Union中的每一個(gè)項(xiàng)，都是一個(gè)語(yǔ)法規(guī)則的每一個(gè)非終結(jié)符；以整數(shù)四則表達(dá)式為例：exp : exp exp    | exp - exp    | exp * exp    | exp / exp    | ( exp )    | lt_integer；lt_integer: LT_INTEGER;這里有兩個(gè)語(yǔ)法規(guī)則，對(duì)應(yīng)了兩個(gè)非終結(jié)符號(hào): exp 

4、;是表達(dá)式， lt_integer表示整數(shù)常量（LT_INTEGER表示詞法分析程序返回的一個(gè)確認(rèn)為整數(shù)的單詞）。對(duì)應(yīng)的，這個(gè)union可以書(shū)寫(xiě)為： % par_exp_t*      exp; int             lt_integer; 其中par_exp_t用來(lái)描述被識(shí)別出的exp的信息，int存放被識(shí)別出的整數(shù)的值。上面的例子很簡(jiǎn)單，所以u(píng)

5、nion只有兩個(gè)字段；在DM6的語(yǔ)法分析程序中，這個(gè)UNION大約有490個(gè)字段，也就是，大概有490個(gè)語(yǔ)法規(guī)則產(chǎn)生式。當(dāng)然你也可以不采用這個(gè)UNION, 那么每一個(gè)規(guī)約出來(lái)的語(yǔ)法成分都是一個(gè)C指針, 需要上層做類(lèi)型轉(zhuǎn)換來(lái)解釋。 三非終結(jié)符的類(lèi)型聲明上面定義了分析棧的UNION類(lèi)型, 還需要把字段名與語(yǔ)法非終結(jié)符號(hào)對(duì)應(yīng)起來(lái)：%type <字段名>  非終結(jié)符號(hào) 如上例，這部分應(yīng)該寫(xiě)為：%type <exp> exp%type <lt_integer> lt_integer 看上去

6、似乎有點(diǎn)多余，每一行都是一個(gè)簡(jiǎn)單的重復(fù)。但前面一個(gè)表示的是UNION中對(duì)應(yīng)的字段名，后一個(gè)是語(yǔ)法符號(hào)；如果我們把UNION改為: %par_exp_t* eeee;int         iiii; 那么對(duì)應(yīng)的類(lèi)型聲明需要改為：%type <eeee> exp%type <iiii> lt_integer; 這種不一致的寫(xiě)法，事實(shí)上會(huì)造成混亂，所以應(yīng)該采用上面一致的寫(xiě)法。 四：?jiǎn)卧~（token）聲明語(yǔ)法分析的輸入是連續(xù)的有確定意義的

7、單詞。下面需要聲明分析程序支持的單詞：%token LT_INTEGER對(duì)于SQL語(yǔ)法，關(guān)鍵字如：SELECT, FROM, WHERE等，都可以定義為單詞: %token KW_SELECT, KW_FROM%token KW_WHERE 五. 確定運(yùn)算符的優(yōu)先級(jí)%left - %left * /%left ( )%left表示是左結(jié)合的，表示先規(guī)約左邊的產(chǎn)生式，反應(yīng)到表達(dá)式計(jì)算中：1 2 3 別識(shí)別為：（1 2） 3), 而不是 (1 (2 3) 優(yōu)先級(jí)低的符號(hào)列在前面，高有限級(jí)的符號(hào)列在后面;同一行的表示優(yōu)先

8、級(jí)相同。所以上面的書(shū)寫(xiě)方式，符合“先乘除，后加減，括號(hào)最優(yōu)先”的原則。 除了%left以后，還有%right, %nonassoc等用來(lái)只是右結(jié)合，或者不結(jié)合等說(shuō)明符號(hào)，可查看bison的詳細(xì)說(shuō)明。 六.聲明語(yǔ)法的開(kāi)始符號(hào)%start exp這是告知bison, 這是語(yǔ)法最終需要規(guī)約的非終結(jié)符號(hào)。 七.語(yǔ)法規(guī)則定義這是語(yǔ)法分析程序的核心定義部分，用%開(kāi)始, 前面已經(jīng)列出了關(guān)于表達(dá)式的語(yǔ)法規(guī)則：%exp : exp exp    | exp - exp    | ex

9、p * exp    | exp / exp    | ( exp )    | lt_integer lt_integer: LT_INTEGER; 八自由添加的C源代碼 在語(yǔ)法規(guī)則定義部分的后面，可以用%開(kāi)始，定義C的輔助代碼。這部分代碼將被原封不動(dòng)地復(fù)制到輸出的.C文件中。 給語(yǔ)法規(guī)則配上規(guī)約動(dòng)作規(guī)約動(dòng)作是一段C代碼，它的作用是每當(dāng)分析器識(shí)別出一個(gè)語(yǔ)法符號(hào)時(shí)，調(diào)用該代碼，完成一定的動(dòng)作。通常，我們使用這段代碼，來(lái)建立當(dāng)前語(yǔ)法節(jié)點(diǎn)與

10、子節(jié)點(diǎn)勾連動(dòng)作。規(guī)約動(dòng)作應(yīng)該緊接在語(yǔ)法規(guī)則的后面。 如上例:exp : exp exp    $ = new_node(PAR_EXP, 1);      $->tag = 1;                       $->exp1 = $1

11、;                     $->exp2 = $3;                     g_root = $;   &#

12、160;                 | ( exp )          $ = $2;                   

13、0;        這里僅列出了其中的兩個(gè)子規(guī)則, 其中A, B, C, D四個(gè)語(yǔ)句構(gòu)成了第一個(gè)子規(guī)則的語(yǔ)句塊:A; 為識(shí)別出的exp 生成一個(gè)結(jié)構(gòu),  用$指向它。$是一個(gè)bison定義的特殊標(biāo)記，其意義是當(dāng)前語(yǔ)法棧的規(guī)約元素。如果沒(méi)有規(guī)約動(dòng)作代碼，缺省情況下賦予$為NULL。new_node是一個(gè)需要自己編寫(xiě)的函數(shù),用于生成各個(gè)子節(jié)點(diǎn)，PAR_EXP是一個(gè)事先定義的常量。顯然，對(duì)于不同的規(guī)則，需要定義不同的常量類(lèi)型。象new_node這樣的函數(shù)，一般放在.y文件

14、的最后一個(gè)部分。 B: 用來(lái)區(qū)分是哪個(gè)子規(guī)則規(guī)約的，這里用tag= 1來(lái)表示兩個(gè)子表達(dá)式 運(yùn)算C. 保留第一個(gè)子表達(dá)式；$1表示這個(gè)產(chǎn)生式的第1個(gè)語(yǔ)法成分所在的語(yǔ)法棧中對(duì)應(yīng)的值D. 保留第二個(gè)子表達(dá)式；$3表示這個(gè)產(chǎn)生式的第3個(gè)語(yǔ)法成分所在的語(yǔ)法棧中對(duì)應(yīng)的值；注意這里的 也占一個(gè)位置，用$2，這里因?yàn)橛衪ag=1，已經(jīng)把相應(yīng)的信息保存到$中，所以不需要管它。 E: 這是一個(gè)比較特別的語(yǔ)句， 它把$賦給了一個(gè)全局量。因?yàn)閑xp是個(gè)開(kāi)始符號(hào)，當(dāng)分析結(jié)束時(shí)，這個(gè)g_root就是語(yǔ)法樹(shù)的根。F: 因?yàn)?#160;加了括號(hào)的表達(dá)式與原表達(dá)式等價(jià)，所以直接把$2賦給$就可以