簡介

如果你有Unix環(huán)境的編程經(jīng)驗(yàn)，想必你肯定遇到過神秘的Lex和YACC工具畸陡，在GUN/Linux中吏颖，又分別稱作Flex和Bison,其中Flex是由Vern Paxon實(shí)現(xiàn)的Lex版本歼冰，Bison是GUN版本的YACC.我們統(tǒng)一稱他們?yōu)長ex和YACC失晴，這些新版本是向上兼容的剧腻，因此你可以在我們的示例中使用Flex以及Bison.

這兩個(gè)程序是非常有用的，但是跟C編譯器一樣师坎，它的用戶手冊(cè)上即不會(huì)解釋C語言,也不會(huì)告訴你如何使用C語言恕酸。YACC與Lex一起使用時(shí)非常有用,然而，Bison用戶手冊(cè)并沒有介紹如何將Lex代碼集成到Bison程序里胯陋。

Lex

Lex 程序生成的的文件被稱作分詞器。它是一個(gè)函數(shù)袱箱，輸入為字符流遏乔，只要發(fā)現(xiàn)一段字符能夠匹配一個(gè)關(guān)鍵字，就會(huì)采取對(duì)應(yīng)的動(dòng)作发笔。一個(gè)非常簡單的示例:

%{
#include <stdio.h>
%}

%%
stop    printf("Stop command received\n");
start   printf("Start command received\n");
%%

位于%{和%}之間的第一個(gè)段原封不動(dòng)的導(dǎo)出到輸出程序盟萨。因?yàn)槭褂昧藀rintf，因此我們需要stdio.h了讨。

段之間被%%分割了開來捻激，第二段的第一行起于stop健值，表示當(dāng)從輸入流中讀取到stop時(shí)就會(huì)執(zhí)行后面的printf("Stop command received\n");
除了stop,我們還定義了start前计，作用與stop一樣胞谭。

段以%%結(jié)束。

為了編譯Example1,執(zhí)行

$ lex example1.lt
cc lex.yy.c -o example -ll 

** 請(qǐng)注意：如果你使用Flex,請(qǐng)用Lex替代之男杈，可能你還要將-ll替換成-lfl.至少RetHat 6.x以及SuSE需要丈屹。**

上面的命令會(huì)生成程序example1，如果你運(yùn)行它，它會(huì)等待你的輸入旺垒。只要你的輸入內(nèi)容與定義的鍵值(stop和start)不匹配彩库，就會(huì)將它們輸出。如果你輸入stop先蒋，它會(huì)輸出 Stop command received骇钦。

以EOF（^D）結(jié)束輸入。

也許你想知道程序?yàn)槭裁茨苓\(yùn)行竞漾，因?yàn)槲覀儔焊鶝]有定義main函數(shù)眯搭。其實(shí)main函數(shù)在libl(liblex)中被定義，通過 -ll被引入了進(jìn)來畴蹭。

正則匹配

上面的示例的實(shí)用效果不佳坦仍，接下來的亦然。不過它會(huì)在Lex中引用正則叨襟，這點(diǎn)將會(huì)在后面的示例中非常有用繁扎。

Example 2:

%{
#include <stdio.h>
%}

%%
[0123456789]+       printf("NUMBER\n");
[a-zA-Z][a-zA-Z0-9]*    printf("WORD\n");
%%

上面這個(gè)Lex文件描述兩種匹配的符號(hào)：WORD和NUMBER。學(xué)習(xí)正則表達(dá)式可能有一點(diǎn)困難糊闽，但只須花點(diǎn)功夫便可輕松的理解它們梳玫。來看下NUMBER的匹配：

[0123456789]+ 

意思是：一系列的一個(gè)或多個(gè)取自于0123456789中的字符。簡便寫法是：

[0-9]+ 

WORD的匹配：

[a-zA-Z][z-zA-Z0-9]* 

第一個(gè)部分（第一個(gè)方括號(hào)內(nèi)）僅匹配一個(gè)介與'a'和'z'之間的字符右犹，或者說提澎，一個(gè)字母。這個(gè)初始的字母后面需要跟0個(gè)多更多的字符念链，這些字符即可以是字母也可以是數(shù)字盼忌。為何此處使用星號(hào)呢？

+意思是1個(gè)或更多的匹配掂墓，但是一個(gè)WORD可以僅由一個(gè)字符組成谦纱，即已經(jīng)匹配的第一個(gè)部分。因此第二人部分或許是0個(gè)匹配君编，因此用'*'跨嘉。

