woaidongmao

關(guān)鍵字： RSCT 內(nèi)存調(diào)試 Expect 正則表達(dá)式 Tcl

       在 UNIX® 中，許多操作系統(tǒng)組成部分都依賴于文本分析，從用來(lái)與系統(tǒng)進(jìn)行交互的 shell，到諸如 awk or Perl 等各種常用的工具和命令，再到用來(lái)構(gòu)建軟件和應(yīng)用程序的 C 編譯器。您可以在 UNIX 應(yīng)用程序（以及其他的應(yīng)用程序）中使用分析器來(lái)構(gòu)建簡(jiǎn)單的配置分析器，甚至構(gòu)建最終的目標(biāo)：您自己的編程語(yǔ)言。

　　本文將研究使用 lex/flex 和 yacc/bison 工具構(gòu)建分析器所需的步驟。首先構(gòu)建一個(gè)簡(jiǎn)單的計(jì)算器，然后深入地研究如何采用相同的原則進(jìn)行文本分析。分析文本，即理解和提取文本中的關(guān)鍵部分，是許多應(yīng)用程序中一個(gè)重要的部分。在 UNIX? 中，許多操作系統(tǒng)組成部分都依賴于文本分析，從用來(lái)與系統(tǒng)進(jìn)行交互的 shell，到諸如 awk or Perl 等各種常用的工具和命令，再到用來(lái)構(gòu)建軟件和應(yīng)用程序的 C 編譯器。您可以在 UNIX 應(yīng)用程序（以及其他的應(yīng)用程序）中使用分析器來(lái)構(gòu)建簡(jiǎn)單的配置分析器，甚至構(gòu)建最終的目標(biāo)：您自己的編程語(yǔ)言。

　　開(kāi)始之前

UNIX? 程序員常常發(fā)現(xiàn)他們需要去理解文本和其他一些具有靈活的標(biāo)準(zhǔn)化格式的結(jié)構(gòu)。通過(guò)使用 lex 和 yacc 工具，您可以構(gòu)建一個(gè)分析引擎，根據(jù)特定的規(guī)則來(lái)處理文本。然后，可以將它集成到您的應(yīng)用程序中以完成各項(xiàng)工作，從配置分析到構(gòu)建您自己的編程語(yǔ)言。在學(xué)習(xí)了本教程之后，您將了解如何定義詞法元素、編寫(xiě) yacc 規(guī)則，并使用相應(yīng)的規(guī)則機(jī)制來(lái)構(gòu)建和定義各種不同的分析引擎和應(yīng)用程序。

　　關(guān)于本教程

　　在 UNIX 中，有許多用來(lái)理解和提取文本的方法。您可以使用 grep、awk、Perl 和其他的解決方案。但有的時(shí)候，您需要理解和提取結(jié)構(gòu)化的但格式不受限制的數(shù)據(jù)。在這種情況下，UNIX lex 和 yacc 工具就很有用處了。前面提到的那些工具，如 awk、Perl 以及 shell 和許多其他的編程語(yǔ)言，都使用 lex 和 yacc 來(lái)生成分析應(yīng)用程序以分析和理解文本，并將其轉(zhuǎn)換為所需的信息或數(shù)據(jù)結(jié)構(gòu)。

Lex 是一種詞法分析工具，它可以用來(lái)從源文本識(shí)別特定結(jié)構(gòu)的文本字符串。Yacc 是一種語(yǔ)法分析器，它可以讀取文本并用來(lái)將單詞序列轉(zhuǎn)換為便于處理的結(jié)構(gòu)化的格式。

　　在本教程中，首先您將研究如何使用 lex 和 yacc 來(lái)構(gòu)建一個(gè)計(jì)算器。使用該計(jì)算器作為示例，您將進(jìn)一步研究 lex 和 yacc 系統(tǒng)生成的輸出和信息，并學(xué)習(xí)如何使用它來(lái)分析其他類(lèi)型的信息。

　　先決條件

　　要使用在本教程中的示例，您需要使用到下列工具：

Lex：這個(gè)工具是大多數(shù) UNIX 操作系統(tǒng)的標(biāo)準(zhǔn)組件。GNU flex 工具提供了相同的功能。

Yacc：這個(gè)工具是大多數(shù) UNIX 操作系統(tǒng)的標(biāo)準(zhǔn)組件。GNU bison 工具提供了相同的功能。

C 編譯器：任何標(biāo)準(zhǔn)的 C 編譯器都可以，其中包括 Gnu CC。

Make 工具：這個(gè)工具是使用示例 Makefile 來(lái)簡(jiǎn)化構(gòu)建過(guò)程所必需的。

　　可以從 GNU Web 站點(diǎn)或本地的 GNU 鏡像站點(diǎn)下載 GNU 工具。

　　使用 lex 進(jìn)行詞法分析

　　編寫(xiě)文本分析器的第一步是要能夠識(shí)別所讀取的內(nèi)容。有許多不同的方法可以完成這項(xiàng)任務(wù)，但是最簡(jiǎn)單的方法是使用 lex，它是將輸入信息轉(zhuǎn)換為一系列標(biāo)記的工具。

　　什么是詞法分析？

　　當(dāng)使用編程語(yǔ)言編寫(xiě)程序或在命令行中輸入命令時(shí)，您是否想過(guò)究竟執(zhí)行了什么操作將您輸入的內(nèi)容轉(zhuǎn)換為一組指令呢？

　　這個(gè)處理過(guò)程非常簡(jiǎn)單，卻又相當(dāng)復(fù)雜。它很復(fù)雜，這是因?yàn)閷?duì)于可能輸入的信息，表面上看起來(lái)似乎存在無(wú)限種可能的組合和序列。例如，要使用 Perl 語(yǔ)言遍歷一個(gè)哈希表，您可以使用如清單 1 所示的序列。

　　清單 1. 在 Perl 中遍歷一個(gè)哈希表

foreach $key (keys %hash)
{
...
}

　　其中的每一項(xiàng)都是有意義的，雖然方式有所不同，這正是該處理過(guò)程的簡(jiǎn)單明了之處。清單 1 中所示的表達(dá)式存在一個(gè)對(duì)應(yīng)的結(jié)構(gòu)，也就是說(shuō)，與人類(lèi)語(yǔ)言一樣，編程語(yǔ)言中也存在著特定的規(guī)則。因此，如果將輸入分解為您所看到的和該信息結(jié)構(gòu)的組合，那么對(duì)該內(nèi)容的分析過(guò)程則相當(dāng)簡(jiǎn)單。

　　要理解提供給文本分析應(yīng)用程序的信息，通常有兩個(gè)階段。第一個(gè)階段是識(shí)別輸入的或提供給應(yīng)用程序的內(nèi)容是什么。您必須能夠從輸入源中識(shí)別關(guān)鍵字、短語(yǔ)或字符序列，以便能夠確定對(duì)其進(jìn)行何種處理。第二個(gè)處理階段是理解該信息的結(jié)構(gòu)，即語(yǔ)法，以便對(duì)輸入進(jìn)行驗(yàn)證和操作。有關(guān)語(yǔ)法的一個(gè)很好的示例是，大多數(shù)編程語(yǔ)言中圓括號(hào)的使用。很明顯，下面的表達(dá)式是錯(cuò)誤的：

