rust - 表驱动词法分析需要多少缓冲？

Question

我正在用 Rust 编写一个 POSIX shell 实现。这带来了一些相当尴尬的要求:

• 必须逐行读取输入。如果输入来自不可搜索的源，则意味着必须一次读取一个字节的输入。
• 反斜线-换行，当不加引号时，是行的延续。它_不是_标记分隔符，理想情况下应该在词法分析之前处理好。

如果词法分析器一次读取一个字符并允许规则设置可以通过词法分析器的字符源查询的内部状态(Rust 不允许填充状态的 C 解决方案)，那么这两个要求都可以轻松处理在全局变量中)。我目前的词法分析器就是这样做的。然而，它是 398 行高度重复的代码，包括一些(不充分的)测试。此代码请求自动生成。

自动生成的词法分析器通常使用基于有限自动机的表驱动设计。我对此不是很熟悉，并且想知道先行是这种设计中固有的还是通常不使用。如果通常不使用前瞻，那么我可能可以修改现有的词法分析器生成器来做我想做的事；否则，我可能会坚持使用手写代码。

Answer 1

这可能是一个过于宽泛的问题或生成包含过多意见的答案，这不是 good attribute of an SO question .它非常像是一个问题的合成词，询问现有词法分析器生成器算法的实现、有限自动机的编程、shell 语言的词法要求和 Rust 程序的特征，可能还有其他一些主题。

首先，让我们来处理有关工具生成的词法分析器功能的问题。让我们考虑最常用的一种，flex GNU 词法分析器生成器。答案是是的；它可以为您构建一个可以执行您想要的操作的词法分析器。它足够灵活并且包含足够多的不同功能来完成这些工作(就像其他类似工具一样)。它会简单明了吗？不必要。该工具使您能够使用内置的读取和有限状态自动机，但您可以提供自己的输入例程、编写自己的状态机，甚至可以处理自写代码片段中的难点(C 或 C++)。在手册、教程网站、教程视频、教科书和 questions here on SO 中有大量关于如何实现此目的的示例。 .

当 flex 使用 C 或 C++ 生成代码时，这对您使用 Rust 编码有何帮助？我们需要一个基于 Rust 的词法分析器。一旦可以进行文献搜索并查看可用的内容。维基百科非常适合列表，并且有一个 list of available parser and lexer generator tools .但是，这些都不会生成 Rust。然而，Rust 中有这样的工具:

• RustLex: lexical analysers generator for Rust
• RACC - Rust Another Compiler-Compiler

由于这两项都是正在进行的实验性工作，您需要自己对其进行评估。

另一种选择是制作您自己的开源工具版本(如 flex)以与 Rust 一起使用。这可以通过两种方式完成:

1. 您可以对 flex 的输出进行后处理，将 C 代码转换为 Rust 代码，然后进行编译。
2. 您可以修改该工具的代码以生成 Rust 而不是 C。 (它不需要用 Rust 本身编写来实现你想要的。)

这些方法已经实现了好几次，以支持其他新语言的目标。结果，有 a whole raft of compiler generator tools for a myriad of languages .

下一个问题是您手写的词法分析器代码的大小和性质。 There are standardised and recognised ways of programming finite state automata in any language. Experienced programmers would should know the pattern :

while ( NOT <<EOF>> ) {
  switch ( next_symbol() ) {

     case state_symbol[1]: 
              ....
             break;

      case state_symbol[2]:
              ....
              break;

       default:
             error(diagnostic);
  }
}

甚至可以在功能上完成:

action[state_symbol[next_symbol()]];

可以手写一个相当紧凑和高效的常规语言解析 FSA 来进行词法分析，但这取决于语言和算法方面的经验。

你宽泛而不精确的问题导致了宽泛而不精确的答案:是的，一切皆有可能，不它不依赖于缓冲和回溯。