使用 yacc 和 lex 编写文本分析器
时间：2010-10-17 来源：osdba
使用 yacc 和 lex 编写文本分析器
关键字： 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 源代码时将对该文件进行处理。
在本教程中，您看到了关于如何使用这些应用程序为计算器应用程序构建简单的分析器的示例。通过这些处理，您了解了标记化、规则集的重要性，以及规则集如何互相作用以提供完整的分析解决方案。您了解了如何使用这些基本原则进行其他的处理，如文本分析器、甚至是构建您自己的编程语言。
相关阅读 更多 +