這樣我們就模仿了大部分編程語言中變量必須由一個(gè)字母開頭，但是后面可以有數(shù)字吃嘿。例如祠乃，'temperature1'是個(gè)合法的名字，但是'1temperature'不是兑燥。

嘗試編譯Example2,方法于Example1一樣亮瓷。輸入一些文字，以下是一些樣例：

$ ./example2
foo WORD bar WORD 123 NUMBER bar123 WORD 123bar NUMBER WORD 

Flex的用戶手冊(cè)上關(guān)于正則表述式描述的很詳細(xì)贪嫂。perl用戶手冊(cè)（perler）關(guān)于正則部分也很有用寺庄，盡管Flex沒有實(shí)現(xiàn)perl的全部。

** 確認(rèn)你沒有創(chuàng)建形如[0-9]這樣可以匹配模式，否則你的lexer會(huì)重復(fù)的匹配空字段串斗塘。*

一個(gè)更復(fù)雜的類C語法示例

假設(shè)下面是一個(gè)我們想解析的文件：

logging {
    category lame?servers { null; };
    category cname { null; };
};

zone "." {
    type hint;
    file "/etc/bind/db.root";
}; 

這個(gè)文件中有以下幾類符號(hào)(tokens)

WORDs 赢织，如zone和type

FILENAMEs ，如/etc/bind/db.root

QUOTEs 馍盟，如包括文件名的符號(hào)

OBRACEs 于置，左花括號(hào){

EBRACEs ，右花括號(hào)}

SEMICOLONs 贞岭，;

對(duì)應(yīng)的Lex文件如下（Example 3）：

%{
#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]+                  /* ignore whitespace */;
%%

當(dāng)我們將文件輸入分詞器時(shí),得到：

WORD OBRACE
WORD FILENAME OBRACE WORD SEMICOLON EBRACE SEMICOLON
WORD WORD OBRACE WORD　SEMICOLON EBRACE SEMICOLON
EBRACE SEMICOLON

WORD QUOTE FILENAME QUOTE OBRACE
WORD WORD SEMICOLON
WORD QUOTE FILENAME QUOTE SEMICOLON
EBRACE SEMICOLON 

與之前提到的配置文件相比八毯，很明顯我們對(duì)其進(jìn)行了符號(hào)化。配置文件的每個(gè)部分都被匹配了并且轉(zhuǎn)化成指定的符號(hào)瞄桨。

這正是我們要給YACC使用的话速。

YACC

YACC能夠?qū)⑤斎氲姆?hào)流解析成指定的值。這里清晰的描述了YACC與Lex之前的關(guān)系芯侥。YACC沒有輸入流的概念泊交，它僅接受預(yù)處理過的符號(hào)集。你可以自己寫符號(hào)生成器柱查，不過本文全部將其交給Lex廓俭。

關(guān)于語法跟語法分析器的一點(diǎn)小注意：當(dāng)YACC成熟時(shí)，它就被用作編譯器的解析文析的工具唉工。計(jì)算機(jī)語言不允許有二義性研乒。因此，YACC在遇到有歧義時(shí)會(huì)抱怨移進(jìn)/歸約或者歸約/歸約沖突淋硝。更多關(guān)于YACC與歧義的問題參考沖突章節(jié)雹熬。

一個(gè)簡單的溫度調(diào)節(jié)控制器

我們想用一門簡單的語言去控制一個(gè)溫度調(diào)節(jié)器，例如：

heat on Heater on!
heat off Heater off!
target temperature 22 New temperature set! 

我們需要辨別的符號(hào)有：heat,on/off(STATE),target,temperature,NUMBER谣膳。對(duì)應(yīng)的Lex文件如下（Example 4）:

%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+                  return NUMBER;
heat                    return TOKHEAT;
on|off                  return STATE;
target                  return TOKTARGET;
temperature             return TOKTEMPERATURE;
\n                      /* ignore end of line */;
[ \t]+                  /* ignore whitespace */;
%%

注意兩個(gè)重要的變化橄唬。第一，引入了頭文件y.tab.h参歹。第二，我們不再使用print函數(shù)隆判，而是直接返回符號(hào)的名字犬庇。這樣做的目的是為了接下來將它嵌入到Y(jié)ACC中，而后者對(duì)打印到屏幕的內(nèi)容根本不關(guān)心侨嘀。Y.tab.h定義了這些符號(hào)臭挽。

