伪代码解释器？

Question

像很多 Stack Overflow 上的用户一样，我经常使用多种语言编写代码。当涉及到计划事项（甚至回答一些 SO 的问题）时，我实际上会用一种未指定的混合语言进行思考和编写。虽然我曾经被教导使用流程图或类似 UML 的图表来做到这一点，但回顾起来，我发现“我的”伪代码语言具有 C、Python、Java、bash、Matlab、perl、Basic 等组成部分。我似乎下意识地选择最适合表达概念/算法的习惯用语。

常见的习惯用语可能包括 Java 风格的大括号用于作用域，Python 风格的列表理解或缩进，C++ 风格的继承，C# 风格的 lambda 表达式，matlab 风格的切片和矩阵操作。

我注意到人们实际上很容易认出我试图做什么，并且很容易智能地将其翻译成其他语言。当然，这一步需要考虑边角情况以及每种语言行为特异的时刻。

但实际上，大多数这些语言共享关键字和库函数的子集，这些关键字和库函数通常表现相同 - 数学函数、类型名称、while/for/if 等。显然，我必须排除许多“奇怪”的语言，如 lisp、APL 派生语言，但是...

所以我的问题是：

1. 是否已经存在可以识别文本文件的编程语言的代码？（这肯定比 Eclipse 的语法树或 Google 翻译的语言猜测功能更简单，对吗？）实际上，Stack Overflow 的语法高亮器有做类似的事情吗？

2. 是否理论上可能创建一个单一的解释器或编译器，它在任何时刻都能识别你使用的语言习惯，并（也许“智能地”）执行或转换为可运行形式。并标记我语法模糊的行为的边角情况。我看到的即时困难包括：知道何时在缩进依赖和大括号依赖模式之间切换，识别有趣的运算符（例如 *pointer vs *kwargs），以及知道何时使用列表 vs 类似数组的表示。

3. 是否存在任何语言或解释器，可以管理这种灵活的解释？

4. 我是否错过了这种可能性的明显障碍？

编辑

感谢您的回答和想法。我计划编写一种基于约束的启发式翻译器，可以“解决”预期意义的代码并将其翻译成实际的Python代码。它将注意许多常见语言的关键字，并使用句法线索来消除人类意图的歧义 - 如间距、括号、可选的辅助词（如let或then）、变量先前使用的上下文等，以及对常见约定的了解（如大写名称、i表示迭代、以及一些简单的有限理解变量/方法命名，例如包含单词get、asynchronous、count、last、previous、my等）。在真正的伪代码中，变量命名与操作本身一样具有信息性！

使用这些线索，它将对每个操作的实现进行假设（例如基于0/1的索引，何时应捕获或忽略异常，哪些变量应为const/global/local，从何处开始和结束执行，以及哪些位应在单独的线程中，注意数值单位匹配/需要转换）。每个假设都有一个确定度 - 程序将在每个语句上列出假设，因为它将您编写的内容转换为可执行内容！

对于每个假设，如果您不喜欢初始解释，可以“澄清”您的代码。库问题非常有趣。我的翻译器，就像一些IDE一样，将从所有模块中读取所有定义，使用一些关于哪些类/方法在什么上下文中最常用的统计数据，然后猜测！（添加一个注释到程序中，说明为什么它这样猜测...）我想它应该尝试执行所有内容，并警告您它不喜欢的内容。它应该允许任何东西，但是让您知道几种替代解释，如果您含糊不清。

当然，要管理像@Albin Sunnanbo的ImportantCustomer示例这样不寻常的示例，需要一些时间。但我会告诉您我的进展情况！

- Sanjay Manohar

---

你知道为什么相当多的编程语言可以使用LL(1)解析器进行解析（即仅查看下一个标记），而自然语言解析仍然无法真正工作吗？编程语言（即使是Perl）具有与特定语法相关联的固定语义。你要求一个程序读取随机的无意义文本并编造作者心中的语义。这就好比在要求强人工智能。 - user395760

