Good day, I'm trying to find a way to program a lambda expression generator in java with this context-free grammar, and I would want to ask ; what would be the best way to tackle this problem and be able to manipulate them with basic lambda calculus functions such as beta reduction, alpha conversion, etc.?

I tried doing this with Strings, but was advised to discontinue because using strings will limit me to what I can do.

Here's the Context Free Grammar I got over the internet:

 <expr>   ::=  <var>
             | <func> <arg>              # This is an application.
             | lambda <var> . <expr>     # This is an abstraction. 
 <func>   ::=  <var>
             | (lambda <var> . <expr>)    
             | <func> <arg>
 <arg>    ::=  <var>
             | (lambda <var> . <expr>) 
             | (<func> <arg>) 
 <var>    ::= a| b| .... | Z
  • 4
    Java 8 already has lambda's. Are you trying to write a compiler? If so, say so in your question. Commented Sep 12, 2016 at 7:32
  • I'm actually trying to create a program which generates/prints Lambda Expressions, not utilizing it as a tool or something. Commented Sep 12, 2016 at 11:35
  • So you are trying to produce examples of expressions that conform to this grammar, for example lambda f . f (g x)? Like a reverse parser? Do you want to turn a data structure describing the expression into a string, or do you want to generate randomly chosen examples?
    – amon
    Commented Sep 12, 2016 at 13:20
  • I want to turn a data structure describing the expression into a string, yeah. on that latter, what do you mean? choose from a list or something? Commented Sep 14, 2016 at 17:02

1 Answer 1


The simplest approach would be to use a parser generate (perhaps antlr) to make a parser that produces a parse tree. You can then perform your reductions and conversions on the parse tree, rather than on a string, which should make them much simpler.

  • And, may I know what I should then do with the parse tree? Sorry kind of ignorant to this -.- Commented Sep 15, 2016 at 9:52
  • I actually find the notion that somebody is familiar with terms like "beta reduction" but not parse trees extremely surprising! I'd suggest looking at an online tutorial for writing a lambda calculus evaluator (e.g. cs.cornell.edu/courses/cs6110/2014sp/handouts/sestoft.pdf gives examples of different approaches to reductions and variable substitutions using a tree structure in ML; if you're not familiar with ML you may have to search for something similar in a language you are fimiliar with). Commented Sep 15, 2016 at 14:05
  • Actually we were taught this, but not as extensively as you might expect. We were taught how to create these stuff, but were not taught how to apply them. Which, as a result, made us forget these things so quickly.. Our professor on Lambda suggests that we weren't given enough exposure to Data Structures that we need to actually apply them. Sucks, sorry for my ignorance though - maybe it's just me. EDIT: BTW the link on the pdf pointing to an example is dead Commented Sep 15, 2016 at 16:46
  • After the latest comment by the OP on the question itself, it sounds to me like he rather wants to write the inverse of a parser, aka "unparser" aka "pretty printer". Commented Sep 16, 2016 at 1:17
  • @JörgWMittag - good point, although he does also say he "needs to manipulate them with beta reduction, alpha conversion, etc". Commented Sep 16, 2016 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.