編譯器是軟件開發(fā)中的核心部件，其作用是其他任何軟件所不能取代的。編譯器在工作過程中，往往完成如下的任務(wù)：
在UNIX早期時代，編寫一個編譯器是一件非常耗時的工作。人們?yōu)榱撕喕_發(fā)過程，開發(fā)了Lex和YACC程序來解決第一個任務(wù)，根據(jù)用戶描述的語言，生成能夠解決問題的C/C++語言代碼，供開發(fā)者使用。GNU軟件協(xié)會開發(fā)了Flex和BISON，其功能與LEX和YACC基本兼容，并且在Lex和YACC提供的功能的基礎(chǔ)上進行了各種擴展。[0123456789]+
為了簡化書寫起見，也可以寫成如下的格式：
[0-9]+
對于任意單詞，其中只能包含字母，所以單詞的正則表達式為：
[a-zA-Z]+
Flex支持如下類型的正則表達式：
x 符合字符串"x"
. 除了換行以外的任何字符
[xyz] 一個字符類，在這個例子中，輸入必須符合要么是'x’要么是'y'要么是'z'
[abj-oZ] 一個帶范圍的字符類，符合任何滿足'a', 'b', 從'j'到'o'還有'Z'
[^A-Z] 一個取反的字符類，比如任何字母除了大寫字母。
[^A-Z\n] 任何字符除了大寫字母和換行
r* 零個或更多r，r可以是任意正則表達式
r+ 一個或更多r
r? 零個或最多一個r
r{2,5} 任何2到5個r
r{2,} 2個或更多r
r{4} 正好4個r
{name} 對name的擴展
"[xyz]\"foo"
符合正則表達式 [xyz]"foo 的字符串
\X 如果X是一個'a', 'b', 'f', 'n', 'r', 't', 或者'v',
則按照ASCII碼\x轉(zhuǎn)義符進行處理，否則，其他的'X'將用來做取消處理符處理
\0 一個ASCII碼空字符
\123 內(nèi)容為八進制123的char型
\x2a 內(nèi)容為十六進制0x2a的char型
(r) 符合一個r，括號是用來越過優(yōu)先級的
rs 正則表達式r，緊跟著一個
r|s 要么是r要么是s
^r 一個r，但是必須是在一行的開始
r$ 一個r，但是必須是在行末
<s>r 一個r，但是之前字符串必須符合條件s
<s1,s2,s3>r
同上，但是必須之前字符串符合s1或者s2或者s3
<*>r 不考慮開始字符串類型，只符合r
<<EOF>> 文件末尾
<s1,s2><<EOF>>
前面符合s1或者s2的文件末尾
按照上一節(jié)我們講述的正則表達式例子，我們嘗試第一次使用Lex來產(chǎn)生我們所需要的程序，實踐一遍Lex的使用以及gcc編譯器如何編譯和生成所需的二進制。
Flex甚至Bison代碼都有如下的編寫格式：
/* 定義段 */
%%
/* Flex、Bison代碼段（規(guī)則） */
%%
/* 輔助代碼段，C語言 */
首先，使用vi編譯器，輸入以下代碼（test.l）:
// 定義段代碼
%{ // 這種括號說明內(nèi)部的代碼不許flex處理，直接進入.C文件
#include <stdio.h>
%}
%%
// 詞法規(guī)則段代碼
[0123456789]+ printf("NUMBER"); // 數(shù)字類型字符串
[a-zA-Z]+ {
printf("WO"); // 單詞類型字符串（WORD）
printf("RD");
}
%%
// 輔助C語言函數(shù)代碼（直接寫C語言，無須括號，我們這里無內(nèi)容）
下面我們首先使用lex程序生成所需的狀態(tài)機代碼：
flex -otest.c test.l # 從正則表達式聲稱對應(yīng)的C語言代碼，注意-o后不要有空格（flex bug？）
gcc test.c -o test -lfl # 從C語言代碼生成二進制，從而運行，-lfl說明鏈接libfl.a庫文件
./test # 運行剛剛生成的二進制
下面我們來對剛生成的二進制進行試驗，以弄清楚flex到底是做什么的，在test程序中輸入以下內(nèi)容，按下Ctrl-D可以退出test程序：
3505
hello
what is 3505
通過這些試驗，相信您已經(jīng)明白了Flex的用途，每當(dāng)一個正則表達式符合時，flex生成的代碼就會自動調(diào)用對應(yīng)的函數(shù)，或者運行對應(yīng)的程序。下面我們對這個例子進行一些深入研究，處理一個類似C語言的程序配置腳本代碼。首先，一個演示腳本如下：
logging {
category lame-servers { null; };
category cname { null; };
};
zone "." {
type hint;
file "/etc/bind/db.root";
}在這個腳本中，我們可以看到一系列的詞匯類型：
%{
#include <stdio.h>
%}
%%
[a-zA-Z][a-zA-Z0-9]* printf("WORD "); /* 字符串 */
[a-zA-Z0-9\/.-]+ printf("FILENAME "); /* 文件名 */
\" printf("QUOTE "); /* 引號" */
\{ printf("OBRACE "); /* 左花括號 */
\} printf("EBRACE "); /* 右花括號 */
; printf("SEMICOLON "); /* 分號 */
\n printf("\n"); /* 換行 */
[ \t]+ /* 忽略空白字符 */
%%
int yywrap(void) /* 當(dāng)詞法分析器到了文件末尾做什么 */
{
return 1; /* 返回1，說明停止前進，0則繼續(xù) */
}
int yyerror(char *s) /* 錯誤信息打印函數(shù) */
{
fprintf(stderr, "%s\n", s);
return 0;
}
int main(int argc, char *argv[])
{
FILE *fp;
fp = fopen(argv[1], "r"); /* 首先打開要被處理的文件（參數(shù)1） */
yyin = fp; /* yyin是lex默認(rèn)的文件輸入指針，則不處理控制臺輸入 */
yylex(); /* 調(diào)用lex的工作函數(shù)，從這里開始，lex的詞法分析器開始工作 */
fclose(fp);
return 0;
}到這里，我們已經(jīng)完全可以對一個包含各種類型詞組的源代碼文件進行分析，得出其中各類型詞組的排列順序。在一個規(guī)范的基于語法的源代碼中，詞組的順序從一定意義上來說，就是語法。對于源代碼，lex的處理能力也就到這里為止，但是我們并沒有完全展示lex的所有功能，讀者如果有興趣，可以繼續(xù)深入閱讀本文提供的參考文獻。如何進行語法分析？我們在下面的章節(jié)中講開始講述Bison的基本使用方法，以及如何使用Bison進行語法分析。
E : E '+' E
E : E '*' E
E : id
在這三句中，E在Bison語言中代表表達式，一個表達式可以是一個數(shù)字，也可以是一個變量名稱，也可以是幾個變量名稱的組合，比如：
1
1+2
a
a+b*c
而以上三句Bison語言就能夠表達這些語法結(jié)構(gòu)。
我們在下面作一個計算器，通過這個實例讓大家明白Flex和Bison的相互關(guān)系和如何共同工作。首先，建立test2ll.l文件，并輸入以下內(nèi)容：
/* 計算器的詞法分析器描述，F(xiàn)lex語言 */
%{ /* 直接翻譯為C語言 */
#include <stdlib.h> /* 包含標(biāo)準(zhǔn)庫文件 */
int yyerror(char *); /* 這是我們上面用到的錯誤報告函數(shù) */
#include "test2yy.h" /* 這個頭文件由Bison自動生成 */
%}
%%
[0-9]+ {
yylval = atoi(yytext); /* yytext是flex內(nèi)部用于指向當(dāng)前詞匯的字符串指針 */
return INTEGER; /* INTEGER是從test2yy.h中包含過來的，在Bison中定義 */
}
[-+\n] return *yytext;
[ \t] ; /* 跳過空白字符 */
. yyerror("invalid character"); /* 產(chǎn)生一個錯誤，說明是無效字符 */
%%
int yywrap(void)
{
return 1; /* 文件結(jié)束時退出 */
}
以上就是計算器使用的Flex語言，描述了我們將會遇到的各種詞匯的格式，比如0-9 編譯過程： 在這個例子中，我們遇到了許多沒有見過的用法，Bison的書寫格式基本與Flex的相同，只是規(guī)則的定義語法不同。其中，$N（N為數(shù)字）代表語法描述中，第N個詞匯的內(nèi)容，比如(1)中的$1代表'+'左邊的expr，$3代表右邊expr的內(nèi)容，其中的N是指當(dāng)前語法的詞匯順序，從1開始計數(shù)。而$$則代表這一段語法處理完后的結(jié)果，每一個語法對應(yīng)的處理都有輸入$N和輸出$$。該例子中還有一個特殊的地方，就是第歸調(diào)用，在Bison中，語法規(guī)則可以是第歸的，這也是Bison之處（或者說是YACC的強大之處）。舉個例子： 這里，program的定義就是任何符合program的表達式后面緊接著expr和'\n'，掃描到該表達式后，將expr處理的結(jié)果打印到屏幕。最后的|是“或者”的意思，也就是說program也可以是空的，什么都不寫，分號代表該語義定義結(jié)束。有了第歸之后，Bison才可以說是一個能夠應(yīng)對任何狀況的語法分析器，當(dāng)然，這里還需要讀者對以上所提供代碼進行深入的研究和分析，考慮清楚后，會發(fā)現(xiàn)無論是C語言，還是Bison，第歸永遠是一個神奇的解決方案。 這樣看，這個計算器的功能已經(jīng)相當(dāng)強大了，下面我們著手實現(xiàn)，首先修改上面例子的Flex文件為如下： 下面是我們新的Bison文件： 現(xiàn)在我們對該例子中引入的新功能介紹，%left，%right，%token都是用來聲明詞匯的，區(qū)別在于，%token聲明的詞匯與左右優(yōu)先級無關(guān)，而%left的處理時，先處理左邊的，%right先處理右邊的，例如遇到字符串"1 - 2- 5"，到底是處理為"(1 - 2) - 5"，還是處理為"1 - (2 -5)"？%left處理為前者，而%right處理為后者（注：第一個計算器代碼中就有這個缺陷，比如執(zhí)行1-2+3，得到的結(jié)果就是-4，作為一個練習(xí)，讀者可以使用這里講解的%left自行更正）。/* 注：您先抄寫，注解見下文 */
%{
#include <stdio.h>
int yylex(void);
int yyerror(char *);
%}
%token INTEGER /* Flex語言中INTEGER定義在此 */
%%
program:
program expr '\n' { printf("%d\n", $2); }
|
;
expr:
INTEGER { $$ = $1; }
| expr '+' expr { $$ = $1 + $3; } /* (1) */
| expr '-' expr { $$ = $1 - $3; } /* (2) */
;
%%
int yyerror(char *s)
{
fprintf(stderr, "%s\n", s);
}
int main(void)
{
yyparse();
return 0;
}flex -otest2ll.c test2ll.l
bison -otest2yy.c test2yy.y -d # 注意-d，用于產(chǎn)生對應(yīng)的頭文件
gcc test2yy.c test2ll.c -o test2program:
program expr '\n' { printf("%d\n", $2); }
|
;3.3.計算器程序的深入研究
于是我們假想設(shè)計出來的計算器能有如下的操作過程（輸入和輸出）：輸入：3 * (4 + 5)
結(jié)果：27
輸入：x = 3 * (4 + 5)
輸入：y = 5
輸入：x
結(jié)果：27
輸入：y
結(jié)果：5
輸入：x + 2 * y
結(jié)果：37%{
#include <stdlib.h>
int yyerror(char *);
#include "test2yy.h"
%}
%%
[a-z] { /* 變量類型詞匯，限制：變量只能用一個字符 */
yylval = *yytext - 'a';
return VARIABLE;
}
[0-9]+ { /* 整數(shù) */
yylval = atoi(yytext);
return INTEGER;
}
[-+()=/*\n] { return *yytext; } /* 數(shù)學(xué)計算符號 */
[ \t] ; /* 跳過空白符號 */
%%
int yywrap(void)
{
return 1;
}%token INTEGER VARIABLE
%left '+' '-'
%left '*' '/'
%{
#include <stdio.h>
int yyerror(char *);
int yylex(void);
int sym[26]；
%}
%%
program:
program statement '\n'
|
;
statement:
expr { printf("%d\n", $1); }
| VARIABLE '=' expr { sym[$1] = $3; }
;
expr:
INTEGER
| VARIABLE { $$ = sym[$1]; }
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
| expr '*' expr { $$ = $1 * $3; }
| expr '/' expr { $$ = $1 / $3; }
| '(' expr ')' { $$ = $2; }
;
%%
int yyerror(char *s)
{
fprintf(stderr, "%s\n", s);
return 0;
}
int main(void)
{
yyparse();
return 0;
}
在下面的例子中，我們便寫了一個更高級的計算器程序，其操作實例如下：
x = 0;
while(x < 3) {
print(x);
x = x + 1;
}
例子中得到的輸出結(jié)果如下：
0
1
2
首先是我們的全局頭文件test3.h：
typedef enum {
typeCon,
typeId,
typeOpr
} nodeEnum;
/* constants */
typedef struct {
int value; /* value of constant */
} conNodeType;
/* identifiers */
typedef struct {
int i; /* subscript to sym array */
} idNodeType;
/* operators */
typedef struct {
int oper; /* operator */
int nops; /* number of operands */
struct nodeTypeTag *op[1]; /* operands (expandable) */
} oprNodeType;
typedef struct nodeTypeTag {
nodeEnum type; /* type of node */
/* union must be last entry in nodeType */
/* because operNodeType may dynamically increase */
union {
conNodeType con; /* constants */
idNodeType id; /* identifiers */
oprNodeType opr; /* operators */
};
} nodeType;
extern int sym[26];下面是Flex語言文件test3ll.l：
%{
#include <stdlib.h>
#include "test3.h"
#include "test3yy.h"
int yyerror(char *);
%}
%%
[a-z] {
yylval.sIndex = *yytext - 'a';
return VARIABLE;
}
[0-9]+ {
yylval.iValue = atoi(yytext);
return INTEGER;
}
[-()<>=+*/;{}.] {
return *yytext;
}
">=" return GE;
"<=" return LE;
"==" return EQ;
"!=" return NE;
"while" return WHILE;
"if" return IF;
"else" return ELSE;
"print" return PRINT;
[ \t\n]+ ; /* ignore whitespace */
. yyerror("Unknown character");
%%
int yywrap(void)
{
return 1;
}然后是我們的Bison文件test3yy.y：
%{
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include "test3.h"
/* prototypes */
nodeType *opr(int oper, int nops, ...);
nodeType *id(int i);
nodeType *con(int value);
void freeNode(nodeType *p);
int yylex(void);
int yyerror(char *s);
int sym[26];
%}
%union {
int iValue; /* integer value */
char sIndex; /* symbol table index */
nodeType *nPtr; /* node pointer */
};
%token <iValue> INTEGER
%token <sIndex> VARIABLE
%token WHILE IF PRINT
%nonassoc IFX
%nonassoc ELSE
%left GE LE EQ NE '>' '<'
%left '+' '-'
%left '*' '/'
%nonassoc UMINUS
%type <nPtr> stmt expr stmt_list
%%
program:
function { exit(0); }
;
function:
function stmt { ex($2); freeNode($2); }
|
;
stmt:
';' { $$ = opr(';', 2, NULL, NULL); }
| expr ';' { $$ = $1; }
| PRINT expr ';' { $$ = opr(PRINT, 1, $2); }
| VARIABLE '=' expr ';' { $$ = opr('=', 2, id($1), $3); }
| WHILE '(' expr ')' stmt { $$ = opr(WHILE, 2, $3, $5); }
| IF '(' expr ')' stmt %prec IFX{ $$ = opr(IF, 2, $3, $5); }
| IF '(' expr ')' stmt ELSE stmt{ $$ = opr(IF, 3, $3, $5, $7); }
| '{' stmt_list '}' { $$ = $2; }
;
stmt_list:
stmt { $$ = $1; }
| stmt_list stmt { $$ = opr(';', 2, $1, $2); }
;
expr:
INTEGER { $$ = con($1); }
| VARIABLE { $$ = id($1); }
| '-' expr %prec UMINUS { $$ = opr(UMINUS, 1, $2); }
| expr '+' expr { $$ = opr('+', 2, $1, $3); }
| expr '-' expr { $$ = opr('-', 2, $1, $3); }
| expr '*' expr { $$ = opr('*', 2, $1, $3); }
| expr '/' expr { $$ = opr('/', 2, $1, $3); }
| expr '<' expr { $$ = opr('<', 2, $1, $3); }
| expr '>' expr { $$ = opr('>', 2, $1, $3); }
| expr GE expr { $$ = opr(GE , 2, $1, $3); }
| expr LE expr { $$ = opr(LE , 2, $1, $3); }
| expr NE expr { $$ = opr(NE , 2, $1, $3); }
| expr EQ expr { $$ = opr(EQ , 2, $1, $3); }
| '(' expr ')' { $$ = $2; }
;
%%
#define SIZEOF_NODETYPE ((char*)&p->con - (char*)p)
nodeType *con(int value) {
nodeType *p;
size_t nodeSize;
/* allocate node */
nodeSize = SIZEOF_NODETYPE + sizeof(conNodeType);
if((p = malloc(nodeSize)) == NULL)
yyerror("out of memory");
/* copy information */
p->type = typeCon;
p->con.value = value;
return p;
}
nodeType *id(int i) {
nodeType *p;
size_t nodeSize;
/* allocate node */
nodeSize = SIZEOF_NODETYPE + sizeof(idNodeType);
if((p = malloc(nodeSize)) == NULL)
yyerror("out of memory");
/* copy information */
p->type = typeId;
p->id.i = i;
return p;
}
nodeType *opr(int oper, int nops, ...) {
va_list ap;
nodeType *p;
size_t nodeSize;
int i;
/* allocate node */
nodeSize = SIZEOF_NODETYPE + sizeof(oprNodeType) +
(nops - 1) * sizeof(nodeType*);
if((p = malloc(nodeSize)) == NULL)
yyerror("out of memory");
/* copy information */
p->type = typeOpr;
p->opr.oper = oper;
p->opr.nops = nops;
va_start(ap, nops);
for(i = 0; i < nops; i++)
p->opr.op[i] = va_arg(ap, nodeType*);
va_end(ap);
return p;
}
void freeNode(nodeType *p) {
int i;
if(!p) return;
if(p->type == typeOpr) {
for(i=0; i<p->opr.nops; i++)
freeNode(p->opr.op[i]);
}
free(p);
}
int yyerror(char *s) {
fprintf(stdout, "%s\n", s);
}
int main(void) {
yyparse();
return 0;
}上面的Flex和Bison代碼所作的工作是根據(jù)語法建立語意描述樹結(jié)構(gòu)。延續(xù)我們上面計算器的例子，我們寫出如何翻譯這些語言的實現(xiàn)部分（對生成的樹進行第歸分析）：
#include <stdio.h>
#include "test3.h"
#include "test3yy.h"
int ex(nodeType *p) {
if(!p) return 0;
switch(p->type) {
case typeCon:
return p->con.value;
case typeId:
return sym[p->id.i];
case typeOpr:
switch(p->opr.oper) {
case WHILE:
while(ex(p->opr.op[0]))
ex(p->opr.op[1]);
return 0;
case IF:
if(ex(p->opr.op[0]))
ex(p->opr.op[1]);
else if(p->opr.nops > 2)
ex(p->opr.op[2]);
return 0;
case PRINT:
printf("%d\n", ex(p->opr.op[0]));
return 0;
case ';':
ex(p->opr.op[0]);
return ex(p->opr.op[1]);
case '=':
return sym[p->opr.op[0]->id.i] = ex(p->opr.op[1]);
case UMINUS:
return -ex(p->opr.op[0]);
case '+':
return ex(p->opr.op[0]) + ex(p->opr.op[1]);
case '-':
return ex(p->opr.op[0]) - ex(p->opr.op[1]);
case '*':
return ex(p->opr.op[0]) * ex(p->opr.op[1]);
case '/':
return ex(p->opr.op[0]) / ex(p->opr.op[1]);
case '<':
return ex(p->opr.op[0]) < ex(p->opr.op[1]);
case '>':
return ex(p->opr.op[0]) > ex(p->opr.op[1]);
case GE:
return ex(p->opr.op[0]) >= ex(p->opr.op[1]);
case LE:
return ex(p->opr.op[0]) <= ex(p->opr.op[1]);
case NE:
return ex(p->opr.op[0]) != ex(p->opr.op[1]);
case EQ:
return ex(p->opr.op[0]) == ex(p->opr.op[1]);
}
}
}
一般實際的編譯器都是以匯編代碼輸出的，所以我們在這里進行一些深入研究，得出了另一個版本的ex函數(shù)實現(xiàn)，能夠?qū)崿F(xiàn)匯編代碼的輸出（compiler.c）：
#include <stdio.h>
#include "test3.h"
#include "test3yy.h"
static int lbl;
int ex(nodeType *p) {
int lbl1, lbl2;
if(!p) return 0;
switch(p->type) {
case typeCon:
printf("\tpush\t%d\n", p->con.value);
break;
case typeId:
printf("\tpush\t%c\n", p->id.i + 'a');
break;
case typeOpr:
switch(p->opr.oper) {
case WHILE:
printf("L%03d:\n", lbl1 = lbl++);
ex(p->opr.op[0]);
printf("\tjs\tL%03d\n", lbl2 = lbl++);
ex(p->opr.op[1]);
printf("\tjz\tL%03d\n", lbl1);
printf("L%03d:\n", lbl2);
break;
case IF:
ex(p->opr.op[0]);
if(p->opr.nops > 2) {
/* if else */
printf("\tjs\tL%03d\n", lbl1 = lbl++);
ex(p->opr.op[1]);
printf("\tjmp\tL%03d\n", lbl2 = lbl++);
printf("L%03d:\n", lbl1);
ex(p->opr.op[2]);
printf("L%03d:\n", lbl2);
} else {
/* if */
printf("\tjs\tL%03d\n", lbl1 = lbl++);
ex(p->opr.op[1]);
printf("L%03d:\n", lbl1);
}
break;
case PRINT:
ex(p->opr.op[0]);
printf("\tprint\n");
break;
case '=':
ex(p->opr.op[1]);
printf("\tpop\t%c\n", p->opr.op[0]->id.i + 'a');
break;
case UMINUS:
ex(p->opr.op[0]);
printf("\tneg\n");
break;
default:
ex(p->opr.op[0]);
ex(p->opr.op[1]);
switch(p->opr.oper) {
case '+': printf("\tadd\n"); break;
case '-': printf("\tsub\n"); break;
case '*': printf("\tmul\n"); break;
case '/': printf("\tdiv\n"); break;
case '<': printf("\tcompLT\n"); break;
case '>': printf("\tcompGT\n"); break;
case GE: printf("\tcompGE\n"); break;
case LE: printf("\tcompLE\n"); break;
case NE: printf("\tcompNE\n"); break;
case EQ: printf("\tcompEQ\n"); break;
}
}
}
return 0;
}
使用方法：取消interpreter.c的編譯，取而代之用compiler.c即可。關(guān)于這個計算器的代碼分析，請等待后續(xù)，（未完待續(xù)）
