我的Lambda微积分语法是否明确? [英] Is My Lambda Calculus Grammar Unambiguous?

问题描述

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

I am trying to write a small compiler for a language that handles lambda calculus. Here is the ambiguous definition of the language that I've found:

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

符号^，.，(，)和v是标记. ^表示lambda，而v表示变量. 形式^ v.E的表达式是一个函数定义，其中v是函数的形式参数，E是其主体.如果f和g是lambda表达式，则lambda表达式fg表示函数f在参数g上的应用.

The symbols ^, ., (, ) and v are tokens. ^ represents lambda and v represents a variable. An expression of the form ^v.E is a function definition where v is the formal parameter of the function and E is its body. If f and g are lambda expressions, then the lambda expression fg represents the application of the function f to the argument g.

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

I'm trying to write an unambiguous grammar for this language, under the assumption that function application is left associative, e.g., fgh = (fg)h, and that function application binds tighter than ., e.g., (^x. ^y. xy) ^z.z = (^x. (^y. xy)) ^z.z

这是我到目前为止的内容，但是我不确定是否正确:

Here is what I have so far, but I'm not sure if it's correct:

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

有人可以帮忙吗?

推荐答案

在阅读您的问题和评论之间，您似乎在寻求学习和实现Lambda演算的更多帮助，而不仅仅是在这里提出的特定问题.如果是这样，那么我在同一条路上，所以我将分享一些有用的信息.

Between reading your question and comments, you seem to be looking more for help with learning and implementing lambda calculus than just the specific question you asked here. If so then I am on the same path so I will share some useful info.

我拥有的最好的书，并不是说最好的书，是类型和编程语言(本杰明·皮尔斯的 WorldCat ).我知道标题听起来不像lambda演算，但请看一下λ-演算扩展:扩展符号的含义列出了本书中的许多lambda结石. OCaml 和

The best book I have, which is not to say the best book possible, is Types and Programming Languages (WorldCat) by Benjamin C. Pierce. I know the title doesn't sound anything like lambda calculus but take a look at λ-Calculus extensions: meaning of extension symbols which list many of the lambda calculi that come from the book. There is code for the book in OCaml and F#.

尝试在 CiteSeerX 中搜索有关Lambda演算的研究论文，以了解更多信息.

Try searching in CiteSeerX for research papers on lambda calculus to learn more.

到目前为止，我发现的最佳λ微积分评估器是:

The best λ-Calculus evaluator I have found so far is:

Lambda演算减少工作台，其中包含信息此外，我发现您可以在 CS:StackExchange 中找到与编程相关的lambda演算问题的更好答案. a>和与数学有关的问题，请访问 Math:StackExcahnge .

Also, I find that you get much better answers for lambda calculus questions related to programming at CS:StackExchange and math related questions at Math:StackExcahnge.

对于用于实现lambda演算的编程语言，您可能需要学习功能语言还没有是的，它是另一种野兽，但是在山另一侧的启示是壮观的.我发现大多数源代码都使用诸如ML或OCaml之类的功能语言，一旦您学习了一种语言，其余的代码就变得更容易学习.

As for programming languages to implement lambda calculus you will probably need to learn a functional language if you haven't; Yes it's a different beast, but the enlightenment on the other side of the mountain is spectacular. Most of the source code I find uses a functional language such as ML or OCaml, and once you learn one, the rest get easier to learn.

更具体地说，此处是来源无类型lambda演算项目的代码，此处是YACC的F#变体的输入文件，从阅读您以前的问题来看，它是并在此处是样本输入.

To be more specific, here is the source code for the untyped lambda calculus project, here is the input file to an F# variation of YACC which from reading your previous questions seems to be in your world of knowledge, and here is sample input.

由于语法用于实现REPL，因此它从顶层开始思考命令提示符，并接受多个命令，在这种情况下为lambda演算表达式.由于此语法用于许多演算，因此在较早的示例中，该语法的某些部分是占位符，因此此处的绑定更多是占位符.

Since the grammar is for implementing a REPL, it starts with toplevel, think command prompt, and accepts multiple commands, which in this case are lambda calculus expressions. Since this grammar is used for many calculi it has parts that are place holders in the earlier examples, thus binding here is more of a place holder.

最后，我们进入了您追求的部分

Finally we get to the part you are after

请注意LCID是小写字母

Note LCID is Lower Case Identifier

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

这篇关于我的Lambda微积分语法是否明确?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！