但是y.tab.h是從哪得到的呢？它是由YACC從語法文件中生成的咬腕。 我們的語言非常簡單欢峰，以下是它的語法：

%%

commands: /* empty */
    | commands command
    ;


command:
    heat_switch
    |
    target_set
    ;

heat_switch:
    TOKHEAT STATE 
    {
        printf("\tHeat turned on or off\n");
    }
    ;

target_set:
    TOKTARGET TOKTEMPERATURE NUMBER
    {
        printf("\tTemperature set\n");
    }
    ;

第一個(gè)部分我稱之為根，它告訴我們有命令集（commands）,并且這些命令集由一些獨(dú)立的命令（command）組成。如你所見纽帖，這些規(guī)則是遞歸的宠漩，因?yàn)樗旧碛职薱ommands.這就意味著通過遞歸可以將這一系列的命令集進(jìn)行歸約。閱讀Lex和YACC內(nèi)部原理獲取更多遞歸的詳細(xì)內(nèi)容懊直。

第二個(gè)部分規(guī)則定義了command具體是什么扒吁。我們只支持兩種命令：heat_switch和target_set。這個(gè)是|-符號(hào)的意思：一個(gè)命令（command）包含了heat_switch或target_set室囊。

heat_switch包含了HEAT符號(hào)雕崩，即一個(gè)簡單的單詞heat以及后面跟一個(gè)狀態(tài)（在Lex中定義的on或off）。

target_set稍微有些復(fù)雜融撞，它由TARGET符號(hào)（單詞target）盼铁，TEMPERATURE符號(hào)（單詞）以及一個(gè)數(shù)字組成。

完整的YACC文件

前面一節(jié)僅列出了YACC文件的部分尝偎，以下是我們省略的開頭部分：

%{
#include <stdio.h>
#include <string.h>

void yyerror(const char *str)
{
    fprintf(stderr,"error: %s\n",str);
}

int yywrap()
{
    return 1;
}

main()
{
    yyparse();
}

%}

%token NUMBER TOKHEAT STATE TOKTARGET TOKTEMPERATURE

函數(shù)yyerror在YACC發(fā)生錯(cuò)誤時(shí)被調(diào)用 饶火，我們只是簡單的將傳入的信息打印了出來，實(shí)際有比這更巧妙的處理冬念，參閱"深度閱讀"一節(jié)趁窃。

函數(shù)yywrap能夠用于是否繼續(xù)讀取其它的文件，當(dāng)遇到EOF時(shí)急前，你可以打開其它文件并返回0醒陆。或者裆针，返回1刨摩，意味著真正的結(jié)束。欲知更多世吨，請(qǐng)參閱"Lex和YACC內(nèi)部工作原理"章節(jié)澡刹。

函數(shù)main是程序的起點(diǎn)。

最后一行簡單的定義了哪些符號(hào)將會(huì)被用到耘婚，如果調(diào)用YACC時(shí)啟用了-d選項(xiàng)罢浇，會(huì)將這些符號(hào)會(huì)輸出到y(tǒng).tab.h文件。

編譯沐祷、運(yùn)行溫度調(diào)節(jié)控制器

lex example4.l
yacc -d example4.y
cc lex.yy.c y.tab.c -o example4 

有一點(diǎn)小變化∪卤眨現(xiàn)在我們使用YACC編譯我們的程序，它生成y.tab.c和y.tab.h文件.然后才是調(diào)用Lex赖临。編譯時(shí)胞锰，不再需要-ll,因?yàn)槌绦蛑形覀兌x了自己的main函數(shù)。

**注意：如果你得到一個(gè)編譯器錯(cuò)誤：not being able to find 'yylval',將下面的內(nèi)容加入到文件example4.l中的#include 下面 **

extern YYSTYPE yylval; 

Lex 和YACC工作內(nèi)部原理有相關(guān)的解釋兢榨。

運(yùn)行示例：

$ ./example4
heat on Heat turned on or off heat off Heat turned on or off target temperature 10 Temperature set
target humidity 20 error: parse error 

以上并不是我們要完成的真正目標(biāo)嗅榕，而是通過此例循序漸進(jìn)顺饮，控制學(xué)習(xí)曲線，使讀者繼續(xù)保持興趣凌那。并非所有酷的特性都能一次被展示兼雄。

