yacc 与 lex 入门案例教程

使用 yacc 和 lex 编写文本分析器

简介： 本文将研究使用 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 %} %%

begin printf(\

hello printf(\thanks printf(\end printf(\%%

代码中的第一块由 %{...%} 定义，表示将其中的文本插入到生成的 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 %} %%

[a-z] printf(\[A-Z] printf(\[a-ZA-Z] printf(\[0-9] printf(\[0-9.] printf(\

\

\\%%

清单 4 中的示例应该是一目了然的，并且对于需要进行分析的任何正则表达式或特殊字符都可以使用相同的原则。 真正的标记化

前面的示例所构建的 C 源代码实质上是独立的。尽管使用这种方法没有什么问题，但是对于分析包含多个单词、短语或序列的给定指令中的文本或其他条目的情况，这种方法并不是很有价值。

使用这种方式分析序列需要一个语法分析器，而它将定义标记序列。但是语法分析器必须知道要分析的是什么标记。在 lex 定义中，当识别标记时所进行的操作是回显字符串，如果要返回一个识别标记，那么需要对该操作进行更改。例如，您可以如清单 5 所示对原始示例进行重写。

清单 5. 返回标记 %{

#include #include %} %%

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(\}

NUMBER 是一个数值的识别标记，并且 PLUSTOKEN 是加号的识别标记。 大括号中的代码定义了识别这个序列后进行何种操作，在本示例中，给出的是将这两个数值相加的 C 代码。请注意，使用命名法 $1 表示该语法表达式中的第一项标记，$3 表示其中的第三项。

对于待识别的语法序列，您必须对序列进行命名，如清单 6 所示。

清单 6. 对序列命名

addexpr: NUMBER PLUSTOKEN NUMBER {

printf(\ } ;

语法组的名称为 addexpr，并且这个组定义以一个分号作为结束。

一个语法定义可以包含多个序列（以及相关的操作），而这些序列都是一个特殊的组中的一部分。例如在计算器中，加法和减法处理是类似的操作，所以可以将它们集中作为一组。一个组中不同的定义可以使用管道符号 (|) 进行分隔（请参见清单 7）。

清单 7. 一个组中不同的定义使用管道符号进行分隔

addexpr: NUMBER PLUSTOKEN NUMBER {

printf(\ }

| NUMBER MINUSTOKEN NUMBER {

printf(\ } ;

您已经了解了基本的语法规范，那么还需要了解如何组合多个序列以及它们的优先级。

语法序列和优先级

在大多数语言中，无论是文本型、数学运算型，还是编程型的语言，通常对于不同的短语都有某种优先级或重要性，这将使得它们与类似的但不同的组合相比具有相应的优先权。

例如，在大多数编程语言的数学运算表达式中，乘法具有比加法或减法更高的优先级。例如，表达式：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() 函数（当对于输入信息无法找到一条

本文来源：https://www.bwwdw.com/article/z62f.html