《編譯與反編譯技術》—第3章3.5節文法分析器的生成器

本節書摘來自華章出版社《編譯與反編譯技術》一書中的第3章，第3.5節文法分析器的生成器，作者龐建民，陶紅偉，劉曉楠，嶽峰，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。

3.5　文法分析器的生成器

本節介紹一個文法分析器的自動産生工具yacc(yet another compiler-complier)，yacc通過輸入使用者提供的語言的文法描述規格說明，基于lalr(1)文法分析的原理，自動構造一個該語言的文法分析器。yacc源程式又稱yacc規格說明，同lex源程式類似，也由說明部分、翻譯規則和輔助過程三部分組成，形式如下：

[說明部分]

%%

翻譯規則

[%%

輔助過程]

其中，用方括号括起來的部分可以省略，但是翻譯規則部分不能省略。下面通過一個例子來說明yacc源程式。

例3.42　構造一個簡單的桌上型電腦，該電腦讀入一個算術表達式，然後計算并列印它的值。該算術表達式文法的産生式為：

e→e+t | t

t→t*f | f

f→(e) | digit

其中，digit表示0～9的單個數字。根據這一文法寫出的yacc源程式如下：

yacc源程式說明部分有任選的兩部分：第一部分是處于“%{”和“%}”之間的部分，這裡是一些普通的c語言的聲明，在翻譯規則或者輔助過程中用到的資料結構都需要在此進行聲明。第二部分是文法記号的聲明，一般以“%start s”的形式說明文法的開始符号，預設為第一條文法規則的左部符号。用 %token if、do、…、id、… 的形式說明記号，記号被yacc賦予了不會與任何字元值沖突的數字值。

yacc源程式翻譯規則部分中的每條規則由一個産生式和有關的語義動作組成。形如産生式a→α1 |α2 |…| αn，在yacc說明檔案中寫成

a : α1 { 語義動作1 }

| α2 { 語義動作2 }

…

| αn { 語義動作n }

;

在yacc産生式裡用單引号括起來的單個字元，如'c'，是由終結符号c組成的記号，沒有用引号括起來，也沒有被說明成token類型的字母數字串是非終結符号。産生式左部非終結符之後是一個冒号，右部候選式之間用豎線分隔。在規則的末尾用“；”表示規則的結束。yacc語義動作是用c語言描述的語句序列，用“$$”表示與産生式左部非終結符号相關的屬性值，用“$i”表示與産生式右部第i個文法符号相關的屬性值。由于語義動作都是放在産生式右部的尾部，是以，每當用某一個産生式進行歸約時，執行與之相關的語義動作。這樣，可以在每個$i值都計算出來之後再求$$的值。比如，在本例的yacc源程式中，産生式e→e+t | t及其相關的語義動作表示為

expr : expr '+' term {$$ = $1 + $3; }

在第一個産生式中，非終結符term是右部的第三個文法符号，“+”是第二個文法符号。第一個産生式的語義動作是把右部expr的值和term的值相加，把結果賦給左部非終結符expr作為它的值。第二個産生式的語義動作描述省略，因為當右部隻有一個文法符号時，語義動作預設就是表示值的複寫，即它的語義動作是{$$ = $1； }。

yacc源程式輔助過程部分由一些c語言函數組成，其中必須包含名為yylex的詞法分析器，其他過程則視需要而定。每次調用函數yylex()時，得到一個二進制式的記号：<記号，屬性值>。傳回的記号必須事先在yacc說明檔案的第一部分中用%token說明，屬性值必須通過yacc定義的變量yylval傳給分析器。