我一直认为这个网站（http://www.python.org/）是一个相当不错的伪代码解释器。 - NullUserException

我不想成为一个唱反调的人，因为在这个领域里我们缺乏足够疯狂的想法。但即使这种方法可行，使用起来也会很不愉快，原因与AppleScript一样令人不愉快。您实现的终极混合语言将非常非紧凑：很难预测任何事情会做什么，并且很难弄清楚如何指定给定的行为。历史上，简洁易模拟的语言已经战胜了复杂的语言。 - David M.

我猜最实际的步骤是设计自己的语言，将你喜欢的所有特性融合进去，然后为其构建一个解释器。不要尝试识别和应用不同的解析器来处理每个程序片段，而是设计一种统一且一致的语法来支持这些特性。 - MAK

松本行弘也曾经面对这个问题。他喜欢大部分语言中的某些东西（从BASIC到Pascal再到lisp），但没有一种语言包含所有他所喜欢的。他的解决方案是发明自己的伪代码语法，将他喜欢的所有想法结合起来，然后编写一个解释器。结果就是Ruby。你似乎已经有了自己心目中的语法/语义，就像Matz刚开始时那样。而且就像你混乱不堪的语言对你来说感觉很自然一样，Ruby是一种将伪代码转化为真正代码并且对Matz来说感觉很自然的风格。我不是说要使用Ruby，而是说要编写一个解释器。 - slebetman

Answer 1

我认为这种语言除了玩具示例和严格的数学算法之外，对于其他任何东西都是无用的。对于其他所有内容，语言不仅仅是语言。有许多标准库和整个环境围绕着这些语言。我认为我写的库调用行数几乎与我写的“实际代码”一样多。

在C#中，你有.NET Framework，在C++中，你有STL，在Java中，你有一些Java库等等。

这些库之间的差异太大了，不仅仅是语法细微差别。 曾经有过将不同语言的语言结构统一到“统一语法”中的尝试。那被称为4GL语言，但从未真正流行起来。 另外，我看到过一个页长的代码示例，它作为c#、Java和JavaScript代码都是有效的。这可以作为一个例子，说明很难确定实际使用的语言。

编辑：

此外，伪代码的整个目的就是不需要以任何方式编译。您编写伪代码的原因是创建一个“草图”，无论您喜欢多么懒散。

foreach c in ImportantCustomers{== OrderValue >=$1M}
    SendMailInviteToSpecialEvent(c)

现在告诉我它是哪种语言，并为其编写一个解释器。

- Albin Sunnanbo

Answer 2

1. 检测所使用的编程语言：从代码片段中检测编程语言
2. 我认为这是可能的。可以利用1中的方法来实现。我会尝试迭代地完成：检测代码的第一行/子句中使用的语法，根据该检测将其“编译”为中间形式，以及任何重要的语法（例如开始/结束包装）。然后是下一行/子句等等。基本上编写一个解析器，试图识别每个“块”。相同算法可以标记歧义。
3. 我怀疑这还没有做到...似乎学习编写例如python兼容的伪代码的认知负荷要比尝试调试您的解释器失败的情况要容易得多。
4. a. 我认为最大的问题是大多数伪代码在任何语言中都是无效的。例如，我可能会完全跳过代码块中的对象初始化，因为对于人类读者来说，推断它几乎总是很简单的。但是对于您选择的语言语法而言，它可能完全无效，甚至可能无法自动确定对象的类（它甚至可能不存在）。等等。
   b. 我认为您能期望的最好结果是一个“有效”的解释器（受4a的限制），只适用于您的伪代码，而不是任何其他人的。

请注意，我认为4a、4b并不一定是不可能实现的障碍。我只是认为它对于任何实际目的都不会有用。

- Zac Thompson

---

为了准确解析伪代码，您需要生成一个可以处理模糊语法的解析器。使用 Earley 解析器生成器（https://nearley.js.org/）很容易做到这一点。 - Anderson Green

