2.1 yacc/lex是什么

如前文所述，本書(shū)會(huì)使用yacc和lex這兩個(gè)工具。本章中將利用yacc/lex嘗試編寫(xiě)一個(gè)簡(jiǎn)單的計(jì)算器程序。

一般編程語(yǔ)言的語(yǔ)法處理，都會(huì)有以下的過(guò)程。

1．詞法分析

將源代碼分割為若干個(gè)記號(hào)（token）的處理。

2．語(yǔ)法分析

即從記號(hào)構(gòu)建分析樹(shù)（parse tree）的處理。分析樹(shù)也叫作語(yǔ)法樹(shù)（syntax tree）或抽象語(yǔ)法樹(shù)（abstract syntax tree, AST）。

3．語(yǔ)義分析

經(jīng)過(guò)語(yǔ)法分析生成的分析樹(shù)，并不包含數(shù)據(jù)類型等語(yǔ)義信息。因此在語(yǔ)義分析階段，會(huì)檢查程序中是否含有語(yǔ)法正確但是存在邏輯問(wèn)題的錯(cuò)誤。

一般來(lái)說(shuō)執(zhí)行語(yǔ)義分析時(shí)主要會(huì)做數(shù)據(jù)類型的解析以及錯(cuò)誤檢查，但本書(shū)中使用的crowbar語(yǔ)言并沒(méi)有設(shè)置變量類型，因此也不會(huì)進(jìn)行數(shù)據(jù)類型的檢查，所以crowbar并不存在一個(gè)明確的語(yǔ)義分析階段（Diksam中是存在這個(gè)階段的，位于fix_tree.c源文件中，請(qǐng)參考本書(shū)6.3.4節(jié)）。

4．生成代碼

如果是C語(yǔ)言等生成機(jī)器碼的編譯器或Java這樣生成字節(jié)碼的編譯器，在分析樹(shù)構(gòu)建完畢后會(huì)進(jìn)入代碼生成階段。

比如說(shuō)有如下的代碼：

                  if（a == 10）{
                      printf（"hoge\n"）;
                  } else {
                      printf（"piyo\n"）;
                  }

執(zhí)行詞法分析后，將被分割為如圖2-1所示的記號(hào)（每一個(gè)塊就是一個(gè)記號(hào)）：

圖2-1 分割為記號(hào)

對(duì)此進(jìn)行語(yǔ)法分析后構(gòu)建的分析樹(shù)，如圖2-2所示（同圖1-1）。

圖2-2 if語(yǔ)句的分析樹(shù)

執(zhí)行詞法分析的程序稱為詞法分析器（lexical analyzer）。lex的工作就是根據(jù)詞法規(guī)則自動(dòng)生成詞法分析器。

執(zhí)行語(yǔ)法分析的程序則稱為解析器（parser）。yacc就是能根據(jù)語(yǔ)法規(guī)則自動(dòng)生成解析器的程序。

順便說(shuō)一下，yacc是“Yet Another Compiler Compiler”的縮寫(xiě)。顧名思義，Compiler Compiler就是生成編譯器的編譯器。yacc其實(shí)只能生成編譯器的一部分（解析器部分），卻自稱編譯器的編譯器，未免有些名不副實(shí)。而在yacc誕生時(shí)還因?yàn)榇嬖谄渌麕讉€(gè)編譯器的編譯器，所以yacc的作者干脆取“又一個(gè)（Yet Another）編譯器的編譯器”之意，起名為yacc。lex則只是簡(jiǎn)單地取自lexical analyzer。

yacc和lex一起使用，可以將一個(gè)特殊格式的定義文件輸出為C語(yǔ)言代碼。

因?yàn)閮烧叨际呛芾系墓ぞ撸詳?shù)據(jù)傳遞都采用全局變量的方式，現(xiàn)在看起來(lái)實(shí)在有些簡(jiǎn)陋。即便如此，至少yacc仍然作為Perl、Ruby等語(yǔ)言的語(yǔ)法處理器活躍在第一線。詞法分析器則相對(duì)簡(jiǎn)單，完全可以自己編寫(xiě)，所以正式的編程語(yǔ)言一般都不會(huì)使用lex。

yacc與lex在UNIX的標(biāo)準(zhǔn)環(huán)境下大多都已經(jīng)預(yù)裝了，在Windows等環(huán)境一般沒(méi)有預(yù)裝，所以需要使用其免費(fèi)的替代品bison和flex（獲得方法請(qǐng)參考1.6.1節(jié)）。

          a+++++b;