關鍵字： RSCT 內存調試 Expect 正則表達式 Tcl
在 UNIX® 中，許多操作系統組成部分都依賴于文本分析，從用來與系統進行交互的 shell，到諸如 awk or Perl 等各種常用的工具和命令，再到用來構建軟件和應用程序的 C 編譯器。您可以在 UNIX 應用程序（以及其他的應用程序）中使用分析器來構建簡單的配置分析器，甚至構建最終的目標：您自己的編程語言。
本文將研究使用 lex/flex 和 yacc/bison 工具構建分析器所需的步驟。首先構建一個簡單的計算器，然后深入地研究如何采用相同的原則進行文本分析。分析文本，即理解和提取文本中的關鍵部分，是許多應用程序中一個重要的部分。在 UNIX? 中，許多操作系統組成部分都依賴于文本分析，從用來與系統進行交互的 shell，到諸如 awk or Perl 等各種常用的工具和命令，再到用來構建軟件和應用程序的 C 編譯器。您可以在 UNIX 應用程序（以及其他的應用程序）中使用分析器來構建簡單的配置分析器，甚至構建最終的目標：您自己的編程語言。
開始之前
UNIX? 程序員常常發現他們需要去理解文本和其他一些具有靈活的標準化格式的結構。通過使用 lex 和 yacc 工具，您可以構建一個分析引擎，根據特定的規則來處理文本。然后，可以將它集成到您的應用程序中以完成各項工作，從配置分析到構建您自己的編程語言。在學習了本教程之后，您將了解如何定義詞法元素、編寫 yacc 規則，并使用相應的規則機制來構建和定義各種不同的分析引擎和應用程序。
關于本教程
在 UNIX 中，有許多用來理解和提取文本的方法。您可以使用 grep、awk、Perl 和其他的解決方案。但有的時候，您需要理解和提取結構化的但格式不受限制的數據。在這種情況下，UNIX lex 和 yacc 工具就很有用處了。前面提到的那些工具，如 awk、Perl 以及 shell 和許多其他的編程語言，都使用 lex 和 yacc 來生成分析應用程序以分析和理解文本，并將其轉換為所需的信息或數據結構。
Lex 是一種詞法分析工具，它可以用來從源文本識別特定結構的文本字符串。Yacc 是一種語法分析器，它可以讀取文本并用來將單詞序列轉換為便于處理的結構化的格式。
在本教程中，首先您將研究如何使用 lex 和 yacc 來構建一個計算器。使用該計算器作為示例，您將進一步研究 lex 和 yacc 系統生成的輸出和信息，并學習如何使用它來分析其他類型的信息。
先決條件
要使用在本教程中的示例，您需要使用到下列工具：
Lex：這個工具是大多數 UNIX 操作系統的標準組件。GNU flex 工具提供了相同的功能。
Yacc：這個工具是大多數 UNIX 操作系統的標準組件。GNU bison 工具提供了相同的功能。
C 編譯器：任何標準的 C 編譯器都可以，其中包括 Gnu CC。
Make 工具：這個工具是使用示例 Makefile 來簡化構建過程所必需的。
可以從 GNU Web 站點或本地的 GNU 鏡像站點下載 GNU 工具。
使用 lex 進行詞法分析
編寫文本分析器的第一步是要能夠識別所讀取的內容。有許多不同的方法可以完成這項任務，但是最簡單的方法是使用 lex，它是將輸入信息轉換為一系列標記的工具。
什么是詞法分析？
當使用編程語言編寫程序或在命令行中輸入命令時，您是否想過究竟執行了什么操作將您輸入的內容轉換為一組指令呢？
這個處理過程非常簡單，卻又相當復雜。它很復雜，這是因為對于可能輸入的信息，表面上看起來似乎存在無限種可能的組合和序列。例如，要使用 Perl 語言遍歷一個哈希表，您可以使用如清單 1 所示的序列。
清單 1. 在 Perl 中遍歷一個哈希表
foreach $key (keys %hash)
{
...
}
其中的每一項都是有意義的，雖然方式有所不同，這正是該處理過程的簡單明了之處。清單 1 中所示的表達式存在一個對應的結構，也就是說，與人類語言一樣，編程語言中也存在著特定的規則。因此，如果將輸入分解為您所看到的和該信息結構的組合，那么對該內容的分析過程則相當簡單。
要理解提供給文本分析應用程序的信息，通常有兩個階段。第一個階段是識別輸入的或提供給應用程序的內容是什么。您必須能夠從輸入源中識別關鍵字、短語或字符序列，以便能夠確定對其進行何種處理。第二個處理階段是理解該信息的結構，即語法，以便對輸入進行驗證和操作。有關語法的一個很好的示例是，大多數編程語言中圓括號的使用。很明顯，下面的表達式是錯誤的：
{ function)( {
其中，大括號不匹配，而圓括號的出現順序錯誤。為了讓分析器理解和識別表達式，那么分析器必須知道正確的序列，以及匹配該序列后應該進行何種操作。
詞法分析首先進行識別輸入數據的處理，并且可以使用 lex 工具來完成該處理過程。
lex 工具
lex 工具（或 GNU 工具 flex）使用一個配置文件來生成相應的 C 源代碼，然后，可以用它來創建獨立的應用程序，或者在您自己的應用程序中使用它。配置文件定義了需要在待分析的文件中查找的字符序列，以及當發現該序列之后應該進行什么操作。該文件的格式十分簡單，即指定輸入序列和相應的結果，用空格（或制表符）隔開。例如：
sequence do-something
清單 2 顯示了一個非常簡單的定義，它可以接受單詞并根據提供的單詞打印出一個字符串。
清單 2. 簡單的 lex 定義
%{
#include <stdio.h>
%}
%%
begin printf("Startedn");
hello printf("Hello yourself!n");
thanks printf("Your welcomen");
end printf("Stoppedn");
%%
代碼中的第一塊由 %{...%} 定義，表示將其中的文本插入到生成的 C 源代碼中。在本示例中，因為后面使用了 printf() 函數，所以必須確保包含了 stdio.h Header。
代碼中的第二塊由 %% 序列標識，其中包含了要識別的字符串輸入和相應結果的定義。在上述的這些情況下，對于一個簡單的單詞，將打印出合適的響應。
生成 C 源代碼
要生成能夠真正分析輸入文本的 C 源代碼，可以對清單 1 所示的文件運行 lex（或 flex）。Lex/flex 文件點號后綴為 'l'，所以上面的文件可能名為 exampleA.l。要生成相應的 C 源代碼：
$ flex exampleA.l
不管您使用哪種工具，其輸出都將為 lex.yy.c。缺乏勇氣的人往往不敢仔細研究這個文件，分析器內部的處理過程的確非常復雜，并且建立在基于表格的復雜分析系統的基礎上，該系統可以根據原始 lex 定義中的定義對輸入文本進行匹配。因為存在這樣的關聯，所以該代碼相當占用內存，特別是對于那些很大且很復雜的文件。
與 lex 相比，flex 的優點在于它提供了大量附加的選項以改進性能（針對內存或速度）、調試選項和對掃描器行為更好的控制（例如，可以忽略某些情況）。在生成 C 源代碼時，通過使用 -l 命令行選項，您可以生成與原始的 lex 工具生成的源代碼非常接近的 C 源代碼。
既然已經有了 C 源代碼，那么您可以將其編譯為相應的應用程序以測試該處理過程：
$ gcc -o exampleA lex.yy.c -lfl
flex 庫（使用 -lfl 進行包含，而 lex 則使用 -ll）包含執行分析代碼的簡單的 main() 函數。當運行生成的應用程序時，它將等待輸入。清單 3 顯示了該應用程序的輸入（和輸出）。
清單 3. 簡單 lex 應用程序的輸入/輸出
$ exampleA
begin
Started
hello
Hello yourself!
end
Stopped
thanks
Your welcome
hello thanks
Hello yourself!
Your welcome
hello Robert
Hello yourself!
Robert
對于單行輸入 ('begin')，該應用程序根據您所提供的命令進行響應，在本示例中，將打印出單詞 'Started'。對于包含多個識別單詞的行，該應用程序分別運行多個命令，并以空格隔開。對于無法識別的標記（包括空白字符），僅對其進行回顯。
這個示例介紹了該系統的基本操作，但是您僅僅使用了標準的單詞。要使用其他的組合，如字符和元素，有各種不同的解決方案可供使用。
識別元素
可識別的元素可以不是前面介紹的固定字符串，標識符支持正則表達式和特殊（例如標點符號）字符，如清單 4 所示。
清單 4. 正則表達式和特殊字符
%{
#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 中的示例應該是一目了然的，并且對于需要進行分析的任何正則表達式或特殊字符都可以使用相同的原則。
真正的標記化
前面的示例所構建的 C 源代碼實質上是獨立的。盡管使用這種方法沒有什么問題，但是對于分析包含多個單詞、短語或序列的給定指令中的文本或其他條目的情況，這種方法并不是很有價值。
使用這種方式分析序列需要一個語法分析器，而它將定義標記序列。但是語法分析器必須知道要分析的是什么標記。在 lex 定義中，當識別標記時所進行的操作是回顯字符串，如果要返回一個識別標記，那么需要對該操作進行更改。例如，您可以如清單 5 所示對原始示例進行重寫。
%{
#include <stdio.h>
#include <y.tab.h>
%}
%%
begin return BEGIN;
hello return HELLO;
thanks return THANKS;
end return END;
%%
現在，當識別了 'hello' 標記時，不再是打印一個字符串，而是返回標記的名稱。在 yacc 中，將使用這個名稱來建立相應的語法。
在這個示例中，沒有顯式地定義這些標記名稱。實際上是在 y.tab.h 文件中指定了這些標記名稱，而在分析 yacc 語法文件時由 yacc 自動生成該文件。
提取變量數據
如果要提取一個值（例如，需要能夠讀取一個數值或字符串），那么您必須指定如何將輸入轉換為所需的類型。通常由于 lex 中的各種限制，這種做法并不是很有價值，但是當使用 yacc 工具來構建一個完整的分析器時，這是至關重要的。
通常可以使用兩個變量來交換信息，yytext 變量包含了在分析過程中由 lex 讀取的原始數據，而 yylval 則用于在兩個系統之間交換實際的值。在本教程后面的內容中，將更詳細地介紹這種結合是如何進行的，但是出于識別信息的目的，您可能使用類似下面的 lex 定義：
[0-9] yylval=atoi(yytext); return NUMBER;
在上面的代碼行中，使用了標準的 atoi() 函數將匹配正則表達式（并保存于 yytext 中）的輸入字符串片段轉換為一個整數，并將 yylval 的值設置為該整數。請注意，盡管對值進行了轉換，但您仍然需要返回值的類型，以便 yacc 知道究竟是什么類型并可以根據自己的定義來使用這個標記。
讓我們通過查看 yacc 如何定義語法結構，以此來了解這項工作是如何進行的。
使用 yacc 進行語法分析
語法定義用于定義標記序列以及應得到的結果。它通常與 lex 聯合使用，由 lex 讀取相應的文本，并且兩者一同構成整個分析器。
yacc 的基本語法
yacc 語法定義的基本結構是定義預期的標記序列。例如，您可以定義表達式 A + B，其中 A 和 B 都是使用下列定義的數值：
NUMBER PLUSTOKEN NUMBER { printf("%fn",($1+$3)); }
NUMBER 是一個數值的識別標記，并且 PLUSTOKEN 是加號的識別標記。
大括號中的代碼定義了識別這個序列后進行何種操作，在本示例中，給出的是將這兩個數值相加的 C 代碼。請注意，使用命名法 $1 表示該語法表達式中的第一項標記，$3 表示其中的第三項。
對于待識別的語法序列，您必須對序列進行命名，如清單 6 所示。
清單 6. 對序列命名
addexpr: NUMBER PLUSTOKEN NUMBER
{
printf("%fn",($1+$3));
}
;
語法組的名稱為 addexpr，并且這個組定義以一個分號作為結束。
一個語法定義可以包含多個序列（以及相關的操作），而這些序列都是一個特殊的組中的一部分。例如在計算器中，加法和減法處理是類似的操作，所以可以將它們集中作為一組。一個組中不同的定義可以使用管道符號 (|) 進行分隔（請參見清單 7）。
清單 7. 一個組中不同的定義使用管道符號進行分隔
addexpr: NUMBER PLUSTOKEN NUMBER
{
printf("%fn",($1+$3));
}
| NUMBER MINUSTOKEN NUMBER
{
printf("%fn",($1-$3));
}
;
您已經了解了基本的語法規范，那么還需要了解如何組合多個序列以及它們的優先級。
語法序列和優先級
在大多數語言中，無論是文本型、數學運算型，還是編程型的語言，通常對于不同的短語都有某種優先級或重要性，這將使得它們與類似的但不同的組合相比具有相應的優先權。
例如，在大多數編程語言的數學運算表達式中，乘法具有比加法或減法更高的優先級。例如，表達式：4+5*6 將計算為： 4+30。
這將得到最終的計算結果 34。其原因是首先進行乘法操作（5 乘以 6 等于 30），然后將其結果用于最后的計算過程，即加上 4 后得到結果 34。
在 yacc 中，通過定義多個語法序列組并將它們連接在一起，就可以定義相應的優先級，不同表達式在組中的順序可以幫助定義其優先級。在清單 8 中，您可以看到用于定義上述行為的代碼。
清單 8. 連接語法并提供優先級
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 執行所有表達式計算都是從左到右進行處理的，所以對于與原始示例類似的復合表達式（例如，4+5*6），yacc 將根據相應的規則查找最佳匹配，即與表達式中的一部分匹配。
根據規則所定義的順序，自上而下進行匹配處理。所以，該處理過程首先試圖匹配 add_expr 中的語法規則。然而，因為乘法具有更高的優先級，所以這些規則表明 yacc 應該首先嘗試 mul_expr。這將迫使 yacc 首先根據乘法語句進行匹配（在 mul_expr 中進行定義）。如果匹配失敗，然后它將嘗試 add_expr 塊中的下一條規則，依此類推，直到該表達式被解析，或者沒能找到任何匹配并生成一個錯誤。
當使用上述的規則集對公式 4+5*6 進行計算時，yacc 首先嘗試 add_expr，然后被重定向到 mul_expr（作為匹配的第一條規則），并且又被重定向到 primary。primary 規則設置了表達式中相應數字的值。$$ 有效地設置了那部分表達式的返回值。
在匹配了這些數字之后，yacc 根據下面這行定義識別了一個乘法表達式：| mul_expr MUL primary { $$ = $1 * $3; }，它設置了原始表達式中的 5*6 部分的返回值。Yacc 生成代碼以執行相應的計算（提取前面由 primary 規則設置的值），并使用計算的結果值替換輸入表達式的原始部分。這就意味著 yacc 現在需要匹配下面的表達式： 4+30。
它可以使用下面的規則匹配這個表達式：| add_expr PLUS mul_expr { $$ = $1 + $3; }，這將最終計算出最后的結果 34。
徹底地研究語法定義
語法定義設置了相應的規則，用于分析輸入標記及其格式和布局，并將其轉換為可以使用的信息。在任何時候都請記住，這里定義的規則集是告訴 yacc 如何識別輸入并執行一段 C 代碼。yacc 工具生成所需的 C 代碼來分析該信息，而并不是由 yacc 來完成分析工作。
大括號中的代碼是 quasi-C 源代碼。Yacc 根據您給出的定義將原始文件轉換為相應的 C 源代碼以及分析具體內容所需的其他的代碼。
除了定義如何分析輸入內容的規則集之外，還有一些附加函數和選項用以幫助定義其他的 C 源代碼。完整的 yacc 定義文件的基本格式類似與 lex/flex 所使用的格式，如下面的清單 9 所示。
清單 9. Yacc 文件格式
%{
/* Global and header definitions required */
%}
/* Declarations (Optional token definitions) */
%%
/* Parsing ruleset definitions
%%
/* Additional C source code */
全局/Header 定義與 lex/flex 文件中所使用的定義相同，如果您在分析和處理輸出時使用了特殊的函數，那么它們都是必需的。
標記定義不僅描述了預期的標記，還描述了分析處理過程中的優先級。通過迫使 yacc 按照特定的順序檢查標記，這可以調整 yacc 對規則的處理方式，并且還影響到在與規則進行比較時如何對表達式進行處理。
例如，您通常可以定義 + 標記具有左優先級，也就是說，首先對這個標記左邊的任何表達式進行匹配，這樣一來，表達式 4+5+6 首先會計算 4+5，然后計算 9+6。
然而，您可能希望為一些標記指定右優先級，例如，計算邏輯 NOT，（例如，! (expr)）您可能希望先計算 expr，然后對通過 ! 標記對其表達式的值取反。
除了控制規則之間的優先級關系之外，還可以指定標記的優先級，這樣您就可以精確地控制如何對輸入進行計算。
有三種主要的標記類型，%token（沒有優先級差別），%left（標記左側的輸入具有優先級）和 %right（標記右側的輸入具有優先級）。例如，清單 10 根據適當的優先級定義了若干標記：
清單 10. 根據適當的優先級定義若干標記
%token EQUALS POWER
%left PLUS MINUS
%left MULTIPLY DIVIDE
%right NOT
請注意，以自上而下優先級遞增的順序指定標記的優先級，并且同一行中的標記具有相同的優先級。在清單 10 所示的示例中，MULTIPLY 和 DIVIDE 具有相同的優先級，該優先級要高于 PLUS 和 MINUS 的優先級。
請注意，如果在規則中使用這里沒有定義的任何標記，則將引發一個錯誤。
自定義初始化和錯誤
您將要定義的兩個關鍵的函數是 main() 函數（可以將自定義的初始化和其他的處理放在這個函數中），以及 yyerror() 函數（當對于輸入信息無法找到一條分析規則時將打印出一個錯誤）。由 yacc 生成的進行實際分析工作的函數稱為 yyparse()。自定義函數的典型定義如清單 11 所示。
清單 11. 分析器的自定義函數
#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() 函數接受一個字符串，并且在引發錯誤的時候將其與程序名稱合并在一起作為輸出。
將語法編譯為 C 代碼
Yacc（最初是 yet another compiler compiler 的縮寫）和 GNU bison 工具都接受一個語法定義文件作為輸入，并生成創建分析器所需的 C 源代碼，而該分析器將對適當的輸入進行處理。
通常，語法定義文件的擴展名為 .y。
當您運行 yacc 時，缺省情況下它將創建一個名為 yy.tab.c 的文件。如果 yacc 和 lex 一同使用，那么您還需要生成一個 C Header 文件，該文件包含了這兩個系統中識別的標記的宏定義。除了 C 源代碼之外，如果還要生成 Header 文件，可以使用 -d 命令行選項：
$ yacc -d calcparser.y
盡管 bison 可以執行相同的基本操作，但缺省情況下，它所生成的文件使用源文件名稱的前綴作為其標識。所以，在上面的示例中，使用 bison 將生成 calcparser.tab.c 和 calcparser.tab.h 文件。
這個區別是很重要的，不僅因為您需要知道究竟要編譯那個文件，而且還因為您需要在 lex.l 定義中導入正確的 Header 文件，以便它能夠讀取正確的標記定義。
當編譯一個 lex/yacc 應用程序時，一般的過程如下：
對分析器定義運行 yacc。
對詞法定義運行 lex。
編譯生成的 yacc 源文件。
編譯生成的 lex 源文件。
編譯任何其他的模塊。
將 lex、yacc 和其他源鏈接為一個可執行文件。
我傾向于使用一個與清單 12 所示類似的 Makefile。
清單 12. 簡單的 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 進行數據交換
lex 和 yacc 之間數據交換的主要方法是當使用 yacc 創建 C 源代碼和生成包含每個標記的 C 宏代碼的 Header 文件時生成的標記定義。
然而，如果您需要交換的數據不僅僅是一個標記，那么您必須設置一個可以包含需要交換的信息的值。
這個處理過程分為兩個階段。首先，您應該根據具體需要定義 YYSTYPE。這是用于在這兩個系統之間進行數據交換的缺省值。對于一個基本的計算器，您可能需要將其定義為整數（實際上這正是缺省的情況）、浮點數或雙精度數。如果您需要交換文本，那么可以將它設置為一個字符指針或數組。如果需要同時交換這兩種信息，那么您應該創建一個可以包含這兩種值的聯合結構。
然后，您還應該在 yacc 和 lex 定義中聲明 yylval 變量（和其他任何需要共享的變量）為該類型。
例如，在這兩個文件的 Header 塊中，您需要指定這個類型（請參見清單 13）。
清單 13. 指定具體的類型
%{
...
#define YYSTYPE double
...
%}
在 lex 定義中，您還需要將 yylval 變量定義為這個類型的外部變量：
extern YYSTYPE yylval;
最后，在 yacc 文件的自定義 C 初始化塊中，您需要定義這個變量：
YYSTYPE yylval;
現在，您就可以在由這兩個系統生成的 C 源代碼中進行數據交換了。
構建一個計算器
您可以使用前面部分中演示的技術來構建一個常規表達式計算器。
計算器的基本概念
您可以構建一個能夠處理表達式的程序，如清單 14 所示。
清單 14. 能夠處理表達式的程序
4+5
(4+5)*6
2^3/6
sin(1)+cos(PI)
通過定義附加的標記和語法規則，您可以進一步擴展它的功能以包括各種函數和方程式，不僅僅是標準 C 語言和數學庫中的函數，您還可以自己進行特殊的定義。
為了能夠分析所有這些不同的元素，第一步需要定義可以由詞法分析組件識別的標記。清單 15 給出了完整的 lex 定義。
清單 15. 高級計算器的 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;
這里有大量的標記，其中許多都是自說明的。這些標記包括基本數學操作、大量的函數（sin、cos 等等）和邏輯運算符。另請注意，對于數值使用了雙精度類型，使用 sscanf() 將數字字符串和小數點解析為適當的雙精度值。
計算器語法
根據前面部分中介紹的標記，存在大量的語法規則用于分析這些標記。語法分析器的完整代碼如清單 16 所示。讓我們更仔細地看一下其中一些重要的部分以及該系統是如何工作的。
清單 16. 計算器語法文件
%{
#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 );
}
對于應用程序中其他的部分，有三個全局結構可供使用：
reg 數組用作通用存儲寄存器，可以在其中存放計算過程的值和結果。
ans 變量包含上次計算的值。
format 用于保存打印結果時所使用的輸出格式。
僅當輸入中包含行結束字符（以 EOLN 標記進行標識）時，才打印出計算結果。這樣就可以在單行中輸入很長的計算式，并且在對相應的內容進行了分析和處理后，再打印出結果值。這項操作使用全局 format 變量所指定的格式，并且將結果存儲在 ans 中。
分析器的主要部分是識別片段并計算結果的組合，直到最后將比較復雜的計算過程中不同的部分解析為最終的值。
設置輸出格式
格式就是用于 printf() 的一個合適的格式字符串，可以通過使用函數方式的調用來設置輸出的精度和格式。例如，要設置固定小數點的輸出以限制小數點右邊的數字，您可以使用 fix(3)，或者可以重新設置缺省格式： fix()。
在清單 17 的序列中，您可以看到相應的效果。
清單 17. 輸出格式
$ calc
1/3
0.333333
fix(3)
0.000
1/3
0.333
因為該格式字符串是全局的，并且僅由一條規則來打印出結果，這就意味著您可以很容易地使用該格式字符串來控制輸出。
計算器寄存器
寄存器實際上是一個浮點值數組，可以通過使用一個數值引用來訪問該數組。這部分代碼中的分析工作由清單 18 中所示的代碼片段完成。
清單 18. 計算器中的寄存器
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。這將限制所能夠對寄存器指定的值，如清單 19 中的序列所示。
清單 19. 限制能夠對寄存器指定的值
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
請注意，中間的表達式 (4+5)*sin(1) 返回正確的結果，但僅將該表達式開始部分的值賦給了寄存器。這是因為該規則僅允許使用匹配 postfix_assign 規則的表達式進行賦值，并且實際上由 primary 規則最終描述帶圓括號的語句的規則。因為不允許將整行輸入作為賦值的一部分，所以分析器匹配了第一個片段 ((4+5)) 并將這個值賦給了寄存器。因為對寄存器賦值時返回了寄存器的值，所以其他的計算過程可以繼續進行并打印出正確的結果。
有一個簡單的解決方案可以處理這個問題。作為一條簡單的輸入規則，您需要使用圓括號將對寄存器的賦值語句括起來：
reg[1]=((4+5)*sin(1))
這并不需要對相應的規則進行任何更改，因為在現有的分析器中可以使用上面的方法，但可能需要對文檔進行相應的更改。
當前的系統還有一個優點，那就是您可以同時對下一個寄存器賦值。這是因為對寄存器賦值時會返回該寄存器的結果。因此，下面的序列可以正常工作（請參見清單 20）。
清單 20. 寄存器的結果
reg[1]=(45+reg[2]=(3+4))
52
reg[1]
52
reg[2]
7
擴展 lex 和 yacc 的原則
這個計算器演示了一些基本處理，但是關于 lex 和 yacc 工具以及如何使用它們，還有很多的內容。
使用計算器分析器
因為分析輸入信息的規則和對信息的處理可以單獨地進行設置和控制，所以實際上可以獨立地改變信息提取和處理的方式。
當我第一次接觸 lex 和 yacc 時，我的初始目標是構建一個逆波蘭表示法 (RPN) 計算器。使用 RPN，您需要首先提供相應的數值，然后是運算符，例如，要將兩個數值相加在一起，您應該使用： 4 5 +。
對于有些人來說，這種序列更有意義，特別是當您希望編寫出與學校里學到的加法運算相同的計算過程時：
4
5 +
----
9
----
對于更加復雜的計算過程，您可以將數值載入到堆棧中，然后使用相應的參數，即自動地放回到堆棧中的計算結果。4+5*6 可以編寫為： 4 5 6 * +。
對于計算機來說，這種表示方式更加直截了當。您可以使用堆棧來實現 RPN 計算器。當分析器識別了一個數值，會將它壓入堆棧，并且當發現了一個運算符時，從堆棧中彈出相應的值，然后執行計算過程。它簡化了在執行常規表達式分析中所需的大量的處理和復雜的分析過程。
然而，再增加一點點工作，您就可以創建一個將常規表達式輸入轉換為 RPN 的分析器。甚至更加完善，您還可以將 RPN 轉換為標準的表達式格式。
例如，將表達式轉換為 RPN：
$ equtorpn
4+5*6
4 5 6 * +
其中有趣的是，分析規則中定義的優先級順序（其 yacc 分析器是這里所介紹的計算器的簡化版本）將產生滿足上述示例的 RPN。
您可以將 equtorpn 工具的輸出作為 RPN 計算器的輸入，并獲得相同的結果：
$ equtorpn|rpn
4+5*6
34
有關 rpn、equtorpn 和 rpntoequ 應用程序的完整示例和代碼及其工作方式的更詳細的討論，請訪問 MCslp Coalface Web 站點（請參見參考資料）。
使用計算器分析器
因為分析輸入信息的規則和對信息的處理可以單獨地進行設置和控制，所以實際上可以獨立地改變信息提取和處理的方式。
當我第一次接觸 lex 和 yacc 時，我的初始目標是構建一個逆波蘭表示法 (RPN) 計算器。使用 RPN，您需要首先提供相應的數值，然后是運算符，例如，要將兩個數值相加在一起，您應該使用： 4 5 +。
對于有些人來說，這種序列更有意義，特別是當您希望編寫出與學校里學到的加法運算相同的計算過程時：
4
5 +
----
9
----
對于更加復雜的計算過程，您可以將數值載入到堆棧中，然后使用相應的參數，即自動地放回到堆棧中的計算結果。4+5*6 可以編寫為： 4 5 6 * +。
對于計算機來說，這種表示方式更加直截了當。您可以使用堆棧來實現 RPN 計算器。當分析器識別了一個數值，會將它壓入堆棧，并且當發現了一個運算符時，從堆棧中彈出相應的值，然后執行計算過程。它簡化了在執行常規表達式分析中所需的大量的處理和復雜的分析過程。
然而，再增加一點點工作，您就可以創建一個將常規表達式輸入轉換為 RPN 的分析器。甚至更加完善，您還可以將 RPN 轉換為標準的表達式格式。
例如，將表達式轉換為 RPN：
$ equtorpn
4+5*6
4 5 6 * +
其中有趣的是，分析規則中定義的優先級順序（其 yacc 分析器是這里所介紹的計算器的簡化版本）將產生滿足上述示例的 RPN。
您可以將 equtorpn 工具的輸出作為 RPN 計算器的輸入，并獲得相同的結果：
$ equtorpn|rpn
4+5*6
34
有關 rpn、equtorpn 和 rpntoequ 應用程序的完整示例和代碼及其工作方式的更詳細的討論，請訪問 MCslp Coalface Web 站點（請參見參考資料）。
進行適當的文本分析
這些示例介紹了如何構建一個表達式分析器，而該分析器可以將數學表達式轉換為可以進行計算的表達式。該分析器說明了序列、分析規則和諸如優先級之類的問題的重要性。在文本處理系統中也可以應用相同的規則，但是處理文本可能更加復雜，除非您建立與計算器示例中同樣嚴格的強制規則。
清單 21 顯示了創建簡單的 set/get 狀態分析器的 lex 文件，而清單 22 顯示了分析其輸出的 yacc 規則。
清單 21. 使用 lex 進行基于文本的標記化
%{
#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 規則
%{
#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 );
}
在計算器示例中，必須將輸入文本轉換為一個數值，而這個示例與計算器示例有所不同，您可以直接使用輸入字符串，而無需進行轉換（請參見清單 23）。
清單 23. 直接使用輸入字符串
$ textparser
get state
State:
set state bob
State set
get state
State: bob
更加復雜的文本分析器也都構建于相同的基本原則，并且可用于完成各種任務，從配置文件分析器，到構建您自己的腳本語言，甚至是可進行編譯的語言。
語言編譯器
語言編譯器（例如 C 編譯器）可以接受您的輸入，并將輸入轉換為指定的目標平臺的原始匯編語言。這就解釋了為什么最初的編譯器都是特定于體系結構的，為什么編寫一個為可選的平臺生成代碼的編譯器（交叉編譯）相當容易。編譯器僅為可選的平臺生成匯編代碼。例如，要將兩個數值相加到一起，您可以對前面使用的規則集進行更改，以便生成如下所示的 Intel x86 匯編代碼：
add_expr: mul_expr
| add_expr PLUS mul_expr
{ printf("MOV ax,%dnADD ax,%dn",$1,$3); }
為了使匯編轉換處理過程能夠構建完整的語言，可以將其他的結構（如循環、遞歸、函數、變量名稱和其他的元素）添加到該系統中。
總結
通過 lex 和 yacc 的組合，您可以生成構建分析器的代碼。lex 工具提供了識別文本片段和元素的方法，并可以返回相應的標記。yacc 工具可以使用一系列描述輸入格式的規則來處理這些標記組成的結構，并且定義了處理識別的序列的方法。在這兩種情況下，這些工具都使用了一個配置文件，在生成構建合適的分析應用程序的 C 源代碼時將對該文件進行處理。
在本教程中，您看到了關于如何使用這些應用程序為計算器應用程序構建簡單的分析器的示例。通過這些處理，您了解了標記化、規則集的重要性，以及規則集如何互相作用以提供完整的分析解決方案。您了解了如何使用這些基本原則進行其他的處理，如文本分析器、甚至是構建您自己的編程語言。