Answer 3

识别程序所用的语言并不是一件难事。但是，识别片段所使用的语言就比较困难了。如果片段没有明确的分界线（例如前四行是Python，而下一行是C或Java），那么识别起来将会非常困难。

假设你已经正确地将这些代码行分配到了各自的语言中，那么进行任何形式的编译都需要为每种语言编写专门的编译器。这本身就是一项巨大的工作。

此外，当你编写伪代码时，并不需要担心语法问题。（如果你还在担心语法问题，那么你做错了。）你最终得到的代码可能根本无法编译，因为它是不完整的甚至是矛盾的。

假设你克服了所有这些障碍，你能确定伪代码正在按照你的想法进行解释吗？

你得到的将是一种新的计算机语言，你需要在其中编写正确的程序。它将是一个庞杂而模糊的语言，非常难以正确地使用。使用它需要极其谨慎。这几乎完全失去了伪代码的价值。伪代码的价值在于可以快速地勾勒出算法，而不必担心细节。而这将完全丧失。

如果你想要一个易于编写的语言，那就学习一门。Python是一个不错的选择。使用伪代码来勾勒出处理过程应该如何进行，而不是作为可编译的语言。

- David Thornley

Answer 4

一个有趣的方法是使用“边打边翻译”的伪代码解释器。你需要在开始时设置要使用的语言，然后它将尝试实时将伪代码转换为真正的代码，以便您输入。交互式工具可用于澄清模棱两可的内容并允许更正。机制的一部分可以是一个库，其中包含转换器尝试匹配的代码。随着时间的推移，它可以根据特定用户的习惯学习和适应其翻译。

经常编程的人可能大多数情况下会选择直接使用该语言。但我可以看到以上内容对于学习者、像科学家这样的“非程序员程序员”以及与各种语言和技能水平的程序员进行头脑风暴的情况非常有用。

-Neil

- TechNeilogy

Answer 5

人类输入的程序需要给出“我不知道”的选项。PL/I语言是一个著名的例子，它被设计用于找到任何类似于计算机程序的合理解释，以避免在猜测错误时造成混乱：请参见http://horningtales.blogspot.com/2006/10/my-first-pli-program.html。

请注意，在后来的C++语言中，当它解决可能存在的歧义时，它会限制它尝试的类型强制转换的范围，并且如果没有唯一的最佳解释，则会标志一个错误。

- mcdowella

---

我使用的PL/I编译器让我印象深刻的是，它会在存在错误的情况下尝试通过编译过程，但任何错误都会导致它停止。考虑到将代码输入编译器需要操作员物理加载一叠卡片到机器中，因此希望从每个提交中获得尽可能多的有用诊断信息，即使这意味着编译器也会输出大量有用的信息。这与早期的Borland编译器非常不同，后者只会在第一个错误处停止（但几乎不需要时间就能到达那里）。 - supercat

Answer 6

要创建一个“伪代码解释器”，可能需要设计一种编程语言，允许用户定义扩展其语法。已经有几种具有此功能的编程语言，例如Coq，Seed7，Agda和Lever。特别有趣的例子是Inform编程语言，因为它的语法本质上是“结构化英语”。 Coq编程语言允许“语法扩展”，因此可以扩展语言以解析新运算符： Notation "A /\ B" := (and A B). 同样地，Seed7编程语言可以通过 "结构化语法定义" 扩展以解析“伪代码”。在Seed7中，while循环的定义如下：

syntax expr: .while.().do.().end.while is -> 25;

另外，也可能通过“训练” 统计机器翻译 系统将伪代码翻译成真正的编程语言，不过这需要大量的 平行文本。

- Anderson Green

Answer 7

我有一种感觉，对于问题2的答案是“NO”。我所需要的只是一个能够被有能力的程序员以不止一种方式解释的代码片段，以证明它是错误的。

- Jose M Vidal

---

