yacc（Yet Another 編譯器 Compiler），是一個經(jīng)典的生成語法分析器的工具。yacc生成的編譯器主要是用c語言寫成的語法解析器（Parser），需要與詞法解析器Lex一起使用，再把兩部分產(chǎn)生出來的C程序一并編譯。yacc本來只在Unix系統(tǒng)上才有，但現(xiàn)時已普遍移植往Windows及其他平臺。
歷史
Yacc由Stephen C. Johnson在20世紀(jì)70年代初于貝爾實(shí)驗(yàn)室/AT&T開發(fā)，最初是用B編程語言編寫，后由Alan Snyder改寫為C語言。它作為unix第3版的一部分出現(xiàn)，并于1975年發(fā)表了Yacc的詳細(xì)描述。Yacc的設(shè)計(jì)受到了Donald Knuth關(guān)于LR分析的工作和TMG編譯器-編譯器的影響。
分析程序生成器
分析程序生成器(parser generator)是一個指定某個格式中的一種語言的語法作為它的輸入，并為該種語言產(chǎn)生分析過程以作為它的輸出的程序。在歷史上，分析程序生成器被稱作編譯-編譯程序(編譯器-compiler)，這是由于按照規(guī)律可將所有的編譯步驟作為包含在分析程序中的動作來執(zhí)行。現(xiàn)在的觀點(diǎn)是將分析程序僅考慮為編譯處理的一個部分，所以這個術(shù)語也就有些過時了。合并LALR(1)分析算法是一種常用的分析生成器，它被稱作Yacc(yet another compiler-compiler)。給出Yacc的概貌來，將使用Yacc為TINY語言開發(fā)一個分析程序。作為Yacc對說明文件中的%token NUMBER聲明的對應(yīng)。Yacc堅(jiān)持定義所有的符號記號本身，而不是從別的地方引入一個定義。但是卻有可能通過在記號聲明中的記號名之后書寫一個值來指定將賦給記號的數(shù)字值。yacc的輸入是巴科斯范式（BNF）表達(dá)的語法規(guī)則以及語法規(guī)約的處理代碼，Yacc輸出的是基于表驅(qū)動的編譯器，包含輸入的語法規(guī)約的處理代碼部分。yacc是開發(fā)編譯器的一個有用的工具，采用LALR(1)語法分析方法。Yacc最初由AT&T的Steven C. Johnson為Unix操作系統(tǒng)開發(fā)，后來一些兼容的程序如Berkeley Yacc，GNU bison，MKS yacc和Abraxas yacc陸續(xù)出現(xiàn)。它們都在原先基礎(chǔ)上做了少許改進(jìn)或者增加，但是基本概念是相同的。由于所產(chǎn)生的解析器需要詞法分析器配合，因此Yacc經(jīng)常和詞法分析器的產(chǎn)生器——一般就是Lex——聯(lián)合使用。IEEE POSIX P1003.2標(biāo)準(zhǔn)定義了Lex和Yacc的功能和需求。
功能和使用
Yacc的輸入是帶有C代碼片段（稱為“動作”）附加到其規(guī)則的語法。它的輸出是一個在C中執(zhí)行與每個規(guī)則關(guān)聯(lián)的C代碼片段的移位-歸約解析器。典型的動作涉及構(gòu)造解析樹。例如，一個規(guī)則可能會識別求和表達(dá)式并為其構(gòu)造節(jié)點(diǎn)。Yacc只生成解析器，可以在無掃描儀解析的情況下單獨(dú)使用，但完整的句法分析通常需要外部詞法分析器首先執(zhí)行標(biāo)記化階段。
應(yīng)用
首次使用Yacc實(shí)現(xiàn)的語言包括AWK、C++、eqn和Pic。Yacc還在Unix上用于實(shí)現(xiàn)便攜式C編譯器，以及用于Fortran 77、Ratfor、APL、bc、m4等編程語言的解析器。此外，Yacc也被重寫以支持其他語言，如OCaml、Ratfor、ML、Ada、Pascal、Java、Python、Ruby、Go、Common Lisp和Erlang。
參考資料 >