{ function)( {

　　其中，大括號(hào)不匹配，而圓括號(hào)的出現(xiàn)順序錯(cuò)誤。為了讓分析器理解和識(shí)別表達(dá)式，那么分析器必須知道正確的序列，以及匹配該序列后應(yīng)該進(jìn)行何種操作。

　　詞法分析首先進(jìn)行識(shí)別輸入數(shù)據(jù)的處理，并且可以使用 lex 工具來(lái)完成該處理過(guò)程。

lex 工具

lex 工具（或 GNU 工具 flex）使用一個(gè)配置文件來(lái)生成相應(yīng)的 C 源代碼，然后，可以用它來(lái)創(chuàng)建獨(dú)立的應(yīng)用程序，或者在您自己的應(yīng)用程序中使用它。配置文件定義了需要在待分析的文件中查找的字符序列，以及當(dāng)發(fā)現(xiàn)該序列之后應(yīng)該進(jìn)行什么操作。該文件的格式十分簡(jiǎn)單，即指定輸入序列和相應(yīng)的結(jié)果，用空格（或制表符）隔開(kāi)。例如：

sequence do-something

　　清單 2 顯示了一個(gè)非常簡(jiǎn)單的定義，它可以接受單詞并根據(jù)提供的單詞打印出一個(gè)字符串。

　　清單 2. 簡(jiǎn)單的 lex 定義

%{
#include <stdio.h>
%}
%%
begin printf("Startedn");
hello printf("Hello yourself!n");
thanks printf("Your welcomen");
end printf("Stoppedn");
%%

　　代碼中的第一塊由 %{...%} 定義，表示將其中的文本插入到生成的 C 源代碼中。在本示例中，因?yàn)楹竺媸褂昧?span lang="EN-US"> printf() 函數(shù)，所以必須確保包含了 stdio.h Header。

　　代碼中的第二塊由 %% 序列標(biāo)識(shí)，其中包含了要識(shí)別的字符串輸入和相應(yīng)結(jié)果的定義。在上述的這些情況下，對(duì)于一個(gè)簡(jiǎn)單的單詞，將打印出合適的響應(yīng)。

　　生成 C 源代碼

　　要生成能夠真正分析輸入文本的 C 源代碼，可以對(duì)清單 1 所示的文件運(yùn)行 lex（或 flex）。Lex/flex 文件點(diǎn)號(hào)后綴為 'l'，所以上面的文件可能名為 exampleA.l。要生成相應(yīng)的 C 源代碼：

$ flex exampleA.l

　　不管您使用哪種工具，其輸出都將為 lex.yy.c。缺乏勇氣的人往往不敢仔細(xì)研究這個(gè)文件，分析器內(nèi)部的處理過(guò)程的確非常復(fù)雜，并且建立在基于表格的復(fù)雜分析系統(tǒng)的基礎(chǔ)上，該系統(tǒng)可以根據(jù)原始 lex 定義中的定義對(duì)輸入文本進(jìn)行匹配。因?yàn)榇嬖谶@樣的關(guān)聯(lián)，所以該代碼相當(dāng)占用內(nèi)存，特別是對(duì)于那些很大且很復(fù)雜的文件。

　　與 lex 相比，flex 的優(yōu)點(diǎn)在于它提供了大量附加的選項(xiàng)以改進(jìn)性能（針對(duì)內(nèi)存或速度）、調(diào)試選項(xiàng)和對(duì)掃描器行為更好的控制（例如，可以忽略某些情況）。在生成 C 源代碼時(shí)，通過(guò)使用 -l 命令行選項(xiàng)，您可以生成與原始的 lex 工具生成的源代碼非常接近的 C 源代碼。

　　既然已經(jīng)有了 C 源代碼，那么您可以將其編譯為相應(yīng)的應(yīng)用程序以測(cè)試該處理過(guò)程：

$ gcc -o exampleA lex.yy.c -lfl

flex 庫(kù)（使用 -lfl 進(jìn)行包含，而 lex 則使用 -ll）包含執(zhí)行分析代碼的簡(jiǎn)單的 main() 函數(shù)。當(dāng)運(yùn)行生成的應(yīng)用程序時(shí)，它將等待輸入。清單 3 顯示了該應(yīng)用程序的輸入（和輸出）。

　　清單 3. 簡(jiǎn)單 lex 應(yīng)用程序的輸入/輸出

$ exampleA
begin
Started
hello
Hello yourself!
end
Stopped
thanks
Your welcome
hello thanks
Hello yourself!
Your welcome
hello Robert
Hello yourself!
Robert

　　對(duì)于單行輸入 ('begin')，該應(yīng)用程序根據(jù)您所提供的命令進(jìn)行響應(yīng)，在本示例中，將打印出單詞 'Started'。對(duì)于包含多個(gè)識(shí)別單詞的行，該應(yīng)用程序分別運(yùn)行多個(gè)命令，并以空格隔開(kāi)。對(duì)于無(wú)法識(shí)別的標(biāo)記（包括空白字符），僅對(duì)其進(jìn)行回顯。

　　這個(gè)示例介紹了該系統(tǒng)的基本操作，但是您僅僅使用了標(biāo)準(zhǔn)的單詞。要使用其他的組合，如字符和元素，有各種不同的解決方案可供使用。

　　識(shí)別元素

　　可識(shí)別的元素可以不是前面介紹的固定字符串，標(biāo)識(shí)符支持正則表達(dá)式和特殊（例如標(biāo)點(diǎn)符號(hào)）字符，如清單 4 所示。

　　清單 4. 正則表達(dá)式和特殊字符

%{
#include <stdio.h>
%}
%%
[a-z] printf("Lowercase wordn");
[A-Z] printf("Uppercase wordn");
[a-ZA-Z] printf("Wordn");
[0-9] printf("Integern");
[0-9.] printf("Floatn");
";" printf("Semicolonn");
"(" printf("Open parenthesesn");
")" printf("Close parenthesesn");
%%

　　清單 4 中的示例應(yīng)該是一目了然的，并且對(duì)于需要進(jìn)行分析的任何正則表達(dá)式或特殊字符都可以使用相同的原則。

　　真正的標(biāo)記化

　　前面的示例所構(gòu)建的 C 源代碼實(shí)質(zhì)上是獨(dú)立的。盡管使用這種方法沒(méi)有什么問(wèn)題，但是對(duì)于分析包含多個(gè)單詞、短語(yǔ)或序列的給定指令中的文本或其他條目的情況，這種方法并不是很有價(jià)值。

　　使用這種方式分析序列需要一個(gè)語(yǔ)法分析器，而它將定義標(biāo)記序列。但是語(yǔ)法分析器必須知道要分析的是什么標(biāo)記。在 lex 定義中，當(dāng)識(shí)別標(biāo)記時(shí)所進(jìn)行的操作是回顯字符串，如果要返回一個(gè)識(shí)別標(biāo)記，那么需要對(duì)該操作進(jìn)行更改。例如，您可以如清單 5 所示對(duì)原始示例進(jìn)行重寫(xiě)。

%{
#include <stdio.h>
#include <y.tab.h>
%}
%%
begin return BEGIN;
hello return HELLO;
thanks return THANKS;
end return END;
%%

　　現(xiàn)在，當(dāng)識(shí)別了 'hello' 標(biāo)記時(shí)，不再是打印一個(gè)字符串，而是返回標(biāo)記的名稱。在 yacc 中，將使用這個(gè)名稱來(lái)建立相應(yīng)的語(yǔ)法。

　　在這個(gè)示例中，沒(méi)有顯式地定義這些標(biāo)記名稱。實(shí)際上是在 y.tab.h 文件中指定了這些標(biāo)記名稱，而在分析 yacc 語(yǔ)法文件時(shí)由 yacc 自動(dòng)生成該文件。