这肯定是可以用适当的工具发现并像我建议的那样“标记为模棱两可”的，对吧？编译器针对C等语言的歧义规则，为什么不为多种语言制定这样的规则呢？如果有这样的检查规则，即使在我们使用“标准”语言编程时也可能会得到改善，因为编译器将会注意到依赖于语言的技巧。 - Sanjay Manohar

然而，有几个程序可以自动识别编程语言。 - Anderson Green

Answer 8

代码中是否已经存在可以识别文本文件编程语言的代码？

是的，Unix file 命令可以。

（肯定比eclipse的语法树或者Google翻译的语言猜测功能简单吧？）实际上，SO语法高亮器做了这样的事情吗？

就我所知，SO有一个一刀切的语法高亮器，试图结合每种主要语言的关键字和注释语法。有时会出错：

def median(seq):
    """Returns the median of a list."""
    seq_sorted = sorted(seq)
    if len(seq) & 1:
        # For an odd-length list, return the middle item
        return seq_sorted[len(seq) // 2]
    else:
        # For an even-length list, return the mean of the 2 middle items
        return (seq_sorted[len(seq) // 2 - 1] + seq_sorted[len(seq) // 2]) / 2

请注意，SO的高亮显示器假定//开始C++风格的注释，但在Python中它是整数除法运算符。

如果您尝试将多种语言组合到一个程序中，这将成为一个重大问题。如果同一标记在不同语言中具有不同的含义，该怎么办？类似的情况包括：

- ^是指幂运算（如BASIC）还是按位异或（如C）？ - ||是逻辑或（如C）还是字符串连接（如SQL）？ - 1 + "2"等于多少？数字转换为字符串（得到"12"），还是字符串转换为数字（得到3）？

“是否存在任何语言或解释器可以处理这种灵活的解释？”在另一个论坛上，我听说过一个编译器（如果我没记错，是FORTRAN的），它可以编译任何语法错误的程序。如果您有以下代码行：

= Y + Z

编译器会识别到变量缺失，并自动将语句转换为X = Y + Z，无论您的程序中是否有X。

这位程序员有一个惯例，即以连字符开头的注释块，就像这样：

C ----------------------------------------

但有一天，他们忘记了前导的C，编译器试图在它认为是减法运算符之间添加数十个变量时发生了错误。

“灵活的解析”并不总是件好事。

- dan04

---

感谢提供这些示例！非常有趣且对我接下来要做的事情非常有用。嗯，所有这些都是我所谓的“不灵活解析”的示例！因此，“^”的含义取决于上下文——根据您在其他逻辑操作/标志中如何使用变量（例如文件后面），或者它是否用作绘图坐标等。基本上，人们很少会在伪代码中遇到问题。因此，编译器将提醒您存在歧义的地方，它所做出的假设以及原因，以及是否要澄清或保留它（如果含义明显）。 - Sanjay Manohar

Answer 9

终于 - 解决了！

截至2023年，我2013年的问题现在当然已经得到了解答。你们中的许多人给出了很好的想法。我尝试构建解析器，使用了一种“抗体-抗原”匹配系统，其中语法匹配的抗体以概率方式“结合”到代码的区域。然而，它很快变得过于复杂，并且解决时间呈指数增长。

Github Copilot（arxiv paper）和ChatGPT以一种我以前无法想象的方式成功解决了这个问题。我在Copilot中尝试了Albin Sunnanbo的 问题。

# pseudocode: 
# foreach c in ImportantCustomers{== OrderValue >=$1M}
#    SendMailInviteToSpecialEvent(c)
# python:

输出

for c in ImportantCustomers:
    if c.OrderValue >= 1000000:
        SendMailInviteToSpecialEvent(c)

甚至连

# c# code:
var importantCustomers = from c in customers
                         where c.OrderValue >= 1000000
                         select c;
foreach (var c in importantCustomers)
{
    SendMailInviteToSpecialEvent(c);
}

所以经过10年，我认为问题已经解决了！

---

- Sanjay Manohar