5

我想用 C 构建一个词法分析器，我正在关注龙书，我可以理解状态转换，但如何实现它们？

有更好的书吗？

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

4

5 回答 5

7

您可以使用单个状态变量来实现简单的状态转换，例如，如果您想在状态 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
于 2009-06-15T11:08:51.080 回答
4

天，

假设您的意思是关于编译器设计的 The Dragon 书籍，我建议您查看有关编译器工具的此页面。

该页面本身很小，但具有指向词法分析器上各种优秀资源的链接。

高温高压

干杯，

于 2009-06-15T11:15:27.740 回答
4

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

// regular expression
digit* [.digit*]

相应的 C 代码将是：

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

在我看来，构建词法分析器的转换表方式过于复杂，而且运行速度明显较慢。

于 2009-06-15T11:28:58.440 回答
1

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

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

看目录

于 2009-06-15T11:27:21.267 回答
0

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

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

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

于 2009-06-15T11:58:32.020 回答