用 C 语言构建词法分析器

Question

我想用 C 语言构建一个词法分析器，并且我正在关注 dragon book，我可以理解状态过渡，但如何实施？

有更好的书吗？

事实上，我必须通过多个状态来解析字符串，以便我可以判断该字符串是否可接受！

Answer 1

如果您正在寻找比龙书更现代的治疗方法：Andrew W. Appel 和 Maia Ginsburg，《现代》C 语言编译器实现，剑桥大学出版社，2008 年。

第 2 章重点介绍词法分析：词法标记、正则表达式、有限自动机； 非确定性有限自动机； 词法分析器生成器

查看目录

Answer 2

程序 flex（lex 的克隆）将为您创建一个词法分析器。

给定一个带有词法分析器规则的输入文件，它将生成一个 C 文件，其中包含这些规则的词法分析器的实现。

因此，您可以检查 flex 的输出，了解如何用 C 编写词法分析器。也就是说，如果您不仅仅想使用 flex 的词法分析器...

Answer 3

您可以使用单个状态变量实现简单的状态转换，例如，如果您想循环状态 start->part1->part2->end 那么您可以使用枚举来跟踪当前状态并使用您想要在每个状态下运行的代码的 switch 语句。

enum state { start=1, part1, part2, end} mystate;

// ...
mystate = start;
do {
  switch (mystate) {
    case start:
      // ...
    case part1:
      // ...
    case part2:
      // ...
      if (part2_end_condition) mystate = end; // state++ will also work
      // Note you could also set the state back to part1 on some condition here
      // which creates a loop
      break;
  }
} while (mystate != end);

对于依赖于多个变量的更复杂的状态转换，您应该使用如下表/数组：

var1    var2    var_end    next_state
0       0       0          state1
0       1       0          state2
1       0       0          state3
1       1       0          state4
-1      -1      1          state_end // -1 represents "doesn't matter" here

Answer 4

天啊，

假设您指的是有关编译器设计的《The Dragon》一书，我建议您浏览一下此页面 关于编译工具。

该页面本身很小，但提供了有关词法分析器的各种优秀资源的链接。

HTH

欢呼，

Answer 5

有不止一种方法可以做到这一点。 每个正则表达式都直接对应于一个简单的结构化程序。 例如，数字的表达式可能是这样的：

// regular expression
digit* [.digit*]

相应的 C 代码将是：

// corresponding code
while(DIGIT(*pc)) pc++;
if (*pc=='.'){
    pc++;
    while(DIGIT(*pc)) pc++;
}

在我看来，构建词法分析器的转换表方式不必要地复杂，并且显然运行速度较慢。