　　提取變量數(shù)據(jù)

　　如果要提取一個(gè)值（例如，需要能夠讀取一個(gè)數(shù)值或字符串），那么您必須指定如何將輸入轉(zhuǎn)換為所需的類(lèi)型。通常由于 lex 中的各種限制，這種做法并不是很有價(jià)值，但是當(dāng)使用 yacc 工具來(lái)構(gòu)建一個(gè)完整的分析器時(shí)，這是至關(guān)重要的。

　　通常可以使用兩個(gè)變量來(lái)交換信息，yytext 變量包含了在分析過(guò)程中由 lex 讀取的原始數(shù)據(jù)，而 yylval 則用于在兩個(gè)系統(tǒng)之間交換實(shí)際的值。在本教程后面的內(nèi)容中，將更詳細(xì)地介紹這種結(jié)合是如何進(jìn)行的，但是出于識(shí)別信息的目的，您可能使用類(lèi)似下面的 lex 定義：

[0-9] yylval=atoi(yytext); return NUMBER;

　　在上面的代碼行中，使用了標(biāo)準(zhǔn)的 atoi() 函數(shù)將匹配正則表達(dá)式（并保存于 yytext 中）的輸入字符串片段轉(zhuǎn)換為一個(gè)整數(shù)，并將 yylval 的值設(shè)置為該整數(shù)。請(qǐng)注意，盡管對(duì)值進(jìn)行了轉(zhuǎn)換，但您仍然需要返回值的類(lèi)型，以便 yacc 知道究竟是什么類(lèi)型并可以根據(jù)自己的定義來(lái)使用這個(gè)標(biāo)記。

　　讓我們通過(guò)查看 yacc 如何定義語(yǔ)法結(jié)構(gòu)，以此來(lái)了解這項(xiàng)工作是如何進(jìn)行的。

　　使用 yacc 進(jìn)行語(yǔ)法分析

　　語(yǔ)法定義用于定義標(biāo)記序列以及應(yīng)得到的結(jié)果。它通常與 lex 聯(lián)合使用，由 lex 讀取相應(yīng)的文本，并且兩者一同構(gòu)成整個(gè)分析器。

yacc 的基本語(yǔ)法

yacc 語(yǔ)法定義的基本結(jié)構(gòu)是定義預(yù)期的標(biāo)記序列。例如，您可以定義表達(dá)式 A + B，其中 A 和 B 都是使用下列定義的數(shù)值：

NUMBER PLUSTOKEN NUMBER { printf("%fn",($1+$3)); }

NUMBER 是一個(gè)數(shù)值的識(shí)別標(biāo)記，并且 PLUSTOKEN 是加號(hào)的識(shí)別標(biāo)記。

　　大括號(hào)中的代碼定義了識(shí)別這個(gè)序列后進(jìn)行何種操作，在本示例中，給出的是將這兩個(gè)數(shù)值相加的 C 代碼。請(qǐng)注意，使用命名法 $1 表示該語(yǔ)法表達(dá)式中的第一項(xiàng)標(biāo)記，$3 表示其中的第三項(xiàng)。

　　對(duì)于待識(shí)別的語(yǔ)法序列，您必須對(duì)序列進(jìn)行命名，如清單 6 所示。

　　清單 6. 對(duì)序列命名

addexpr: NUMBER PLUSTOKEN NUMBER
{
printf("%fn",($1+$3));
}
;

　　語(yǔ)法組的名稱為 addexpr，并且這個(gè)組定義以一個(gè)分號(hào)作為結(jié)束。

　　一個(gè)語(yǔ)法定義可以包含多個(gè)序列（以及相關(guān)的操作），而這些序列都是一個(gè)特殊的組中的一部分。例如在計(jì)算器中，加法和減法處理是類(lèi)似的操作，所以可以將它們集中作為一組。一個(gè)組中不同的定義可以使用管道符號(hào) (|) 進(jìn)行分隔（請(qǐng)參見(jiàn)清單 7）。

　　清單 7. 一個(gè)組中不同的定義使用管道符號(hào)進(jìn)行分隔

addexpr: NUMBER PLUSTOKEN NUMBER
{
printf("%fn",($1+$3));
}
| NUMBER MINUSTOKEN NUMBER
{
printf("%fn",($1-$3));
}
;

　　您已經(jīng)了解了基本的語(yǔ)法規(guī)范，那么還需要了解如何組合多個(gè)序列以及它們的優(yōu)先級(jí)。

　　語(yǔ)法序列和優(yōu)先級(jí)

　　在大多數(shù)語(yǔ)言中，無(wú)論是文本型、數(shù)學(xué)運(yùn)算型，還是編程型的語(yǔ)言，通常對(duì)于不同的短語(yǔ)都有某種優(yōu)先級(jí)或重要性，這將使得它們與類(lèi)似的但不同的組合相比具有相應(yīng)的優(yōu)先權(quán)。

　　例如，在大多數(shù)編程語(yǔ)言的數(shù)學(xué)運(yùn)算表達(dá)式中，乘法具有比加法或減法更高的優(yōu)先級(jí)。例如，表達(dá)式：4+5*6 將計(jì)算為： 4+30。

　　這將得到最終的計(jì)算結(jié)果 34。其原因是首先進(jìn)行乘法操作（5 乘以 6 等于 30），然后將其結(jié)果用于最后的計(jì)算過(guò)程，即加上 4 后得到結(jié)果 34。

　　在 yacc 中，通過(guò)定義多個(gè)語(yǔ)法序列組并將它們連接在一起，就可以定義相應(yīng)的優(yōu)先級(jí)，不同表達(dá)式在組中的順序可以幫助定義其優(yōu)先級(jí)。在清單 8 中，您可以看到用于定義上述行為的代碼。

　　清單 8. 連接語(yǔ)法并提供優(yōu)先級(jí)

add_expr: mul_expr
| add_expr PLUS mul_expr { $$ = $1 + $3; }
| add_expr MINUS mul_expr { $$ = $1 - $3; }
;
mul_expr: primary
| mul_expr MUL primary { $$ = $1 * $3; }
| mul_expr DIV primary { $$ = $1 / $3; }
;
primary: NUMBER { $$ = $1; }
;

yacc 執(zhí)行所有表達(dá)式計(jì)算都是從左到右進(jìn)行處理的，所以對(duì)于與原始示例類(lèi)似的復(fù)合表達(dá)式（例如，4+5*6），yacc 將根據(jù)相應(yīng)的規(guī)則查找最佳匹配，即與表達(dá)式中的一部分匹配。

　　根據(jù)規(guī)則所定義的順序，自上而下進(jìn)行匹配處理。所以，該處理過(guò)程首先試圖匹配 add_expr 中的語(yǔ)法規(guī)則。然而，因?yàn)槌朔ň哂懈叩膬?yōu)先級(jí)，所以這些規(guī)則表明 yacc 應(yīng)該首先嘗試 mul_expr。這將迫使 yacc 首先根據(jù)乘法語(yǔ)句進(jìn)行匹配（在 mul_expr 中進(jìn)行定義）。如果匹配失敗，然后它將嘗試 add_expr 塊中的下一條規(guī)則，依此類(lèi)推，直到該表達(dá)式被解析，或者沒(méi)能找到任何匹配并生成一個(gè)錯(cuò)誤。