拓展溫度調(diào)節(jié)器使其可處理參數(shù)

上面的示例可以正確的解析溫度調(diào)節(jié)器的命令，但是它并不知道應(yīng)該做什么案怯，它并不能取到你輸入的溫度值君旦。

接下來工作就是向其中加一點(diǎn)功能使之可以讀取出具體的溫度值。為此我們需要學(xué)習(xí)如何將Lex中的數(shù)字（NUMBER）匹配轉(zhuǎn)化成一個(gè)整數(shù)嘲碱，使其可以在YACC中被讀取金砍。

當(dāng)Lex匹配到一個(gè)目標(biāo)時(shí)，它就會(huì)將匹配到的文字放到y(tǒng)ytext中麦锯。YACC從變量yylval中取值恕稠。在下面的Example5中，是一種直接的方法：

%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+                  yylval=atoi(yytext); return NUMBER;
heat                    return TOKHEAT;
on|off                  yylval=!strcmp(yytext,"on"); return STATE;
target                  return TOKTARGET;
temperature             return TOKTEMPERATURE;
\n                      /* ignore end of line */;
[ \t]+                  /* ignore whitespace */;
%%

如你所見扶欣，以yytext作為參數(shù)調(diào)用atoi函數(shù)鹅巍，并將其返回值賦給yylval變量，這樣YACC就可以使用它料祠。我們對(duì)STATE采用類似的處理方式：如果為on,yylval為1骆捧。
請(qǐng)注意，在Lex中分別對(duì)on和offf進(jìn)行匹配可以得到更快的處理代碼髓绽，但是我想展示一點(diǎn)更復(fù)雜的規(guī)則敛苇。

接下來我們學(xué)習(xí)YACC如何處理這些。Lex中我們稱為yylval顺呕，在YACC有另外一個(gè)名字枫攀。下面檢查設(shè)置溫度目標(biāo)的規(guī)則：

target_set:
    TOKTARGET TOKTEMPERATURE NUMBER
    {
        printf("\tTemperature set to %d\n",$3);
    }
    ;

為了取到規(guī)則中的第三個(gè)部分的值，（例如株茶，NUMBER）,我們需要使用$3来涨，只要yylex返回，yylval的值就會(huì)被顯示在終端中启盛，其值經(jīng)由$取得蹦掐。

為了闡述這個(gè)特性，讓我們觀查新的heat_switch規(guī)則：

heat_switch:
    TOKHEAT STATE 
    {
        if($2)
            printf("\tHeat turned on\n");
        else
            printf("\tHeat turned off\n");
    }
    ;

解析配置文件

讓我們繼續(xù)討論前面提到的配置文件：

zone "." { type hint; file "/etc/bind/db.root";
} 

之前我們已經(jīng)為其寫過一個(gè)分詞器〗┐常現(xiàn)在需要為其寫一個(gè)YACC語法文件并且修改那個(gè)分詞器以適應(yīng)YACC笤闯。
Example 6:

%{
#include <stdio.h>
#include "y.tab.h"
%}

%%

zone            return ZONETOK;
file            return FILETOK;
[a-zA-Z][a-zA-Z0-9]*    yylval=strdup(yytext); return WORD;
[a-zA-Z0-9\/.-]+        yylval=strdup(yytext); return FILENAME;
\"                      return QUOTE;
\{                      return OBRACE;
\}                      return EBRACE;
;                       return SEMICOLON;
\n                      /* ignore EOL */;
[ \t]+                  /* ignore whitespace */;
%%

仔細(xì)看你會(huì)發(fā)現(xiàn)yylval有所不同！我們不再期望它是一個(gè)整數(shù)棍厂，而是假設(shè)它為一個(gè)字符串。為了使其保持簡單超陆，采用了strdup并且浪費(fèi)了一些內(nèi)存牺弹。
使用字符串是因?yàn)榇蠖鄶?shù)時(shí)候我們處理的是名字：文件名和區(qū)域名浦马。稍后我們會(huì)解釋如何多類型數(shù)據(jù)。

為了告訴YACC中yylval的類型张漂，將下面的一行添加到Y(jié)ACC語法中：

#define YYSTYPE char * 

語法本身也變得更復(fù)雜了晶默，為了使其更容易理解，我們將其分成幾個(gè)部分來介紹航攒。

commands:
    |    
    commands command SEMICOLON
    ;


