yacc - lex 和 yacc 有什么区别

Question

每当找到一些正则表达式时，我都会使用 lex 来执行一些代码，
Yacc 还能做更多的事情吗？如果是，那是什么？

Answer 1

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

Input Stream (characters) -> Lex (tokens) -> Yacc (Abstract Syntax Tree) -> Your Applcation

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

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

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

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

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