　　當(dāng)使用上述的規(guī)則集對(duì)公式 4+5*6 進(jìn)行計(jì)算時(shí)，yacc 首先嘗試 add_expr，然后被重定向到 mul_expr（作為匹配的第一條規(guī)則），并且又被重定向到 primary。primary 規(guī)則設(shè)置了表達(dá)式中相應(yīng)數(shù)字的值。$$ 有效地設(shè)置了那部分表達(dá)式的返回值。

　　在匹配了這些數(shù)字之后，yacc 根據(jù)下面這行定義識(shí)別了一個(gè)乘法表達(dá)式：| mul_expr MUL primary { $$ = $1 * $3; }，它設(shè)置了原始表達(dá)式中的 5*6 部分的返回值。Yacc 生成代碼以執(zhí)行相應(yīng)的計(jì)算（提取前面由 primary 規(guī)則設(shè)置的值），并使用計(jì)算的結(jié)果值替換輸入表達(dá)式的原始部分。這就意味著 yacc 現(xiàn)在需要匹配下面的表達(dá)式： 4+30。

　　它可以使用下面的規(guī)則匹配這個(gè)表達(dá)式：| add_expr PLUS mul_expr { $$ = $1 + $3; }，這將最終計(jì)算出最后的結(jié)果 34。

　　徹底地研究語(yǔ)法定義

　　語(yǔ)法定義設(shè)置了相應(yīng)的規(guī)則，用于分析輸入標(biāo)記及其格式和布局，并將其轉(zhuǎn)換為可以使用的信息。在任何時(shí)候都請(qǐng)記住，這里定義的規(guī)則集是告訴 yacc 如何識(shí)別輸入并執(zhí)行一段 C 代碼。yacc 工具生成所需的 C 代碼來(lái)分析該信息，而并不是由 yacc 來(lái)完成分析工作。

　　大括號(hào)中的代碼是 quasi-C 源代碼。Yacc 根據(jù)您給出的定義將原始文件轉(zhuǎn)換為相應(yīng)的 C 源代碼以及分析具體內(nèi)容所需的其他的代碼。

　　除了定義如何分析輸入內(nèi)容的規(guī)則集之外，還有一些附加函數(shù)和選項(xiàng)用以幫助定義其他的 C 源代碼。完整的 yacc 定義文件的基本格式類(lèi)似與 lex/flex 所使用的格式，如下面的清單 9 所示。

　　清單 9. Yacc 文件格式

%{
/* Global and header definitions required */
%}
/* Declarations (Optional token definitions) */
%%
/* Parsing ruleset definitions
%%
/* Additional C source code */

　　全局/Header 定義與 lex/flex 文件中所使用的定義相同，如果您在分析和處理輸出時(shí)使用了特殊的函數(shù)，那么它們都是必需的。

　　標(biāo)記定義不僅描述了預(yù)期的標(biāo)記，還描述了分析處理過(guò)程中的優(yōu)先級(jí)。通過(guò)迫使 yacc 按照特定的順序檢查標(biāo)記，這可以調(diào)整 yacc 對(duì)規(guī)則的處理方式，并且還影響到在與規(guī)則進(jìn)行比較時(shí)如何對(duì)表達(dá)式進(jìn)行處理。

　　例如，您通常可以定義 + 標(biāo)記具有左優(yōu)先級(jí)，也就是說(shuō)，首先對(duì)這個(gè)標(biāo)記左邊的任何表達(dá)式進(jìn)行匹配，這樣一來(lái)，表達(dá)式 4+5+6 首先會(huì)計(jì)算 4+5，然后計(jì)算 9+6。

　　然而，您可能希望為一些標(biāo)記指定右優(yōu)先級(jí)，例如，計(jì)算邏輯 NOT，（例如，! (expr)）您可能希望先計(jì)算 expr，然后對(duì)通過(guò) ! 標(biāo)記對(duì)其表達(dá)式的值取反。

　　除了控制規(guī)則之間的優(yōu)先級(jí)關(guān)系之外，還可以指定標(biāo)記的優(yōu)先級(jí)，這樣您就可以精確地控制如何對(duì)輸入進(jìn)行計(jì)算。

　　有三種主要的標(biāo)記類(lèi)型，%token（沒(méi)有優(yōu)先級(jí)差別），%left（標(biāo)記左側(cè)的輸入具有優(yōu)先級(jí)）和 %right（標(biāo)記右側(cè)的輸入具有優(yōu)先級(jí)）。例如，清單 10 根據(jù)適當(dāng)?shù)膬?yōu)先級(jí)定義了若干標(biāo)記：

　　清單 10. 根據(jù)適當(dāng)?shù)膬?yōu)先級(jí)定義若干標(biāo)記

%token EQUALS POWER
%left PLUS MINUS
%left MULTIPLY DIVIDE
%right NOT

　　請(qǐng)注意，以自上而下優(yōu)先級(jí)遞增的順序指定標(biāo)記的優(yōu)先級(jí)，并且同一行中的標(biāo)記具有相同的優(yōu)先級(jí)。在清單 10 所示的示例中，MULTIPLY 和 DIVIDE 具有相同的優(yōu)先級(jí)，該優(yōu)先級(jí)要高于 PLUS 和 MINUS 的優(yōu)先級(jí)。

　　請(qǐng)注意，如果在規(guī)則中使用這里沒(méi)有定義的任何標(biāo)記，則將引發(fā)一個(gè)錯(cuò)誤。

　　自定義初始化和錯(cuò)誤

　　您將要定義的兩個(gè)關(guān)鍵的函數(shù)是 main() 函數(shù)（可以將自定義的初始化和其他的處理放在這個(gè)函數(shù)中），以及 yyerror() 函數(shù)（當(dāng)對(duì)于輸入信息無(wú)法找到一條分析規(guī)則時(shí)將打印出一個(gè)錯(cuò)誤）。由 yacc 生成的進(jìn)行實(shí)際分析工作的函數(shù)稱為 yyparse()。自定義函數(shù)的典型定義如清單 11 所示。

　清單 11. 分析器的自定義函數(shù)

#include <stdio.h>
#include <ctype.h>
char *progname;
double yylval;
main( argc, argv )
char *argv[];
{
progname = argv[0];
yyparse();
}
yyerror( s )
char *s;
{
fprintf( stderr ,"%s: %sn" , progname , s );
}

yyerror() 函數(shù)接受一個(gè)字符串，并且在引發(fā)錯(cuò)誤的時(shí)候?qū)⑵渑c程序名稱合并在一起作為輸出。

　　將語(yǔ)法編譯為 C 代碼

Yacc（最初是 yet another compiler compiler 的縮寫(xiě)）和 GNU bison 工具都接受一個(gè)語(yǔ)法定義文件作為輸入，并生成創(chuàng)建分析器所需的 C 源代碼，而該分析器將對(duì)適當(dāng)?shù)妮斎脒M(jìn)行處理。

　　通常，語(yǔ)法定義文件的擴(kuò)展名為 .y。

　　當(dāng)您運(yùn)行 yacc 時(shí)，缺省情況下它將創(chuàng)建一個(gè)名為 yy.tab.c 的文件。如果 yacc 和 lex 一同使用，那么您還需要生成一個(gè) C Header 文件，該文件包含了這兩個(gè)系統(tǒng)中識(shí)別的標(biāo)記的宏定義。除了 C 源代碼之外，如果還要生成 Header 文件，可以使用 -d 命令行選項(xiàng)：

$ yacc -d calcparser.y