command:
    zone_set 
    ;

zone_set:
    ZONETOK quotedname zonecontent
    {
        printf("Complete zone for '%s' found\n",$2);
    }
    ;

上面是個(gè)引子磺陡，包含了前面提到的遞歸根，請(qǐng)注意我們指明了命令集以;結(jié)束漠畜。我們定義了一個(gè)叫zone_set的命令币他，它包含ZONE符號(hào)（單詞zone）,后面跟著一個(gè)帶引號(hào)的名稱和zonecontent。zonecontent很簡單：

zonecontent: OBRACE zonestatements EBRACE 

它以一個(gè)OBRACE（{）為開始憔狞，然后跟著zonestatements,再跟著一個(gè)EBRACE(})蝴悉。

qutedame: QUOTE FILENAME QUOTE { $$=$2 } 

上面定義了quotedname：一個(gè)在引號(hào)中間的文件名。然后特別定義：quotedname符號(hào)的值是FILENAME瘾敢，即quotedname的值是其本身文件名拍冠，但不包含包裹著它的引號(hào)。這就是命令$$=$2的含意簇抵。它指：我的值是我本身的第二個(gè)部分庆杜。當(dāng)quotedname在其它規(guī)則中被引用時(shí)，可通過$取其值碟摆，實(shí)際得到的值是經(jīng)由$$=$2指定的晃财。

zonestatements:
        |
        zonestatements zonestatement SEMICOLON
        ;
zonestatement:
        statements
        |
        FILETOK quotedname
        { printf("A zonefile name '%s' was encountered\n",$2);
        }
        ; 

以上是zone塊里面所有申明的框架，我們又一次看到了遞歸焦履。

block: 
    OBRACE zonestatements EBRACE SEMICOLON
    ;

statements:
    | statements statement
    ;

statement: WORD | block | quotedname

上面定義了一個(gè)塊拓劝，里面包含了申明語句。
執(zhí)行它嘉裤，得到如下結(jié)果：

$ ./example6
zone "." { type hint;
        file "/etc/bind/db.root"; type hint;
};
A zonefile name '/etc/bind/db.root' was encountered
Complete zone for '.' found 

用c++制作解析器

盡管Lex和YACC比C++要出現(xiàn)的早郑临，但也可以生成一個(gè)c++版的解析器。雖然Flex包含一個(gè)可以生成c++的分詞器的參數(shù) 屑宠，但我們不會(huì)使用它厢洞，因?yàn)閅ACC不知道如何直接使用它們。

我比較喜歡通過Lex生成一個(gè)c語言文件典奉，然后再用YACC生成c++代碼躺翻。不過當(dāng)你使用鏈接器生成你程序時(shí)，可能會(huì)遇到一些問題卫玖，因?yàn)閏++代碼默認(rèn)不能找到C語言中的函數(shù)公你。除非你用extren申明這些函數(shù)。為了這樣做假瞬，在YACC中放入如下的C代碼：

extern "C" { 
  int yyparse(void);
  int yylex(void);
  int yywrap() {
     return 1;
  }
} 

如果你想申明或者改變yydebug,你得這樣做：

extern int yydebug;
main()
{
    yydebug=1;
    yyparse();
} 

你也許已經(jīng)發(fā)現(xiàn)需要將YYSTYPE的定義放到Lex文件中陕靠，因?yàn)镃++是嚴(yán)格類型的檢查迂尝。

用下以方式編譯：

lex bindconfig2.l
yacc ??verbose ??debug ?d bindconfig2.y ?o bindconfig2.cc
cc ?c lex.yy.c ?o lex.yy.o
c++ lex.yy.o bindconfig2.cc ?o bindconfig2 

因?yàn)閅ACC使用了-o選項(xiàng)，y.tab.h現(xiàn)在被稱作bindconfig2.cc.h剪芥。
總結(jié)：不要將分詞器編譯成c++垄开。用c++生成語法解析器時(shí)需要用exetern "C"語句告訴編譯器C中的函數(shù)。

Lex和YACC內(nèi)部工作原理

在YACC文件中税肪，main函數(shù)調(diào)用了yyparse()溉躲，此函數(shù)由YACC替你生成的，在y.tab.c文件中益兄。

函數(shù)yyparse從yylex中讀取符號(hào)/值組成的流锻梳。你可以自己編碼實(shí)現(xiàn)這點(diǎn)，或者讓Lex幫你完成偏塞。在我們的示例中唱蒸，我們選擇將此任務(wù)交給Lex。

