1

I've got my answer to this in the comment of the one I checked. Which Algorithm Approach Should I Take to Generate Lambda Expressions in Java? but I don't exactly know where to look in terms of generating lambda expressions with Parsing in Reverse. I'm not exactly allowed to use programs like ANTLR.

The tutorials and instructions I see are the traditional parsing tutorials, I can't seem to find anything that relates to Parsing in Reverse. Is there a more specific term for this, that I can search for? Sorry newbie.

Community
  • 1
nathan De Guia
  • 41
  • 4
  • 1
    I gather from "not exactly allowed to use programs like ANTLR" that this is some sort of assignment? You aren't asking us to solve this so I'm OK with your question. The problem here is that it's not clear what your skill level is. If you know how to write Java, the generation of Java code should be the easiest part of this problem. It's the parsing that will be a challenge. Have you considered asking for assistance from a teacher or TA? – JimmyJames Sep 23 '16 at 17:04
  • I think this might be more on the line of what you are interested in: http://eli.thegreenplace.net/2010/01/28/generating-random-sentences-from-a-context-free-grammar/ – Winston Ewert Sep 23 '16 at 21:52
  • @JimmyJames Actually, my skill level is at the lowest. I understand this will be hard for me, which is why I'm forcing myself to learn as quickly as possible. For now I'm just using strings, which is very limiting. – nathan De Guia Sep 24 '16 at 11:47

2 Answers2

5

Parsing in reverse is code generation.

Think of a compiler as a translator: first, it parses usually to an intermediate data structure (often a tree), then it walks that intermediate data structure generating code for another language, sometimes as a textual output. Essentially code generation is the reverse of parsing.

The output language of a compiler is usually more primitive (i.e. byte code, assembly, or machine code), but can just as easily be another high-level language.

See, for example, google closure compiler (JavaScript input, JavaScript output). Or TypeScript, which takes TypeScript input to JavaScript output.

So, you should try to encode your content as a tree and employ code generation techniques. Or encode as text and use translation techniques (parse the text input, generate text output).

Translation can be done for a lot of reasons. For example, in the early days, different SQL implementations actually had different operator precedence! So, compiler technology translation was employed to take SQL written for one vendor and translate to SQL fully parenthesized to use with another.

Erik Eidt
  • 33,282
  • 5
  • 57
  • 91
  • Thanks, So basically my approach should be basically focused on trees when trying to generate a random lambda expression? to solve the problem here http://programmers.stackexchange.com/questions/330823/which-algorithm-approach-should-i-take-to-generate-lambda-expressions-in-java/330846?noredirect=1#comment705369_330846 ? – nathan De Guia Sep 23 '16 at 16:14
  • Yes, it is pretty easy to generate text expression output from an abstract syntax tree. You can start with brain dead, and over parenthesize everything, or if you want more human readable, add optimizations like removing unnecessary parenthesis. And if you want to generate those trees from text you put a parser in front; now you have a translator. – Erik Eidt Sep 23 '16 at 17:20
  • Thanks, now I have a pretty clear idea on how to generate these random expressions. Now, time to figure out how to manipulate them after. lol – nathan De Guia Sep 23 '16 at 17:27
  • ... another analogy is that parsing is (complex) deserialization and code generation is (complex) serialization... – Erik Eidt Sep 23 '16 at 21:47
3

Parsing in reverse is called unparsing or pretty printing. Creating a parser that can operate in reverse (instead of simply creating separate parsers and unparsers) is for example covered in the paper Invertible syntax descriptions: Unifying parsing and pretty printing by Tillmann Rendel and Klaus Ostermann, which describes a mechanism for having a single syntax description be able to operate both as a parser and a pretty printer. In addition to the code from the paper, there is also a more recent Haskell package called syntax which implements this idea.

Jörg W Mittag
  • 101,921
  • 24
  • 218
  • 318