　　盡管 bison 可以執(zhí)行相同的基本操作，但缺省情況下，它所生成的文件使用源文件名稱的前綴作為其標(biāo)識(shí)。所以，在上面的示例中，使用 bison 將生成 calcparser.tab.c 和 calcparser.tab.h 文件。

　　這個(gè)區(qū)別是很重要的，不僅因?yàn)槟枰谰烤挂幾g那個(gè)文件，而且還因?yàn)槟枰?span lang="EN-US"> lex.l 定義中導(dǎo)入正確的 Header 文件，以便它能夠讀取正確的標(biāo)記定義。

　　當(dāng)編譯一個(gè) lex/yacc 應(yīng)用程序時(shí)，一般的過(guò)程如下：

　　對(duì)分析器定義運(yùn)行 yacc。

　　對(duì)詞法定義運(yùn)行 lex。

　　編譯生成的 yacc 源文件。

　　編譯生成的 lex 源文件。

　　編譯任何其他的模塊。

　　將 lex、yacc 和其他源鏈接為一個(gè)可執(zhí)行文件。

　　我傾向于使用一個(gè)與清單 12 所示類(lèi)似的 Makefile。

　　清單 12. 簡(jiǎn)單的 lex/yacc Makefile

YFLAGS = -d
PROGRAM = calc
OBJS = calcparse.tab.o lex.yy.o fmath.o const.o
SRCS = calcparse.tab.c lex.yy.c fmath.c const.c
CC = gcc
all: $(PROGRAM)
.c.o: $(SRCS)
$(CC) -c $*.c -o $@ -O
calcparse.tab.c: calcparse.y
bison $(YFLAGS) calcparse.y
lex.yy.c: lex.l
flex lex.l
calc: $(OBJS)
$(CC) $(OBJS) -o $@ -lfl -lm
clean:; rm -f $(OBJS) core *~ #* *.o $(PROGRAM)
y.* lex.yy.* calcparse.tab.*

　　與 lex 進(jìn)行數(shù)據(jù)交換

lex 和 yacc 之間數(shù)據(jù)交換的主要方法是當(dāng)使用 yacc 創(chuàng)建 C 源代碼和生成包含每個(gè)標(biāo)記的 C 宏代碼的 Header 文件時(shí)生成的標(biāo)記定義。

　　然而，如果您需要交換的數(shù)據(jù)不僅僅是一個(gè)標(biāo)記，那么您必須設(shè)置一個(gè)可以包含需要交換的信息的值。

　　這個(gè)處理過(guò)程分為兩個(gè)階段。首先，您應(yīng)該根據(jù)具體需要定義 YYSTYPE。這是用于在這兩個(gè)系統(tǒng)之間進(jìn)行數(shù)據(jù)交換的缺省值。對(duì)于一個(gè)基本的計(jì)算器，您可能需要將其定義為整數(shù)（實(shí)際上這正是缺省的情況）、浮點(diǎn)數(shù)或雙精度數(shù)。如果您需要交換文本，那么可以將它設(shè)置為一個(gè)字符指針或數(shù)組。如果需要同時(shí)交換這兩種信息，那么您應(yīng)該創(chuàng)建一個(gè)可以包含這兩種值的聯(lián)合結(jié)構(gòu)。

　　然后，您還應(yīng)該在 yacc 和 lex 定義中聲明 yylval 變量（和其他任何需要共享的變量）為該類(lèi)型。

　　例如，在這兩個(gè)文件的 Header 塊中，您需要指定這個(gè)類(lèi)型（請(qǐng)參見(jiàn)清單 13）。

　　清單 13. 指定具體的類(lèi)型

%{
...
#define YYSTYPE double
...
%}

　　在 lex 定義中，您還需要將 yylval 變量定義為這個(gè)類(lèi)型的外部變量：

extern YYSTYPE yylval;

　　最后，在 yacc 文件的自定義 C 初始化塊中，您需要定義這個(gè)變量：

YYSTYPE yylval;

　　現(xiàn)在，您就可以在由這兩個(gè)系統(tǒng)生成的 C 源代碼中進(jìn)行數(shù)據(jù)交換了。

　　構(gòu)建一個(gè)計(jì)算器

　　您可以使用前面部分中演示的技術(shù)來(lái)構(gòu)建一個(gè)常規(guī)表達(dá)式計(jì)算器。

　　計(jì)算器的基本概念

　　您可以構(gòu)建一個(gè)能夠處理表達(dá)式的程序，如清單 14 所示。

　　清單 14. 能夠處理表達(dá)式的程序

4+5
(4+5)*6
2^3/6
sin(1)+cos(PI)

　　通過(guò)定義附加的標(biāo)記和語(yǔ)法規(guī)則，您可以進(jìn)一步擴(kuò)展它的功能以包括各種函數(shù)和方程式，不僅僅是標(biāo)準(zhǔn) C 語(yǔ)言和數(shù)學(xué)庫(kù)中的函數(shù)，您還可以自己進(jìn)行特殊的定義。

　　為了能夠分析所有這些不同的元素，第一步需要定義可以由詞法分析組件識(shí)別的標(biāo)記。清單 15 給出了完整的 lex 定義。

　　清單 15. 高級(jí)計(jì)算器的 Lex 文件

%{
#define YYSTYPE double
#include "calcparse.tab.h"
#include <math.h>
extern double yylval;
%}
D [0-9.]
%%
[ t] { ; }
log return LOG;
pi return PIVAL;
sin return SIN;
cos return COS;
tan return TAN;
and return AND;
not return NOT;
xor return XOR;
or return OR;
reg return REGA;
ans return ANS;
fix return FIX;
sci return SCI;
eng return ENG;
const return CONST;
bintodec return BINTODEC;
dectobin return DECTOBIN;
{D}+ { sscanf( yytext, "%lf", &yylval ); return NUMBER ; }
[a-zA-Z_]+ return IDENT;
"[" return OPENREG;
"]" return CLOSEREG;
"<<" return LEFTSHIFT;
">>" return RIGHTSHIFT;
"++" return INC;
"--" return DEC;
"+" return PLUS;
"-" return MINUS;
"~" return UNARYMINUS;
"/" return DIV;
"*" return MUL;
"^" return POW;
"!" return FACT;
"(" return OPENBRACKET;
")" return CLOSEBRACKET;
"%" return MOD;
"^^" return XOR;
"!!" return NOT;
"=" return ASSIGN;
"&&" return LAND;
"||" return OR;
"|" return IOR;
"&" return AND;
"~~" return COMPLEMENT;
"n" return EOLN;

　　這里有大量的標(biāo)記，其中許多都是自說(shuō)明的。這些標(biāo)記包括基本數(shù)學(xué)操作、大量的函數(shù)（sin、cos 等等）和邏輯運(yùn)算符。另請(qǐng)注意，對(duì)于數(shù)值使用了雙精度類(lèi)型，使用 sscanf() 將數(shù)字字符串和小數(shù)點(diǎn)解析為適當(dāng)?shù)碾p精度值。

　　計(jì)算器語(yǔ)法

　　根據(jù)前面部分中介紹的標(biāo)記，存在大量的語(yǔ)法規(guī)則用于分析這些標(biāo)記。語(yǔ)法分析器的完整代碼如清單 16 所示。讓我們更仔細(xì)地看一下其中一些重要的部分以及該系統(tǒng)是如何工作的。

　　清單 16. 計(jì)算器語(yǔ)法文件

