1

我正在尝试为处理 lambda 演算的语言编写一个小型编译器。这是我发现的语言的模棱两可的定义：

E → ^ v . E  | E E | ( E ) | v

符号 ^, ., (, ) 和 v 是记号。^ 表示 lambda，v 表示变量。^vE 形式的表达式是函数定义，其中 v 是函数的形参，E 是函数体。如果 f 和 g 是 lambda 表达式，则 lambda 表达式 fg 表示函数 f 对参数 g 的应用。

我正在尝试为这种语言编写一个明确的语法，假设函数应用程序是左关联的，例如 fgh = (fg)h，并且该函数应用程序的绑定比 . 更紧密，例如 (^x. ^y. xy) ^zz = (^x. (^y. xy)) ^zz

这是我到目前为止所拥有的，但我不确定它是否正确：

E -> ^v.E | T
T -> vF | (E) E
F -> v | epsilon

有人可以帮忙吗？

4

2 回答 2

6

在阅读您的问题和评论之间，您似乎更多地寻求学习和实施 lambda 演算的帮助，而不仅仅是您在此处提出的具体问题。如果是这样，那么我在同一条路上，所以我将分享一些有用的信息。

我拥有的最好的书，也不是说最好的书，是Benjamin C. Pierce 的Types and Programming Languages ( WorldCat )。我知道标题听起来不像 lambda 演算，但请看一下λ-Calculus extensions:meaning of extension symbols，其中列出了本书中的许多 lambda 演算。在OCaml和F#中有本书的代码。

尝试在CiteSeerX中搜索关于 lambda 演算的研究论文以了解更多信息。

到目前为止，我发现的最好的 λ-Calculus 评估器是：

带有信息的Lambda微积分减少工作台。

此外，我发现您在CS:StackExchange和数学相关的数学问题上获得了更好的答案，这些问题与 CS:StackExcahnge 上的编程相关。

至于实现 lambda 演算的编程语言，如果你还没有的话，你可能需要学习一门函数式语言；是的，它是另一种野兽，但在山的另一边的启蒙是壮观的。我发现的大多数源代码都使用了一种函数式语言，例如 ML 或 OCaml，一旦你学会了一种，其余的就会变得更容易学习。

更具体地说，这里是无类型 lambda 演算项目的源代码，这里是 YACC 的 F# 变体的输入文件，从阅读你以前的问题来看，它似乎在你的知识世界中，这里是示例输入。

由于该语法用于实现 REPL，因此它从顶层开始，认为命令提示符，并接受多个命令，在这种情况下是 lambda 演算表达式。由于该语法用于许多演算，它在前面的示例中具有占位符的部分，因此这里的绑定更多是占位符。

终于我们到了你所追求的部分

注意 LCID 是小写标识符

Term : AppTerm
     | LAMBDA LCID DOT Term 
     | LAMBDA USCORE DOT Term 

AppTerm : ATerm   
        | AppTerm ATerm

/* Atomic terms are ones that never require extra parentheses */
ATerm : LPAREN Term RPAREN 
      | LCID
于 2013-03-02T06:41:26.573 回答
2

您可能会在次线性时间内找到特定语法歧义的证明，但证明语法明确是一个 NP 完全问题。您必须生成该语言中所有可能的句子，并检查每个句子是否只有一个派生词。

于 2013-03-03T00:43:36.080 回答