yacc - what is the difference between lex and yacc

Question

I have worked with lex for executing some code whenever some regular expression is found, Can Yacc do something more than that? If yes, then what?

Answer 1

是的，YACC 是一个解析器，Lex 是一个词法分析器。它们通常一起使用：Lex 是字符串输入，YACC 是 Lex 提供的标记化输入。

现在，正则表达式只能表示正则语言。常规语言的限制之一是缺乏“记忆”。您不能根据之前的情况进一步定义接受规则。

这在括号的情况下最为明显。常规语言无法将嵌套括号匹配到正确的级别。或任何其他此类结构。（大多数）计算机语言的语法可以并且可以，因此，它们不能用 Lexer 或正则表达式解析。这就是 YACC 的用武之地。

也可以扭转这个问题。如果 YACC 可以做得更多，为什么不用它来做词法分析呢？好吧，碰巧您可以非常有效地验证正则表达式的有效性，这不是一般语法的情况 - 不是同一级别。尽管如此，如果语言的词法规则足够简单，YACC 还是可以进行基本的词法分析。

Answer 2

lex 是一个词法分析器。它将文本拆分为标记。它的威力大致相当于正则表达式匹配。yacc 是一个解析器生成器。它采用一系列标记（例如，来自 lex）并将它们解释为一系列语句。它的威力大致相当于上下文无关文法。

lex 和 yacc 的一个典型应用是用于实现编程语言。lex 对输入进行标记，将其分解为关键字、常量、标点符号等。yacc 然后实现实际的计算机语言；例如，识别 for 语句或函数定义。

在实际意义上，您经常使用 lex 将输入文本处理成块。然后使用 yacc 将这些块串在一起，并将它们处理成更大的含义。

Answer 3

lex 用于标记输入。也就是说，将您的输入分离到您的语法定义的最低级别的对象中。例如，您使用 lex 来识别关键字、标识符、字符串、注释、空格等。

yacc 用于解析您的语法。语法是对您的语言的描述，通常在 EBNF 或其他一些与上下文无关的语法中定义。一旦您向 yacc 描述了您的语法，您就可以在识别出语言的元素时使用它来运行您的工具的操作。例如，这可能是构建用于表达式求解的语法树、定义范围对象、记录变量定义等。

它们是免费产品。

Answer 4

lex 和 yacc 通常一起使用。这就是您通常使用以下两种方式构建应用程序的方式：

输入流（字符）-> Lex（令牌）-> Yacc（抽象语法树）-> 您的应用程序

更一般地说，Lex 将做的是从头开始读取源文件，并尝试匹配多个正则表达式（lex 有自己的特殊语法，这与 perl 或 sed 正则表达式有点不同），然后将使用它识别的每个令牌调用另一个程序。标记可能只是一个普通的枚举值，例如关键字或运算符，也可能附加一些元数据，例如文字值。

Lex 通常（尽管不是必须）用于调用 Yacc。Yacc 使用 LALR 解析器算法，粗略地说，它通过将每个令牌推入堆栈来工作。如果堆栈具有它识别的一系列令牌，它将弹出所有令牌，执行一个操作，并将另一个令牌推回堆栈。

Yacc 工作的正确词汇实际上是终端和非终端。终端是它从调用程序（通常是 Lex）获得的令牌，而非终端是匹配其堆栈上的序列的结果。

通常，每个 Yacc 规则所采取的操作要么是评估与该规则对应的计算结果，要么是生成一个中间表示，如语法树，以供另一个应用程序层处理。

Yacc 和 lex 一样，可以单独使用。例如，您可以通过将源文本中的单个字符传递给 Yacc 来使用 Yacc，并使用 Yacc 规则来识别每种标记。然而，Yacc 的设计并不是很容易以这种方式使用，因此生成的词法分析器将比 Lex 中的等效词法分析器复杂得多。出于性能或您需要更智能的词法分析器的原因，更典型的用途是制作手动编码的词法分析器。第二种情况的一个常见示例是在类 C 语言中使用，它们必须了解标识符的先前用途才能知道它们是否用于描述类型或变量。

Answer 5

Lex 是一个构建词法分析器的工具，它可以做一些相当愚蠢的词法工作（比如查找关键字）。Yacc 是一个解析器生成器，可以为真正的计算机语言创建解析器。它的分析通常基于 lex 的输出（它是一个标记流），并由此可以创建您的编程语言的解析树——这比 lex 所做的更多。

传统上，编译器构建器区分词法分析和句法分析——这是编译器中的两个重要步骤（进一步的步骤，例如代码创建、优化）。