%{
#include <alloca.h>
#include <math.h>
#include <stdlib.h>
#include <stddef.h>
#include <ctype.h>
#define YYSTYPE double
double calcfact();
double reg[99];
double ans;
char format[20];
%}
%token NUMBER SPACE MOD RIGHTSHIFT LEFTSHIFT SEMICOLON SIN EOLN PIVAL
%token PLUS MINUS DIV MUL POW OPENBRACKET CLOSEBRACKET UNARYMINUS
%token COS TAN ASIN ACOS ATAN FACT INC DEC LAND OR COMPLEMENT
%token NOT XOR ASSIGN IOR AND OPENREG CLOSEREG REGA ANS FIX SCI ENG
%token CONST
%left PLUS MINUS
%left MUL DIV
%left UNARYMINUS
%left LAND OR XOR NOT AND IOR
%left LOG
%%
list: /* nothing */
| list EOLN
| list expr EOLN
{ printf( format , (double) $2 ); ans=$2; }
;
expr: conditional_expr
;
conditional_expr: logical_or_expr
;
logical_or_expr: logical_and_expr
| logical_or_expr OR logical_and_expr
{ $$ = (int) $1 || (int) $3; }
;
logical_and_expr: inclusive_or_expr
| logical_and_expr LAND inclusive_or_expr
{ $$ = (int) $1 && (int) $3; }
;
inclusive_or_expr: exclusive_or_expr
| inclusive_or_expr IOR exclusive_or_expr
{ $$ = (int) $1 | (int) $3; }
;
exclusive_or_expr: and_expr
| exclusive_or_expr XOR and_expr
{ $$ = (int) $1 ^ (int) $3; }
;
and_expr: shift_expr
| and_expr AND shift_expr
{ $$ = (int) $1 & (int) $3; }
;
shift_expr: pow_expr
| shift_expr LEFTSHIFT pow_expr
{ $$ = (int) $1 << (int) $3; }
| shift_expr RIGHTSHIFT pow_expr
{ $$ = (int) $1 >>(int) $3; }
;
pow_expr: add_expr
| pow_expr POW add_expr { $$ = pow($1,$3); }
;
add_expr: mul_expr
| add_expr PLUS mul_expr { $$ = $1 + $3; }
| add_expr MINUS mul_expr { $$ = $1 - $3; }
;
mul_expr: unary_expr
| mul_expr MUL unary_expr { $$ = $1 * $3; }
| mul_expr DIV unary_expr { $$ = $1 / $3; }
| mul_expr MOD unary_expr { $$ = fmod($1,$3); }
;
unary_expr: assign_expr
| MINUS primary %prec UNARYMINUS { $$ = -$2; }
| INC unary_expr { $$ = $2+1; }
| DEC unary_expr { $$ = $2-1; }
| NOT unary_expr { $$ = !$2; }
| LOG unary_expr { $$ = log($2); }
;
assign_expr: postfix_expr
| REGA OPENREG expr CLOSEREG ASSIGN postfix_expr
{ reg[(int)$3]=$6; $$=$6; }
| REGA OPENREG expr CLOSEREG
{ $$=reg[(int)$3]; }
| REGA
{ int i;
for(i=0;i<100;i++)
if (reg[i]!=0)
printf("%02d = %.2fn",i,reg[i]);
$$=0;
}
;
postfix_expr: primary
| postfix_expr INC { $$ = $1+1; }
| postfix_expr DEC { $$ = $1-1; }
| postfix_expr FACT
{ $$ = calcfact((unsigned long int)$1); }
;
primary: NUMBER { $$ = $1; }
| PIVAL { $$ = M_PI; }
| OPENBRACKET expr CLOSEBRACKET { $$ = $2; }
| ANS { $$ = ans; }
| CONST OPENBRACKET expr CLOSEBRACKET { $$ = constval($3); }
| set_format
;
set_format: function_call
| FIX OPENBRACKET expr CLOSEBRACKET
{ sprintf(format,"%%.%dfn",(int)$3); $$=0; }
| FIX { sprintf(format,"%%fn"); $$=0; }
| SCI OPENBRACKET expr CLOSEBRACKET
{ sprintf(format,"%%.%dgn",(int)$3); $$=0; }
| SCI { sprintf(format,"%%gn"); $$=0; }
| ENG OPENBRACKET expr CLOSEBRACKET
{ sprintf(format,"%%.%den",(int)$3); $$=0; }
| ENG { sprintf(format,"%%en"); $$=0; }
;
function_call: SIN OPENBRACKET expr CLOSEBRACKET
{ $$ = (cos($3)*tan($3)); }
| COS OPENBRACKET expr CLOSEBRACKET
{ $$ = cos($3); }
| TAN OPENBRACKET expr CLOSEBRACKET
{ $$ = tan($3); }
| ASIN OPENBRACKET expr CLOSEBRACKET
{ $$ = asin($3); }
| ACOS OPENBRACKET expr CLOSEBRACKET
{ $$ = acos($3); }
| ATAN OPENBRACKET expr CLOSEBRACKET
{ $$ = atan($3); }
;
%%
#include <stdio.h>
#include <ctype.h>
char *progname;
double yylval;
main( argc, argv )
char *argv[];
{
progname = argv[0];
strcpy(format,"%gn");
yyparse();
}
yyerror( s )
char *s;
{
warning( s , ( char * )0 );
yyparse();
}
warning( s , t )
char *s , *t;
{
fprintf( stderr ,"%s: %sn" , progname , s );
if ( t )
fprintf( stderr , " %sn" , t );
}

　　對(duì)于應(yīng)用程序中其他的部分，有三個(gè)全局結(jié)構(gòu)可供使用：

reg 數(shù)組用作通用存儲(chǔ)寄存器，可以在其中存放計(jì)算過(guò)程的值和結(jié)果。

ans 變量包含上次計(jì)算的值。

format 用于保存打印結(jié)果時(shí)所使用的輸出格式。

　　僅當(dāng)輸入中包含行結(jié)束字符（以 EOLN 標(biāo)記進(jìn)行標(biāo)識(shí)）時(shí)，才打印出計(jì)算結(jié)果。這樣就可以在單行中輸入很長(zhǎng)的計(jì)算式，并且在對(duì)相應(yīng)的內(nèi)容進(jìn)行了分析和處理后，再打印出結(jié)果值。這項(xiàng)操作使用全局 format 變量所指定的格式，并且將結(jié)果存儲(chǔ)在 ans 中。

　　分析器的主要部分是識(shí)別片段并計(jì)算結(jié)果的組合，直到最后將比較復(fù)雜的計(jì)算過(guò)程中不同的部分解析為最終的值。

　　設(shè)置輸出格式

　　格式就是用于 printf() 的一個(gè)合適的格式字符串，可以通過(guò)使用函數(shù)方式的調(diào)用來(lái)設(shè)置輸出的精度和格式。例如，要設(shè)置固定小數(shù)點(diǎn)的輸出以限制小數(shù)點(diǎn)右邊的數(shù)字，您可以使用 fix(3)，或者可以重新設(shè)置缺省格式： fix()。

　　在清單 17 的序列中，您可以看到相應(yīng)的效果。

　　清單 17. 輸出格式

$ calc
1/3
0.333333
fix(3)
0.000
1/3
0.333

　　因?yàn)樵摳袷阶址侨值模⑶覂H由一條規(guī)則來(lái)打印出結(jié)果，這就意味著您可以很容易地使用該格式字符串來(lái)控制輸出。

　　計(jì)算器寄存器

