3

（以下问题与 OCaml 语言有关，并在 OCaml 中有示例，但这个问题非常笼统，可能任何其他计算机语言的正确答案也可以解决我的问题。所以，只要用你最喜欢的语言假设这个问题。）

我想编写一个函数，它将 OCaml 中的任意程序作为字符串并确定程序是正确还是不正确，在后一种情况下，我是否可以通过在末尾连接适当的字符来使其成为正确的.

我假设某处有该语言的编译器，并且我可以应用它并得到回复说“编译”或“不编译 - 第 X 行错误，字符 Y”（大多数情况下无论如何语言）。总之，我想要一个函数，它接受一个程序并返回：

  • 正确——如果字符串包含正确的程序；
  • 错误——如果字符串包含不正确的程序，无论你如何将字符连接到它，都永远不会正确；
  • 不完整——如果字符串包含一个不错误的不正确的程序。

例如，OCaml 程序let x = f是不正确的，因为f它在使用时尚未定义。而且它不能继续，因为你在 f 之后写的任何东西都将永远是一些以前没有定义过的标识符。程序let x =也不正确；但是如果我们扩展到let x = 5then 我们有一个完全有效的程序。所以，我的函数应该在第一种情况下返回错误，在第二种情况下返回不完整。

如果我们有这个程序，事情可能会变得棘手

let ans = 5
let x = a

因为我的功能必须看到，如果我继续程序，ns那么程序就会变得正确。

我的问题是：您认为可以编写这样的函数/算法吗？如果是这样，一般的想法是什么？如果不是，试着说服我它不是。

（我会对任何见解或部分答案感到满意，例如暗示不完整的东西。例如，我相信如果语言编译器说第 3 行有错误并且程序有 100 行，那么就不可能继续的程序。）

4

1 回答 1

6

在您的第一个示例中let x = f，如果我添加un y -> y怎么办？

我认为您想要的是可能的，但是使用当前的工具则不行。如果你只对语法正确性感兴趣，基本的想法是运行解析器/词法分析器，如果它引发错误则返回“错误”，如果它没有返回完整的 AST 但没有错误则返回“不完整”（所以它仍在等待更多输入）。

注意：仍然存在一个小的不匹配，因为词法分析器将在 EOF 之前返回一个标记，这可能会继续。您无需将该令牌视为完整令牌并在此时进行一些更精细的推理。更一般地说，您输入的极值将需要专门的推理，我在这里没有介绍。

使词法分析/解析阶段变得容易的属性是词法分析器是由解析器需求驱动的——它只在解析器推理令牌流所需的范围内读取——并且解析器是“严格的” ，或提前失败，而不是在失败站点询问更多信息。

程序正确性的后一个主要阶段是标识符解析（这个变量名称指的是什么？）和类型系统——还有其他标准，例如检查构造函数和类型名称的数量，但它们不是很有趣的文字。你的问题。这些通常不是以需求驱动的风格编写的，或者更一般地不会尝试对部分信息进行推理。应该可以以这种方式重新设计它们，但这可能需要付出很多努力。

一个好的方向是“增量解析器”。很多人已经认识到与编辑器相关的程序工具需要增量（程序是增量编写的）。他们解决了在源代码发生具体更改后更新抽象信息的更普遍的问题；不仅是“最后添加”的更改，而且是更一般的更改。他们的工具可能也可以解决您的问题。

编辑：啊，我终于找到了我想要的东西。您应该看看 Oleg 的差异化解析器。

于 2011-03-16T06:11:23.737 回答