lex 和 yacc：值得了解的工具
本文讲述了如何使用 Linux 编程 Sun 机器来处理测井记录，以支持在加拿大西部寻找石油和天然气勘探。它将描述问题，提供足够的背景知识以使问题易于理解，然后描述如何使用两个引人入胜的 UNIX 实用程序 lex 和 yacc 让用户准确描述他想要满足其特定需求的内容。
在 1993 年秋季，我最近被裁员，一位前同事联系我寻求帮助。他和另一位前同事（他们都还在我的上一家雇主那里工作）都是业内所谓的测井分析师。
要理解什么是测井分析师，需要对石油和天然气勘探方法有一些了解。能源公司（他们喜欢被称为能源公司）雇佣了几类不同的专业人员来协助他们寻找可销售数量的碳氢化合物。其中最主要的是地质学家和地球物理学家（我是其中之一），他们研究钻孔中制作的记录，或处理和检查地震记录，以识别俗称的“圈闭”或“异常”。
钻孔只是钻机离开钻井平台后留下的孔。通常，这些孔由服务公司进行测井，这些公司将称为 工具 的仪器放入孔中，然后在磁带上记录这些仪器进行的读数。
工具有很多不同的类型，包括声波（测量声能脉冲从工具一端穿过岩壁到达另一端所需的时间）、密度（连续记录岩壁密度）和伽马射线（测量岩石中的伽马辐射强度）。这些只是测量、记录和称为 测井 的众多类型中的一部分。
地质学家检查各种测井，以了解在形成钻孔的岩石沉积时发生了什么，以及随后当较浅的岩石在其上方形成时发生了什么。
地球物理学家更倾向于研究地震记录，地震记录本质上是对形成地下的岩石特性的间接测量。地球物理学和 Linux 将不在此处讨论，但您可能会对 Sid Hellman 的“高效、用户友好的地震学”感兴趣，Linux Journal，1995 年 8 月，第 16 期。
虽然地震记录提供了更大范围的可解释数据，但测井是在单个位置进行的确定性测量，有时彼此靠近，有时则不靠近。地质学家经常关联相邻的测井，以创建地下的横截面，很像地震记录所提供的。然而，单个测井的详细解释通常留给测井专家。
我的两位熟人是测井专家，他们想要一个额外的工具来帮助他们处理和解释单个或组合的测井。具体来说，他们希望告诉计算机对单个测井或某些测井的代数组合执行算术运算。
例如，他们可能需要将特定的测井按任意量缩放，例如 1.73。在另一种情况下，他们可能想要将一个测井除以另一个测井，然后将结果添加到第三个测井，所有这些都在添加常数之前，然后将结果值提高到某个任意幂。
请记住，测井由每隔几英寸（或厘米，因为它们在加拿大和世界许多其他地方）采集的单个样本值组成，这些示例请求意味着相当数量的计算，在第一个示例中，将数千米记录测井值的每个样本乘以 1.73。简单的缩放问题并不特别困难，但识别所需的测井可能会很困难。
我的熟人工作的能源公司对所有测井曲线（一条曲线对应于一个钻孔中一个工具的所有记录样本）使用简单的文件方法，其中每条曲线都用一个名称标识。在此基础上，添加了一些关于单位等的附加信息，以及井的所有曲线的所有样本。所有数据都存储为 ASCII。（文件格式称为测井 ASCII 标准格式，或 LAS 版本 2.0，虽然曲线的名称通常在井与井之间相同，但这并不能保证。）
因此，更复杂的曲线组合需要一种相当复杂和健壮的机制来进行任意名称识别，同时描述所需的代数运算。鉴于这样一个有趣的挑战，我认识到有机会将一些相对不常用的工具投入使用：lex 和 yacc。
程序 lex 是一个词法分析器。词法分析是识别语言中的单词。在这一特定应用中，lex，更具体地说是 flex，用于识别形成测井曲线名称、算术运算符和代数组合的字符。
flex 是 UNIX 系统可用的词法分析程序的一个特定示例，是 Linux 发行版附带的实现。最初的实现由 Mike Lesk 和 Eric Schmidt 在贝尔实验室完成，并在 John R. Levine、Tony Mason 和 Doug Brown 于 1992 年由 O'Reilly & Associates, Inc. 出版的 lex & yacc 一书中进行了记录。
yacc 是一个语言解析器。它接受单词项，并给定一个描述这些项如何形成更大实体的规则列表，推断哪些项或项的组合满足规则。这也可以被认为是语法分析。一旦规则得到满足，程序员的代码就会应用于结果。
在英语中，句子中的单词可以被赋予语法类型，例如名词、动词、形容词等等。单词的特定组合形成更复杂的单元，而这些单元又可以被描述为完整的句子。
例如，句子“The lazy dog lay in the sun，”由冠词 “the”、介词 “in”、形容词 “lazy”、名词 “dog, sun” 和动词 “lay” 组成。这些语法项的组合形成更复杂的实体，例如名词短语 “The lazy dog” 和 “in the sun”。第一个名词短语是句子的主语，第二个名词短语与动词结合，构成谓语。它们共同构成一个完整的句子。
有可能为英语形成解析器，尽管考虑到英语的许多特殊性，yacc 可能被证明不足以完成此任务。也可能是 yacc 程序员在尝试描述该语言的所有细微之处时会感到筋疲力尽。
yacc 最初是为了提供一种开发编译器的机制而开发的，但它也可以很容易地用于创建解释器。例如，BASIC 通常是一种解释型语言，并且可以很容易地用 yacc 语法来描述。一旦 yacc 理解 了 BASIC 代码的特定行，它就可以导致执行主机计算机的本机语言中的等效指令。
一些 Linux 发行版提供了 yacc 程序的选择。可以安装 Berkeley yacc 或 GNU bison 程序（或两者都安装）。您可能会在 /usr/bin 中找到它们。它们非常相似；bison 最初是从 yacc 派生出来的，尽管多年来存在一些差异。
lex、yacc 和一些程序员的 C 代码的组合提供了一种完整的方法来解释和执行用户的意愿。lex 程序使用其正则表达式解释功能将字符字符串识别为单词或标记。（术语“单词”被宽泛地用于描述任何已识别的字符字符串。）一旦识别出标记，它就会传递给 yacc，在 yacc 中，各种规则被应用，直到标记的某些组合形成可识别的结构，yacc 将一些预编程的 C 代码应用于该结构。
如前所述，lex 使用正则表达式将字符字符串识别为感兴趣的项目。正则表达式由描述可接受的字符组合的特殊字符组成。
例如，正则表达式通常使用字符 .（句点）来指示 任何 字符都是可接受的，除了换行符 (\n)。
类似地，字符 [ 和 ]（方括号）用于指示接受括在它们之间或在它们之间描述的字符范围内的任何字符。例如，表达式 [abc] 表示接受字符 a、b 或 c 中的 任何 一个；表达式 [a-c] 表示相同的事情。一个更复杂的例子可能是 [a-zA-Z0-9]，它表示接受任何字母数字字符。
有关 lex 正则表达式语法的完整描述，请参阅 Levine、Mason 和 Brown 的 lex & yacc（O'Reilly，1992 年）。
一旦正则表达式与 lex 正在解释的文本流匹配，程序员创建的代码就会被执行。当与 yacc 一起使用时，此代码通常相当于向 yacc 传递刚刚识别的内容的指示以进行进一步处理。该指示是 yacc 知道的标记，实际上，这些标记是在分析器/解析器程序的 yacc 部分中定义的，以便它们对 lex 和 yacc 都是通用的。
同样如前所述，yacc 使用语法描述来解码 lex 传递给它的标记的含义。当标记传递给 yacc 时，它会应用其规则，直到单个标记或某些标记序列成为可识别的结构。
但是，在程序员的 C 代码执行之前，yacc 可能需要识别几个结构或标记-结构组合。例如，使用我们的示例句子，我们的规则可能如下所示
sentence : subject + predicate
{...execute some C code...}
subject : noun
| noun_phrase
predicate : verb + noun_phrase
noun_phrase : preposition + adjective + noun
| adjective + noun
第一个规则说明句子由两个部分组成：主语后跟谓语。如果满足该规则，则将执行花括号之间的 C 代码。为了满足第一个规则，yacc 必须识别主语和谓语。后续规则帮助 yacc 完成这项工作。
例如，第二个规则说明当识别到名词或名词短语时，主语被识别。名词是 yacc 处理的最小单位，在 yacc 语法中，名词是 yacc 希望 lex 识别的标记。因此，在 yacc 程序的某个地方，将定义一个标记（可能称为 NOUN），lex 和 yacc 将使用该标记来传达名词已被解释的事实。我们将很快看到这是如何完成的。
请注意，名词短语也用于创建谓语。如果识别到动词，并且后面跟有名词短语，则谓语被识别。如果仅识别出名词短语，则主语已被识别。
引用的示例不是 yacc 语法，而是旨在提供理解。可以在参考文献中找到非常详细的示例。
您可能想知道 yacc 解析器实际上是如何工作的。yacc 作为有限状态机工作，并且它有一个堆栈（可以将其视为已看到内容的内存，因为它试图推断传入的标记流代表什么）。
有限状态机在解释每个可识别的项目时记录其当前状态。例如，当解释名词短语时，它从接收到介词时的状态 3 移动到形容词被解释时的状态 4，最后移动到名词被识别时的状态 5。当整个短语都被识别出来时，它会切换到另一个状态，可能是 37，以记录这一事实。请不要对本示例中使用的数字附加任何特定含义。选择它们是任意的，以演示 yacc 如何在解释从 lex 接收的标记时进行。您应该得出的结论是，要达到状态 5（名词短语），yacc 必须经过几个先前的状态，每个状态都可能导致另一个最终状态，这取决于 yacc 正在使用的语法。
换句话说，给定其当前状态，yacc 从 lex 请求下一个标记（如果需要），并将新状态放到堆栈上。在这样做时，它可能会将新状态压入堆栈（如在解释名词短语时），或将旧状态弹出堆栈，并用新状态替换它（如在名词短语完全被识别时）。这些操作称为“移位”和“归约”，描述了将状态压入和弹出堆栈。
当句子最终被识别出来时，yacc 接受它并返回到调用程序（调用 yacc 和间接 lex 的主程序）。有关 yacc 解析器如何工作的完整描述，请参阅 Christopher Morgan 的 Inside Xenix，Howard W. Sams and Co.，1986 年。此参考文献非常详细地描述了 yacc 语法以及 yacc 如何解析其输入。
这两个工具都以类似的方式编码。每个程序都有三个部分：声明、规则和用户例程。每个部分都由仅包含两个字符 %% 的行分隔。
对于 yacc，声明部分包含它可以在解析输入时使用的标记。每个标记都有一个大于 256 的唯一值，并且标记集通过行首的 %token 引入。lex 可以使用声明部分来定义它在查找要传递给 yacc 的标记时必须识别的项目的别名。
例如，lex 需要知道空白字符，虽然空白字符不用于识别标记，但必须以某种方式进行处理。类似地，必须识别数学符号，例如 + 或 =。这些在解释用户编码的代数语句时是必需的。
在规则部分中，yacc 保留其解析智能。这是包含前面英语句子示例中引用的语法规则的部分。事实上，前面使用的编码是 yacc 语法的典型编码：要识别的项目与识别它们的方式之间用冒号 (:) 分隔，并且替代识别方式之间用竖线 (|) 符号分隔。
lex 使用规则部分来包含正则表达式，这些正则表达式允许它识别要传递给 yacc 的标记。这些表达式可以是来自声明部分的别名、正则表达式或某些组合。
最后一部分包含 C 代码，这些代码可以在每个工具处理其输入时调用。
一个要求是 lex 程序必须知道 yacc 标记。这通过包含以下语句来实现
#include "y.tab.h"
在 lex 声明部分，并在编译 yacc 程序代码时创建它。
编译按以下方式完成
yacc -d yacc.file -create 'y.tab.c and y.tab.h' flex flex.file -create 'lex.yy.c'
yacc 命令行上的 -d 选项创建 lex.yy.c 所需的 y.tab.h 文件。
为了成功解释用户期望的过程，程序需要知道哪些测井可用于处理。此信息可在用户选择的 ASCII 文件中找到。此文本文件包含曲线描述和数据值之间的一一对应关系。列表 1 显示了典型文件的一个非常小的子集。
可以看出，有几个部分，包括井信息（包括一些孔参数）、曲线信息（记录文件中包含哪些曲线）和 “A”（包含记录的数据值）。每个部分都以波浪号 (~) 开头。由于文件的格式是约定俗成的，因此这些部分很容易解析，并且所需的值被存储以供后续处理。
为客户编写的程序是一个 Motif 应用程序。用户选择要处理的文件；它被完整读取，数字文本项被转换为双精度值。
除了允许文件和曲线合并和编辑之外，还有一个用于曲线处理的菜单项。选择此菜单项后，将弹出一个对话框，其中包含可用曲线和算术运算的列表。用户选择曲线名称、数字常量和运算，这些名称、常量和运算依次显示为文本输入行上的代数运算。当用户对数学运算感到满意时，单击确定，lex 和 yacc 的魔力就会发生。结果存储为单独的曲线，可以包含在后续运算中。
lex 使用列表 2 中显示的代码处理传入的代数语句。
第 1 行到第 16 行之间是要在 lex 生成的程序中使用的声明。特别是，您会注意到包含头文件 y.tab.h，其中包含以下定义
#define INTEGER 257 #define FLOAT 258 #define DOUBLE 259 #define NUMBER 260 #define VARIABLE 261 #define EQUAL 262 #define LPAREN 263 #define RPAREN 264 #define PLUS 265 #define MINUS 266 #define TIMES 267 #define DIVIDE 268 #define RAISE 269 #define LHS 270
这些定义供 lex 和 yacc 使用，以描述 yacc 期望从 lex 接收的项目。它们由 yacc 源代码的第 73 行到第 77 行的语句生成，我们将在稍后进行检查。
从 lex 列表的第 17 行到第 31 行是声明，这些声明相当于我们希望 lex 识别的常见项目的别名。例如，我们在第 21 行将 DIGIT 声明为 0 到 9 之间的任何单个数字。这样做允许我们将 INT（整数）声明为一个或多个 DIGIT。
第 33 行到第 90 行包含 lex 解释传入文本项的规则。例如，在第 34 行，我们识别等号 (=) 并将标记 EQUAL 返回给调用者。在 y.tab.h 中，EQUAL 被定义为 262。
如您所见，lex 规则只是识别文本项，然后告知调用者在输入流中看到了什么。
yacc 使用以下代码解释 lex 传递给它的标记流，列表 3 中仅显示了其中的一部分。yacc 例程的代码（带有调用子例程 do_arithmetic 及其辅助函数）超过 900 行。对于那些感兴趣的人，可以从 SSC 的公共 FTP 站点获取以供查阅。列表 3 是一个示例，指示需要完成的工作。
与 lex 例程一样，yacc 以要包含在输出代码中的行开始。为图形用户界面编写的程序在一个循环中等待用户单击某些内容。当指示用户的需求时，基于 GUI 的程序会调用一个函数来执行所需的操作。这些“被调用函数”通常被称为 回调。在此程序中，回调之一是 do_arithmetic，它又调用了 yacc 例程，而 yacc 例程又调用了 lex 例程。
在列表 3 中，do_arithmetic 在前几行中描述，代码的一部分可以在第 428 行到第 532 行中看到。显示它们只是为了给出一些关于正在完成的工作的指示。
yacc 使用其从第 79 行开始到第 426 行结束的规则部分来完成工作。虽然太长而无法完全包含，但您可以看到 equation 被定义为第 80 行的称为 lhs（左侧）EQUAL rhs（右侧）的东西。向下查看列表，您将看到方程也可以用 expr（表达式）来描述。当遇到其中任何一个时，yacc 会从由名为 push 的函数创建的内部堆栈中弹出一个键（参见第 557 行附近），然后通过调用另一个名为 get_curve 的函数（此处未显示，但包含在 yacc 和 lex 代码中）使测井曲线返回给调用者。
在第 118 行和第 139 行之间，您可以看到当识别出 yacc 期望的某些标记时，如何处理这些标记。完整列表还有更多。
lex、yacc 和支持代码已成功用于允许测井分析师处理各种测井曲线。编写 C 代码来实现词法分析和解析逻辑将比允许的四个星期花费更长的时间。事实证明，这段代码比将其引入最终的 Motif 应用程序更容易创建和调试，即使它是作为回调编写的。
事实上，lex（152 行）和 yacc（953 行）代码的行数远少于两者生成的行数（2765 行）。当然，人们可以花时间编写比这些通用工具提供的更紧凑的代码。
尽管如此，如果您遇到类似的问题，我强烈建议使用 lex 和 yacc。它们是功能强大、可靠且值得了解的工具。
本文中引用的所有列表都可以通过匿名下载文件 ftp://ftp.linuxjournal.com/pub/lj/listings/issue51/2227.tgz 获取。