　　寄存器實(shí)際上是一個(gè)浮點(diǎn)值數(shù)組，可以通過(guò)使用一個(gè)數(shù)值引用來(lái)訪問(wèn)該數(shù)組。這部分代碼中的分析工作由清單 18 中所示的代碼片段完成。

　　清單 18. 計(jì)算器中的寄存器

assign_expr: postfix_expr
| REGA OPENREG expr CLOSEREG ASSIGN postfix_expr
{ reg[(int)$3]=$6; $$=$6; }
| REGA OPENREG expr CLOSEREG
{ $$=reg[(int)$3]; }
| REGA
{ int i;
for(i=0;i<100;i++)
if (reg[i]!=0)
printf("%02d = %.2fn",i,reg[i]);
$$=0;
}
;

　　第一條規(guī)則允許進(jìn)行賦值，并且該分析器允許使用表達(dá)式對(duì)寄存器進(jìn)行引用，但對(duì)于相應(yīng)的值只能使用 postfix_expr。這將限制所能夠?qū)拇嫫髦付ǖ闹担缜鍐?span lang="EN-US"> 19 中的序列所示。

　　清單 19. 限制能夠?qū)拇嫫髦付ǖ闹?

reg[0]=26
26
reg[0]
26
reg[1]=(4+5)*sin(1)
7.57324
reg[1]
9
reg[4+5]=29
29
reg[9]
29

　　請(qǐng)注意，中間的表達(dá)式 (4+5)*sin(1) 返回正確的結(jié)果，但僅將該表達(dá)式開(kāi)始部分的值賦給了寄存器。這是因?yàn)樵撘?guī)則僅允許使用匹配 postfix_assign 規(guī)則的表達(dá)式進(jìn)行賦值，并且實(shí)際上由 primary 規(guī)則最終描述帶圓括號(hào)的語(yǔ)句的規(guī)則。因?yàn)椴辉试S將整行輸入作為賦值的一部分，所以分析器匹配了第一個(gè)片段 ((4+5)) 并將這個(gè)值賦給了寄存器。因?yàn)閷?duì)寄存器賦值時(shí)返回了寄存器的值，所以其他的計(jì)算過(guò)程可以繼續(xù)進(jìn)行并打印出正確的結(jié)果。

　　有一個(gè)簡(jiǎn)單的解決方案可以處理這個(gè)問(wèn)題。作為一條簡(jiǎn)單的輸入規(guī)則，您需要使用圓括號(hào)將對(duì)寄存器的賦值語(yǔ)句括起來(lái)：

reg[1]=((4+5)*sin(1))

　　這并不需要對(duì)相應(yīng)的規(guī)則進(jìn)行任何更改，因?yàn)樵诂F(xiàn)有的分析器中可以使用上面的方法，但可能需要對(duì)文檔進(jìn)行相應(yīng)的更改。

　　當(dāng)前的系統(tǒng)還有一個(gè)優(yōu)點(diǎn)，那就是您可以同時(shí)對(duì)下一個(gè)寄存器賦值。這是因?yàn)閷?duì)寄存器賦值時(shí)會(huì)返回該寄存器的結(jié)果。因此，下面的序列可以正常工作（請(qǐng)參見(jiàn)清單 20）。

　　清單 20. 寄存器的結(jié)果

reg[1]=(45+reg[2]=(3+4))
52
reg[1]
52
reg[2]
7

　　擴(kuò)展 lex 和 yacc 的原則

　　這個(gè)計(jì)算器演示了一些基本處理，但是關(guān)于 lex 和 yacc 工具以及如何使用它們，還有很多的內(nèi)容。

　　使用計(jì)算器分析器

　　因?yàn)榉治鲚斎胄畔⒌囊?guī)則和對(duì)信息的處理可以單獨(dú)地進(jìn)行設(shè)置和控制，所以實(shí)際上可以獨(dú)立地改變信息提取和處理的方式。

　　當(dāng)我第一次接觸 lex 和 yacc 時(shí)，我的初始目標(biāo)是構(gòu)建一個(gè)逆波蘭表示法 (RPN) 計(jì)算器。使用 RPN，您需要首先提供相應(yīng)的數(shù)值，然后是運(yùn)算符，例如，要將兩個(gè)數(shù)值相加在一起，您應(yīng)該使用： 4 5 +。

　　對(duì)于有些人來(lái)說(shuō)，這種序列更有意義，特別是當(dāng)您希望編寫(xiě)出與學(xué)校里學(xué)到的加法運(yùn)算相同的計(jì)算過(guò)程時(shí)：

4
5 +
----
9
----

　　對(duì)于更加復(fù)雜的計(jì)算過(guò)程，您可以將數(shù)值載入到堆棧中，然后使用相應(yīng)的參數(shù)，即自動(dòng)地放回到堆棧中的計(jì)算結(jié)果。4+5*6 可以編寫(xiě)為： 4 5 6 * +。

　　對(duì)于計(jì)算機(jī)來(lái)說(shuō)，這種表示方式更加直截了當(dāng)。您可以使用堆棧來(lái)實(shí)現(xiàn) RPN 計(jì)算器。當(dāng)分析器識(shí)別了一個(gè)數(shù)值，會(huì)將它壓入堆棧，并且當(dāng)發(fā)現(xiàn)了一個(gè)運(yùn)算符時(shí)，從堆棧中彈出相應(yīng)的值，然后執(zhí)行計(jì)算過(guò)程。它簡(jiǎn)化了在執(zhí)行常規(guī)表達(dá)式分析中所需的大量的處理和復(fù)雜的分析過(guò)程。

　　然而，再增加一點(diǎn)點(diǎn)工作，您就可以創(chuàng)建一個(gè)將常規(guī)表達(dá)式輸入轉(zhuǎn)換為 RPN 的分析器。甚至更加完善，您還可以將 RPN 轉(zhuǎn)換為標(biāo)準(zhǔn)的表達(dá)式格式。

　　例如，將表達(dá)式轉(zhuǎn)換為 RPN：

$ equtorpn
4+5*6
4 5 6 * +

　　其中有趣的是，分析規(guī)則中定義的優(yōu)先級(jí)順序（其 yacc 分析器是這里所介紹的計(jì)算器的簡(jiǎn)化版本）將產(chǎn)生滿足上述示例的 RPN。

　　您可以將 equtorpn 工具的輸出作為 RPN 計(jì)算器的輸入，并獲得相同的結(jié)果：

$ equtorpn|rpn
4+5*6
34

　　有關(guān) rpn、equtorpn 和 rpntoequ 應(yīng)用程序的完整示例和代碼及其工作方式的更詳細(xì)的討論，請(qǐng)?jiān)L問(wèn) MCslp Coalface Web 站點(diǎn)（請(qǐng)參見(jiàn)參考資料）。

　　使用計(jì)算器分析器

　　因?yàn)榉治鲚斎胄畔⒌囊?guī)則和對(duì)信息的處理可以單獨(dú)地進(jìn)行設(shè)置和控制，所以實(shí)際上可以獨(dú)立地改變信息提取和處理的方式。

　　當(dāng)我第一次接觸 lex 和 yacc 時(shí)，我的初始目標(biāo)是構(gòu)建一個(gè)逆波蘭表示法 (RPN) 計(jì)算器。使用 RPN，您需要首先提供相應(yīng)的數(shù)值，然后是運(yùn)算符，例如，要將兩個(gè)數(shù)值相加在一起，您應(yīng)該使用： 4 5 +。

　　對(duì)于有些人來(lái)說(shuō)，這種序列更有意義，特別是當(dāng)您希望編寫(xiě)出與學(xué)校里學(xué)到的加法運(yùn)算相同的計(jì)算過(guò)程時(shí)：