Lex中的yylex函數(shù)從一個(gè)稱作yyin的文件指針?biāo)傅奈募凶x取字符灸叼。如果你沒有設(shè)置yyin神汹，默認(rèn)是標(biāo)準(zhǔn)輸入(stdin)。輸出為yyout古今，默認(rèn)為標(biāo)準(zhǔn)輸出(stdout)屁魏。

你可以在yywrap函數(shù)中修改yyin，此函數(shù)在每一個(gè)輸入文件被解析完畢時(shí)被調(diào)用捉腥，它允許你打開其它的文件繼續(xù)解析氓拼，如果是這樣，yywarp的返回值為0抵碟。如果想結(jié)束解析文件桃漾，返回1。

每次調(diào)用yylex函數(shù)用一個(gè)整數(shù)作為返回值拟逮，表示一種符號(hào)類型撬统，告訴YACC當(dāng)前讀取到的符號(hào)類型，此符號(hào)是否有值是可選的敦迄，yylval即存放了其值恋追。

默認(rèn)yylval的類型是整型（int）,但是可以通過重定義YYSTYPE以對(duì)其進(jìn)行重寫。分詞器需要取得yylval,為此必須將其定義為一個(gè)外部變量罚屋。原始YACC不會(huì)幫你做這些苦囱，因此你得將下面的內(nèi)容添加到你的分詞器中，就在#include下即可：

extern YYSTYPE yylval; 

Bison會(huì)自動(dòng)幫你做這些脾猛。

符號(hào)值

前面提到過撕彤，函數(shù)yylex需要返回它遇到的符號(hào)類型，并將其值放到y(tǒng)ylval中猛拴。這些符號(hào)經(jīng)由命令%token定義喉刘，并對(duì)其賦值了數(shù)字類型的id號(hào)瞧柔，以256開始。

基于此睦裳，所有ascii字符都可以作為一個(gè)符號(hào)。比方說你要寫一個(gè)計(jì)算器撼唾，到目前為止廉邑，我們可以寫一個(gè)如下的分詞器：

[0-9]+          yylval=atoi(yytext);return NUMBER;
[ \n]+ /*eat whitespace */;
- return MINUS;
\* return MULT
\+ return PLUS;
... 

語法可以是這樣：

exp:    NUMBER
        | exp PLUS exp | exp MINUS exp | exp MULT exp 

其實(shí)沒必要這樣復(fù)雜。通過使用ascii字符為符號(hào)的id,分詞器可以寫成這樣：

[0-9]+          yylval=atoi(yytext);return NUMBER;
[ \n]+ /*eat whitespace */;
. return (int)yytext[0];
... 

.匹配所有匹配的單字符倒谷。對(duì)應(yīng)的語法為：

exp:    NUMBER
        | exp '+' exp | exp '-' exp | exp '*' exp 

這樣看起來更直接也更短了蛛蒙，你不需要在頭部使用%定義那些字符。

這樣做還有一個(gè)優(yōu)點(diǎn)渤愁，即對(duì)于所有的輸入牵祟，Lex都會(huì)匹配，避免了默認(rèn)不匹配時(shí)將其輸出到標(biāo)準(zhǔn)輸出抖格。比方說用戶在計(jì)算器中使用^,會(huì)產(chǎn)生一個(gè)解析錯(cuò)誤诺苹，而非將其輸出到標(biāo)準(zhǔn)輸出。

遞歸：'右即是錯(cuò)'

遞歸是YACC必不可少的雹拄。沒有它收奔，你就不能指定一個(gè)文件包含一系列的獨(dú)立命令或語句。根據(jù)規(guī)定滓玖，YACC僅對(duì)第一條規(guī)則感興趣坪哄，或者使用%start符號(hào)指定的起始規(guī)則。

YACC中的遞歸分為兩類：左遞歸和右遞歸势篡。大部分時(shí)候你應(yīng)該使用左遞歸翩肌，就像這樣：

commands: /*empty*/ |
        commands command 

它的意思是，一個(gè)命令集要么是空禁悠，要么它包含更多的命令集以及后面跟著一個(gè)命令念祭。YACC的工作方式意味著它可以輕松的砍掉單獨(dú)的命令塊（從前面）并逐步歸約它們。
與左遞歸相比绷蹲，右遞歸迷惑了大部分人棒卷，覺得看起來更好：

