編譯原理實踐11—語法分析程序的自動生成工具YACC

1、編譯原理實踐11語法分析程序的自動生成工具yacc 編譯原理實踐 -語法分析程序的自動生成工具yacc yacc簡潔的介紹 yacc(yet another compilercompiler) 是美國貝爾試驗室開發(fā)的 語法分析程序自動生成器 輸入是某個語言的語法規(guī)章，輸出是 該語言的語法分析器。 目前yacc生 成的是一個lalr(1)分析器 常用版本：berkeley高校的byacc, gnu工程的bison yacc的使用流程yacc源程序y_tab.c (宏定義文件) 字符串源程序 yaccc編譯器 y_tab.exe y_tab.c (宏定義文件) y_tab.exe 分析結(jié)果 yac

2、c的輸入文件稱為yacc源文件，以.y為擴展名，輸出文 件有兩個，一個是包含有語法分析函數(shù)yyparse()的c程序， 另一個是包含源文件中全部終結(jié)符編碼的宏定義文件，擴展 名為.h。這兩個文件經(jīng)過c編譯器的編譯就生成一個語法分析 器，該語法分析器的輸入是源程序經(jīng)過詞法分析的結(jié)果，輸 出可以是一棵語法樹，或者是所生成的目標代碼，也可以是 關(guān)于輸入串是否符合語法規(guī)章的信息。詳細的輸出形式可以 在yacc源程序中自己定義。 yacc和lex有直接的接口，由于yacc與lex 的特別功能，這兩個姐妹程序成為軟件工程的重 要工具，被稱為“黃金組合”。 許多程序設計語言編譯程序的設計都使用了 lex和y

3、acc,比如聞名的gnu c語言編譯器， pascal語言向c語言的轉(zhuǎn)換工具p2c等，就是 用flex和bison實現(xiàn)的 多數(shù)程序設計語言的語法分析都采納lalr(1) 分析法，yacc也正是以lalr(1)文法為基礎。 它通過對輸入的形式文法規(guī)章進行分析，產(chǎn)生 lalr(1)分析表，輸出以該分析表驅(qū)動的語法分 析器c語言源程序。 yacc源程序結(jié)構(gòu)yacc源程序由三個部分組成，各部分以 “%”為分隔符。說明部分和程序部分可 選，規(guī)章部分是必需的。 說明部分 % 規(guī)章部分 % 程序部分 yacc源程序結(jié)構(gòu)說明部分 yacc源程序說明部分定義語法規(guī)章中要用 的終結(jié)符號，語義動作中使用的數(shù)據(jù)類型、

4、 變量、語義值的聯(lián)合類型以及語法規(guī)章中運 算符的優(yōu)先級等。說明部分可以是空的。 說明部分通常包含兩部分內(nèi)容： c語言代碼部分 yacc說明部分 % yacc源程序結(jié)構(gòu)說明部分 頭文件表宏定義 數(shù)據(jù)類型定義 全局變量定義 % 文法開頭符號定義語義值類型定義 終結(jié)符定義 非終結(jié)符定義 優(yōu)先級和結(jié)合性定義 1-頭文件表 yacc直接把這部分定義抄到所生成的c語言程 序y.tab.c去的，所以要按c語言的語法規(guī)定來 寫。頭文件表是一系列c語言的#include語句， 要從每行的第一列開頭寫，例如： % #include stdio.h #include math.h #include ctype.h

5、#include “header.h” % % 2-宏定義 這部分用c語言的 #define語句定義程序 中要用的宏 例如% #define max(x,y)(xy)?x:y) % 3-數(shù)據(jù)類型定義 這部分定義語義動作中或程序段部分中要用到 的數(shù)據(jù)類型 例如 % typedef struct interval double lo,hi; interval; % 4-全局變量定義 . 外部變量(external variable)和yacc源程序中要用 到的全局變量都在這部分定義 例如 % extern int nfg;douhle dreg 26; interval vreg26; . % 5