4
5 +
----
9
----

　　對(duì)于更加復(fù)雜的計(jì)算過(guò)程，您可以將數(shù)值載入到堆棧中，然后使用相應(yīng)的參數(shù)，即自動(dòng)地放回到堆棧中的計(jì)算結(jié)果。4+5*6 可以編寫(xiě)為： 4 5 6 * +。

　　對(duì)于計(jì)算機(jī)來(lái)說(shuō)，這種表示方式更加直截了當(dāng)。您可以使用堆棧來(lái)實(shí)現(xiàn) RPN 計(jì)算器。當(dāng)分析器識(shí)別了一個(gè)數(shù)值，會(huì)將它壓入堆棧，并且當(dāng)發(fā)現(xiàn)了一個(gè)運(yùn)算符時(shí)，從堆棧中彈出相應(yīng)的值，然后執(zhí)行計(jì)算過(guò)程。它簡(jiǎn)化了在執(zhí)行常規(guī)表達(dá)式分析中所需的大量的處理和復(fù)雜的分析過(guò)程。

　　然而，再增加一點(diǎn)點(diǎn)工作，您就可以創(chuàng)建一個(gè)將常規(guī)表達(dá)式輸入轉(zhuǎn)換為 RPN 的分析器。甚至更加完善，您還可以將 RPN 轉(zhuǎn)換為標(biāo)準(zhǔn)的表達(dá)式格式。

　　例如，將表達(dá)式轉(zhuǎn)換為 RPN：

$ equtorpn
4+5*6
4 5 6 * +

　　其中有趣的是，分析規(guī)則中定義的優(yōu)先級(jí)順序（其 yacc 分析器是這里所介紹的計(jì)算器的簡(jiǎn)化版本）將產(chǎn)生滿足上述示例的 RPN。

　　您可以將 equtorpn 工具的輸出作為 RPN 計(jì)算器的輸入，并獲得相同的結(jié)果：

$ equtorpn|rpn
4+5*6
34

　　有關(guān) rpn、equtorpn 和 rpntoequ 應(yīng)用程序的完整示例和代碼及其工作方式的更詳細(xì)的討論，請(qǐng)?jiān)L問(wèn) MCslp Coalface Web 站點(diǎn)（請(qǐng)參見(jiàn)參考資料）。

　　進(jìn)行適當(dāng)?shù)奈谋痉治?

　　這些示例介紹了如何構(gòu)建一個(gè)表達(dá)式分析器，而該分析器可以將數(shù)學(xué)表達(dá)式轉(zhuǎn)換為可以進(jìn)行計(jì)算的表達(dá)式。該分析器說(shuō)明了序列、分析規(guī)則和諸如優(yōu)先級(jí)之類(lèi)的問(wèn)題的重要性。在文本處理系統(tǒng)中也可以應(yīng)用相同的規(guī)則，但是處理文本可能更加復(fù)雜，除非您建立與計(jì)算器示例中同樣嚴(yán)格的強(qiáng)制規(guī)則。

　　清單 21 顯示了創(chuàng)建簡(jiǎn)單的 set/get 狀態(tài)分析器的 lex 文件，而清單 22 顯示了分析其輸出的 yacc 規(guī)則。

　　清單 21. 使用 lex 進(jìn)行基于文本的標(biāo)記化

%{
#include <stdio.h>
#include "text.tab.h"
%}
%%
set return SET;
state return STATE;
mode return MODE;
get return GET;
[a-zA-Z]+ { yylval=strdup(yytext); return STRING; }
%%

　　清單 22. 分析文本的 yacc 規(guī)則

%{
#include <stdlib.h>
#define YYSTYPE char *
char mode[20];
char state[20];
%}
%token SET STATE MODE GET STRING EOLN
%%
list: /* nothing */
| list getorset
;
getorset: getvalue
| setvalue
;
setvalue:
SET STATE STRING { strcpy(state,$3); printf("State setn"); }
| SET MODE STRING { strcpy(mode,$3); printf("Mode setn"); }
;
getvalue:
GET STATE { printf("State: %sn",state); }
| GET MODE { printf("Mode: %sn",mode); }
;
%%
#include <stdio.h>
#include <ctype.ha>
char *progname;
main( argc, argv )
char *argv[];
{
progname = argv[0];
yyparse();
}
yyerror( s )
char *s;
{
fprintf( stderr ,"%s: %sn" , progname , s );
}

　　在計(jì)算器示例中，必須將輸入文本轉(zhuǎn)換為一個(gè)數(shù)值，而這個(gè)示例與計(jì)算器示例有所不同，您可以直接使用輸入字符串，而無(wú)需進(jìn)行轉(zhuǎn)換（請(qǐng)參見(jiàn)清單 23）。

　　清單 23. 直接使用輸入字符串

$ textparser
get state
State:
set state bob
State set
get state
State: bob

　　更加復(fù)雜的文本分析器也都構(gòu)建于相同的基本原則，并且可用于完成各種任務(wù)，從配置文件分析器，到構(gòu)建您自己的腳本語(yǔ)言，甚至是可進(jìn)行編譯的語(yǔ)言。

　　語(yǔ)言編譯器

　　語(yǔ)言編譯器（例如 C 編譯器）可以接受您的輸入，并將輸入轉(zhuǎn)換為指定的目標(biāo)平臺(tái)的原始匯編語(yǔ)言。這就解釋了為什么最初的編譯器都是特定于體系結(jié)構(gòu)的，為什么編寫(xiě)一個(gè)為可選的平臺(tái)生成代碼的編譯器（交叉編譯）相當(dāng)容易。編譯器僅為可選的平臺(tái)生成匯編代碼。例如，要將兩個(gè)數(shù)值相加到一起，您可以對(duì)前面使用的規(guī)則集進(jìn)行更改，以便生成如下所示的 Intel x86 匯編代碼：

add_expr: mul_expr
| add_expr PLUS mul_expr
{ printf("MOV ax,%dnADD ax,%dn",$1,$3); }

　　為了使匯編轉(zhuǎn)換處理過(guò)程能夠構(gòu)建完整的語(yǔ)言，可以將其他的結(jié)構(gòu)（如循環(huán)、遞歸、函數(shù)、變量名稱和其他的元素）添加到該系統(tǒng)中。

　　總結(jié)

　　通過(guò) lex 和 yacc 的組合，您可以生成構(gòu)建分析器的代碼。lex 工具提供了識(shí)別文本片段和元素的方法，并可以返回相應(yīng)的標(biāo)記。yacc 工具可以使用一系列描述輸入格式的規(guī)則來(lái)處理這些標(biāo)記組成的結(jié)構(gòu)，并且定義了處理識(shí)別的序列的方法。在這兩種情況下，這些工具都使用了一個(gè)配置文件，在生成構(gòu)建合適的分析應(yīng)用程序的 C 源代碼時(shí)將對(duì)該文件進(jìn)行處理。

　　在本教程中，您看到了關(guān)于如何使用這些應(yīng)用程序?yàn)橛?jì)算器應(yīng)用程序構(gòu)建簡(jiǎn)單的分析器的示例。通過(guò)這些處理，您了解了標(biāo)記化、規(guī)則集的重要性，以及規(guī)則集如何互相作用以提供完整的分析解決方案。您了解了如何使用這些基本原則進(jìn)行其他的處理，如文本分析器、甚至是構(gòu)建您自己的編程語(yǔ)言。