commands: /*empty*/ |
        command commands 

但這樣代價(jià)太高了。如果使用%start規(guī)則祝钢，需要YACC將所有的命令放在棧上比规，消耗很多的內(nèi)存。因此盡可能使用左遞歸解析長語句拦英，比如解析整個(gè)文件蜒什。
有時(shí)則無可避免的使用右遞歸，如果你的語句不是太長疤估，你不需要想盡一切方法使用左遞歸灾常。

如果命令有終結(jié)符霎冯，右遞歸看起來更自然一些,但是仍然代價(jià)昂貴：

commands: /*empty*/ |
        command SEMICOLON commands 

正確的代碼是使用左遞歸：

commands: /* empty */ |
        commands command SEMICOLON\ 

高級(jí)yylval:%union

現(xiàn)在，我們需要定義yylval的類型钞瀑，雖然這并不總是合適的沈撞。有時(shí)我們需要處理多類型的數(shù)據(jù)〉袷玻回到早前的溫度調(diào)節(jié)器示例缠俺，假設(shè)我們想要能夠選擇一個(gè)加熱器進(jìn)行控制，像這樣：

heater mainbuiling
        Selected 'mainbuilding' heater
target temperature 23 'mainbuilding' heater target temperature now 23 

我們稱這這種yylval是個(gè)聯(lián)合體贷岸，它即可以處理字符串壹士，也可以是整數(shù)，但不是同時(shí)處理這兩種偿警。

之前說過躏救，YACC的yylval類型是取決于YYSTYPE，可以想象螟蒸，我們可以通過定義YYSTYPE為聯(lián)合體盒使。不過YACC有一個(gè)更簡單的方法：使用%union語句。

基于例4尿庐，現(xiàn)在我們寫出如下的YACC語法（Example 7）忠怖，剛開始為：

%token TOKHEATER TOKHEAT TOKTARGET TOKTEMPERATURE %union { int number;
    char *string;
} %token  STATE %token  NUMBER %token  WORD 

定義了我們的聯(lián)合體，它僅包含數(shù)字和字體串抄瑟，然后使用一個(gè)擴(kuò)展的%token語法鞭莽，告訴YACC應(yīng)該取聯(lián)合體的哪一個(gè)部分赘来。

這個(gè)例子中膘盖，我們定義STATE 為一個(gè)整數(shù)衩椒，這點(diǎn)跟前面一樣，NUMBER符號(hào)用于讀取溫度值惹资。

不過新的WORD被定義為一個(gè)字符串贺纲。

分詞器文件也有很多改變：

%{ #include  #include  #include "y.tab.h" %}
%%
[0?9]+          yylval.number=atoi(yytext); return NUMBER;
heater return TOKHEATER;
heat return TOKHEATER;
on|off          yylval.number=!strcmp(yytext,"on"); return STATE;
target return TOKTARGET;
temperature return TOKTEMPERATURE;
[a?z0?9]+       yylval.string=strdup(yytext);return WORD;
\n /* ignore end of line */;
[ \t]+ /* ignore whitespace */;
%% 

如你所見，我們不再直接獲取yylval的值褪测，而是添加一個(gè)后綴指示想取得哪個(gè)部分的值猴誊。不過在YACC語法中，我們無須這樣做侮措，因?yàn)閅ACC為我們做了神奇的這些：

heater_select:
        TOKHEATER WORD
        { printf("\tSelected heater '%s'\n",$2);
            heater=$2;
        }
        ; 

由于上面的%token定義懈叹，YACC自動(dòng)從聯(lián)合體中挑選string成員。同時(shí)也請(qǐng)注意分扎，我們保存了一份$2的副本澄成，它在后面被用于告訴用戶是哪一個(gè)加熱器發(fā)出的命令：

target_set:
        TOKTARGET TOKTEMPERATURE NUMBER
        { printf("\tHeater '%s' temperature set to %d\n",heater,$3);
        }
        ; 

更多詳情請(qǐng)參考example7.y。

調(diào)試

特別是剛學(xué)習(xí)時(shí)，調(diào)度工具非常重要墨状。幸運(yùn)的是卫漫，YACC能夠給出許多反饋信息。這些反饋信息需要一定的開銷肾砂，你需要一些開關(guān)參數(shù)來啟用它們列赎。