6、-語法開頭符定義 上下文無關(guān)文法的開頭符號是一個特別的 非終結(jié)符，全部的推導都從這個非終結(jié)符 開頭 在yacc中，語法開頭符定義語句是 % start 非終結(jié)符 假如沒有上面的說明，yacc自動將語法 規(guī)章部分中第一條語法規(guī)章左部的非終結(jié) 符作為語法開頭符 6-語義值類型定義 yycc生成的語法分析程序yyparse用的 是lr分析方法，它在作語法分析時除了 有一個狀態(tài)棧外，還有一個語義值棧 語義值棧存放它所分析到的非終結(jié)符和終 結(jié)符的語義值，這些語義值有的是從詞法 分析程序傳回的，有的是在語義動作中賦 與的 假如沒有對語義值的類型做定義，那么 yacc認為它是整型(int)的，即全部語 法符

7、號假如賦與了語義值，則必需是整型 的，否則會出類型錯 6-語義值類型定義 但是用戶常常會盼望語義值的類型比較簡單， 如雙精度浮點數(shù)，字符串或樹結(jié)點的指針 這時就可以用語義值類型定義進行說明。由于 不同的語法符號的語義值類型可能不同，所以 語義值類型說明就是將語義值的類型定義為一 個聯(lián)合(union),這個聯(lián)合包括全部可能用 到的類型(各自對應一個成員名) 為了使用戶不必在存取語義值時每次都指出成 員名，在語義值類型定義部分還要求用戶說明 每一個語法符號(終結(jié)符和非終結(jié)符)的語義 值是哪一個聯(lián)合成員類型 6-語義值類型定義 例:% union int ival double dval inter

8、val vval; 引用時候的方式%token ival dreg vreg %token dval const %type dvaldexp %type vvalvexp 以%token開頭的行定義的是終結(jié)符的類型 以%type開頭的行定義是非終結(jié)符的類型 7-終結(jié)符定義 在yacc源程序語法規(guī)章部分消失的全部 終結(jié)符(正文字符“+”,“-”等除外) 等必需用%token定義，定義形式： 單一數(shù)據(jù)類型： %token 終結(jié)符1 終結(jié)符2 多數(shù)據(jù)類型： %token 類型 終結(jié)符1 終結(jié)符2 8-終結(jié)符定義 優(yōu)先級和結(jié)合性定義 %left 左結(jié)合 %right 右結(jié)合 %nonassoc 無結(jié)

9、合性 %prec 終結(jié)符 強制定義優(yōu)先級 yacc源程序語法規(guī)章部分 語法規(guī)章部分是整個yacc源程序的主體，它是由一組 產(chǎn)生式及相應的語義動作組成。 規(guī)章部分包括修改的bnf格式的文法規(guī)章，以及將在識 別出識別出相關(guān)的文法規(guī)章時被執(zhí)行的c代碼中的動作 (即依據(jù)lalr(1)分析算法，在歸約中使用 )。 文法規(guī)章中使用的元符號慣例如下： 通常，豎線|被用作替換(也可以分別寫出替換項),而 用來分隔文法規(guī)章的左右兩邊的箭頭符號-在yacc中 用冒號表示，最終，必需用分號來結(jié)束每個文法規(guī)章。 yacc源程序語法規(guī)章部分對文法中的產(chǎn)生式 a: a 1 | 2 | | m 在yacc程序中可表示成 | 2 1 語義動作1 語義動作2 語義動作m | m; yacc源程序語法規(guī)章部分 yacc中的動作是由在每個文法規(guī)章中將其寫作真正的c 代碼(在大括號中)來實現(xiàn)的。 在書寫動作時，可以使用yacc偽變量。當識別一個文 法規(guī)章時，規(guī)章中的每個符號都擁有一個值，除非它被 參數(shù)轉(zhuǎn)變了。 這些值由yacc保存在一個與分析棧保持平行的值棧 (value stack)中，每個在棧中的符號值都可以使用以 $開頭的偽變量來引用。 $代表剛才被識別出來的非終結(jié)符的值，也就是文法規(guī) 則左邊的符號。偽變量$1、$2、$3等代表了文法規(guī)章右 邊的每個連續(xù)的符號。 yacc源程序語