當(dāng)你編譯語法文件時(shí)，在YACC命令行中增加 --debug和--verbose镐确。在語法的C語言的頭部粥谬，添加如下：

int yydebug=1; 

這樣會(huì)生成文件y.output,里面解釋了我們創(chuàng)建的狀態(tài)機(jī)。

當(dāng)你運(yùn)行生成的二進(jìn)制辫塌，它會(huì)輸出很多信息，包含狀態(tài)機(jī)目前的狀態(tài)派哲，以及哪些符號(hào)被讀取了臼氨。

Peter Jinks 寫了一篇關(guān)于調(diào)式方面的文章，包含一些常見的錯(cuò)誤及其處理方法芭届。

狀態(tài)機(jī)

YACC解析器內(nèi)部運(yùn)行著一個(gè)叫狀態(tài)機(jī)的東西储矩。這個(gè)名字暗示著這個(gè)機(jī)器有多種狀態(tài)。而規(guī)則控制著狀態(tài)機(jī)從一個(gè)狀態(tài)到另外一個(gè)狀態(tài)的改變褂乍。所有的東西起始于之前我提到的根的規(guī)則持隧。

引用示例7中y.output的輸出內(nèi)容:

state 0 ZONETOK     , and go to state 1 $default reduce using rule 1 (commands)
    commands    go to state 29 command     go to state 2 zone_set    go to state 3 

默認(rèn)情況下，這個(gè)狀態(tài)經(jīng)由commands規(guī)則歸約逃片，這是前面提到的由多個(gè)單一命令語句建立起來的遞歸規(guī)則形成的命令集屡拨，后跟一個(gè);，也許還有更多的命令集褥实。

狀態(tài)一直遞減呀狼，直到遇到它能理解的東西，在這個(gè)例子里损离，比如一個(gè)ZONETOKE哥艇，單詞zone。然后它轉(zhuǎn)向狀態(tài)1僻澎，它將處理一個(gè)zone 命令：

state 1 zone_set  ?>  ZONETOK . quotedname zonecontent   (rule 4)
    QUOTE       , and go to state 4 quotedname  go to state 5 

上面的第一行有一個(gè).在里面貌踏，它指示所處的位置：我們正好遇到一個(gè)ZONETOK,現(xiàn)在尋找quotedname。很明顯窟勃，一個(gè)quotedname起始于一個(gè)QUTOTE,而它將我們轉(zhuǎn)向狀態(tài)4祖乳。

欲進(jìn)一步了解，用調(diào)試一節(jié)提到的參數(shù)編譯Example 7拳恋。

沖突：'移進(jìn)/歸約'凡资，'歸約/歸約'

只要YACC發(fā)出關(guān)于沖突的警告，可能就有麻煩了。解決這些沖突似乎是門藝術(shù)隙赁，也許會(huì)讓你對(duì)那門語言理解的更深刻垦藏，遠(yuǎn)比你想知道的多。

解決問題圍繞著如何解釋一系列的符號(hào)伞访。假設(shè)我們定義了一門語言掂骏，它需要接收一系列的命令：

delete heater all delete heater number1 

為此，我們這樣定義語法：

delete_heaters:
        TOKDELETE TOKHEATER mode
        {
                deleteheaters($3);
        }
mode:   WORD
delete_a_heater:
        TOKDELETE TOKHEATER WORD
        { delete($3);
        } 

也許你已經(jīng)感覺到了有問題厚掷。狀態(tài)機(jī)開始讀入單詞'delete'弟灼，然后需要由接下來的符號(hào)決定轉(zhuǎn)向哪。這個(gè)接下來的符號(hào)即可以是一個(gè)mode冒黑，指明了如何刪除加熱器田绑，或者一個(gè)待刪除的加熱器。

但問題出自于這兩個(gè)命令的下一個(gè)符號(hào)是WORD抡爹。YACC不知道應(yīng)該要怎樣做掩驱，這導(dǎo)致了一個(gè)'歸約/歸約'警告，以及一個(gè)更具體的警告：'delete_a_heater'永遠(yuǎn)不能被訪問冬竟。

這個(gè)示例的沖突很容易解決（例如欧穴，將第一個(gè)命令重命名為'delete heaters all'，或者將'all'單獨(dú)定義為一個(gè)符號(hào)）泵殴，但是有時(shí)卻非常困難涮帘。用--verbose標(biāo)記生成的y.output文件能夠起到很大的幫助。